A Memetic Path Planning Algorithm for Unmanned Air/Ground Vehicle Cooperative Detection Systems

The studies of Unmanned Air/Ground Vehicle (UAV/UGV) cooperative detection systems have received much attention due to their wide applications in the disaster rescue, target tracking, intelligent surveillance, and automatical package delivery missions. UAVs provide a broad view and have a fast speed in the air, while UGVs have sufficient load capacity and can serve as repeater stations on the ground. The path planning of a UAV/UGV cooperative system is an important but difficult issue, which aims to plan paths for both the UAVs and the UGVs in the system to cooperatively complete a mission. In this article, we consider the path planning problem of the UAV/UGV cooperative system for illegal urban building detection, by taking the limits of UGV speed, UAV load power, and UAV/UGV communication restriction into consideration. To solve this problem, we first model the path planning problem as a constraint optimization problem which tries to minimize an overall execution time for completing the illegal urban building detection tasks, and then propose a two-level memetic algorithm (called Two-MA) to solve the path planning problems of both the UAV and the UGV. Experiments on both synthetic and real-world data sets show the superiority of the proposed Two-MA over several states-of-the-art algorithms in solving the path planning problems of the UAV and UGV for illegal urban building detection tasks. Note to Practitioners—This article was motivated by the task of detecting illegal buildings in cities by unmanned vehicles. Previous works mainly focus on path planning of either UAVs or UGVs in this task. This article proposes a new approach using an Unmanned Air/Ground Vehicle (UAV/UGV) cooperative system for detecting illegal buildings in parks, by taking the limits of UGV speed, UAV load power, and UAV/UGV communication restriction into consideration. This cooperative system consists of a UAV, UGV, and control center. The UAV equipped with cameras takes aerial photography in the air, and can transmit collected photos to the control center. The UGV executes loading and transportation on the ground, and can serve as takeoff and landing platforms for the UAV. The control center executes computationally intensive tasks such as data transmission and processing, task scheduling, and vehicle coordination. To quickly complete all detection tasks, a memetic algorithm is proposed for path planning of both the UAV and the UGV. The simulated results show that the proposed algorithm enables the UAV/UGV cooperative system to visit all buildings in cities with a minimum task execution time.