A Path Planner for Large-Scale Drone Swarms Using Optimal Transport-Based Density Control

Abstract

Path planning for multi-agent swarms is a challenging problem due to the requirement for collision avoidance with environmental obstacles and neighboring agents. This paper proposes a novel path planner for large-scale drone swarms that utilizes optimal transport based density control. The path planner consists of three main processes: environment abstraction, optimal transport, and collision avoidance. First, environment abstraction abstracts the given flight space to generate adjacency and cost matrices. Subsequently, an optimal transport plan is calculated to derive a Markov matrix which enables each drone to select its target region probabilistically without inter-drone communication. Finally, a Voronoi based collision avoidance method ensures safe navigation during flights. The majority of the computation occurs during the environment abstraction. However, it is an offline process that can be pre-computed before the flights, and the collision avoidance method only requires the state information of neighboring drones. The proposed path planner is computationally efficient for large-scale drone swarms, and its effectiveness has been verified through simulations with up to 20,000 drones and real-world flight experiments.