マルチエージェント実時間探索における組織化とその評価

北村 泰彦

寺西 憲一
年月

辰巳 昭治
日

まえがき
試行錯誤を伴うような非決定的問題解決のための基本的な解決手法として，これまでに様々な探索手法が研究されてきた．深さ優先探索や幅優先探索等の力ずく探索手法は計算量の組合せ的爆発を招き，それに対処するために発見的知識を用いて枝刈りを行うや反復深化等のヒューリスティック探索手法が提案されるようになった．しかしながら一般的には，その計算量は問題のサイズ（状態数）に対して指数的に増加する．
オフライン探索と見なすことができるが，やは探索と移動が分離されたは一定時間内の探索結果を基に移動を行なわねばならないというゲーム探索の概念を導入することにより，先読み探索と移動を交互に行うオンライン探索手法として実時間を提案した．

では最適解を保証することはできないが，先読み探索の範囲は有限であることから計算量は改善され，解の長さに対して線形となる．
は準最適解を求める探索アルゴリズムと見なせるが，その解の質を向上させるためにには二つの手法が提案されている．一つは先読み探索の範囲を広げ ることであるが，その計算量は先読み探
人工知能学会誌採録決定

索の深さに対して指数的となる．もう一つはアルゴリズムに学習機能を付加したであるが，解の質を向上させるためには同一の問題を何度も繰り返し探索しなければならない．
さて，は探索に関わるエージェントの数を増加させることにより解の質を向上させるマルチエー

ジェント実時間探索を提案した問題に対して複数のエージェントはそれぞれ自律的，並行的に．

では同一のを実行する．エージェントが探索過程で分岐に遭遇し，そのそれぞれの経路が同等に望ましいときには，エージェントはランダ ムに経路を選択する．それゆえ，エージェント数を増加させれば，異なる経路がより多く探索されることになり，確率的により良い解経路が得られることになる．
り，はでは，計算量はエージェント 数に対して線形であパズル等の問題に対しては，先読み探索の範囲を広げ た（熟考する）少数のエージェン

トよりも，先読み範囲を最小限にした（即応的な）多数のエージェントの方が有効であることを示している．さらにアルゴリズムは並列システムに実装することも容易であり，その有効性はさらに大きいといえる．
われわれがにおいて興味あるのは，より望ましい経路をより速く発見するためにエージェントはいかに協力すべきかという点である．のでは，エージェントは独立して経路選択を行うだけで，エージェント間で経路選択に関する調整は行われていない．したがって冗長な経路探索が行われる可能性が大きく，必ずしも効率よい探索が群として行われているとはいえなかった．そこで本論文では，エージェントが相互に協調して組織的に探索を行う手法を研究の対象とする．すなわちエージェントが互いの位置関係を把握することにより，分散と密集に基づく二つのエージェント組織化手法を提案する．
対象となる問題に応じて適切に組織化されたエージェント群は，ランダ ムな経路選択を行なうエージェント群と比べて，探索効率の向上をもたらすことが予想され，その評価のために迷路探索問題
パズル問題とを用い，シミュレーション実験を通してその有効性を明らかにする．

マルチエージェント 実時間探索
グラフに関する基礎概念
まず数学的な準備としてグラフに関する基本的な用語を定義する．
グラフは節点の集合で表される．ここでは，ば，はの子に，と（ 有向）辺とする．あるグラフ， はの親の時にからへの経路と呼び，と呼ぶ．辺にコストが集合 として与えられる場合には，経路のコストは木

は親をもたない根の組において，であれと呼ぶ．節点の列のとき，その経路を閉路持たない木の節点は葉の集合
はを経路の長さと呼ぶ．特但しは正の実数ので与えられる．

（節点）を除く全ての節点がたった つの親をもつグラフである．子をと呼ばれる．根からある節点までの経路の長さをの深さと呼ぶ．

問題の定式化
人工知能で扱うような非決定的な問題解決は以下のような状態空間表現により定式化することができる．
問題

は，組により与えられる．ここで， は空でない状態は状態遷移を生じさせるオペレータは目標状態の集合である．この時，組によりグラフとなり，状態空間グラフの集合，は初期状態の集合，，は状態を節点，オペレータを辺とみなすことと呼ぶ．

求めるべき問題の解だし，とは初期状態から目標状態である．オペレータにコストに至る任意の経路たが与えられているとき，解のコストはその経路のコストとして与えられる．あるコストの解が存在し，それよりも小さいコストの解が存在しなければ，その解は最適解であるという．

ヒューリスティック探索
状態空間グラフ探索の最も基本的な操作は，ある状態にオペレータを適用して得られる子状態を求める
状態生成である．特に全ての子を生成することを状態展開

このとき親状態は展開されたと呼び，という．一般的なグラフ探索は初期状態から始めて，目標状態が発見されるまで，次々と生成された状態を展開することにより実行される．通常，探索過程を記録しておくために，生成された子にはその親 に戻るポインタ

インタから初期状態を根とした探索木が付けられ，生成された状態とポが形成される．

展開する状態の順序によって深さ優先や幅優先など，さまざまな探索手法が利用可能であるが，このよ
うな力ずくの探索手法は状態空間が大きい問題に対しては計算量の組合せ的爆発により現実には実行不可能である．そこで，それぞれの状態に評価値を与え，評価値の高い状態の展開を優先することにより，探索効率の向上を図っている．最適解を求める探索では一般に，状態 の評価値は以下に示す評価関数により与えている．

ここでは初期状態から状態までの最適経路のコスト，のコストである．しかしながら，このとは状態から目標状態までの最適経路は探索の途中では正しい値を得ることができないので，などのヒューリスティック探索では以下に示す推定値を評価値として用いる．

ここで，た，は既に得られている探索木の中で，初期状態から状態はまでの最適経路のコストとする．まから目標状態までの最適経路のコストの推定値であり，ヒューリスティック関数として発見的に与えられるものである．

アルゴリズムでは解の最適性を保証する適格性て，全ての状態においての条件としが満たされなければならない．

実時間探索
アルゴリズムは経路探索（求解）と移動（解の適用）が分離されたオフライン探索と見なすことができる．

アルゴリズムは最適解を保証するが，一般的には問題のサイズ（状態数）に応じて指数的な計算量を必要とするために大きな探索空間を持つ問題に適用することは困難であった．

は一定の先読み探索と移動を交互に行うことにより，最適解を保証することはできないけれども計算量を削減することのできるオンライン探索手法として以下に示す
〔初期化〕
〔展開〕

アルゴリズムを提案した．とする．
を展開して，その子状態の集合を〔終了判定〕とする．

を満たす目標状態が存在するなら，として，終了．
〔先読み探索〕全ての評価値について， を経由して目標状態に至る場合のを計算する．ここで，はから深さのまでの先読み探索結果をもとに次のように計算する．

ただし，はを根とする深さはその時点で知られているからの先読み探索木の葉状態の集合とし，までの最適経路のコストとする．

〔移動候補選択〕となる隣接状態を求める．複数存在するときはランダ ムに選択する．
〔推定コスト更新〕の値を二番目に小さいに更新する．もし存在しなければ，〔移動〕とする．とする．

へ．
では移動しながら探索を行うので，状態の評価値にはは含まれず，目標状態までのコストのような初期状態からのコストを表すのみを用いている．したがって探索の経過が評価値には現れないので，同じ状態を何度も訪問する無限ループ に陥る可能性がある．しかしではにおいてが単調増加するように更新されるので，無限ループ に陥らず，解が存在すれば必ず発見されるというアルゴリズムの完全性
また，が保証されている．

として更新される二番目に小さい評価値の値は，状態から移動の対象となる以外の状態を経由して目標状態まで至る経路の最小推定コストを示している．

においてを二番目に小さい評価値に更新することは，以前に訪問した状態への再訪問を抑制して，探索効率を向上させることになる．なぜならば，二番目に小さい値に更新することは最小値に更新する場合と比べて，その状態の推定コストを大きくし，移動先としてその状態を選択する可能性を低くするからである．その反面，この値は状態の評価値としては過大評価を与えている場合もある．
さてみ深さ

はにおいて解の質を改善する二つの方法を示している．一つは先読み探索において先読を増大させることであるが，計算量は先読みの深さに対して指数的に増加するという性質がある．

もう一つは各状態から目標状態までの推定コストににおけるを学習する方法である．この場合，先に述べたようの更新は過大評価となる場合があるので，最小評価値アルゴリズムを用いることになる．これによって同一の状態に繰り返し訪問する回数はに更新するの値は徐々に真の値に収束することが保証されるが，より多くなり，解を求める探索速度は低下する．また学習する場合には同じ問題を連続的に繰り返し探索する必要があり，計算量も増加する．

マルチエージェント 実時間探索において解の質を改善するもう一つの方法として，
索でを提案した．
を実行する．

はマルチエージェント実時間探では，複数のエージェント はそれぞれ自律的，並行的に先読み深さにおいて最小評価値を持つ移動候補が複数存在するときには，エージェントはランダ ムに移動先を選択する．の有効性は次の点にまとめられる．

〔発見効果〕エージェント 数を増加させれば，それだけ異なる経路がより多く探索されることになり，解の質が改善される．また一部のエージェントが探索に行き詰まっても残りのエージェントが探索を続けることができる．
〔学習効果〕エージェント数を増加させれば，推定コストの更新が活発になり，解の質が改善される．

また，における探索時間は，先読み深さの増大に対しては指数的に増大するが，エージェント数の増加に対しては線形にしか増大しないので計算量の面からは有利であるといえる．さらには並列システムへの実装が容易であり，探索の高速化が期待できるという利点もある．
ただしの提案したには二つの問題点がある．第一の問題点は番目に小さい評価値に更新する
では，の更新手法として二方式を用いている点である．複数のエージェントがを共有するを二番目に小さい評価値に更新することは，状態の評価値としては過大評価になり，他のエージェントの探索を妨げ る可能性がある．一方で，方式の推定コスト更新は，推定距離の過大評価を行なわないが，エージェントの再訪問を抑制しないため探索時間を増加させるという欠点がある．
そこで本研究では，

方式と方式を組み合わせた推定コスト更新手法を提案する．すなわち，エージェントが互いに共有する大局的推定コストはと個別に管理する局所的推定コスト方式で更新することにより推定コストの過大評価を防ぎ，同時に新することにより再訪問を抑制するようにしている．のアルゴリズムのを用い，をと方式で更は以下のように修正される．
〔先読み探索〕全ての評価値について， を経由して目標状態に至る場合ののを計算する．ここで，は未訪問は訪問済である．
〔推定コスト更新〕とする．またの値を二番目に小さいに更新する．もし存在しなければ，とする．
方式と方式を組合わせた推定コスト 更新手法を用いたは，の提案した方式のみのものに比べて，解の質に関して改善が見られた．また探索速度に関してはエージェント密度が高くなるにつれ効果が現れたが，低い場合は逆に探索速度は低下した 寺西が密集して探索する場合に．これはエージェント方式のみでは，エージェントは互いに探索を妨げ あっていることを示している．
第二の問題点はエージェント群の組織化に関してである．のにおいて，同等な評価値をもつ複数の子状態に遭遇した場合，移動候補選択はランダムに行われていたが，これではエージェントの探索経路が重複することを避けることができない．このような探索経路の重複は，その探索の冗長性からエージェントの群としての探索効率を低下させることになる．そこで次節ではエージェントが互いの位置関係を把握することにより，分散と密集に基づいて組織的に探索を行う手法を提案する．

分散と密集に基づくエージェント の組織化のでは移動候補選択においてエージェント 間で明示的な調整は行われていなかった．

そこで本研究では，においてエージェント間で調整を行う組織化手法を提案する．対象となる問

題に応じて適切に組織化されたエージェント群は，ランダ ムな経路選択を行なうエージェント群と比べて，探索効率の向上をもたらすことが予想される．組織化手法として，分散と密集に基づく二つの組織化手法を提案する．分散に基づく組織化は，エージェントが互いに反発しながら移動することにより，より広い探索空間に位置することが促進され，の発見効果が強化される．また密集に基づく組織化は，エージェントが互いに誘引しながら移動することにより，探索空間の狭い範囲に密集して，の学習効果を強化する．

分散に基づく組織化
分散に基づく組織化手法は，エージェントは互いに他のエージェントとの位置関係を把握し，エージェントが同等に望ましい経路に遭遇した場合には他のエージェントから離れる経路を選択するように調整する．
ここでエージェント間の位置関係を表現するものとして，エージェントの隣接度る．エージェント が状態ここで，態はから状態に位置する場合の隣接度を定義すは以下のように計算される．に関わるエージェントの集合， はエージェント が位置する状態，は状までの経路の推定コストとする．すなわち，エージェントの隣接度は経路コストを尺度として最も近くに位置するエージェントとの距離を表している．
次にエージェント が互いに離れるように移動するかどうかを決定する基準として反発領域を定義する．エージェント の現在の状態における反発領域は以下のように計算する．

ここで， は初期状態である．この反発領域はエージェントが初期状態に位置するとき，最も大きくなり，目標状態に近づくにつれて小さくなるように工夫している．この結果，探索初期においては各エージェントは互いに離れる経路を選択する．しかし目標状態へ近づくにつれて反発領域は小さくなり，目標状態に収束する．また，パラメータ を変化させることによっても，反発領域の大きさを調整することができる．
以上のような隣接度 と反発領域を用いて，アルゴリズムの移動候補選択ステップ は以下のように変更される．
〔移動候補選択〕エージェント は移動候補集合から次のように移動先を決定する．となるとなるを選択．

を選択．

移動候補が複数存在するとき，ランダ ムに選択する．
すなわち全ての移動候補が反発領域内にあれば，その中でもっとも隣接度が大きくなるものを選択する．
反発領域の外側に候補が存在すれば，その中からランダ ムに選択する．

密集に基づく組織化
密集に基づく組織化手法では，エージェントは互いに他のエージェントとの位置関係を把握し，エージェントが同等に望ましい経路に遭遇した場合には他のエージェントに近づく経路を選択するように調整する．
ここではエージェント 間の分離度おける分離度を定義する．エージェント の状態に位置する場合には隣接度と同様に以下のように計算する．

密集による組織化では，エージェントが誘引領域うに経路選択を調整する．すなわち，で示される範囲内にに位置するよの値が大きいとき各エージェントはまばらになり，の値が小さいとき各エージェントは互いに密集して探索を進めることになる．
密集に基づく組織化ではアルゴリズムの移動候補選択ステップ は以下のようになる．

〔移動候補選択〕エージェント は移動候補集合から次のように移動先を決定する．となるとなるを選択．

を選択．

移動候補が複数存在するとき，ランダ ムに選択する．
すなわち全ての移動候補が誘引領域外にあれば，その中でもっとも遠隔度の小さいものを選択する．誘
引領域の内側に候補が存在すれば，その中からランダ ムに選択する．
また，分散に基づく組織化と密集に基づく組織化を併用することも容易である．この場合はとで定義されるド ーナツ状の領域にエージェントが位置するように経路選択が行われる．以上のような組織化を行う場合の付加計算量はエージェント間の隣接度と分離度の計算に伴うものであり，それはる．ここでであは探索に関わるエージェントの集合である．

評価実験と考察
評価問題
における組織化の効果に関する評価を，以下に示す迷路探索問題とパズル問題を用いて行なう．
迷路探索問題

格子状グラフ上の迷路において入口から出口までの経路を求める問題である

ジェントには上下左右のみの移動を許し，斜めには移動できないとする．エージェントのきコスト．エー回の移動につかかるとする．また移動不可能なマス目をランダ ムに発生し，障害物としている．問題には，ランダ ムに発生させた障害物の比率をとし，入口，出口とするの格子状グラフを用いている．推定コストの初期値には，目標状態までのユークリッド 距離 対角線距離 を用いている．また，隣接度 ，遠隔度 の計算にもユークリッド 距離を用いている．また，ランダムな選択が探索結果に影響を与えるため， 題を回実行してその平均値を取った．実験結果は個の問題 を解いた平均値である．
パズル問題

パズル問題は，い位置 を含んだ，個の数が付けられた正方形のタイルとブランク タイルの存在しなの正方形の枠からなっている．ブランクを移動する毎にコストかかるとする．

タイルの配置を与えられた目標状態まで移動させることが問題となる．推定コストの初期値，隣接度，遠隔度には，タイルの現在位置と目標位置との間のマンハッタン距離の総和を用いている．迷路探索問題と同じく題を回実行してその平均値を取った．実験結果はで示されている題の内， 題の問題 を解いた平均値である．

評価実験
迷路探索問題，パズル問題ともに，エージェントは並列に動作可能で， 回の移動毎にかると仮定している．またエージェントは大局的推定コスト
解の存在するもののみを選択している．
問題の難度を配慮して上級 問，中級 問，下級問を選択している．

単位時間かを共有している．ただし先読み探索や組4000

α = 402500

2000

α = 60α = 80360

Solution Length

α = 60α = 803000

α= 0α = 20365

α = 403500

Search Time370

α= 0α = 20355
350
345

1500

340

1000

335
24681012141624681012

Number of Agents

Number of Agents(a) 探索時間(b) 解の質図

14

分散に基づく組織化の迷路探索問題における効果織化などの計算コストは含めておらず，組織化の手法に応じた移動先決定の優劣のみを比較している．実験では探索時間と解の質を測定するが，複数のエージェントの中で最初に目標状態に到達したエージェントの所要時間が探索時間となり，その解経路の中で閉路を除いたものが解の質を表している．
分散に基づく組織化の実験では誘引領域を無制限の時はとし，反発領域のパラメータ を変化させた．の手法と等価になる．迷路探索問題の実験結果を図 ，図 に示す．いずれも横軸はエージェント数

パズル問題の実験結果をである．実験の結果から分散に基づく組織化は探索時間においては迷路探索問題で効果を示したが，パズル問題では探索時間，解の質ともに性能が低下している．
次に密集に基づく組織化の実験では反発領域をはとし，誘引領域の手法と等価になる．迷路探索問題の実験結果を図 ，

この結果から密集に基づく組織化は迷路探索問題では性能が悪化し，を変化させた．の時

パズル問題の実験結果を図 に示す．
パズル問題では性能が向上するという，分散に基づく組織化とは対照的な結果が得られた．

考察におけるエージェント組織化手法の効果は推定凹部

石田を用いて説明できる．推定凹部とは直観的にいえば，目標状態への推定コストの局所的な凹みである．実時間探索を行なうエージェントは単純に最小な評価値を持つ状態を選択し，移動を続けるので，容易に推定凹部の底へ移動してしまう．推定凹部に陥ったエージェントは推定凹部の各状態の推定コストの更新を繰り返し，推定凹部を埋めなければそこから抜け出すことはできない．
ここで迷路探索問題とパズル問題がどのような推定凹部を持っているかどうかを，エージェントが目標状態に到達するまでに通過した各状態の最適コストと推定コストの初期値の差を以下のように測定することで確認してみる．
エージェント数のにおいて，エージェントが目標状態に到達するまでに通過した各状態

16

1700

900

α= 0α= 51600

α= 5α = 201500

α = 20α = 40800

α = 40

Solution Length

1400
1300

Search Time

α= 01200
1100
1000
900

700

600500800
700400600
500

300
246810246810

Number of Agents

Number of Agents(a) 探索時間(b) 解の質図

分散に基づく組織化の4500

370

G = 40360

Solution Length

3000
2500
2000
1500

∞

G=
G = 80G = 60365

G = 60G = 40G = 203500

12

パズル問題における効果

G =∞G = 804000

Search Time

12G = 20355
350
345
340

1000

335
246810

Number of Agents

1214162468(a) 探索時間
図10

Number of Agents

密集に基づく組織化の迷路探索問題における効果(b) 解の質

121416

1600

850

∞
G = 201400

Search Time

1200

∞

800

G=

G = 15750

G = 15

G = 10G= 5700

Solution Length

G=1000800

G = 20

G = 10G= 5650
600
550

500
450400

600

350
300

400

250
246810122468

Number of Agents

Number of Agents(a) 探索時間(b) 解の質図

密集に基づく組織化の10

パズル問題における効果の推定コストの初期値を記憶する．
目標状態から幅優先探索を行なうことにより，目標状態からエージェントが通過した全ての状態までの最適コストを計算し，記憶する．
各状態における最適コストと初期推定コストの差，すなわち推定凹部の深さを計算する．
ただし，パズル問題では探索空間が非常に大きくなるので，その代わりに定凹部を持つと考えられるパズル問題と同様の推パズル問題を用いて測定を行なった．

推定凹部に関して迷路探索問題の測定結果を図 に， パズル問題のの測定結果を図 に示す．横軸は推定凹部の深さ，縦軸はその値を持つ状態の割合

推定凹部の深さは からまでの広い範囲に分布し，同じ値である状態の割合は全てに， パズル問題においては推定凹部の深さはると迷路探索問題はである．迷路探索問題では，から未満である．逆までの狭い範囲に集中している．これらを比較すパズル問題に比べて深い推定凹部が多数分布していることが確認できる．

すなわち，迷路探索問題は，障害物による壁の存在がその向こう側にある目標状態に対して推定凹部を作るため，深い推定凹部が状態空間に点在するが， パズルやパズル問題では迷路探索問題のような深い推定凹部がほとんど現れず，浅い推定凹部が広い範囲に分布しているといえる．
したがって密集に基づく組織化を迷路探索問題に適用した場合，多くのエージェントが集団として推定凹部の底へ吸い込まれてしまう．一方で，エージェントを互いに反発させる分散に基づく組織化手法では，エージェントはそれぞれ間隔をあけながら移動するので，深い推定凹部に陥らないような経路を選択するエージェントの割合は多くなり，発見効果が有効に働いている．したがって，迷路探索問題には反発領域を大きくし，エージェント群の範囲を広げ る分散に基づく組織化手法は有効であるといえる．
しかしパズル問題では深い推定凹部は少なく，多数の浅い推定凹部が存在する．その際にはエージェントはばらばらで移動するよりも，協力して推定凹部を埋めて行くほうが効果的であるといえる．すなわ
ち，あるエージェントが行なった推定距離の更新を他のエージェントが利用できる密集に基づく組織が適している．誘引領域を狭めれば学習効果が強化され，よりコストの小さい経路を見つける可能性が高くな

120.500.250.00
0100200300400500h(s) -＾h(s)図

迷路探索問題の推定凹部

462520

Ratio of States(%)

Ratio of States(%)

0.75

151050028101214h(s) -＾h(s)図

パズル問題の推定凹部

161820る．したがってパズル問題には密集に基づく組織化手法が有効であるといえる．

むすび
マルチエージェント実時間探索において，分散と密集に基づく二つの組織化手法の提案とその評価を行った．実時間探索に関わるエージェントはそれぞれ相互の位置関係を把握し，分散の場合はより離れる方向に，密集の場合はより近づく方向に移動しながら探索を行う．には発見効果と学習効果の二つの利点があり，分散と密集に基づく組織化はそれぞれを強化する性質がある．評価のために，推定凹部の視点からそれぞれ対照的な特徴を持つ迷路探索問題とパズル問題を用いた．深い推定凹部が点在する迷路探索問題では発見効果を強化した分散に基づく組織化が，浅い推定凹部が偏在するパズル問

題では学習効果を強化した密集に基づく組織化が有効であることが示された．以上のことから対象となる問題の性質に応じて適切な組織化手法を用いれば，従来の組織化を行わない手法に比べて，探索効率を向上させることができる．推定凹部と有効な組織化の関係は明らかになったといえるが，さらに詳細な反発領域や誘引領域の決定は今後の課題である．また，探索の過程でエージェントを動的に組織化することも興味ある課題の一つといえる．

参考文献
人工知能 共立出版 東京寺西

寺西憲一 マルチエージェント実時間探索における組織化手法に関する研究

大

阪市立大学工学研究科電気工学専攻
石田

石田亨 実時間両方向探索 マルチエージェントと協調計算

近代科学社