1 はじめに

MSC ; RT A  (hS O s0 Gi)
準最適解を求めるヒューリスティック探索の高速化手 1: s  s0法の一つである多状態コミット メント探索 (Multi-State 2: generate successors(s)Commitment Search:MSCS) は，展開する状態を 1 つの 3: if successors(s) \ G 6=  then return success
状態に絞り込んでし まう 1-状態コミット メント 探索や， 4: update(s)全く絞り込まない全状態コミット メント探索よりも効率 5: add(commit list successors(s))
的な探索を行うことが示されている 6] 1．しかし，問題 6: while length(commit list) > n dos  get max(commit list)
のど のような性質が MSCS の性能に影響を与えているの 7:
8: if commit list =  then return failure
かは十分に説明されていなかった．
本稿で は ，6] で提 案され てい る 多状態コミット メ 9: s  get min(commit list)
ント 実時間 A* (Multi-State Commitment Real-Time 10: goto 2
図 1. MSC-RTA*アルゴ リズム
A*:MSC-RTA*) アルゴ リズム と 多状 態コミット メン
ト 重み付き A* (Multi-State Commitment Weighted
A*:MSC-WA*) アルゴ リズムについて性能解析を行う．
具体的には，N パズル問題，ハノイの塔問題，迷路問題 るか選択でき，以下では探索時間を重視するため，先読における MSCS の動作を解析することで，MSCS が有効 みの深さを 0 とし ている．
RTA*は状態を展開して隣接する状態を生成し ，次にな問題の性質を解明する．また，そのような性質を持つ
展開する状態を隣接する状態の中で最小の f(s s ) =人工モデルを作成し ，シミュレ ーション実験によって検c(s s ) + h(s ) を持つものに決定する．探索は目標状態証を行う．
を生成したとき終了する．RTA*はクローズド リストを用いないが，次の状態を展開する前に h(s) を隣接する状
ヒューリスティック探索の定式化 態の中で二番目に小さい f(s s ) に更新することでアル解析の前に，まずヒューリスティック探索の定式化を行 ゴ リズムの完全性を保証している．RTA*は隣接する状
う．問題は四つ組 hS O s0  Gi で表され，ここで S(6= ) 態の中で最小の評価値を持つ状態のみ保持するため，1は状態の集合，O は状態遷移を示すオペレ ータの集合， 状態コミット メント探索と見なすことができる．
s0 (2 S) は初期状態，G( S) は目標状態の集合である． MSC-RTA*と RTA*の違いは，コミット メントリスト
問題は初期状態からオペレータを繰り返し適用して目標 を用いるかど うかである．MSC-RTA*において隣接す
0

0

0

2

00

状態へ到達することによって解決される．

る状態は一旦コミット メント リストに追加され ，次にペレータの適用により得られる状態の系列は経路と呼ばの大きさの上限 n を持ち，コミット メントリストが n よれ，初期状態から目標状態への経路を解または解経路とりも大きくなると，評価値の大きい状態から取り除かれオペレータの適用にコスト (> 0) が定義される場合は， 展開する状態はコミット メント リストから 選択される．
状態 s，s0 (2 S) 間の遷移のコストを c(s s0 ) で示す．オ MSC-RTA*はパラ メータとし てコミット メントリスト

いコストをもつ解が存在しなければ，その解を最適解とる．このようにして MSC-RTA*は次に展開する状態を
1 個ではなく，n 個に絞り込む．n = 1 の MSC-RTA*は
RTA*と等価である．MSC-RTA*のアルゴ リズムを図 1

呼ぶ．

に示す．

呼ぶ．解経路を構成するオペレータのコストの和を解のコストとする．ある解が存在したとき，それよりも小さ

ヒューリスティック探索では，各状態 s(2 S) から目標状態までのコストの推定値が与えられており，ヒューリ
スティック関数 h(s) で表される．

3 MSC-RTA*アルゴリズム
実時間 A*(Real-Time A*:RTA*) アルゴ リズム 3] は

いくつかの問題上で MSC-RTA*と RTA*の性能を比較した結果を以下に示す．まず，15 パズル問題においてシミュレ ーション実験を行った．ヒューリスティックな評価関数に各タイルの目標状態におけ る位置とのマン

ハッタン距離の和を用い，ランダムに生成した 100 個の問題で各 100 回，合計 10,000 回試行した．解を得るまでに状態を展開した回数について平均値を取ると，RTA*は一定の先読み探索と移動を交互に行うアルゴ リズムであ2647.1 回展開したが，n = 2 とした MSC-RTA*は 1380.1

る．先読みの深さで解の質と探索時間のいずれを重視す

回しか展開しなかった．

1 展開する状態を n 個に絞り込むため， 6] では n-状態コミット メ
ント探索と呼ばれている．

次に ，円盤の数を 7 とし たハノイの塔問題においてMSC-RTA*と RTA*が状態を展開した回数を調べた．初期状態を全ての円盤がペグ 1 にある状態とし，全ての円

盤をペグ 3 に移動させることで解決されるものとし て，

8

1

4 11

9

2

10,000 回試行した．なお，ヒューリスティックな評価関

10

7

3

5

10

1

4

数には次式を用いた．

9

2

6

8

5

12 13 14 15

h(s) = max(2m1 ; 1 0) + max(2m2 ; 1 0) + 2m3
m1 ，m2 はペグ 1，ペグ 2 の円盤数，m3 はペグ 3 にあるが正しくは置かれていない円盤数である．このとき，RTA*は 2150.9 回，状態を展開し たが，n = 15 とし た MSCRTA*は 980.8 回しか状態を展開しなかった．
最後に，大きさを 120 120 とし た迷路問題でシミュ

3

1

7

6 11

12 13 14 15

5

2

3

4

6

7

8

9 10 11

12 13 14 15(a) 15 パズル問題

1

2

3

1

2

3

1

2

3

(b) ハノイの塔問題
図 2. 直列化可能な副目標

レーション実験を行った．ヒューリスティックな評価関数にはゴ ールとのマンハッタン 距離を用い，障害物のRTA*は展開する状態が 1 つに絞り込まれているため，各 100 回，合計 10,000 回試行した．RTA*は 7413.1 回し

一度副目標を破壊するような状態を選択するだけで副割合を 40% とし てランダ ムに生成し た 100 個の問題でか状態を展開しなかったにもかかわらず，n = 2 とし た

目標を保持できなくなる．例えば ，図 2(a) 中央のよう

MSC-RTA*は 7852.9 回も状態を展開しており，n を大き にタイルが配置されているとき，3 番のタイルを左に動かすと副目標は破壊されるが，2 番や 4 番のタイルを動くする程，より多く状態を展開した．
かしても副目標は保持される．もし 3 番のタイルを左に以上のように，MSC-RTA*は 15 パズル問題では n = 2
動かしたならば，RTA*は 3 番のタイルを動かした配置とし たとき RTA*の約半分の展開数で，ハノイの塔問題
だけを保持するため，副目標は保持されない．しかし ，でも n = 15 とし たとき RTA*の半分以下の展開数で解
MSC-RTA*では 2 番や 4 番のタイルを動かした配置がコを得ることができたが，迷路問題では RTA*よりも多く
ミット メントリストに残っている限り，いずれそれらのの展開数を必要とした (n > 1)．このように問題によっ配置から探索を再開することができるため，副目標は保て MSC-RTA*の効果が異なるのはなぜか？それぞれの持される．
問題の状態空間を調べ，MSC-RTA*と RTA*の動作を比
15 パズル問題上で 10,000 回試行し た際に状態を展開
較した結果，原因は副目標の保持と再展開の回数にあると予想される．

した回数と副目標を一度も壊さずに解くことができた問

題の数の平均値を表 1 に示す．15 パズル問題において，n = 2 とした MSC-RTA*は RTA*の 4 倍も副目標を保持
しやすいことが分かる．なお，n = 6 とした MSC-RTA*
目標が複数の副目標に分割でき，かつ副目標を順に達 は n = 2 としたものよりも副目標を保持しやすいにもか

3.1

副目標の保持成する際に以前の副目標を保持したままで以降の副目標を達成できるとき，その問題は直列化可能な副目標を持つという．15 パズル 問題は図 2(a) に示されているように，最初に一番下の並びのタイルを正しい位置に並べると, それ以降はこれらのタイルを動かすことなしに残りのタイルを正しい位置に並べることができる．さらに一番右の並びのタイルを正しい位置に並べると, これらのかわらず，状態を展開した回数は多くなっているが，この理由とし ては MSC-RTA*が RTA*よりも展開する状
態の絞り込みが緩いため，より多くの空間を探索しなけ

ればならなかったことがあげられる．副目標を破壊する
ことなく問題を解くこと場合の結果にのみ注目すると，探索空間の増大による展開数の増加が明確になる．副目
標を破壊することなく問題を解くことができた際に，状タイルを動かすことなしに残りのタイルを正しい位置に態を展開した回数と，展開した状態の個数，すなわち探上より，15 パズル問題は直列化可能な副目標を持っていまた，ハノイの塔問題を解く際に副目標を保持できた

並べられ，残りの問題は 8 パズル問題と等価になる．以る．そして，ハノイの塔問題も図 2(b) のように，一度ペグ 3 に正し く置かれた円盤を動かすことなく，他の円盤をペグ 3 に置くことができ，直列化可能な副目標を持つと考えられる．副目標は破壊されることもあり，もう一度達成するには余分な状態を展開しなければならないた

索した空間の大きさの平均値を表 2 に示す．

問題の数と状態を展開し た回数を表 3 に示す．RTA*では全体の約 4 分の 3 の問題でしか，副目標を保持できなかったが，n = 15 とし た MSC-RTA*ではほぼ 全ての問

題で副目標を保持できている．n を大きくすると副目標を完全に保持できる反面，展開数が増加するのは 15 パ

め，副目標を保持できるかが展開数を大きく左右する． ズルと同じく，絞り込みを緩くすると探索空間が増大す表 1. 15 パズル問題における副目標の保持
副目標を保持アルゴ リズム

展開数できた問題数RTA*
MSC-RTA*(n = 2)
MSC-RTA*(n = 6)

2647.11380.11600.3

216
984
4986

表 3. ハノイの塔問題における副目標の保持
副目標を保持アルゴ リズム

展開数できた問題数RTA*
MSC-RTA*(n = 15)
MSC-RTA*(n = 30)

2150.9980.8
1022.8

7456
9982
10000

表 2. 副目標を保持できた場合の展開数と空間量
アルゴ リズム
展開数 空間量

RTA*
MSC-RTA*(n = 2)
MSC-RTA*(n = 6)

済641.5 579.7
646.0 579.6
1127.5 1009.1

未済

済

RTA*の場合るためである．

以上より，直列化可能な副目標を持つ問題では，MSC-

RTA*が RTA*よりも副目標を保持しやすいため，結果として RTA*より少ない展開数で解が得られると考えら
れる．

3.2

済

済

済
MSC-RTA*の場合

図 3. MSC-RTA*による再展開の回避

る．このように同じ 評価値を持つ状態が密集した領域では，一度でも展開した状態の評価値は必ず未展開の状態

再展開数の減少

MSC-RTA*や RTA*はクローズド リストを用いないたよりも大きくなるため，MSC-RTA*の再展開数は RTA*
よりも少なくなる．表 4 に円盤の数を 7 とし たハノイの塔問題において，MSC-RTA*と RTA*が状態を再展開しめ，状態の再展開が起こり得るアルゴリズムである．従っ た数を示す．MSC-RTA*が RTA*の約 10 分の 1 しか再展て，同じ 領域を探索し ても再展開の回数が少なければ， 開をしないことが分かる．
結果とし て少ない展開数で解が得られる．MSC-RTA*

が状態の再展開を抑制する仕組みを説明するための例として，隣接する状態が全て展開済みである状況を考える(図 3)．RTA*は隣接する状態のみから次に展開する状態

また，ヒューリスティックな評価関数にゴールへのマン

ハッタン距離を用いた迷路問題では MSC-RTA*は RTA*

よりも再展開数が多くなる (表 5)．これは図 5 のように

袋小路の奥ほど 評価値が小さくなる傾向があり，MSC-を選択するため，必ず状態の再展開が起こる．しかし ， RTA*では，袋小路の状態の評価値がコミット メントリ
MSC-RTA*では 隣接する状態よりも小さい評価値を持 スト内で最小でなくなるまで，袋小路の状態を何度も再つ未展開の状態がコミット メントリストに存在すれば， 展開するためである．
以上より，同じ 評価値を持つ状態が密集している問題
その状態が次に展開されるため再展開は生じない．
ハノイの塔問題において，未だペグ 3 に正し く置かれていない円盤の枚数が等しい状態のほとんど で h(s) はでは，MSC-RTA*が RTA*よりも状態を再展開しにくい

ため，結果として MSC-RTA*が RTA*よりも少ない回数

等し くなる．未だペグ 3 に正しく置かれていない円盤の しか状態を展開せずに解が得られると考えられる．

枚数を M とし，ペグ 1，ペグ 2 に置かれた円盤の枚数をそれぞれ m1 ，m2 ，ペグ 3 にあるが，正しくは置かれていない円盤の枚数を m3 とすると，図 4 のように状態は4 MSC-WA*アルゴリズム

m2 = 0 の場合と m2 6= 0 の場合に分けることができ A*アルゴ リズ ム 5] は 状態 s の 評価に 初期状態からる．なお，m1 と m2 を入れ換えても同様である．ペグ 状態 s まで のコスト の和 g(s) と，状態 s から目 標状態
3 に正し く置かれた円盤の枚数が変化しない限り，h(s) までのコストの推定値 h(s) の和を用いるが，重み付きは 2M ; 1 と 2M ; 2 の 2 値しか取らず，m2 6= 0 となる A*(Weighted A*:WA*) アルゴ リズム 4] は g(s) と h(s)状態の数 (2 3M 1 ; 2M 1) は m2 = 0 となる状態の数 の比重を変更できるアルゴ リズムであり，状態 s の評価(2M 1) より遥かに多いため，M 枚の円盤がペグ 3 に正 には (1 ; W)g(s) + Wh(s) を用いる．このとき，W がしく置かれていない状態の大部分で h(s) = 2M ; 2 であ h(s) に対する重みであり，W によって解の質と探索時間;;;

m2 ≠ 0の場合

m2 = 0の場合

Start
10

h(s)=(2m1 -1)+2m3= 2(m1 + m3 )-1= 2M-1
状態数 =(2M -2M-1)= 2M-1h(s)=(2m1 -1)+(2m2 -1)+2m3= 2(m1 + m2 +m3 )-2= 2M-2
状態数 =(3M -3M-1)-(2M -2M-1 )= 2・3M-1-2M-1

図 4. ハノイの塔問題における h(s) のパターンと

9

8

7

6

5

9

7

6

5

4

8

6

5

4

3

7

5

4

3

2

3

2

1

0

6
5

4

Goal

それぞれの状態数

図 5. 迷路問題

表 4. ハノイの塔問題における再展開数
アルゴ リズム
展開数 再展開数

表 5. 迷路問題における再展開数
アルゴ リズム
展開数 再展開数

RTA*
MSC-RTA*(n = 15)2150.9980.81136.3115.2

RTA*
MSC-RTA*(n = 2)
MSC-RTA*(n = 6)

7413.17852.98104.46163.06606.56863.9のいずれを重視するかを決定できる．以下では，探索時間を重視するため，W = 1 の場合を想定し ，評価にはでシミュレーション実験を行った．まず，15 パズル問題
h(s) だけを用いる．
において，状態を WA*は 1889.0 回展開したが，n = 4 とA*と同じ く WA*もオープンリスト，クローズド リス した MSC-WA*は 1374.0 回しか状態を展開しなかった．
トと呼ばれる 2 つのリストを用いる．全ての生成された そして，ハノイの塔問題では WA*は状態を 838.4 回展開
状態は一旦オープンリストに保存され，また一度展開さ し ，n = 2 とした MSC-WA*は 796.4 回，状態を展開しれた状態はクローズド リストに保存されるため，一度展 た．最後に，迷路問題では，WA*は状態を 1229.9 回展開した状態は必ずいずれかのリストに存在する．従って， 開し，n = 2 とし た MSC-WA*は 1223.7 回，状態を展開
隣接する状態が生成済みか否かをいずれかのリストに存 した．わずかながら MSC-WA*の方が少ないが，これは在するかど うかで判断できるため，WA*は状態の再生 ほとんど 誤差の範疇である．
成を避けることができる．
以上のように，MSC-WA*は 15 パズル問題では WA*
WA*は未展開の状態を全てオープンリストに保持し の約 3 分の 2 しか状態を展開せずに解を得ることができており，展開する状態が全く絞り込まれていないため， たが，ハノイの塔問題や迷路問題では WA*と大差ない
全状態コミット メント探索と考えることができる．

MSC-WA*では， WA*のオープンリストの一部をコ
ミット メントリストとし ，WA*がオープンリストに対し性能しか示すことができなかった．この原因がど こにあるかを調べた結果，それぞれの問題における刈り込みの有効性にあると予想した．

て行う処理をコミット メントリストに対して行う．すな
わち，生成された状態はオープンリストではなく，コミッ
ト メントリストに追加され，次に展開する状態はコミッ

4.1 刈り込みの有効性

ト メントリストから選択される．MSC-WA*はパラメー

MSC-WA*が WA*のオープンリストをコミット メン

コミット メントリストが n よりも大きくなると，評価値

スト内の状態から探索を勧めて行くことは一時的な刈りの大きい状態からオープンリストへ移し変えられる．ま込みと考えることができる．刈り込みの効果は余分な空タとしてコミット メントリストの大きさの上限 n を持ち， トリストとオープンリストに分割し，コミット メントリ

た，コミット メントリストが n より小さければ，オープ

ンリスト内で評価値の小さい状態からコミット メントリ間を探索しないことにあるが，刈り込んだ場合と刈り込
まなかった場合で同じ空間を探索していれば，刈り込み

ストへ移し 変える．このようにし て MSC-WA*は次に展は無意味になってし まう．

WA*と等価である．MSC-WA*のアルゴ リズムを図 6 に態を展開した回数と，解が得られた際，コミット メント

示す．

リスト，オープンリスト，クローズド リストに保存され開する状態を n 個に絞り込む．n = 1 の MSC-WA*は15 パズル問題，ハノイの塔問題，迷路問題における状MSC-WA*と WA*を用いて MSC-RTA*と同様の条件 ていた状態の和，すなわち探索した空間の大きさを表 6

MSC ; WA  (hS O s0  Gi)
1: s  s0
2: generate successors(s)3: if successors(s) \ G 6=  then return success
4: add(commit list successors(s))
5: add(closed list s)
6: while length(commit list) > n do
7:s  get max(commit list)8:
add(open list s)
9: while length(commit list) < n and
10:(open list 6= ) do
11: s  get min(open list)
12: add(commit list s)
13: if (commit list = ) and (open list = ) then
14: return failure
15: s  get min(commit list)
16: goto 2
図 6. MSC-WA*アルゴ リズム

表 6. それぞれの問題における展開数と空間量
アルゴ リズム
展開数 空間量MSC-WA*(n = 4) 1374.0 2886.6
WA*
1889.0 3905.6(a) 15 パズル問題
アルゴ リズム

展開数

空間量

MSC-WA*(n = 2) 796.4
WA*
838.4
(b) ハノイの塔問題

876.3
891.3

アルゴ リズム

空間量

MSC-WA*(n = 2) 1223.7 1427.4
WA*
1229.9 1429.4(c) 迷路問題
表 7. 各問題における新しい状態を生成しない回数
新規生成
問題

展開数

なし の回数15 パズル問題

3940.7900.71233.4

9.2
219.8
294.3

ハノイの塔問題に示す．15 パズル問題において n = 4 とした MSC-WA*

は WA*よりも少ない空間しか探索していないが，ハノイの塔問題や迷路問題では WA*とほぼ 同じ 大きさの空間を探索している．

展開数

迷路問題

5 人工モデルMSC-RTA*の性能が副目標の保持と再展開数の減少
刈り込みの有効性を示す指標とし て，n = 1 とし た に依存し，MSC-WA*の性能が刈り込みの有効性に依存
MSC-WA*を用いて，状態を展開した際，新しい状態を していることを確かめるため，3 つの人工モデルを作成
生成しないことがどれくらいあるかを測定した (表 7)．す し ，シミュレーション実験によって検証を行った．
なわち，極端に刈り込まれた状況で状態を展開した回数
まず，MSC-RTA*が RTA*よりも副目標を保持しやすと比して新しい状態を生成しないことが多ければ，オー
プンリストからたびたび補充を受けることになり，刈り込みの効果が小さいと考えられる．15 パズル問題ではほぼ毎回新しい状態を生成しているが，ハノイの塔問題や迷路問題では状態を展開してもおよそ 4 回に 1 回は生成済みの状態しか生成できず，オープンリストから補充を受けており，刈り込みがあまり有効でないことを示していことを示すため，直列化可能な副目標を持つ人工モデ

ルとして，中央の障害物によって h(s) の初期値が異なる

2 つの領域に分割された迷路問題を作成した (図 7(a))．左
上が初期状態であり，右下が目標状態である．障害物の左側の領域から右側の領域に移動することで副目標は達成されるが，領域をつなぐ 通路は 2 つしかない上に，領域間の移動の際，h(s) の更新によって通路の h(s) は周囲よいる．なお，15 パズル問題で n = 1 とした MSC-WA*よりも大きくなるため，右側の領域から左側の領域に戻っ込みを厳しくしすぎると副目標の保持が困難になるためなるまで，もう一度右側の領域に移動できない．このたりも n = 4 とし たものの方が良い性能を示すのは，刈りである．

てしまうと，通路周辺の h(s) が通路の h(s) よりも大きくめ，副目標を破壊した場合，もう一度達成するには余分に状態を展開する必要がある．大きさが 30

30 の人工モ

以上より，状態を展開するたびに未生成の状態の状態 デルで 10,000 回試行した際に副目標を保持できなかったを生成するような問題では，刈り込みの効果によって問題の数と展開数の平均値を表 8(a) に示す．MSC-RTA*

MSC-WA*が WA*よりも少ない展開数で解を得られ る は RTA*の 16 分の 1 の問題でしか副目標の保持に失敗しておらず，結果とし て RTA*より少ない展開数で解を得と考えられる．

ている．表 8(b) はこの人工モデルおいて探索中に副目標を保持できた場合と保持できなかった場合の展開数を示しており，副目標を保持できなかった場合は保持できた
場合の 2 倍以上も状態を展開しなければならないことが分かる．
この人工モデルでは，障害物の左側の領域では h(s) =2 だが，右側の領域では h(s) = 1(< 2) であるため， 15
パズル問題やハノイの塔問題と同様に副目標を保持している状態の方が副目標を保持していない状態より h(s) が小さくなっている．このため，たとえ副目標を破壊する

表 8. 副目標を持つモデルにおける実験結果
副目標を保持でき
アルゴ リズム

では RTA*よりも副目標の保持が容易である．

MSC-RTA*において n を大きくするほど 副目標を保持し やすくなる条件に，副目標を保持し ている状態の

展開数

RTA*
3353 1075.7
MSC-RTA*(n = 2)
728 687.2
MSC-RTA*(n = 3)
398 628.4
MSC-RTA*(n = 4)297 610.8
MSC-RTA*(n = 5)
202 597.4(a) 副目標を保持できなかった問題の数と展開数

ような状態を選択したとしても，副目標を保持している状態がコミット メントリストに残りやすく，MSC-RTA*

なかった問題の数

保持できた

保持でき

場合

なかった場合アルゴ リズム

RTA*
708.7
1803.2
MSC-RAT*(n = 5)573.2
1770.4(b) 副目標保持の可否による展開数の相違

h(s) が 保持し ていない状態の h(s) よりも小さくなることが挙げられる．この人工モデルのように条件を満たす問題では，副目標を破壊されていない状態がコミット メ
ントリストに残りやすい．ハノイの塔問題では副目標を保持している状態の h(s) は 保持し ていない状態よりも必ず小さくなり (maxf2M ; 1 2M ; 2g < minf2(M +1) ; 1 2(M + 1) ; 2g)，15 パズル 問題でも副目標を達成するほど ，残りのタイルが減るため h(s) の最大値は小さくなる．
また，副目標の保持の容易さには副目標を達成する経路の数も関係しており，経路の数が多いと副目標は達成

表 9. 初期値が全て等しい人工モデルにおける実験結果
アルゴ リズム
再展開数 展開数

RTA*
MSC-RTA*(n = 2)
MSC-RTA*(n = 3)
MSC-RTA*(n = 4)
MSC-RTA*(n = 5)

453.5 1161.6
182.5 775.2
145.4 728.7
127.0 713.7
115.8 708.1

しやすいが，保持は困難になり，この人工モデルのように経路の数が少ないと副目標を達成しにくい反面，保持は容易になる傾向がある．15 パズル問題では 副目標をは h(s) > 1 となるため， MSC-RTA*ではコミット メン
め，副目標の達成方法が多く，ハノイの塔問題では最大 トリストに未展開の状態がある限り再展開は起こらないの円盤をペグ 1 からペグ 3 へ，またはペグ 2 からペグ 3 へ からである．
達成するタイルの並びには何通りものパターンがあるた置くというわずか 2 通りの方法しか副目標を達成できな

最後に，図 7(c) に示される刈り込みが有効な人工モデのことは 15 パズル 問題と比べてハノイの塔問題で副目 ルを用いて MSC-WA*が WA*より小さな空間だけを探標を保持しやすいことの原因となっている．
索することを示す．この人工モデルにおいて，一番右のいため，副目標の達成方法は極端に少ないといえる．こ次に，MSC-RTA*が RTA*よりも状態を再展開しにく列の状態だけは h(s) がゴ ールまでのコストを正確に示い迷路問題を作成し，各状態の h(s) の初期値を全て 1 との列へ到達するまでど の経路も同等に望まし くみえる．

が目標状態に関する情報を全く示さないため，ランダム

だが，途中までは 全ての状態が同じ 評価値を持つため，な選択を繰り返して，隣接する状態が全て展開済みの状

刈り込みを行わなければ ，余分な空間を探索し てし ま

いことを示すための人工モデルとし て，障害物を含まな しているが，他の状態の h(s) は全て等しいため，一番右した (図 7(b))．この人工モデルではヒューリスティック どの経路を選んでも結局は同じ 展開数で解が得られるの況を作り，状態を再展開しやすい．大きさが 30

30 の人 う．大きさが 30 30 の人工モデルで 10,000 回試行し た工モデルで 10,000 回試行した結果を表 9 に示す．MSC- 結果を表 10 に示す．WA*は全ての経路を探索しようとRTA*は RTA*の 4 分の 1 しか再展開を行わず，RTA*よ するが，n = 1 とした MSC-WA*はいずれか 1 つの経路
り少ない展開数で解を得ることができた．これは未展開 のみ探索するため，結果として MSC-WA*は WA*の約の状態は全て h(s) = 1 だが，一度でも展開し た状態で 4 分の 1 しか状態を展開せずに解を得ることができた．

Start
2

2

2

1

1

1

2

2

2

1

1

1

2

2

2

1

1

1

2

2

2

1

1

1

2

2

2

1

1

1

2

2

2

1

1

1

Goal

(a) 副目標の達成と対応した h(s) を持つ人工モデル
Start
1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Goal

(b) h(s) の初期値が全て等しい人工モデル
Start
5

5

5

5

5

5

5

6

6

6

6

4

5

5

5

5

5

3

5

6

6

6

6

2

5

5

5

5

5

1

6

6

6

6

6

0

Goal

(c) 刈り込みが有効な人工モデル
図 7. 人工モデル

6 関連研究MSC-RTA*はマルチエージェント実時間 A*アルゴ リ

ズム 2] に確率的再配置を導入した探索アルゴ リズム 7]からヒントを得て考案された．そのため，これらも MSC-RTA*と同様に RTA*より副目標を保持し やすくなっており，直列化可能な副目標を持つ問題では非常に有効である．しかし ，複数のエージェントが同じ状態を展開することがあるため，MSC-RTA*より効率が悪い．

MSC-WA*と良く似た刈り込みを行う探索アルゴ リズ

ムにビ ーム探索 1] があり，MSC-WA*が有効な性質を持つ問題ではビーム探索も同じ く有効である．しかし ，

MSC-WA*は完全性が保証されているが，ビーム探索は完全性が保証されていないため，MSC-WA*では解くことができても，ビーム探索では解けない問題が存在する．

表 10. 刈り込みが有効な人工モデルにおける実験結果
アルゴ リズム
展開数 空間量MSC-WA*(n = 1)
MSC-WA*(n = 2)
MSC-WA*(n = 3)
MSC-WA*(n = 4)
MSC-WA*(n = 5)
WA*

58.0
83.9
110.4
134.0
156.4
224.2

72.5
99.5
127.3
152.5
176.5
248.8

7 むすび
15 パズル問題，ハノイの塔問題，迷路問題におけるMSCS の動作を調べることにより，MSCS が有効な問題の性質を明らかにした．人工モデル上のシミュレーショ

ン実験によって，MSC-RTA*が RTA*より副目標を保持しやすく，再展開の回数も少ないため，RTA*より少な
い展開数で解が得られることを示した．また，刈り込みが有効な人工モデルで WSC-WA*が WA*より少ない展
開数で解を得ることを示した．

参考文献

1] Bisiani, R. Beam search. In Shapiro, S. C., ed.,Encyclopedia of Articial Intelligence. New York:
Wiley-Interscience Publication. 1467{1468. 1992.
2] K.Knight. Are Many Reactive Agents Better Thana Few Deliberative Ones?. Proc. of IJCAI-93, 432{
437. 1993.
3] Korf，R. E. Real-time heuristic search. ArticialIntelligence, 42(2-3):189{211. 1990.
4] Korf, R. E. Liner-space best-rst search. ArticialIntelligence, 62(1):41{78. 1993.
5] J. Pearl. Heuristics. Addison Wesley. 1984.
6] 宮地 智久, 北村 泰彦, 横尾 真, 辰巳 昭治. ヒュー
リスティック探索への n-状態コミット メントの導入.
信学技報, AI97-58. 1998.
7] 横尾 真, 北村 泰彦. 淘汰を用いたマルチエージェン
ト実時間探索の高速化:協調探索への競争の導入. コ
ンピュータソフトウェア, 14(4):47{55. 1997.