未知環境におけるロボット群の均一分散:時間・移動距離・エネルギー
Time, Travel, and Energy in the Uniform Dispersion Problem
未知のグリッド環境でロボット群を均一に分散させる問題を定式化し、時間・移動距離・エネルギー・センシング・通信・メモリの関係を分析。単連結環境ではアリ型ロボットによるFCDFSアルゴリズムでエネルギーを最小化できることを示した。
著者: Michael Amir, Alfred M. Bruckstein
分類: cs.RO, cs.DM, cs.MA
原文アブストラクト
We investigate the algorithmic problem of uniformly dispersing a swarm of robots in an unknown, gridlike environment. In this setting, our goal is to study the relationships between performance metrics and robot capabilities. We introduce a formal model comparing dispersion algorithms based on makespan, traveled distance, energy consumption, sensing, communication, and memory. Using this framework, we classify uniform dispersion algorithms according to their capability requirements and performance. We prove that while makespan and travel can be minimized in all environments, energy cannot, if the swarm's sensing range is bounded. In contrast, we show that energy can be minimized by ``ant-like'' robots in synchronous settings and asymptotically minimized in asynchronous settings, provided the environment is topologically simply connected, by using our ``Find-Corner Depth-First Search'' (FCDFS) algorithm. Our theoretical and experimental results show that FCDFS significantly outperforms known algorithms. Our findings reveal key limitations in designing swarm robotics systems for unknown environments, emphasizing the role of topology in energy-efficient dispersion.
