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

CREATOREduard Eiben, Robert Ganian, Iyad Kanj
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE159021
LICENSEhttps://creativecommons.org/licenses/by/4.0
RIGHTSCC BY
SOURCEEurope PMC

Source: https://europepmc.org/article/MED/PMC13619704

Browse the full library · About the Tower of Babel