(A) scalable path planning algorithm for drone swarms using density control

Abstract

Unmanned aerial vehicles are utilized to wide applications and adopt different flight control algorithms according to the given flight missions and flight environments. In a single-agent case where there are no obstacles in the flight environment, it is possible to carry out an autonomous flight using the existing widely researched guidance algorithms. Additionally, if there are obstacles in the environment, path planning algorithms can be utilized to avoid collision with obstacles.

However, autonomous flights become more complicated in the case of multi-agent or swarm being considered. Even if there are no obstacles in the environment, collision avoidance nearby surrounding agents should be considered for the flight. In this case, the problem can be solved by applying the guidance algorithm and the collision avoidance algorithm simultaneously. Furthermore, the presence of obstacles in the flight environment of the swarm leads to more complicated problem, since the vehicle should consider collision avoidance with neighboring agents and obstacles around.

In this research, a scalable path planning algorithm for drone swarms using density control is proposed to handling this complicated planning problem. The algorithm discretizes a given flight environment using centroidal Voronoi tessellations to reduce computational load, and utilizes an optimal transport algorithm to obtain Markov matrix. To avoid collision with surrounding obstacles and agents, the proposed algorithm adopts Voronoi based collision avoidance algorithm. Therefore, the proposed algorithm can be applied to highly scaled swarm effectively, and the algorithm has been verified through several numerical simulations.