A study on Byzantine-tolerant algorithms for mobile robots

本研究では、多数のモバイルロボットが協調動作する環境において、一部のロボットにビザンチン故障（ソフトウェアのバグや悪意ある第三者の制御により、予期せぬ動作を行う故障）が発生しても、残りのロボットで正常に目的を達成するアルゴリズムの開発を目指す。主な成果は以下のとおりである。(a) グラフ環境における耐ビザンチン故障集合アルゴリズム：ロボットの動作環境をグラフでモデル化し、ビザンチン故障が発生したロボットが存在しても、全ての正常ロボットを１ノードで集合させるアルゴリズムを提案した。本アルゴリズムでは、kを全ロボット数、fをビザンチン故障が発生したロボット数とするとき、k>=9f+8であれば集合を実現することができる。同様の故障耐性を実現する既存アルゴリズムはk>=f+1でも動作するものしか存在しないが、本アルゴリズムはこの既存アルゴリズムより高速に集合を実現できる。(b) 平面環境における耐ビザンチン故障アルゴリズムの設計手法：平面環境でモデル化されるロボットに対して、位置関数という概念を提案し、位置関数を用いた耐ビザンチン故障アルゴリズムの設計手法を提案した。本手法では、ロボットを位置関数に従って動作させることで、ビザンチン故障が発生したロボットを無視し、正常なロボットでタスクを実現できるようにする。また、代表的な基本タスクである集合・行進・探索タスクに対して本設計手法を適用し、これらのタスクに対する耐ビザンチン故障アルゴリズムを実現した。

本研究では、多数のモバイルロボットが協調動作する環境において、一部のロボットにビザンチン故障（ソフトウェアのバグや悪意ある第三者の制御により、予期せぬ動作を行う故障）が発生しても、残りのロボットで正常に目的を達成するアルゴリズムの開発を目指す。主な成果は以下のとおりである。(a) グラフ環境における耐ビザンチン故障集合アルゴリズム：ロボットの動作環境をグラフでモデル化し、ビザンチン故障が発生したロボットが存在しても、全ての正常ロボットを１ノードで集合させるアルゴリズムを提案した。本アルゴリズムでは、kを全ロボット数、fをビザンチン故障が発生したロボット数とするとき、k>=9f+8であれば集合を実現することができる。同様の故障耐性を実現する既存アルゴリズムはk>=f+1でも動作するものしか存在しないが、本アルゴリズムはこの既存アルゴリズムより高速に集合を実現できる。(b) 平面環境における耐ビザンチン故障アルゴリズムの設計手法：平面環境でモデル化されるロボットに対して、位置関数という概念を提案し、位置関数を用いた耐ビザンチン故障アルゴリズムの設計手法を提案した。本手法では、ロボットを位置関数に従って動作させることで、ビザンチン故障が発生したロボットを無視し、正常なロボットでタスクを実現できるようにする。また、代表的な基本タスクである集合・行進・探索タスクに対して本設計手法を適用し、これらのタスクに対する耐ビザンチン故障アルゴリズムを実現した。