2026-08-17T08:32:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19904 2024-05-31T08:33:44Z ddc:004 open_access

Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them Gupta, Siddharth van Kreveld, Marc Michail, Othon Padalkin, Andreas Modular robots Collision detection Computational Geometry Complexity We consider geometric collision-detection problems for modular reconfigurable robots. Assuming the nodes (modules) are connected squares on a grid, we investigate the complexity of deciding whether collisions may occur, or can be avoided, if a set of expansion and contraction operations is executed. We study both discrete- and continuous-time models, and allow operations to be coupled into a single parallel group. Our algorithms to decide if a collision may occur run in O(n²log² n) time, O(n²) time, or O(nlog² n) time, depending on the presence and type of coupled operations, in a continuous-time model for a modular robot with n nodes. To decide if collisions can be avoided, we show that a very restricted version is already NP-complete in the discrete-time model, while the same problem is polynomial in the continuous-time model. A less restricted version is NP-hard in the continuous-time model. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siddharth Gupta and Marc van Kreveld and Othon Michail and Andreas Padalkin 2024 Is Part Of LIPIcs, Volume 292, 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2024.26 urn:nbn:de:0030-drops-199044 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2024.26 eng https://creativecommons.org/licenses/by/4.0/legalcode