複数の環境に適応可能な移動ロボット群向けの分散アルゴリズム設計

本プロジェクトでは、自律移動ロボット群向けの協調および合意問題に対する研究を行う。平成24年度は、自律エージェントのグループがグラフを描くために協調するという拡張問題についての成果を主に得た。研究代表者らは以下の2つのソフトウェアツールを開発した。1つ目のプログラムは、環境の抽象的表現を入力情報としてとり、あらゆる探索アルゴリズムを生成する。本ツールにより、逆に、不能問題にはアルゴリズムが存在しないということを証明することができた。本成果は、他の研究者による既存論文の誤りの指摘に役立っている。2つ目のプログラムは、専門的なモデルチェックツールである。探索プログラムの正確性を自動的にチェックする。環境サイズ、ロボット数といった特定のパラメーターにより、本ツールは(1)アルゴリズムが構文的に正しいか、(2)アルゴリズムが安全か(たとえば、衝突の回避が保証できるか)、そして(3)アルゴリズムが正確か(たとえば、探索が必ず成功するか)を示す。現在のところ、本ツールはリングトポロジーのみで動作する。予備的な研究結果はSSS国際会議(SSS2012:14th International Symposium on Stabilization, Safety, and Security of Distributed Systems)で発表済みであり、最終的な成果は今後発表予定である。

本プロジェクトでは、自律移動ロボット群向けの協調および合意問題に対する研究を行う。平成24年度は、自律エージェントのグループがグラフを描くために協調するという拡張問題についての成果を主に得た。研究代表者らは以下の2つのソフトウェアツールを開発した。1つ目のプログラムは、環境の抽象的表現を入力情報としてとり、あらゆる探索アルゴリズムを生成する。本ツールにより、逆に、不能問題にはアルゴリズムが存在しないということを証明することができた。本成果は、他の研究者による既存論文の誤りの指摘に役立っている。2つ目のプログラムは、専門的なモデルチェックツールである。探索プログラムの正確性を自動的にチェックする。環境サイズ、ロボット数といった特定のパラメーターにより、本ツールは(1)アルゴリズムが構文的に正しいか、(2)アルゴリズムが安全か(たとえば、衝突の回避が保証できるか)、そして(3)アルゴリズムが正確か(たとえば、探索が必ず成功するか)を示す。現在のところ、本ツールはリングトポロジーのみで動作する。予備的な研究結果はSSS国際会議(SSS2012:14th International Symposium on Stabilization, Safety, and Security of Distributed Systems)で発表済みであり、最終的な成果は今後発表予定である。