Continuous Multi-Agent Path Finding for Drone Delivery
摘要
Unmanned Aircraft Systems Traffic Management (UTM) is important for the safety and efficiency of multiple drone delivery. In the paper, we introduce continuous time Multi-Agent Path Finding (MAPF) for UTM system with pre-flight Conflict Detection and Resolution (CDR), and propose a new version of MAPF named Multi-Drone Delivery Path Finding (MDDPF), where agents move continuously in the metric space with different path costs and traverse the conflict-free paths in round trips. We also propose a novel algorithm called RCCBS that continuously solves a continuous-time MAPF instance according to newly assigned tasks. Simulations on the Sendai 2030 drone delivery model case show that RCCBS efficiently solves the MDDPF problem.