2026-07-21T11:22:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26046 2026-06-23T13:18:34Z ddc:004 open_access

Robotic Arm Rotation: Standing up Is Harder Than You Think Bousquet, Nicolas Connor, Frank El Sabeh, Remy Langevin, Louis-Roy Mouawad, Amer E. Nishimura, Naomi Totschnig, Agnes search optimization robotics robotic arms parameterized complexity computational geometry combinatorial reconfiguration We study motion-planning problems for planar robotic arms that rotate around fixed centers while avoiding collisions. In the SM-RAMP model, each unit-length arm may rotate at most once; the question is whether all arms can be rotated to the vertical position. We resolve an open problem of Bousquet et al. [Bousquet et al., 2026] by proving that SM-RAMP is NP-complete, even in the horizontal-to-vertical setting. Our hardness proof uses a structural analysis of rotation-propagation chains and introduces a combinatorial abstraction of independent interest, the Lighthouse Propagation problem, which we show is itself NP-complete. We then consider the multi-move variant MM-RAMP, where each arm may rotate multiple times among a fixed set of allowed angles (or orientations). We prove that MM-RAMP is PSPACE-complete even when each arm has only a few allowed angles, in sharp contrast with the single-move case. Finally, we give two fixed-parameter tractable algorithms: for MAX-SM-RAMP parameterized by the number k of arms to be made vertical, and for 2A-MM-RAMP (restricted to horizontal and vertical) parameterized by the number 𝓁 of allowed rotations. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Bousquet and Frank Connor and Remy El Sabeh and Louis-Roy Langevin and Amer E. Mouawad and Naomi Nishimura and Agnes Totschnig 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.10 urn:nbn:de:0030-drops-260467 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.10 eng https://creativecommons.org/licenses/by/4.0/legalcode