Abstract
This paper presents a decentralized multi-agent trajectory planning (MATP) algorithm that guarantees to generate a safe, deadlock-free trajectory in an obstacle-rich environment under a limited communication range. The proposed algorithm utilizes a grid-based multi-agent path planning (MAPP) algorithm for deadlock resolution, and we introduce the subgoal optimization method to make the agent converge to the waypoint generated from the MAPP without deadlock. In addition, the proposed algorithm ensures the feasibility of the optimization problem and collision avoidance by adopting a linear safe corridor (LSC). We verify that the proposed algorithm does not cause a deadlock in both random forests and dense mazes regardless of communication range, and it outperforms our previous work in flight time and distance. We validate the proposed algorithm through a hardware demonstration with ten quadrotors.
Introduction
Multi-agent trajectory planning (MATP) is essential for coordinating robot swarms in complex environments. While centralized systems offer global optimality, they lack the scalability required for large swarms. Decentralized approaches are more scalable but frequently encounter deadlocks—situations where local collision-avoidance constraints prevent forward progress, particularly in narrow corridors or cluttered spaces. Most existing decentralized methods rely on simple heuristics that fail in dense environments. This research introduces a decentralized solution that is both scalable and mathematically guaranteed to be deadlock-free.
Methodology
The proposed algorithm follows a three-stage pipeline executed at every replanning step:
- Decentralized Multi-Agent Path Planning (MAPP): Robots within communication range form an ad-hoc network and select a local coordinator. This coordinator uses the Priority Inheritance with Backtracking (PIBT) algorithm to generate discrete waypoints that guide agents toward their global goals.
- Subgoal Optimization: To bridge the gap between discrete pathfinding and continuous control, the algorithm solves a Linear Programming (LP) problem to find the closest reachable "subgoal." This subgoal satisfies all current safety corridors and communication limits, ensuring that the subsequent trajectory optimization problem is always feasible.
- Trajectory Optimization: Smooth trajectories are generated using piecewise Bernstein polynomials. The system employs Linear Safe Corridors (LSC) and Safe Flight Corridors (SFC) to define mathematical "tunnels" of free space, preventing collisions with obstacles and other agents.
Experimental Evaluation
The algorithm was evaluated across several challenging simulated scenarios:
- Random Forest: 10 agents navigating through 40 randomly placed static obstacles.
- Sparse Maze: A $6 \times 6$ grid with wide corridors.
- Dense Maze: A $9 \times 9$ grid with narrow corridors designed to maximize deadlock risk.
Hardware validation was conducted using 10 Crazyflie 2.1 nano-quadrotors in a dense maze environment, utilizing the Crazyswarm architecture and Octomap for real-time obstacle representation.
Results and Validation
The proposed method (LSC-DR) demonstrated significant improvements over the previous state-of-the-art (LSC-PB):
- Deadlock Resolution: In the "Dense Maze" scenario, LSC-DR achieved a 100% success rate, whereas LSC-PB failed completely (0% success) due to its inability to resolve deadlocks in narrow passages.
- Efficiency: The new algorithm reduced flight time by 27.6% and flight distance by 7.4% in random forest environments.
- Real-time Performance: The decentralized architecture allowed for real-time navigation with an average computation time per agent of only 7-8 milliseconds.
Conclusion and Future Work
This work provides a robust framework for decentralized swarm navigation in obstacle-rich environments. By combining high-level pathfinding with a "feasibility bridge" via subgoal optimization, the authors provide formal guarantees for deadlock-free flight. Future research will focus on extending these proofs to fully 3D environments and incorporating strategies for navigating through dynamic obstacles.
Summary updated