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