マルチエージェント実時間探索に関する研究

ヒューリスティックス探索は人工知能における基本的な問題解決手法の一つである．しかしながらA*のように最適解を求める手法は探索の過程における計算量の組み合わせ的爆発に直面し，問題のサイズが大きくなると現実的な時間で解を求めることが不可能になる．一方，実時間A*では先読み探索と移動を交互に実行することにより近似解を現実的な時間で求めることのできる手法である．ここでは，複数のエージェントが並列的に実時間A*を実行する場合における組織化に基づく協調手法を研究している．本研究では性能向上の原因を明らかにすることを目的とし，特に，問題の性質（ランドスケープ）とエージェントの組織化にはどのような関係があるのかを明らかにした．

またエージェントを再配置することによりN-パズルのような問題では劇的に性能が向上することを示した．さらに得られた知見を単一エージェント探索に応用した多状態コミットメント探索を提案した．

関連論文

北村泰彦，宮地智久，横尾真，辰巳昭治．多状態コミットメント探索とその評価，人工知能学会誌，14(5), 1999.

Yasuhiko Kitamura, Makoto Yokoo, Tomohisa Miyaji, and Shoji Tatsumi. Multi-State Commitment Search, Proc. 10th IEEE International Conference on Tools with Artificial Intelligence, 431-439, 1998.

横尾真，北村泰彦．淘汰を用いたマルチエージェント実時間探索の高速化：協調探索への競争の導入．コンピュータソフトウェア，14(4):379-387, 1997.

Yasuhiko Kitamura, Ken-ichi Teranishi, and Shoji Tatsumi. Organizational Strategies for Multiagent Real-time Search. Proc. International Conference on Multi-Agent Systems (ICMAS-96), 150-156, 1996.

Makoto Yokoo and Yasuhiko Kitamura. Multiagent Real-time A* with Selection: Introducing Competition in Cooperative Search. Proc. International Conference on Multi-Agent Systems (ICMAS-96), 409-416, 1996.

北村泰彦，寺西憲一，辰巳昭治．マルチエージェント実時間探索における組織化とその評価．人工知能学会誌，11(3):470-477, 1996.

北村泰彦，寺西憲一，辰巳昭治，奥本隆昭．マルチエージェント実時間探索における組織化手法．マルチエージェント協調計算IV，近代科学社，85-91，1995.