Event
New Algorithm Achieves Collision-Free Planning for a Million Robots
1 reports · 1 sources
Jan Kamm, Antonio Terpin, and Raffaello D'Andrea propose the Sequential Contact Insertion (SCI) algorithm for collision-free motion planning for multiple robots. The method starts from unconstrained trajectories, inserts contact points at spacing violations, jointly adjusts the timing and states of each contact point, and then analytically reconstructs trajectories between contact points. The authors report that in numerical experiments, the method can complete planning for one million robots within minutes, and for thousands of robots in under one second. On problems solvable by a fixed-grid sequential convex programming baseline, SCI achieves median speedups of several orders of magnitude with comparable solution accuracy. All of the above results come from the authors' numerical experiments.
Report timeline
- SCI: A Contact-Based Optimization Method for Collision-Free Motion Planning for a Million Robots
The authors propose the sequential contact insertion (SCI) algorithm, which organizes optimization around contact points where robots reach the minimum allowed separation and analytically reconstructs trajectories between contacts. In numerical experiments, the method can plan for one million robots within minutes, while thousands of robots take less than one second; on problems solvable by a fixed-grid sequential convex programming baseline, SCI achieves median speedups of several orders of magnitude with comparable solution accuracy.
arXiv cs.RO ·
Related topics
Interest trend
- Current
- 3
- Peak
- 4Nov 4 01:00
- Past 24 hours
- –
The trend compares participants observed throughout the same period, so its range may be smaller than the current interest count. Move or tap to inspect each hour; use the arrow keys on a keyboard.