Sampling-based and conflict-based planners that coordinate teams of quadrupeds through cluttered terrain — comparing speed, completeness, and success rate.
Objective. As robotics expands into search-and-rescue, exploration, and warehousing, the demand for autonomous robots that can perform collision-free, coordinated tasks keeps rising. Given my research in quadruped robots and the unique mobility the platform offers, my team set out to compare a variety of multi-agent planning strategies to see which performed best.
Solution. We built on Quad-SDK, my lab's ROS-based framework for quadrupedal locomotion, reusing its visualization tools, local footstep planner, and low-level motor controller to test planners across terrain. Each discrete robot state is a vector of body position, orientation, and velocity. We explored three planners:
- Sequential RRT-Connect (Rapidly-exploring Random Trees)
- Joint-space RRT-Connect
- Conflict-Based Search (CBS)
Sequential RRT-Connect solves each robot's path in turn, treating prior paths as static obstacles — fast, but at the cost of probabilistic completeness. Joint-space RRT-Connect plans for all robots simultaneously in a combined state space: complete, but it scales poorly. CBS is the middle ground, planning each robot individually with a low-level RRT-Connect while detecting and resolving conflicts in a high-level search — only solving the joint problem when necessary. My main responsibilities were implementing and testing CBS, onboarding teammates onto the codebase, and debugging.
Results. We validated each method in Gazebo and Rviz, first with two agents and then four, across randomly generated environments. Every planner produced kinodynamically feasible, collision-free body trajectories; the aggregate results are below.
| Planner | Avg. path length (m) | Avg. planning time (s) | Success rate |
|---|---|---|---|
| Sequential | 18.2 | 0.094 | 69% |
| Joint | 16.9 | 1.067 | 81% |
| Conflict-Based Search | 15.1 | 0.254 | 100% |
As expected, the sequential planner was quickest but often produced suboptimal paths and failed when later robots became over-constrained. The joint planner handled crossing paths but at longer solve times. On average, CBS performed best — shortest path length with reasonable planning time — highlighting the value of application-specific planners that trade off speed, completeness, and efficiency for real-world multi-agent motion planning.