A Meta-Heuristic Approach for an Aerial-Ground Vehicle Path Planning Problem
Jaekyung Jackie Lee, Sivakumar Rathinam · 2024
This study concerns the challenges of path planning and scheduling for multi-agent unmanned aerial vehicles (UAVs) operating under battery constraints while considering the presence of unmanned ground vehicles (UGVs) capable of recharging them. The objective is to efficiently coordinate UAVs and a UGV to maximize collected rewards by visiting nodes continuously in a 20 km x 20 km coverage area. The reward for each node is calculated based on the time difference between the last visit and the current visit, and the total nodes' reward contributes to the overall team score. The problem is a form of the Team Orienteering Problem (TOP), which is known to be NP-Hard. To solve this problem, we propose a new algorithm and simulation using a meta-heuristic approach. Specifically, our approach employs an advanced tabu search specialized in this problem with three improved tabu search stages: 2-point exchange, one-point movement, 2-opt cleanup, and two extra rearrange and reattach processes. It provides a feasible solution within a few minutes of computation time for large problems with accumulated nodes and rewards. Subsequently, our investigation uncovers a novel scheduling rule, which we apply to a demanding 72-hour mission schedule. Computational and simulation results demonstrate the algorithm's runtime, cumulative rewards, node visits, and charging schedules. The proposed approach is evaluated through simulations, further affirming its efficacy in addressing the challenges of path planning and scheduling for UAVs with battery constraints.