Decentralized Planning for Car-Like Robotic Swarm in Cluttered Environments

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

TL;DR

This paper introduces a decentralized planning framework that allows a swarm of car-like robots to navigate cluttered, unknown environments in real-time. By combining topology-guided path searching with a novel fixed-time-step optimization strategy, the system ensures smooth, collision-free trajectories that respect the tricky non-holonomic constraints of car-like vehicles.

What Problem Does This Paper Address?

Planning for a robotic swarm is a balancing act between computational efficiency and trajectory quality. Centralized planners, which manage every robot from a single "brain," become prohibitively slow as the number of robots increases. Decentralized planners—where each robot thinks for itself—scale better but often struggle in "cluttered" environments filled with obstacles.

For car-like robots, the challenge is even steeper due to non-holonomic constraints (they can't move sideways) and the risk of "topological jumps." In dense environments, frequent replanning can cause a robot to suddenly decide to pass an obstacle on the opposite side, often leading to a collision because the vehicle's physics can't handle the abrupt change. This paper aims to provide a decentralized system that is fast enough for real-time use while remaining robust enough to avoid these "indecisive" crashes.

Methods

The authors propose a three-stage pipeline:

  1. Topology-Guided Path Planning (Front-end): Using a modified Kinodynamic hybrid A search, the robot finds a spatial path. Crucially, they introduce the SD-VD (S-Distance Visibility Deformation)* condition. This ensures the newly planned path stays in the same "homotopy class" as the previous one—meaning the robot won't suddenly try to switch sides of an obstacle during a replan.
  2. Search-based Speed Planning (Mid-end): Once the path is set, the robot searches an S-T (Space-Time) graph to find a feasible speed profile. They use a "one-shot" mechanism (bang-bang control) to quickly find valid initial values, preventing the final optimizer from getting stuck in "bad" local minima.
  3. Spatial-Temporal Joint Optimization (Back-end): The path and speed are refined into a smooth trajectory.
  4. The "Aha" Innovation: Unlike previous methods that discretize trajectories by a fixed number of points, this system uses fixed time steps ($\delta t = 0.2s$). Because the timestamps of the constraint points remain constant during optimization, the robot doesn't need to repeatedly re-calculate the positions of other moving agents, significantly slashing the computational burden.

Datasets

The researchers evaluated their system using:

  • CARLA Simulator: A high-fidelity simulation environment. They created a "farm scene" ($90m \times 90m$) with 48 randomly placed obstacles and tested scenarios with up to 8 robots crossing paths from multiple directions.
  • Real-World Experiments: A $3m \times 8m$ indoor space using three custom car-like robots equipped with NVIDIA Jetson Nano processors and single-line LiDARs. Localization was provided by a NOKOV motion capture system.

Key Insights and Ideas

  • Consistency is Safety: The biggest insight is that maintaining "topological homotopy" (staying on the same side of an obstacle) is vital for car-like robots. If a planner "wavers" between two paths, the robot’s physical turning radius often makes a collision inevitable.
  • Optimization Shortcuts: By fixing the time steps in the optimization phase, the authors turned a dynamic problem (where are the other robots at time $t$?) into a partially static one. This reduced the optimization computation time by approximately 20%.
  • Decoupling with a Safety Net: While they decouple path and speed planning initially to save time, the final joint optimization ensures the resulting trajectory is still dynamically feasible and smooth.

Key Results

  • Real-Time Performance: The average total planning time was less than 30ms, with a maximum peak under 100ms, making it well-suited for high-speed navigation.
  • High Success Rates: In ablation studies, the success rate "fell off a cliff" when topology guidance or speed planning was removed. With the full system, robots achieved near-perfect success rates even when crossing paths at $10m/s$ in simulation.
  • Hardware Efficiency: The system ran successfully on low-power onboard hardware (Jetson Nano), proving its decentralized efficiency.

Limitations and Future Work

  • Deadlocks: The authors note that while the system avoids collisions, it can still result in "deadlocks" where robots block each other's paths entirely. They suggest "partial coordination" or group planning as a future solution.
  • 2D Constraints: The current framework operates in a 2D plane. The authors plan to extend this to 2.5D environments to handle uneven terrain.
  • Communication Dependency: The system relies on robots broadcasting their trajectories over a wireless network. While delays were ignored here, extremely congested networks might impact performance.

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 Cluttered Environments}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=H4fnBLG0Ln},
}

Loading related content...

Figure