The Parameterized Complexity of Coordinated Motion Planning
Eduard Eiben, Robert Ganian, Iyad Kanj · 2026
Read The Parameterized Complexity of Coordinated Motion Planning by Eduard Eiben, Robert Ganian, Iyad Kanj (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/PMC13619704.txt.
Description
Eduard Eiben, Robert Ganian, and Iyad Kanj settle open questions about coordinated motion planning, the problem of moving many robots on a grid to their goals without collisions, in a 2026 paper. Two goals compete: finishing as fast as possible overall, or keeping the total distance traveled small. The authors ask how the difficulty of each version depends on the number of robots and on the target value itself.
Both versions turn out to be solvable by fixed-parameter methods when the number of robots is the chosen measure, using new insight into the shape of optimal plans. When the target value is the measure instead, the distance version stays tractable while the speed version becomes genuinely hard. That hardness proof also yields a simpler proof that two classic path problems on grids are hard even with short fixed path lengths.
Catalog record
| CREATOR | Eduard Eiben, Robert Ganian, Iyad Kanj |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 159021 |
| LICENSE | https://creativecommons.org/licenses/by/4.0 |
| RIGHTS | CC BY |
| SOURCE | Europe PMC |