2026-07-23T07:58:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24496 2025-12-16T13:59:58Z ddc:004 open_access

Sliding Squares in Parallel A. Akitaya, Hugo Fekete, Sándor P. Kramer, Peter Molaei, Saba Rieck, Christian Stock, Frederick Wallner, Tobias Sliding squares parallel motion reconfigurability motion planning multi-agent path finding makespan swarm robotics computational geometry We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given n square-shaped modules in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work has aimed at minimizing the total number of moves, resulting in fully sequential schedules that can perform reconfiguration in 𝒪(n²) moves, or 𝒪(nP) for arrangements of bounding box perimeter size P. We provide first results in the sliding square model that exploit parallel motion, performing reconfiguration in worst-case optimal makespan of 𝒪(P). We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan 1 is NP-complete in the unlabeled case. In the labeled variant, we note that deciding the same for makespan 2 is NP-complete, while makespan 1 is straightforward. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hugo A. Akitaya and Sándor P. Fekete and Peter Kramer and Saba Molaei and Christian Rieck and Frederick Stock and Tobias Wallner 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.28 urn:nbn:de:0030-drops-244961 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.28 eng https://creativecommons.org/licenses/by/4.0/legalcode