Decentralized Planning for Car-Like Robotic Swarm in Unstructured Environments

Changjia Ma, Zhichao Han, Tingrui Zhang, Jingping Wang, Long Xu, Chengyang Li, Chao Xu, Fei Gao

Abstract

Robot swarm is a hot spot in robotic research community. In this paper, we propose a decentralized framework for car-like robotic swarm which is capable of real-time planning in cluttered environments. In this system, path finding is guided by environmental topology information to avoid frequent topological change, and search-based speed planning is leveraged to escape from infeasible initial value's local minima. Then spatial-temporal optimization is employed to generate a safe, smooth and dynamically feasible trajectory. During optimization, the trajectory is discretized by fixed time steps. Penalty is imposed on the signed distance between agents to realize collision avoidance, and differential flatness cooperated with limitation on front steer angle satisfies the non-holonomic constraints. We validate the robustness of our system in simulation and real-world experiments. Code will be released as open-source packages.

Introduction

Planning for robotic swarms requires a delicate balance between computational efficiency and trajectory quality. While centralized planners offer global optimality, they scale poorly as the number of agents increases. Decentralized planners scale better but face significant challenges in cluttered environments, particularly for car-like robots. These vehicles are governed by non-holonomic constraints—they cannot move laterally—and are prone to "topological jumps." In dense environments, a robot might abruptly switch its intended path to the opposite side of an obstacle during replanning. Such indecisiveness often leads to collisions because the vehicle's physical turning radius cannot accommodate the sudden change in trajectory.

Methodology

The proposed framework utilizes a three-stage pipeline to ensure safe and efficient navigation.

1. Topology-Guided Path Planning

The front-end uses a modified Kinodynamic hybrid A search to find a spatial path. To prevent topological jumps, the authors introduce the SD-VD (S-Distance Visibility Deformation)* condition. This ensures that any newly planned path remains within the same "homotopy class" as the previous one, maintaining consistency in how the robot navigates around obstacles.

Maintaining topological consistency during replanning to avoid infeasible maneuvers.

2. Search-Based Speed Planning

Once a spatial path is established, the system searches a Space-Time (S-T) graph to determine a feasible speed profile. A "one-shot" mechanism based on bang-bang control is employed to quickly identify valid initial values, preventing the subsequent optimizer from becoming trapped in poor local minima.

3. Spatial-Temporal Joint Optimization

The final stage refines the path and speed into a smooth, dynamically feasible trajectory. A key innovation here is the use of fixed time steps ($\delta t = 0.2s$) for trajectory discretization. By keeping timestamps constant, the robot avoids the need to repeatedly re-calculate the positions of other moving agents during optimization, reducing the computational load by approximately 20%.

Experiments and Results

The system was rigorously tested in both simulated and physical environments.

Simulation and Hardware Setup

In the CARLA Simulator, the researchers tested scenarios with up to 8 robots in a $90m \times 90m$ "farm scene" containing 48 random obstacles. Real-world validation was conducted in a $3m \times 8m$ indoor space using three custom robots powered by NVIDIA Jetson Nano processors. Localization was handled by a NOKOV motion capture system.

Real-world experimental validation of the decentralized planning framework with three car-like robots.

Performance Metrics

  • Efficiency: The average planning time was under 30ms, with peaks staying below 100ms, enabling high-speed real-time navigation.
  • Robustness: Ablation studies showed that removing topology guidance or speed planning significantly degraded success rates. With the full system, robots maintained near-perfect success rates even at speeds of $10m/s$ in simulation.
  • Onboard Deployment: The successful execution on low-power Jetson Nano hardware demonstrates the framework's suitability for decentralized, edge-computing applications.

Conclusion

This research presents a robust decentralized planning framework for car-like swarms that effectively handles non-holonomic constraints and cluttered environments. While the system excels at collision avoidance, future work will address potential "deadlocks" through partial coordination and extend the framework to 2.5D environments for uneven terrain. Additionally, the impact of communication delays in congested wireless networks remains a subject for further investigation.

Summary updated

Abstract

Robot swarm is a hot spot in robotic research community. In this paper, we propose a decentralized framework for car-like robotic swarm which is capable of real-time planning in cluttered environments. In this system, path finding is guided by environmental topology information to avoid frequent topological change, and search-based speed planning is leveraged to escape from infeasible initial value's local minima. Then spatial-temporal optimization is employed to generate a safe, smooth and dynamically feasible trajectory. During optimization, the trajectory is discretized by fixed time steps. Penalty is imposed on the signed distance between agents to realize collision avoidance, and differential flatness cooperated with limitation on front steer angle satisfies the non-holonomic constraints. With trajectories broadcast to the wireless network, agents are able to check and prevent potential collisions. We validate the robustness of our system in simulation and real-world experiments. Code will be released as open-source packages.
BibTeX
@inproceedings{ma2023decentralized,
  author = {Changjia Ma and Zhichao Han and Tingrui Zhang and Jingping Wang and Long Xu and Chengyang Li and Chao Xu and Fei Gao},
  title = {{Decentralized Planning for Car-Like Robotic Swarm in Unstructured Environments}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=H4fnBLG0Ln},
}
Figure