Technical Summary: FLIP – Real-Time and Resilient Formation Planning for Large-Scale Distributed Swarms via Point Cloud Registration

1. Problem Statement

Large-scale formation planning for swarm robots faces a fundamental trade-off between performance and computational scalability. Existing approaches generally fall into two categories, both of which exhibit significant limitations:

• Oversimplified Representations: Methods using polyhedral structures, probability distributions, or artificial potential fields decouple agent interactions to reduce computational load. However, this simplification leads to poor formation performance, particularly in obstacle-rich environments, resulting in significant shape deformation and slow convergence.
• Complete Collaborative Relationships: Methods that meticulously account for every agent's motion (approximating a complete graph) ensure high formation fidelity but introduce excessive computational constraints. As the swarm scale increases, these methods suffer from high computational loads, susceptibility to local optima, and a lack of resilience. In these systems, suboptimal trajectories or abnormal agent states can propagate through the network, degrading the performance of the entire swarm.

Current sparse graph approaches attempt to balance these factors but often fail to guarantee formation performance when the swarm exceeds 100 agents. Furthermore, existing methods often struggle with elongated formations due to the limitations of normalized Laplacian matrices, which can cause major-axis gradients to overshadow minor-axis ones.

2. Methodology

The proposed FLIP (Real-Time and Resilient Formation Planning) framework addresses these challenges by transforming the Optimal Formation Position Sequence (OFPS) calculation problem into a Spatiotemporal Point Cloud Registration (PCR) problem. The system operates within a distributed, asynchronous planning framework where agents broadcast their trajectories to neighbors.

Core Mechanism: PCR-Based OFPS Calculation

Instead of optimizing a complex graph-based cost function, each agent treats the current positions of all other agents as a source point cloud and the desired formation positions as a target point cloud.

1. Problem Transformation: The objective of finding the optimal formation position for an agent is reformulated as finding the optimal transformation parameters (rotation $R$, translation $t$, and scale $s$) that align the source point cloud (other agents' positions) with the target point cloud (desired formation).
2. Efficient Approximation: To avoid the computational burden of iterative optimization for every agent, the method relaxes the problem. It computes the optimal transformation parameters $\{R^*, t^*, s^*\}$ using the positions of all other agents (excluding the agent itself). The optimal formation position for the agent is then derived directly via the transformation: $p^*_i = s^* R^* p^{des}_i + t^*$.
3. Outlier Rejection: To ensure resilience, the framework employs the RANSAC (Random Sample Consensus) algorithm within the PCR process. This allows the system to identify and reject outlier points (representing abnormal or suboptimal agent trajectories) during the registration process. Consequently, abnormal states do not propagate through the network to affect the planning of normal agents.

Trajectory Optimization

Once the OFPS is calculated, each agent uses it as a constraint for its local trajectory optimization. The trajectory is represented using TMINCO (a minimal-control polynomial trajectory representation). The optimization minimizes control effort and flight time while satisfying:

• Dynamic feasibility constraints.
• Obstacle avoidance.
• Swarm reciprocal avoidance.
• The formation constraint derived from the OFPS.

The constrained optimization problem is converted into an unconstrained one using penalization strategies and solved efficiently using the L-BFGS algorithm.

3. Key Contributions

The paper outlines three primary contributions:

1. PCR-Based Large-Scale Planning: The authors propose a novel algorithm that leverages efficient PCR to compute the optimal formation position sequence. This approach enables real-time planning for large-scale swarms by avoiding the computational explosion associated with fully connected collaborative graphs.
2. Resilient Planning via Outlier Rejection: By integrating outlier rejection (RANSAC) into the PCR step, the method inherently eliminates the influence of suboptimal or abnormal agent trajectories during distributed optimization. This prevents the propagation of errors and ensures the swarm maintains its formation even with a significant percentage of anomalous agents.
3. Validation and Open Source: The effectiveness of the method is validated through extensive simulations and benchmarks against State-of-the-Art (SOTA) methods. The authors also commit to open-sourcing their code to facilitate further research.

4. Experimental Results

The authors conducted simulations on a standard PC (Intel Core i7 8700K, 32GB RAM) to evaluate performance across varying swarm sizes (up to 120 agents) and formation shapes.

• Scalability and Efficiency:

  • Compared to SOTA methods (Quan's [1] and Zhou's [10]), FLIP demonstrates superior computational efficiency. While Quan's method fails to maintain real-time planning (computation time > 1s) with 40 drones, and Zhou's method struggles with 100 drones, FLIP maintains a mean planning time of 0.040s for 100 agents and 0.09s for 120 agents in obstacle environments.
  • The formation distance error ($\bar{e}_{dist}$) for FLIP remains low (e.g., 0.6065 for 100 agents), outperforming Zhou's method which showed failure or high error at similar scales.
  • The OFPS computation itself is extremely lightweight, remaining below 0.06s even with 1000 agents.

• Resilience:

  • In experiments with abnormal agents (outliers), FLIP successfully maintained formation performance with up to 12% abnormal agents (9 out of 75 in specific tests, and nearly 10% in general claims).
  • In contrast, Zhou's method (which uses a single-step maximum clique approach) struggled to cope when the number of abnormal agents increased beyond 3%, leading to formation degradation. Quan's method showed oscillations due to the propagation of abnormal states.

• Formation Shape Versatility:

  • FLIP performed consistently across various shapes (heart, cube, random 3D) with errors comparable to SOTA methods.
  • Crucially, for elongated formations (e.g., a 13.5m x 1.5m rectangle), FLIP outperformed methods based on normalized Laplacian matrices. The latter suffered from reduced sensitivity to short-axis errors, leading to deformation, whereas FLIP maintained consistent sensitivity and lower error ($\bar{e}_{dist} = 0.028$ in obstacle-free conditions).

5. Significance and Claims

The paper claims that FLIP represents a significant advancement in large-scale swarm robotics by achieving a balance between high-performance formation maintenance and computational efficiency.

• Real-Time Capability: The method enables real-time trajectory planning for swarms exceeding 100 agents, a scale where previous distributed methods often fail due to latency or local optima.
• Inherent Resilience: By treating abnormal agents as outliers in a point cloud registration problem, the system naturally filters out noise and failures without requiring complex adaptive control laws or pre-planning anomaly removal steps.
• Scalability: The approach scales effectively because the computational cost of the core formation coordination (PCR) does not grow prohibitively with the number of agents, unlike graph-based optimization methods.

The authors conclude that while their method slightly sacrifices precision by ignoring the agent's own current position impact during the transformation calculation, the trade-off yields a robust, scalable, and real-time solution suitable for complex, large-scale missions. Future work aims to extend this to even larger scales using group-based strategies and integrating global path planning.