A Two-Phase Planner for Messenger Routing Problem in UAV-UGV Coordination Systems

In this paper, a new Messenger Routing Problem (MRP) is studied, which is motivated by Uncrewed Aerial Vehicles (UAVs) accessing Uncrewed Ground Vehicles (UGVs) to deliver information in UAV-UGV coordination systems. The objective is to minimize the longest path among multiple messengers, ensuring fast and reliable information transmission. Two key challenges arise in tackling this problem. First, the targets are moving, incurring the travel cost between targets to vary with the travel process. Second, the messengers accessing the neighborhood of targets needs to satisfy the communication time constraint. Based on the idea of decoupling, a two-phase planner is proposed to sequentially determine global access sequence and optimize local access locations. In the first phase, a motion prediction module is introduced in the Adaptive Large Neighborhood Search (ALNS) framework to deal with the dynamic characteristics of MRP. In the second phase, an efficient bisection sampling method based on the prediction points is proposed to obtain a shorter access path while satisfying the communication time constraint. Finally, the effectiveness and efficiency of the proposed method are demonstrated by performance evaluation and comparison with the state-of-the-art algorithms.