TY - GEN
T1 - A Memetic Algorithm for Curvature-Constrained Path Planning of Messenger UAV in Air-Ground Coordination
AU - Ding, Yulong
AU - Xin, Bin
AU - Zhang, Hao
AU - Chen, Jie
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/10/11
Y1 - 2020/10/11
N2 - This paper addresses a UAV path planning problem for a team of cooperating heterogeneous vehicles composed of one unmanned aerial vehicle (UAV) and multiple unmanned ground vehicles (UGVs). The UGVs are used as mobile actuators and scattered in a large area. To achieve multi-UGV communication and collaboration, the UAV serves as a messenger to fly all UGVs to transmit information. The path planning of messenger UAV is formulated as a Dynamic Dubins Traveling Salesman Problem with Neighborhood (DDTSPN). A novel memetic algorithm is proposed to find the shortest route enabling the UAV to fly over all requested UGVs. In the memetic algorithm, the combination of genetic algorithm and local search is employed to find a high-quality solution in a reasonable time, and a gradient-based repair strategy is used to repair the individuals violating dynamic constraints. The calculation results on both small and large instances show that the proposed method can generate high-quality solutions as compared with the state-of-the-art algorithms.
AB - This paper addresses a UAV path planning problem for a team of cooperating heterogeneous vehicles composed of one unmanned aerial vehicle (UAV) and multiple unmanned ground vehicles (UGVs). The UGVs are used as mobile actuators and scattered in a large area. To achieve multi-UGV communication and collaboration, the UAV serves as a messenger to fly all UGVs to transmit information. The path planning of messenger UAV is formulated as a Dynamic Dubins Traveling Salesman Problem with Neighborhood (DDTSPN). A novel memetic algorithm is proposed to find the shortest route enabling the UAV to fly over all requested UGVs. In the memetic algorithm, the combination of genetic algorithm and local search is employed to find a high-quality solution in a reasonable time, and a gradient-based repair strategy is used to repair the individuals violating dynamic constraints. The calculation results on both small and large instances show that the proposed method can generate high-quality solutions as compared with the state-of-the-art algorithms.
KW - Air-ground coordination
KW - Dubins traveling salesman problem
KW - curvature-constrained path planning
KW - memetic algorithm
UR - http://www.scopus.com/inward/record.url?scp=85098889380&partnerID=8YFLogxK
U2 - 10.1109/SMC42975.2020.9282894
DO - 10.1109/SMC42975.2020.9282894
M3 - Conference contribution
AN - SCOPUS:85098889380
T3 - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
SP - 1465
EP - 1472
BT - 2020 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2020 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2020
Y2 - 11 October 2020 through 14 October 2020
ER -