Collision Detection for Modular Robots: It Is Easy to Cause Collisions and Hard to Avoid Them

Siddharth Gupta; Marc van Kreveld; Othon Michail; Andreas Padalkin

doi:10.1007/978-3-031-74580-5_6

Collision Detection for Modular Robots: It Is Easy to Cause Collisions and Hard to Avoid Them

Siddharth Gupta, Marc van Kreveld, Othon Michail, Andreas Padalkin^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

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.

Original language	English
Title of host publication	Algorithmics of Wireless Networks - 20th International Symposium, ALGOWIN 2024, Proceedings
Editors	Quentin Bramas, Arnaud Casteigts, Kitty Meeks
Publisher	Springer Nature
Pages	76-90
Number of pages	15
ISBN (Electronic)	978-3-031-74580-5
ISBN (Print)	978-3-031-74579-9
DOIs	https://doi.org/10.1007/978-3-031-74580-5_6
Publication status	Published - 27 Dec 2024
Event	20th International Symposium on Algorithmics of Wireless Networks, ALGOWIN 2024 - Egham, United Kingdom Duration: 5 Sept 2024 → 6 Sept 2024

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	15026 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Symposium on Algorithmics of Wireless Networks, ALGOWIN 2024
Country/Territory	United Kingdom
City	Egham
Period	5/09/24 → 6/09/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

Keywords

Collision detection
Complexity
Computational geometry
Modular robots

Access to Document

10.1007/978-3-031-74580-5_6

Cite this

Gupta, S., van Kreveld, M., Michail, O., & Padalkin, A. (2024). Collision Detection for Modular Robots: It Is Easy to Cause Collisions and Hard to Avoid Them. In Q. Bramas, A. Casteigts, & K. Meeks (Eds.), Algorithmics of Wireless Networks - 20th International Symposium, ALGOWIN 2024, Proceedings (pp. 76-90). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15026 LNCS). Springer Nature. https://doi.org/10.1007/978-3-031-74580-5_6

Gupta, Siddharth ; van Kreveld, Marc ; Michail, Othon et al. / Collision Detection for Modular Robots : It Is Easy to Cause Collisions and Hard to Avoid Them. Algorithmics of Wireless Networks - 20th International Symposium, ALGOWIN 2024, Proceedings. editor / Quentin Bramas ; Arnaud Casteigts ; Kitty Meeks. Springer Nature, 2024. pp. 76-90 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c3caf832a2784bec970b6cea2ca906f6,

title = "Collision Detection for Modular Robots: It Is Easy to Cause Collisions and Hard to Avoid Them",

abstract = "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.",

keywords = "Collision detection, Complexity, Computational geometry, Modular robots",

author = "Siddharth Gupta and {van Kreveld}, Marc and Othon Michail and Andreas Padalkin",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.; 20th International Symposium on Algorithmics of Wireless Networks, ALGOWIN 2024 ; Conference date: 05-09-2024 Through 06-09-2024",

year = "2024",

month = dec,

day = "27",

doi = "10.1007/978-3-031-74580-5_6",

language = "English",

isbn = "978-3-031-74579-9",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature",

pages = "76--90",

editor = "Quentin Bramas and Arnaud Casteigts and Kitty Meeks",

booktitle = "Algorithmics of Wireless Networks - 20th International Symposium, ALGOWIN 2024, Proceedings",

}

Gupta, S, van Kreveld, M, Michail, O & Padalkin, A 2024, Collision Detection for Modular Robots: It Is Easy to Cause Collisions and Hard to Avoid Them. in Q Bramas, A Casteigts & K Meeks (eds), Algorithmics of Wireless Networks - 20th International Symposium, ALGOWIN 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 15026 LNCS, Springer Nature, pp. 76-90, 20th International Symposium on Algorithmics of Wireless Networks, ALGOWIN 2024, Egham, United Kingdom, 5/09/24. https://doi.org/10.1007/978-3-031-74580-5_6

Collision Detection for Modular Robots: It Is Easy to Cause Collisions and Hard to Avoid Them. / Gupta, Siddharth; van Kreveld, Marc; Michail, Othon et al.
Algorithmics of Wireless Networks - 20th International Symposium, ALGOWIN 2024, Proceedings. ed. / Quentin Bramas; Arnaud Casteigts; Kitty Meeks. Springer Nature, 2024. p. 76-90 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 15026 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Collision Detection for Modular Robots

T2 - 20th International Symposium on Algorithmics of Wireless Networks, ALGOWIN 2024

AU - Gupta, Siddharth

AU - van Kreveld, Marc

AU - Michail, Othon

AU - Padalkin, Andreas

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

PY - 2024/12/27

Y1 - 2024/12/27

N2 - 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.

AB - 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.

KW - Collision detection

KW - Complexity

KW - Computational geometry

KW - Modular robots

UR - http://www.scopus.com/inward/record.url?scp=85215518304&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-74580-5_6

DO - 10.1007/978-3-031-74580-5_6

M3 - Conference contribution

AN - SCOPUS:85215518304

SN - 978-3-031-74579-9

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 76

EP - 90

BT - Algorithmics of Wireless Networks - 20th International Symposium, ALGOWIN 2024, Proceedings

A2 - Bramas, Quentin

A2 - Casteigts, Arnaud

A2 - Meeks, Kitty

PB - Springer Nature

Y2 - 5 September 2024 through 6 September 2024

ER -

Gupta S, van Kreveld M, Michail O, Padalkin A. Collision Detection for Modular Robots: It Is Easy to Cause Collisions and Hard to Avoid Them. In Bramas Q, Casteigts A, Meeks K, editors, Algorithmics of Wireless Networks - 20th International Symposium, ALGOWIN 2024, Proceedings. Springer Nature. 2024. p. 76-90. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-74580-5_6