| Title: |
Collision Detection for Modular Robots: It Is Easy to Cause Collisions and Hard to Avoid Them |
| Authors: |
Gupta, Siddharth; van Kreveld, Marc; Michail, Othon; Padalkin, Andreas; Dep Informatica; Sub Geometric Computing; Bramas, Quentin; Casteigts, Arnaud; Meeks, Kitty |
| Publication Year: |
2024 |
| Subject Terms: |
Collision detection; Complexity; Computational geometry; Modular robots; Taverne; Theoretical Computer Science; General Computer Science |
| Description: |
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(n2log2n) time, O(n2) time, or O(nlog2n) 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. |
| Document Type: |
book part |
| File Description: |
application/pdf |
| Language: |
English |
| ISSN: |
0302-9743 |
| Relation: |
https://dspace.library.uu.nl/handle/1874/482671 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/482671 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.9FFB35CB |
| Database: |
BASE |