Abstract
This paper presents a new online multi-agent trajectory planning algorithm that guarantees to generate safe, dynamically feasible trajectories in a cluttered environment. The proposed algorithm utilizes a linear safe corridor (LSC) to formulate the distributed trajectory optimization problem with only feasible constraints, so it does not resort to slack variables or soft constraints to avoid optimization failure. We adopt a priority-based goal planning method to prevent the deadlock without an additional procedure to decide which robot to yield. The proposed algorithm can compute the trajectories for 60 agents on average 15.5 ms per agent with an Intel i7 laptop and shows a similar flight distance and distance compared to the baselines based on soft constraints. We verified that the proposed method can reach the goal without deadlock in both the random forest and the indoor space, and we validated the safety and operability of the proposed algorithm through a real flight test with ten quadrotors in a maze-like environment.
Challenges in Swarm Trajectory Planning
Planning trajectories for a swarm of quadrotors is a balancing act between speed, safety, and decentralization. Existing methods often struggle with two main issues:
- Optimization Failure: In crowded or narrow spaces, the mathematical constraints for collision avoidance can become "infeasible," meaning the computer can't find a valid path. Many researchers use "soft constraints" (slack variables) to get around this, but this risks actual physical collisions.
- Deadlocks: In complex, non-convex environments like mazes, distributed agents often get stuck because they cannot coordinate who should yield or move first without a centralized "brain."
The proposed LSC Planner aims to create a distributed system that is fast enough for real-time use, scales to dozens of agents, and provides a mathematical guarantee that a safe, feasible trajectory will always be found.
The Linear Safe Corridor (LSC) Approach
The core innovation of this work is the Linear Safe Corridor (LSC). Unlike previous methods like Buffered Voronoi Cells (BVC) that only look at an agent's current position, the LSC utilizes the entire trajectory from the previous time step. This ensures that the optimization problem for the next step always has at least one valid starting solution, guaranteeing mathematical feasibility.
The algorithm represents trajectories using piecewise Bernstein polynomials, leveraging the convex hull property to ensure the entire flight curve stays within the safe LSC volume. To resolve deadlocks, a Priority-Based Goal Planning strategy is used. Priority is assigned based on distance to the goal and travel direction. Higher-priority agents are treated as moving obstacles by lower-priority ones, which then find intermediate goals using a grid-based search.
Performance and Real-World Validation
The LSC Planner was evaluated through extensive simulations and hardware tests. In a simulated indoor maze, the priority-based method achieved a 100% success rate, whereas competing methods like EGO-Swarm failed (0% success) due to the topological complexity of the environment. Compared to the BVC method, the LSC planner resulted in 50% less flight time and 17% less flight distance, proving it is far less conservative.
Hardware validation with 10 Crazyflie 2.0 quadrotors in a maze-like environment confirmed the algorithm's robustness. The average computation time was only 6.8 ms, and no physical collisions occurred despite the tight constraints of the maze. The algorithm effectively scaled to compute trajectories for 60 agents in an average of 15.5 ms per agent on a standard laptop.
Conclusion
The LSC Planner provides a robust framework for decentralized swarm navigation with feasibility guarantees. By using the previous trajectory to build the corridor, agents can fly closer to each other and maintain higher speeds. While performance is high in moderately cluttered environments, future work will address density limits and communication resilience to further enhance the system's robustness in real-world deployments.
Summary updated