Heuristicbased Multiple Mobile Depots Route Planning for Recharging Persistent Surveillance Robots Persistent surveillance of a target space using multiple unmanned aerial vehicles (UAVs) has multiple applications such as geographical surveys, air quality monitoring, and security monitoring. The limited onboard battery capacity challenges the continuous operation in these applications of persistent robots. We consider the problem for recharging persistent robots using mobile depots. The mobile depots collectively compute a set of tours to recharge all persistent robots with the minimum total cost. Compared to other works, the persistent UAVs are not required to detour to a static depot for energy replenishment such as recharging or battery swapping. We formulate this problem as a Generalized Multiple Depots Travelling Salesman Problem (GMDTSP) on a complete graph. A heuristicbased algorithm Multiple Depots Random Select (RSMD) is proposed to solve the recharging problem efficiently. The RSMD has proved to have an analytical constant upper bound in the worstcase scenario. We also propose a postprocessing heuristic (RSMDIM) to improve the solution quality further. We demonstrate the efficiency and effectiveness of our algorithm via benchmark on multiple instances from TSPLIB and GTSPLIB. The simulation results show that RSMD and RSMDIM will perform significantly faster than the state of the art heuristic solver LKH with a loss of about 10% of solution quality.

Constrained Heterogeneous Vehicle Path Planning for Largearea Coverage There is a strong demand for covering a large area autonomously by multiple UAVs (Unmanned Aerial Vehicles) supported by a ground vehicle. Limited by UAVsxe2x80x99 battery life and communication distance, complete coverage of large areas typically involves multiple takeoffs and landings to recharge batteries, and the transportation of UAVs between operation areas by a ground vehicle. In this paper, we introduce a novel largeareacoverage planning framework which collectively optimizes the paths for aerial and ground vehicles. Our method first partitions a large area into subareas, each of which a given fleet of UAVs can cover without recharging batteries. UAV operation routes, or trails, are then generated for each subarea. Next, the assignment of trials to different UAVs and the order in which UAVs visit their assigned trails are simultaneously optimized to minimize the total UAV flight distance. Finally, a ground vehicle transportation path which visits all subareas is found by solving an asymmetric traveling salesman problem (ATSP). Although finding the globally optimal trail assignment and transition paths can be formulated as a Mixed Integer Quadratic Program (MIQP), the MIQP is intractable even for small problems. We show that the solution time can be reduced to closetorealtime levels by first finding a feasible solution using a Random Key Genetic Algorithm (RKGA), which is then locally optimized by solving a much smaller MIQP.