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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Continuous Multi-Agent Path Finding for Drone Delivery

  • Ming Chen,
  • Ning He,
  • Chen Hong

摘要

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.