Enhanced Decentralized Autonomous Aerial Robot Teams With Group Planning

Jialiang Hou, Xin Zhou, Zhongxue Gan, Fei Gao

TL;DR

This paper introduces "group planning," a novel decentralized approach for autonomous aerial robot teams. It dynamically groups robots based on their proximity and uses a two-stage process (efficient multi-agent pathfinding and trajectory joint optimization) to significantly improve planning quality and success rates, especially in large-scale and complex environments.

What Problem Does This Paper Address?

Designing effective autonomous aerial robot teams is a significant challenge. Current approaches fall into two main categories: centralized and decentralized. Centralized methods, while potentially offering high-quality plans, struggle with scalability due to the combinatorial explosion of interactions and communication overhead in large teams. On the other hand, existing decentralized methods, which are more scalable, often sacrifice planning quality and success rates, particularly in dense environments with many potential conflicts. This paper aims to bridge this gap by proposing a decentralized system that achieves both scalability and high-quality planning.

Methods

The core of the proposed system is the "group planning" strategy. When robots are spatially close, they are dynamically grouped. This group planning mechanism consists of two main components:

  1. Efficient Multi-Agent Pathfinding (EMAPF): This is an enhanced, online, three-dimensional pathfinding method based on the Conflict-Based Search (CBS) algorithm. It uses a two-level search (high-level on a Conflict Tree and low-level constraint-based search) with a novel "tie-breaker" function in the low-level search. This tie-breaker helps reduce the search space and guides paths closer to optimal trajectories. The EMAPF generates multiple collision-free paths for agents within a group.
  2. Group Trajectory Joint Optimization: Using the paths generated by EMAPF, this back-end process jointly optimizes the trajectories of all agents in a group. It employs the TMINCO (Trajectory with Minimum Control effort) class for trajectory representation. The optimization problem is formulated to minimize control effort, execution time, and incorporate penalties for dynamic feasibility (velocity, acceleration, jerk limits), obstacle avoidance, and crucially, group reciprocal avoidance. This last component ensures that agents consider the impact of their planned trajectories on others in the group, a key factor for robust coordination.

When robots are dispersed, they revert to single-agent planning.

Datasets

Not discussed in the paper. The evaluation relies on simulations and real-world experiments designed by the authors.

Key Insights and Ideas

  • Dynamic Grouping is Key: The insight that robots don't always need to coordinate at a global level, but can benefit from localized group coordination when spatially clustered, is central to achieving both scalability and quality.
  • Bridging Centralized and Decentralized: The "group planning" acts as a flexible plugin that allows decentralized systems to leverage more comprehensive, almost centralized-like, optimization within local groups when needed.
  • Tie-breaker for MAPF Efficiency: The introduction of a tie-breaker function in the low-level search of EMAPF is a clever way to improve path quality and reduce search space without significantly increasing computational cost.
  • Reciprocal Avoidance in Joint Optimization: Explicitly modeling and penalizing the reciprocal avoidance between agents during joint trajectory optimization is crucial for preventing collisions in dense, dynamic scenarios.

Key Results

  • Improved Planning Quality: The proposed method demonstrates top-level planning quality, resulting in shorter flight times and distances compared to existing methods like RBP, MADER, EGO, and DSTO.
  • Efficiency: The EMAPF component achieves an average search time of 0.0381s for up to 8 agents in a 1276m³ space, which is considered adequate for real-time applications.
  • Robustness in Complex Scenarios: The method successfully navigates challenging environments, such as passing through a narrow gate with multiple drones, as shown in Fig. 2.

  • Scalability: The system is shown to be applicable to large-scale teams (simulated with 50 drones) and real-world experiments (8 drones indoors, 4 drones outdoors).

  • Reduced Replan Times: The method exhibits fewer replan times compared to other decentralized approaches, indicating more stable and reliable planning.

Limitations and Future Work

  • Theoretical Guarantee: The authors acknowledge that they cannot theoretically guarantee that a solution always exists for the nonlinear optimization problem. To mitigate this, they perform a post-check on optimized trajectories and only execute safe ones, with an emergency stop mechanism if safety is still compromised.
  • Future Work: The authors plan to further improve the efficiency and scalability of their EMAPF method, particularly by considering kino-dynamic constraints more rigorously. They also aim to explore applications in the field of transportation.

Summary updated

Abstract

Designing autonomous aerial robot team systems remains a grand challenge in robotics. Existing works in this field can be categorized as centralized and decentralized. Centralized methods suffer from scale dilemmas, while decentralized ones often lead to poor planning quality. In this paper, we propose an enhanced decentralized autonomous aerial robot team system with group planning. According to the spatial distribution of agents, the system dynamically divides the team into several groups and isolated agents. For conflicts within each group, we propose a novel coordination mechanism named group planning. The group planning consists of efficient multi-agent pathfinding (MAPF) and trajectory joint optimization, which can significantly improve planning quality and success rate. We demonstrate through simulations and real-world experiments that our method not only has applicability for a large-scale team but also has top-level planning quality.
BibTeX
@article{hou2022enhanced,
  author = {Jialiang Hou and Xin Zhou and Zhongxue Gan and Fei Gao},
  title = {{Enhanced Decentralized Autonomous Aerial Robot Teams With Group Planning}},
  journal = {IEEE Robotics Autom. Lett.},
  year = {2022},
  url = {https://openreview.net/forum?id=eQkQhIqXsZ},
}
Figure