モジュラーロボットの衝突検出:衝突は起こしやすく避けにくい
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
分類: cs.CG, cs.DS, cs.RO
原文アブストラクト
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^2\log^2 n)$ time, $O(n^2)$ time, or $O(n\log^2 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.
関連論文
- CuBot-STT:格子型モジュラー再構成ロボットの搬送と締結を同時に行う外部ロボットモジュラーロボット
- ロボットの出芽:物理的自己複製における均質なモジュールから多様な形態へモジュラーロボット
- 異種モジュラーロボットの形態形成アセンブリと適応制御モジュラーロボット
- 変形可能な四辺形モジュールロボットの自己再構成計画モジュラーロボット
- RhoMorph:安定かつ媒体非依存の再構成動作を実現する菱形変形モジュールロボットモジュラーロボット
- 格子型モジュラー・ロボットのための連続的雌雄同体結合機構モジュラーロボット
