Decentralized Deadlock-free Trajectory Planning for Quadrotor Swarm in Obstacle-rich Environments

Jungwon Park, Inkyu Jang, H. Jin Kim

TL;DR

This paper introduces a decentralized trajectory planning algorithm that allows swarms of quadrotors to navigate dense, maze-like environments without getting stuck in "deadlocks." By combining high-level discrete pathfinding with a novel subgoal optimization technique, the researchers provide mathematical guarantees for collision-free and deadlock-free flight, even with limited communication ranges.

What Problem Does This Paper Address?

Multi-agent trajectory planning (MATP) is the art of getting a group of robots from point A to point B without hitting obstacles or each other. While centralized systems (one "brain" for all robots) work well, they don't scale to large swarms. Decentralized approaches are more scalable but suffer from deadlocks: situations where robots in tight spaces (like narrow corridors) block each other because their local collision-avoidance constraints prevent any forward movement.

Most existing decentralized methods either ignore obstacles entirely or rely on simple heuristics like the "right-hand rule," which often fail in complex, cluttered environments. This paper seeks a decentralized solution that is both scalable and mathematically guaranteed to be deadlock-free in obstacle-rich spaces.

Methods

The authors propose a three-stage pipeline executed at every replanning step:

  1. Decentralized Multi-Agent Path Planning (MAPP): Using an ad-hoc network, robots within communication range select a local coordinator. This coordinator uses a grid-based algorithm (specifically Priority Inheritance with Backtracking, or PIBT) to generate discrete high-level waypoints that are globally "aware" of the goal.
  2. Subgoal Optimization: This is the core innovation. Instead of trying to fly directly to a waypoint that might be unreachable due to current safety constraints, the robot solves a Linear Programming (LP) problem. It finds the closest possible "subgoal" that satisfies all current safety corridors and communication limits. This ensures the optimization problem in the next step is always feasible.
  3. Trajectory Optimization: The robot generates a smooth, continuous trajectory using piecewise Bernstein polynomials. It utilizes Linear Safe Corridors (LSC) and Safe Flight Corridors (SFC)—mathematical "tunnels" of free space—to ensure the quadrotor never hits an obstacle or another agent.

Datasets

The researchers evaluated their algorithm using simulated environments generated to test specific navigation challenges:

  • Random Forest: 40 static obstacles placed randomly with 10 agents starting in a circle.
  • Sparse Maze: A $6 \times 6$ grid where corridors are wide enough for three agents to pass.
  • Dense Maze: A $9 \times 9$ grid with narrow corridors where only one agent can pass at a time, maximizing the risk of deadlock.
  • Hardware Validation: A real-world test using 10 Crazyflie 2.1 nano-quadrotors in a dense maze, utilizing the Crazyswarm architecture and Octomap for obstacle representation.

Key Insights and Ideas

  • The "Feasibility Bridge": The biggest "aha" moment is the subgoal optimization. By calculating a reachable intermediate point between the robot's current position and the high-level waypoint, the authors ensure that the complex trajectory math never hits a "no solution" state.
  • Guaranteed Deadlock Resolution: The paper provides formal proofs showing that as long as the high-level grid-planner (MAPP) can find a path, the continuous trajectory controller will eventually follow it.
  • Communication-Aware Constraints: The algorithm explicitly accounts for limited communication ranges ($r_c$). It adds constraints to ensure robots don't wander so far from their waypoints that they lose touch with the ad-hoc network or collide with "invisible" agents outside their range.

Key Results

  • Success Rate: In the "Dense Maze" scenario, the proposed method (LSC-DR) achieved a 100% success rate, whereas the previous state-of-the-art decentralized method (LSC-PB) had a 0% success rate because it couldn't resolve deadlocks in narrow passages.
  • Efficiency: Compared to their previous work, the new algorithm reduced flight time by 27.6% and flight distance by 7.4% in random forest environments.
  • Scalability: The decentralized nature allowed 10 quadrotors to navigate a complex maze in real-time with an average computation time per agent of only ~7-8 milliseconds.

Limitations and Future Work

  • 2D Planning: The current implementation and proofs are primarily focused on 2D space (though quadrotors fly in 3D, the planning logic here is planar). The authors plan to extend the algorithm to fully three-dimensional environments.
  • MAPP Dependency: The system's success relies on the underlying grid-based MAPP algorithm. The authors suggest exploring other MAPP variants to further improve performance and path optimality.
  • Static Obstacles: While the agents avoid each other (dynamic), the environment obstacles are assumed to be static and known beforehand. Navigating through moving obstacles in a decentralized way remains a future challenge.

Summary updated

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.
BibTeX
@inproceedings{park2023decentralized,
  author = {Jungwon Park and Inkyu Jang and H. Jin Kim},
  title = {{Decentralized Deadlock-free Trajectory Planning for Quadrotor Swarm in Obstacle-rich Environments}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2023},
  url = {https://openreview.net/forum?id=C0w2QiHtDp},
}

Loading related content...

Figure