TY - GEN
T1 - 3D Drone Path Planning Algorithms with Collision Avoidance
T2 - 9th IEEE World Forum on Internet of Things, WF-IoT 2023
AU - Shivgan, Rutuja
AU - Medina, Jorge
AU - Dong, Ziqian
AU - Rojas-Cessa, Roberto
N1 - Publisher Copyright: © 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - Because of their limited flight range, multiple drones are often deployed simultaneously to perform complex tasks. The flight path is planned for each drone to follow to complete the job before task execution. However, multi-drone path planning places drones at risk of in-flight collisions. To overcome this problem, we model the multi-drone path planning problem as a multi-vehicle routing problem that maximizes job coverage subject to collision-free paths. We propose three 3D collision-free path planning algorithms, namely, XTRACT, 3DETACH, and ASCEND. XTRACT and 3DETACH provide collision-free paths by setting partial paths at different altitudes while ASCEND prevents intersecting paths at the planning phase by selecting different altitudes. We limit the search processes to two altitudes to demonstrate sufficiency with the lowest height complexity. Through exhaustive evaluations, we compare the performance of the proposed schemes and show the trade-offs between resolving and preventing collisions from path planning. We identify the best-performing strategy by using a profit model to evaluate the plethora of applicable performance metrics.
AB - Because of their limited flight range, multiple drones are often deployed simultaneously to perform complex tasks. The flight path is planned for each drone to follow to complete the job before task execution. However, multi-drone path planning places drones at risk of in-flight collisions. To overcome this problem, we model the multi-drone path planning problem as a multi-vehicle routing problem that maximizes job coverage subject to collision-free paths. We propose three 3D collision-free path planning algorithms, namely, XTRACT, 3DETACH, and ASCEND. XTRACT and 3DETACH provide collision-free paths by setting partial paths at different altitudes while ASCEND prevents intersecting paths at the planning phase by selecting different altitudes. We limit the search processes to two altitudes to demonstrate sufficiency with the lowest height complexity. Through exhaustive evaluations, we compare the performance of the proposed schemes and show the trade-offs between resolving and preventing collisions from path planning. We identify the best-performing strategy by using a profit model to evaluate the plethora of applicable performance metrics.
KW - 3D path planning
KW - altitude planning
KW - collision avoidance
KW - in-flight collisions
KW - multiple depot vehicle routing problems
KW - optimization
KW - path planning
KW - Unmanned aerial vehicles
UR - http://www.scopus.com/inward/record.url?scp=85195411102&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85195411102&partnerID=8YFLogxK
U2 - 10.1109/WF-IoT58464.2023.10539596
DO - 10.1109/WF-IoT58464.2023.10539596
M3 - Conference contribution
T3 - 2023 IEEE World Forum on Internet of Things: The Blue Planet: A Marriage of Sea and Space, WF-IoT 2023
BT - 2023 IEEE World Forum on Internet of Things
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 12 October 2023 through 27 October 2023
ER -