著者

横尾 真 北村 泰彦

出版者

一般社団法人日本ソフトウェア科学会

雑誌

コンピュータソフトウェア (ISSN:02896540)

巻号頁・発行日

vol.14, no.4, pp.379-387, 1997-07-15

被引用文献数

8

---

複数のエージェントが1つの問題を並行して解く協調探索において,進化的計算における淘汰と同様なアイデアを用いてエージェント間の競争を導入したアルゴリズムを開発した.本アルゴリズムでは,状態空間探索問題を解くマルチエージェントReal-Time A^*アルゴリズムにおいて,複数のエージェントが定期的に適合度に応じて確率的に次世代の子を作る.適合度はエージェントの現在位置の評価値によって決定され,より良い評価値を持つエージェントが次の世代により多くの子を残せる.この方法により,有望な経路に労力を集中しアルゴリズムを効率化することと,多様性を保ち知識の誤りに対して頑健であることが両立可能である. 例題を用いた評価により,nパズルのように問題の目標が直列化可能な複数の副目標(serializable subgoals)に分解可能な場合には,エージェントは副目標に関する知識を持っていないにもかかわらず,本方式により劇的な高速化が得られることを示す.特に,本アルゴリズムは48パズルを安定して解くことが可能である.この問題は副目標に関する知識を陽に与えない限り,従来のヒューリスティック探索アルゴリズムでは現実的な時間内で解を得ることは不可能であった.