A Memetic Algorithm for Curvature-Constrained Path Planning of Messenger UAV in Air-Ground Coordination

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, modeled as a Dubins vehicle, serves as a messenger to fly over the effective communication range of all UGVs to relay information. The curvature-constrained path planning of the messenger UAV is formulated as a Dubins Traveling Salesman Problem with Dynamic Neighborhood (DTSPDN) which is a complex optimization problem involving coupled variables and contains dynamic constraints. We design an effective memetic algorithm to find the shortest route that enables the messenger UAV to visit all moving UGVs. This algorithm combines the genetic algorithm procedure, two kinds of local search operators based on gradient search and uniform sampling respectively, and a gradient-based repair operator to repair the solutions violating dynamic constraints. During the evolutionary process, a special phenomenon may occur that changing some decision variables (i.e., visiting sequence and location) may not affect the evaluation function value, but may alter the feasible region of another decision variable (i.e., visiting time) due to the encounter constraint between the UAV and UGV. To track and utilize the change of the feasible region, a transformation procedure is proposed to change one solution to another with less visiting time by analyzing the encounter pattern between UAV and UGV. The computational results on random instances with different scales demonstrate that the proposed approach can effectively generate better curvature-constrained tours to encounter all moving UGVs when compared to other four competitive algorithms in the literature. Note to Practitioners - This paper studies an emerging path planning problem for a UAV which is used to provide communication service for multiple moving UGVs. These UGVs are required to execute tasks (e.g., firefighting, search and rescue) within a large area. Due to their limited communication capabilities, they may be unable to obtain necessary information from other UGVs. The UAV serves as a messenger to fly over the effective communication range of all moving UGVs to relay information. We propose a novel memetic algorithm to efficiently search for the shortest tour that enables the messenger UAV to visit all moving UGVs. The memetic algorithm combines the parallel global search virtue of genetic algorithm with efficient local search procedure to improve the generated tour. A gradient-based repair procedure is also employed to make sure that the planned tour can guide the UAV to sequentially encounter each moving UGV. Simulations exhibit that the proposed approach can effectively generate high-quality tours for messenger UAV to rapidly visit all UGVs, which assists UGVs to achieve collaboration in large area. In future work, the proposed memetic algorithm will be extended to plan tours for multiple messenger UAVs.