自律分散ロボット群に対する故障耐性をもつ協調プロトコル

点击翻译按钮获取中文摘要

自律分散ロボットシステムの理論モデルでは,各ロボットは固有の識別子を持たず(匿名性),過去の履歴を記憶できず(無記憶性),全てのロボットは同じアルゴリズムで制御され.非同期的に動作する.このロボットモデルでは,従来ロボットの故障に関しては,センサーの故障はロボットが認識する共通座標系の不一致として,筆者らのグループを含めていくつか考えられているが,ロボット自体の故障を考慮したものはほとんどない.平成21年度は,前年度の研究に引き続き,故障を含めた自律分散ロボットシステムにおける協調問題を検討した.具体的には,一時故障を含む自律分散ロボット群に対するフロッキング問題を理論的に定式化し,準同期耐故障性アルゴリズムを開発した.また,ロボットが任意のふるまいをするビザンチン故障を含むロボット群に対して,故障していないロボット群が円形成するための条件を明らかにした.すなわち,ロボットの台数をN,ビザンチン故障のロボット数をfとしたとき,N〓2f+2(f〓1)ならば,円形成できる完全同期アルゴリズムは存在しないことを示し,N>4f+1の場合には,円形成できる完全同期アルゴリズムを与えた.また,準同期を仮定した場合には,N〓3f+2であるとき,円形成するアルゴリズムは存在しないことも証明した.