Online Distributed Trajectory Planning for Quadrotor Swarm With Feasibility Guarantee Using Linear Safe Corridor

Jungwon Park, Dabin Kim, Gyeong Chan Kim, Dahyun Oh, H. Jin Kim

TL;DR

This paper introduces a novel distributed trajectory planning algorithm for quadrotor swarms that guarantees collision-free and dynamically feasible flight in cluttered environments. By utilizing a "Linear Safe Corridor" (LSC) and a priority-based goal planning strategy, the system ensures that optimization problems always remain mathematically feasible, preventing the "deadlocks" and solver failures common in previous decentralized swarm methods.

What Problem Does This Paper Address?

Planning trajectories for a swarm of quadrotors is a balancing act between speed, safety, and decentralization. Existing methods often struggle with two main issues:

  1. 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.
  2. 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 authors aim 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.

Methods

The proposed algorithm, called the LSC Planner, relies on three core technical pillars:

  • Trajectory Representation: Trajectories are represented using piecewise Bernstein polynomials. This is a standard but powerful choice because of the "convex hull property," which allows the planner to guarantee that the entire flight curve stays within a safe volume just by checking a few control points.
  • Linear Safe Corridor (LSC): This is the paper's primary innovation. The LSC is a set of linear constraints that define a safe "tunnel" for each agent. Unlike previous methods (like Buffered Voronoi Cells) 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.
  • Priority-Based Goal Planning: To solve deadlocks, the agents use a decentralized priority system. Priority is assigned based on an agent's distance to the goal and its current direction of travel. Higher-priority agents are treated as moving obstacles by lower-priority ones, which must then find a "Line-of-Sight free" intermediate goal using a grid-based path search.
  • Quadratic Programming (QP): The final trajectory is generated by solving a QP problem, which is computationally efficient and well-suited for real-time onboard processing.

Datasets

The researchers evaluated their algorithm through extensive simulations and real-world hardware tests:

  • Simulated Environments:
    • Random Forest: A 3m x 3m space with 10 static obstacles and up to 60 agents.
  • Indoor Maze: A 10m x 15m space designed to test deadlock resolution.
  • Hardware Validation: A real-world flight test using 10 Crazyflie 2.0 quadrotors in a cluttered, maze-like indoor environment.
  • Benchmarks: The proposed method was compared against state-of-the-art baselines: DMPC, BVC, and EGO-Swarm.

Key Insights and Ideas

  • The Feasibility Guarantee: The "aha moment" is the mathematical proof that if a swarm starts in a collision-free state, the LSC construction ensures a feasible solution exists for every subsequent step. This eliminates the need for "slack variables" that compromise safety to keep the solver running.
  • Aggressive but Safe: By using the previous trajectory to build the corridor (rather than just the current position), agents can fly much closer to each other and maintain higher speeds. It bridges the gap between conservative "safe" methods and aggressive "on-demand" methods.
  • Social Coordination via Priority: The deadlock resolution mimics a "right-of-way" system. By ignoring lower-priority agents during path searching, the higher-priority agents can clear narrow passages first, effectively "unzipping" potential traffic jams in mazes.

Key Results

  • Scalability: The algorithm is highly efficient, computing trajectories for 60 agents in an average of 15.5 ms per agent on a standard laptop.
  • Success Rate: In the simulated indoor maze, the LSC-PB (Priority Based) method achieved a 100% success rate, while EGO-Swarm failed to reach the goal (0% success) due to the topological complexity of the environment.
  • Efficiency: Compared to the Buffered Voronoi Cell (BVC) method, the proposed LSC planner resulted in 50% less flight time and 17% less flight distance, proving it is far less conservative.
  • Real-World Robustness: In physical tests with 10 drones, the average computation time was only 6.8 ms, and no physical collisions occurred despite the tight constraints of the maze.

Limitations and Future Work

  • Density Limits: While the algorithm performs well in sparse and moderately cluttered environments, the authors note that performance may still degrade in "very dense" environments where the distributed nature of the approach limits global coordination.
  • Tracking Errors: Real-world data showed that drones occasionally "invaded" the desired safe distance buffer due to physical tracking errors and external disturbances. Future work could involve tighter integration between the planner and the low-level controller to account for these physical realities.
  • Communication: The model assumes agents can share trajectories without delay or loss; testing the system's resilience to communication drops would be a logical next step.

Summary updated

Abstract

This letter 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.
BibTeX
@article{park2022online,
  author = {Jungwon Park and Dabin Kim and Gyeong Chan Kim and Dahyun Oh and H. Jin Kim},
  title = {{Online Distributed Trajectory Planning for Quadrotor Swarm With Feasibility Guarantee Using Linear Safe Corridor}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2022},
  url = {https://openreview.net/forum?id=7ZdeXoqLA2},
}

Loading related content...

Figure