Path planning is important for the autonomy of Unmanned Aerial Vehicle (UAV), especially for scheduling UAV delivery. However, the operating environment of UAVs is usually uncertain and dynamic. Without proper planning, collisions may happen where multiple UAVs are congested. Besides, there may also be temporary no-fly zone setup by authorities that makes airspace unusable. Thus, proper pre-departure planning that avoids such places is needed.In this paper, we formulate this problem into a Constraint Satisfaction Problem to find a collision-free shortest path on a dynamic graph. We propose a collision-free path planning algorithm that is based on A* algorithm. The main novelty is that we invent a heuristic function that also considers waiting time. We later show that, with added waiting penalty, the proposed algorithm is optimal because the heuristic is admissible. Implementation of this algorithm simulates UAV delivery using Singapore's airspace structure. Our simulation exhibits desirable runtime performance. Using the proposed algorithm, the percentage of collision-free routes decreases as number of requests per unit area increases, and this percentage drops significantly at boundary value. Our empirical analysis could aid the decision-making of no-fly zone policy and infrastructure of UAV delivery.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A Collision-Free Path Planning Algorithm for Unmanned Aerial Vehicle Delivery


    Beteiligte:
    Shi, Ziji (Autor:in) / Ng, Wee Keong (Autor:in)


    Erscheinungsdatum :

    01.06.2018


    Format / Umfang :

    1381131 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    A Collision-Free Path Planning Algorithm for Unmanned Aerial Vehicle Delivery

    Shi, Ziji / Ng, Wee Keong | ArXiv | 2018

    Freier Zugriff

    Collision-free path planning of Unmanned Aerial robots based on A* algorithm

    Xiangrong Xu / Hao Xu / Xiaosheng Zhu et al. | IEEE | 2014


    Unmanned aerial vehicle swarm path planning

    JAMES SCOTT / RAHEB ROBERT | Europäisches Patentamt | 2025

    Freier Zugriff


    UNMANNED AERIAL VEHICLE SWARM PATH PLANNING

    JAMES SCOTT / RAHEB ROBERT | Europäisches Patentamt | 2023

    Freier Zugriff