Decentralized trajectory planning for quadrotor swarm in cluttered environments with goal convergence guarantee

Decentralized multi-agent trajectory planning (MATP) can enhance the efficiency of multi-robot systems thanks to high scalability and short computation time. However, it may lead to deadlock or livelock in obstacle-rich environments. To tackle this challenge, this paper presents a decentralized MATP algorithm for a quadrotor swarm that ensures convergence to a goal in maze-like environments. The proposed method guides the agents to their goal using the waypoints generated by a grid-based multi-agent path planning (MAPF) algorithm. Additionally, we introduce subgoal optimization to prevent deadlock while the agents follow the waypoints. The proposed algorithm guarantees that the agents converge to their goal if there is no dynamic obstacle and the agents are connected through a fully connected network. Moreover, it ensures deadlock-free even when the agent has a limited communication range. For dynamic obstacle avoidance, we revise the grid-based MAPF to prioritize collision avoidance when the agents encounter dynamic obstacles in a narrow corridor. In simulation, the proposed algorithm achieves a 100% success rate in static environments and shows a higher success rate and shorter flight time compared to most state-of-the-art baseline algorithms in dynamic environments. We validate the safety and robustness of the proposed work through the experiment with 10 quadrotors and one pedestrian in a maze-like environment.