Graph-Sparse Distributed Predictive Control for Multi-Robot Motion Planning vianEdge-Consensus ADMM
Organizations: Automatic Control Department (ESAII), Universitat Politècnica de Catalunya – BarcelonaTech, Barcelona, Spain
Abstract
This paper presents a distributed model predictive control (MPC) architecture for collision-avoiding motion planning of planar robots with double-integrator dynamics. To reduce coordination demands, a time-varying predicted conflict graph selects relevant pairwise interactions. The associated collision-avoidance constraints are convexified once per MPC update using warm-start trajectories, yielding a fixed convex quadratic program (QP). The resulting QP is then decomposed using an edge-consensus formulation of the alternating direction method of multipliers (ADMM), enabling parallel robot-local optimization and independent closed-form projections onto separating half-spaces. Execution is selectively supervised by a centralized high-order control barrier function (HOCBF) QP when the distributed candidate does not satisfy the direct-execution conditions. Evaluated in C++ simulations involving 8, 16, and 32 robots, the proposed architecture achieves collision-free execution and substantially improves computational scalability while maintaining task-level performance comparable to a centralized complete-graph baseline.
Figures & tables
| Parameter | Symbol | Value |
|---|---|---|
| MPC model and objective | ||
| Sampling time | s | |
| Prediction horizon | ||
| Robot radius | m | |
| Safety margin | m | |
| Velocity bound | m/s | |
| KPI | Dist. | Cent. | Dist. | Cent. | Dist. | Cent. |
|---|---|---|---|---|---|---|
| Mean MPC time [ms] | ||||||
| 90th-percentile MPC time [ms] | ||||||
| Worst MPC time [ms] | ||||||
| Mean active edges / total pairs | ||||||
| Min. clearance w.r.t. [m] | ||||||
| Diagnostic | |||
|---|---|---|---|
| Mean ADMM rounds | |||
| Residual stop [%] | |||
| Certificate stop [%] | |||
| stop [%] | |||
| HOCBF call rate [%] | |||
| Mean [m/s 2 ] |
Multi-Robot Motion Planning
Multi-Robot Motion Planning coordinates collision-free paths and trajectories for robot teams sharing space, tasks, and changing environments.
See all 157 papers