{"ID":2881193,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.13032","arxiv_id":"2508.13032","title":"On the complexity of constrained reconfiguration and motion planning","abstract":"Coordinating the motion of multiple agents in constrained environments is a fundamental challenge in robotics, motion planning, and scheduling. A motivating example involves $n$ robotic arms, each represented as a line segment. The objective is to rotate each arm to its vertical orientation, one at a time (clockwise or counterclockwise), without collisions nor rotating any arm more than once. This scenario is an example of the more general $k$-Compatible Ordering problem, where $n$ agents, each capable of $k$ state-changing actions, must transition to specific target states under constraints encoded as a set $\\mathcal{G}$ of $k$ pairs of directed graphs. We show that $k$-Compatible Ordering is $\\mathsf{NP}$-complete, even when $\\mathcal{G}$ is planar, degenerate, or acyclic. On the positive side, we provide polynomial-time algorithms for cases such as when $k = 1$ or $\\mathcal{G}$ has bounded treewidth. We also introduce generalized variants supporting multiple state-changing actions per agent, broadening the applicability of our framework. These results extend to a wide range of scheduling, reconfiguration, and motion planning applications in constrained environments.","short_abstract":"Coordinating the motion of multiple agents in constrained environments is a fundamental challenge in robotics, motion planning, and scheduling. A motivating example involves $n$ robotic arms, each represented as a line segment. The objective is to rotate each arm to its vertical orientation, one at a time (clockwise or...","url_abs":"https://arxiv.org/abs/2508.13032","url_pdf":"https://arxiv.org/pdf/2508.13032v3","authors":"[\"Nicolas Bousquet\",\"Remy El Sabeh\",\"Amer E. Mouawad\",\"Naomi Nishimura\"]","published":"2025-08-18T15:50:57Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\",\"cs.RO\",\"math.CO\"]","methods":"[]","has_code":false}