Gupta, Siddharth
[Verfasser:in];
van Kreveld, Marc
[Verfasser:in];
Michail, Othon
[Verfasser:in];
Padalkin, Andreas
[Verfasser:in]
;
Siddharth Gupta and Marc van Kreveld and Othon Michail and Andreas Padalkin
[Mitwirkende:r]
Brief Announcement: Collision Detection for Modular Robots - It Is Easy to Cause Collisions and Hard to Avoid Them
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.