1

Technical Papers

論 文

多状態コミット メント探索とその評価
Multi-State Commitment Search and Its Evaluation
北村 泰彦 1
Yasuhiko Kitamura

横尾真 2
Makoto Yokoo

宮地 智久 1,yTomohisa Miyaji

辰巳 昭治 1
Shoji Tatsumi

 1 大阪市立大学工学部情報工学科
Dept. of Information and Communication Engineering, Faculty of Engineering, Osaka City University, Osaka 5588585, Japan.

コミュニケーション科学研究所
 2 NTTNTT Communication Science Laboratories, Kyoto 619-0237, Japan.

19YY 年 MM 月 DD 日 受理

Keywords: heuristic search, RTA*, weighted A*, commitment
Summary

We propose the Multi-State Commitment (MSC) method to speed up heuristic search algorithms
for semi-optimal solutions. The Real-Time A* (RTA*) and the Weighted A* (WA*) are representative
heuristic search algorithms for semi-optimal solutions and can be viewed as a single-state and an allstate commitment search algorithms respectively. In these algorithms, there is a tradeo between therisk of making wrong choices in search process and the amount of memory for the recovery, with RTA*
and WA* being the extremes. The MSC method introduces a moderate and exible characteristic into
these algorithms and can increase the performance dramatically in problems such as the N-puzzle. In
this paper, by introducing a commitment list, we show a modi cation of RTA* and WA* to their MSC
versions without violating their completeness. Then, we experiment with their performance in mazeand N-puzzle problems, and discuss conditions that the MSC method is e ective.

最適解を得ることが望ましい場合も多い．そのような
1.

ま

え が

き

ヒューリスティック探索アルゴ リズムとし ては，重み付き A*(Weighted A*:WA*)[Korf 93] アルゴ リズムや人工知能における問題解決は，一般に状態空間グラ

実時間 A*(Real-Time A*:RTA*) アルゴ リズム [Korfのサイズが大きくなると単純な探索手法では現実的な90] がある．
WA*と RTA*では展開する状態を選択する手法に特徴的な違いがある．WA*は探索木の最前線にある全ての状態を展開候補とし て記憶しているが，RTA*は先時間内に解を求めることが困難になる．そこで問題にに展開した状態の子状態のみに展開候補を絞り込んでフにおける初期状態から目標状態までの解経路を発見することとし て定式化することができ，その問題解決手法とし て探索がある．しかしながら状態空間グラフ

関するヒューリスティックな知識を状態評価関数としいる．RTA*はヒューリスティック探索におけるコミッて用いることによって性能を改善するヒューリスティッ

ト メントという視点からは，その後の探索の可能性をク探索アルゴ リズムが提案され，その代表的なものに次に展開する単一の状態からの子孫に限定するという

A*アルゴ リズムがある [Pearl 84]．
A*アルゴ リズムは最適解を発見することを保証す

なすことができる．一方，WA*は探索の可能性を一切るが，実用的な探索アルゴ リズムとしては，時間をか限定していないので，全状態コミット メント 探索アル

けて最適解を得ることよりも，許容可能な時間内に準y 現在，住友電気工業（株）
Sept. 1999

意味で単一状態コミット メント探索アルゴ リズムと見ゴ リズムと見なすことができる．1* 1 全ての状態にコミットすることは，どの状態にもコミッ

多状態コミット メント探索とその評価

1

2
準最適解探索は一般に，展開する状態を一つ以上の状態といい，それを得ることを生成するという．また候補の中から選択する判断を繰返し 行なうが，選択の状態 s の全ての子状態を得ることを状態 s を展開する

誤りは目標状態までの探索ステップを長くしてし まうという．

後の探索の可能性を単一の状態の子孫に絞り込んでしは，状態 s，s0 間の遷移のコストを c(s; s0 ) で表す．オ

まうアルゴ リズムでは，その判断を誤った場合におけるペレ ータの連続的な適用により得られ る状態の系列は

悪影響は大きい．一方，選択を誤った場合における回復経路と呼ばれ，初期状態から目標状態への経路を解（経とい う悪影響を及ぼ す．したが って RTA*のように以を容易にするためには WA* のように可能な候補を全

オペレ ータの適用にコスト (> 0) が定義され る場合路）と呼ぶ．解を構成するオペレ ータのコストの和をてオープンリストとして保存しておくという方法もあ

解のコストとする．ある解が存在するとき，それよりる．しかしこの方法では探索の範囲が広くなりすぎても小さいコストをもつ解が存在しなければ，その解を計算機の記憶領域をすぐに消費してし まい，実質的に最適解と呼ぶ．

解が得られないという問題がある．このように探索における選択誤りのリスクと回復のための記憶量の間にはトレード オフの関係があり，そのそれぞれの両極端が単一状態コミット メント 探索アルゴ リズムの RTA*と，全状態コミット メント探索アルゴ リズムの WA*でヒューリスティック探索では，各状態 s(標状態までのコストの推測値が与えられており，ヒュー
リスティック関数 h(s) で表される．とくにこの推測値

が 実際の値を上回らない場合，そのヒューリスティッ
ク関数は適格 (admissible) であるといわれ る．

あるといえる．
本論文では単一状態コミット メントと全状態コミッ

ト メントの中間的なものとし てパラメータ n をもつ多WA*アルゴリズ ムへの多状態コミット

3.

メント の導入

状態コミット メント 探索アルゴ リズムを提案する．これは選択誤りリスクと回復に必要な記憶量のバランス

2 S ) から目

3・1

WA*アルゴリズム

ついて述べる．また同時にこの拡張を加えたとしても，

A*アルゴ リズムは状態 s の評価に初期状態から状態
s までのコストの推測値 g(s) と，状態 s から目標状態
までのコ ストの推測値 h(s) の和を用いるが ，WA*はg(s) と h(s) の比重を変化させたもので，状態 s の評価には (1 , W )g(s)+ Wh(s) を用いる．ただし W (2 R)
は 0  W  1 である．一般に W の値が大きいほど 解

もとのアルゴ リズムのもつ，解を発見し 停止するといを早く発見することができるが，逆にその質は悪くな

う完全性が損なわれないことも示す．そして，多状態る．本稿では準最適解発見の高速化に興味があるので，を柔軟にとることができ，うまく n の値を調整すれば，N-パズルのような問題に対しては極めて効果的である

ことを示す．本論文では以下，ヒューリスティック探索の定式化を行なった後，WA*と RTA*アルゴ リズムの多状態コミット メント探索アルゴ リズムへの拡張法にコミット メント手法の効果を示すため，迷路と N-パズ

ルを用いたシミュレーション実験を行ない，N-パズル

に関しては劇的な性能向上が見られることを示す．最

以下では W = 1 の場合を議論する．

WA*は A*と同じく OPEN，CLOSED と呼ばれる 2つのリストを用いる．生成された状態は一旦 OPEN に

後に，多状態コミット メント 探索が有効な問題に関す保存され ，また展開された状態は CLOSED に 移される考察と関連研究を示す．

るため，一度生成された状態は必ずいずれかのリストに存在する．従って，それらのリストをチェックする

2.

ことで WA*は状態の再生成を避けている．2

ヒューリスティック探索の定式化

問題は四つ組 hS; O; s0 ; Gi で表される．ここで S (6=) は状態の集合，O は状態遷移を示すオペレ ータの集合，s0 (2 S ) は初期状態，G( S ) は目標状態の集合である．ここで組 hS; Oi で定義され るグ ラフを状
態空間グラフと 呼ぶ．ある状態 s(2 S ) に オペレ ータ
o = (s;s0 )(2 O) を適用して得られる状態 s0 を s の 子
トしていないこととも等価であるので，このアルゴ リズム
を無状態コミット メント探索アルゴ リズムと見なすこともできる．

2

WA*アルゴ リズムを図 1に示す．まず初期状態から探索を開始する (1 行目)．状態を展開し，子状態を生成する (2 行目)．ただし ，OPEN あるいは CLOSED に入っている状態は生成しない．生成した状態に目標状態が含まれていれば探索は成功で終了である (3 行目)．

そうでなければ ，生成し た状態を OPEN に 加え (4 行

* 2 解の質を考慮する場合は状態の評価値が前のものよりもよければ状態を再生成する（ CLOSED から OPEN に移= 1 の場合を扱い，動する ）ことがあるが，ここでは( )(= ( )) の値は固定されているので，そのような操作は行なわれない．

fs

人工知能学会誌

hsW

Vol.14 No.5

3
WA*
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: add(OPEN; successors(s));
5: add(CLOSED; s);6: if OPEN =  then return failure;
7: s get min(OPEN );8: goto 2;
図1

WA*アルゴ リズム

MSC-WA*
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: add(COMMITMENT; successors(s));
5: add(CLOSED; s);
6: while length(COMMITMENT ) > n do
7:s get max(COMMITMENT );8:
add(OPEN; s);
9: while (length(COMMITMENT ) < n) and
10:(OPEN 6= ) do
11: s get min(OPEN );12: add(COMMITMENT; s);13: if (COMMITMENT = ) then return failure;
14: s get min(COMMITMENT );15: goto 2;
図2

MSC-WA*アルゴ リズム

MSC-WA*において子状態は COMMITMENT，
OPEN， CLOSED に 含まれ ないもののみを生成す
る (2 行目)．また，生成し た状態は OPEN ではなく，
COMMITMENT に 加 え る (4 行 目)．展 開し た 状 態
は WA*と同様に CLOSED に加える (5 行目)．COMMITMENT が長さの上限を越えていれば，評価値が最大の状態から OPEN に移し 変える (6-8 行目)．COMMITMENT に空きがあれば ，COMMITMENT の上限まで OPEN から最小の評価値を持つ状態を移し変える (9-12 行目)．COMMITMENT が空ならば探索は失敗に終る (13 行目)．そして，次に展開を行う状態として COMMITMENT の中から評価値最小の状態を選択する (14 行目)．なお，複数の状態の評価値が同じときはその中からランダムに選択する．

MSC-WA*は n = 1 のときに，もとの WA*と等しくなる．

3・3 アルゴリズムの性質

まず，WA*に多状態コミット メントを導入しても完全性が保たれていることを示す．なお，この場合の完全性とは，初期状態から目標状態に至る経路が存在す
るとき，アルゴ リズムが必ず解を得て停止することで目)，展開した状態を CLOSED に 加える (5 行目)．もある．

うでなければ，OPEN の中で最小の評価値 h(s) を持つ

存在し ，状態空間グラフが有限であるときに保証されし OPEN が空であれば探索は失敗であり (6 行目)，そ状態 s を取り出し (7 行目)，探索を続ける (8 行目)．この一連の動作を 1 ステップと定義する．

3・2

WA*の完全性は，初期状態から目標状態への経路がている．これは WA*は一度展開した状態を再展開しな
いため無限ループに陥ることがなく，また，アルゴリズ
ムが停止する以前では解経路上の状態が少なくとも一MSC-WA*アルゴリズム

WA*は OPEN に保存された状態から次に展開するもつは OPEN に保存されているからである [Shirai 82]．

MSC-WA*も同様に，状態を再展開することがないののを選択する全状態コミット メント探索アルゴ リズムでで無限ループには陥らず必ず停止する．失敗で終了する

択すべき候補を n 状態に限定する．そのために，COM-

この場合には 9-12 行 目の操作により OPEN もともにある．多状態コミット メント WA*(MSC-WA*) では選

MITMENT と呼ばれる新たなリストを導入し，生成された状態は OPEN ではなく COMMITMENT に追加

する．そして，COMMITMENT から次に展開を行う
状態を選択する．COMMITMENT の長さは n 以下に制限され，上限を越えた場合は評価値の悪いものからOPEN に移し変える．また，COMMITMENT の長さが n 未満になった場合は，OPEN から評価値の良いものを移し変える．なお，CLOSED に関する扱いは WA*と同様である．従って，MSC-WA*においても一度生成した状態は COMMITMENT, OPEN, CLOSED のいずれかに 必ず存在する．MSC-WA*のアルゴ リズムを図 2に示す．
Sept. 1999のは COMMITMENT が空の場合 (13 行目) であるが，空になっているはずである．しかし解経路上の状態は少なくとも一つは COMMITMENT あるいは OPEN に存在するので，失敗で終了することはない．以上より，初期状態から目標状態への経路が存在し，状態空間グ

ラフが有限ならば，MSC-WA*の完全性は保証される．
次に MSC-WA*で得られる解の最適性について説明を加えよ う．先述したよ うに WA* は状態 s の評価値

, W )g(s) + Wh(s) を用いており，h(s) が適格で，0  W  1=2 の場合には最適解を得ることが 保証され る．また 1=2 < W  1 の場合には最適とし て (1解のコストを C  とし た時，得られる解のコスト C はC   C  C  (1+ ") となることが保証される．ここで多状態コミット メント探索とその評価

3

4
RTA*
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: update h(s);5: if successors(s) =  then return failure;
6: s get min(successors(s));
7: goto 2;
図3

MSC-RTA*
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: update h(s);5: add(COMMITMENT; successors(s));
6: while length(COMMITMENT ) > n do
7:
remove max(COMMITMENT );8: if COMMITMENT =  then return failure;
9: s get min(COMMITMENT );10: goto 2;

RTA*アルゴ リズム" = W=(1,W ),1 である．3しかしながら MSC-WA*

図4

MSC-RTA*アルゴ リズム

では展開候補は OPEN リストと COMMITMENT リ
ストに分断されてし まい，n =1 の場合を除いて，評

価値最小の状態が展開の対象となる COMMITMENTの評価値 h(s0 )(s02 successors(s)) を持つ状態を次にリストに含まれるという保証がないので，解のコスト展開する (6,7 行目)．なお，複数の状態の評価値が同じの保証もない．

ときはその中からランダムに選択する．

4.

RTA*アルゴリズムへの多状態コミット
メント の導入

4・2

MSC-RTA*アルゴリズム

RTA*は展開された状態の子孫のみが以後の探索に影響を与える単一状態コミット メント 探索アルゴ リズ
ムである．ここでは，RTA*に多状態コミット メント

RTA*アルゴリズ ム

4・1

Korf の提案した RTA*[Korf 90] は先読み探索と移動を交互に行なう準最適解探索アルゴリズムである．4 先の概念を導入することにより，コミット メントの範囲を広げる．すなわち，MSC-WA*と同様に COMMIT-

読み深さを大きくすれば 解の質を改善することができ

MENT リストを導入し，生成した状態をそのリストにるが，ここでは解発見の高速化に焦点をあて，その深保存する．そして，そこから次に展開を行う状態を選を保証するために，RTA*では CLOSED リストを用いそれを越えた場合は評価値の悪いものから取り除く．多リズムを図 3に示す．

態を再展開する意味がないので，

RTA*: MSC-RTA*) アルゴ リズムを図 4に示す．
RTA*アルゴ リズムと比較すると，図 3の 5,6 行目が図 4の 5-8 行目に変更されている．すなわち，生成した状
態は一旦 COMMITMENT に加えられる (5 行目)．ただし，COMMITMENT 内で同じ状態の重複は許さない．COMMITMENT の長さが 上限を越えていれば ，
評価値 h(s) が 大きいものから削除する (6,7 行目)．もし COMMITMENT が空ならば，探索は失敗に終る (8行目)．次に展開する状態は COMMITMENT に 保存されているものから評価値が最小のものを選択する (9行目)．なお，COMMITMENT から状態を取り出す

評価値が際，同じ評価値のものがあればランダ ムに選択する．

さは 1 の場合のみを扱う．またアルゴ リズムの完全性ず，探索しながら評価値を更新してゆく．RTA*アルゴ

まず初期状態から探索を開始する (1 行目)．そして子状態の全てを生成する (2 行目)．ただし ，子状態 s0 (2

successors(s)) の評価値が無限大 (h(s0 ) = 1) の場合，その状態より先に探索を進めても目標状態へ到達することはないので，生成状態に含めない．生成した状態に目標状態が含まれていれば探索は成功である (3 行目)．

目標状態が含まれていなければ ，h(s) を子状態の中で2 番目に小さい c(s; s0 )+ h(s0)(s0 2 successors(s)) に更新する (4 行目)．子状態の数が 1 個以下ならばその状

1 に更新する．もし
1 でない子状態が存在しなければ探索は失敗である (5 行目)．そうでなければ ，子状態の中で最小

W

"

1

*3
= 1 の場合は = となり得られる解のコストの保証はない．
* 4 RTA*アルゴリズムには二つの解釈がある．一つの解釈
は RTA*が 準最適解を求めるためのオフラインアルゴリズ
ムで，もう一つの解釈はプランニングと行動を交互に実行
するエージェントのためのオンラインアルゴ リズムである
とい うものである．本論文では前者の解釈をとっており，
多状態コミット メントの導入によりその性能を改善し ようとし ている．

4

択する．COMMITMENT の長さは n 以下に制限され，状態コミット メント RTA*(Multi-State Commitment

MSC-RTA*は n = 1 のとき，もとの RTA*と等しくなる．

4・3 アルゴリズムの性質

RTA*の完全性は初期状態から到達可能な全ての状
態から目標状態に到達可能，評価値の初期値が有限，状態空間が有限の場合に保証されている [Korf 90]．

以下では， RTA*を多状態コミット メント RTA*に人工知能学会誌

Vol.14 No.5

5
RTA*と同じ く，各状態に対する評価値の初期値が有限であり，初期状態から目標状態に至る経路は存在するので，評価値が無限大となる状態が目標状態を取り囲んでアルゴ リズムが目標状態まで到達できずに 失敗で終了することはない．
また，以下の理由によりアルゴ リズムは無限ループに陥ることもない．もしアルゴ リズムが無限ループに

MSC-WA*の迷路における実験結果

表1

変更しても，完全性が保たれていることを示す．まず，アルゴ リズム

成功率

ステップ数

MSC-WA*(1)MSC-WA*(2)MSC-WA*(3)MSC-WA*(4)MSC-WA*(5)MSC-WA*(6)
WA*

100
100
100
100
100
100
100

1233.41228.81223.21232.6
1231.11223.21229.9MSC-WA*の 48-パズル問題における実験結果陥っているとすれば，そこには当然のことながら目標状

表2

態は含まれない．展開された状態の評価値は子状態のアルゴ リズム

評価値と非負のオペレ ータのコストの和の 2 番目に良いものに更新されるため，更新された評価値は子状態の評価値の最小のものよりも必ず大きい．よって，ループ内の状態の最小の評価値は一巡する毎に確実に増加する．したが ってループに含まれる状態の最小の評価

MSC-WA* (1)MSC-WA* (2)MSC-WA* (3)MSC-WA* (4)MSC-WA* (5)MSC-WA* (6)WA*

値は，いずれそれに含まれない状態の評価値よりも大

表3きくなり，ループから抜け出すことになる．状態の数は有限であるので，いずれ目標状態にも到達する．この性質は n に依存しない．ゆえに，MSC-RTA*の完全性は保証される．

次に，MSC-RTA*で得られる解の最適性に関して述べる．RTA*アルゴ リズムは初期状態からの状態 s へのコストを示す g(s) を考慮しておらず，解のコストの保迷路は入口 (0,0)，出口 (119,119) とする 120 120の格子状グラフにおいて入口から出口への経路を求める問題である．グラフ内には通過することのできない

障害物が 40%の割合でランダ ムに配置されている．各

370374.0
190507.0
134848.0120051.0133266.0
157416.0
189241.9

ステップ 数RTA*
MSC-RTA*(2)MSC-RTA*(3)MSC-RTA*(4)MSC-RTA*(5)MSC-RTA*(6)

100
100
100
100
100
100

7413.17852.97918.58005.18108.28104.4

アルゴリズム験をおこなった．用いた問題は迷路と N-パズルである．

ステップ 数成功率

表4

多状態コミット メント手法の性能を評価するための実

38
97
98
100
96
99
10

解の長さ

9495.09470.710180.711138.1
11584.811622.1
3151.0MSC-RTA*の迷路における実験結果

適性は保証されない．

性能評価実験

成功率

アルゴ リズム

証はない．したがって，MSC-RTA*においても解の最

5.

解の長さ

(最適解との比 )383.2 (1.24)
374.1 (1.21)
373.6 (1.21)
373.8 (1.21)
373.3 (1.21)
373.3 (1.20)
373.5 (1.21)解の長さ(最適解との比)
363.5 (1.18)
359.1 (1.16)
358.5 (1.16)
358.3 (1.16)
358.1 (1.16)
358.2 (1.16)

MSC-RTA*の 48-パズル問題における実験結果

RTA*
MSC-RTA* (2)MSC-RTA* (3)MSC-RTA* (4)MSC-RTA* (5)MSC-RTA* (6)

成功率

2
100
100
100
100
100

ステップ 数解の長さ393439.0 228849.0
155770.0 44569.0
93822.0 23426.0
120640.0 21231.0
181778.0 24243.0
210497.0 24512.0と初期配置の異なる 48-パズルをそれぞれ 100 個用意した．これらの問題はランダムに生成させたものである
が，すべて解を持つものである．そしてコミット メン

状態の評価値としては目標状態とのマンハッタン距離

トリストの長さ n を変化させ，アルゴリズム毎に各 100を用い，上下左右に移動する各オペレータのコストは回試行した．なお，実験に使用する計算機には利用可

1 とした．
また N-パズルとして 48-パズルを用いた．これは 77の盤面に 1 か ら 48 までの番号のついたタイルと一つの能な記憶量に限界があるため，各リストに含まれる状
態数の和が 150 万を越えた場合，探索は失敗とし て中断している．

しく並ぶ目標状態へとタイルをスライド させてゆく問MSC-WA*の実験結果を表 1（ 迷路），表 2（ 48-パズル），MSC-RTA*の実験結果を表 3（ 迷路），表 4（ 48-

題である．オペレ ータには空白の位置を上下左右のそパズル ）にそれぞれ示す．ここでアルゴ リズム名にお空白があり，タイルをランダ ムな状態から，番号が正れぞれに移動させる 4 つのものがあり，それぞれのコ

ける括弧内の数字は n である．成功率は記憶量の制限

スト 1 とする．各状態の評価値とし ては各タイルの正によることなく解を得た試行の割合である．ステップ

しい位置とのマンハッタン距離の総和を用いた．

数，解の長さはそれぞれ成功したものの平均である．

シミュレーション実験には障害物配置の異なる迷路
Sept. 1999

迷路では MSC-WA*，MSC-RTA*ともに n に関わり

多状態コミット メント探索とその評価

5

6
なく性能にほとんど 変化がなかった．一方，48-パズル

s0

ではともに劇的な性能改善が得られた．WA*はわずか

1 割の問題でしか解を得ることができなかったのに対し，n = 4 としたときの MSC-WA*は全ての問題で解を得ることができた．この実験からわかることは n = 4

s1

s2

SG(s2)の時が最良の結果を得ており，それよりも大きくてもSG(s1)

小さくても性能は悪化する．解の長さに関しては WA*が極端に良いように見えるが，これは解の短いものしか発見できないからである．

また RTA*ではわずか 2%の問題しか解決できなかっsGたのに対し ，n = 2 から n = 6 の MSC-RTA*では全図5て解を発見している．また n = 3 とし たときステップ

探索グラフ

数が最小となり，n はそれより大きくても小さくても性能が悪化する．

N-パズルに 関してはサイズの異なる N = 24; 35; 63など の問題を用いた実験を行なったが同様の結果を得ており，この性能改善は N-パズルにおける一般的性質といえる．

さて，3，4 節において MSC-WA*， MSC-RTA*がともに解のコストに関してその保証を行うことができないことを指摘したが，実際に最適解とど の程度の違いがあるのかを示しておこう．迷路に関しては容易に最適解を求めることが でき，表 1，表 3に 示すように

MSC-WA*で 1.21 倍，MSC-RTA*で 1.16 倍ほど 大きなコストの解が得られた．

48-パズルでは最適解を求めることは現在の計算機の能力では不可能である．そこで文献 [Korf 88b] で示されている 100 個の 15-パズル問題とその最適解を用いてその評価を行った．その結果，RTA*で最適解の 20.16 倍，
n = 6 の場合の MSC-RTA*で 6.56 倍であった．またWA*では 3.90 倍，n = 6 の場合の MSC-WA*で 8.00倍であった．

6・1 選択の誤りと回復
ここで多状態コミット メント探索がどのような問題に対して有効かを図 5に示すグラフを用いて説明する．このグラフは状態 s0 をもち，s0 は二つの子状態 s1 と s2を持つ．またそれぞれの子状態から部分グラフ SG(s1 )，SG(s2 ) の探索が開始される．ここで SG(s1 ) を経て目標状態 sG に至るには多くの時間を要すが，SG(s2 ) を経て目標状態に至るには短時間ですむと仮定する．また s1 と s2 に関する評価値は h(s1 ) < h(s2 ) の関係にあり，誤った選択を引き起こすとする．
このような問題において，単一状態コミット メント

探索アルゴ リズムは以下のように振舞う．探索は s0 から開始され，その子状態 s1 と s2 が生成される．ここで誤った評価値のために s1 が選択され，SG(s1 ) が開始されるので，目標状態に至るまで多くの時間を費やすことになる．一方で多状態コミット メント探索アルゴ リズ
ムは以下のように振舞う．単一状態コミット メントと同様に探索は s0 から開始され，その子状態 s1 と s2 が生成される．また誤った評価値のために s1 が選択される．

しかし多状態コミット メントでは s2 も他の選択肢とし
6.

考て COMMITMENT に保存される．そして SG(s1 ) の察

探索中に h(s2 ) の値がいずれ COMMITMENT の中で実験では多状態コミット メント探索は N-パズルにおいて劇的な性能改善を示すことを明らかにし た．また性能を最適にする n の値が存在することも示した．一方で迷路においてはほとんど 性能に違いが見られなかった．本節では以下の疑問に関して考察を加える．

 なぜ多状態コミット メントは N-パズルに対して効果的であったのに，迷路ではそうでなかったのか？

 N-パズルではなぜこれほど の性能改善がなされたのか ?

6最小となり，アルゴ リズムは SG(s1 ) の探索を中断し ，s2 から探索を再開し，目標状態に至る．このように多状態コミット メントは SG(s1 ) の探索を中断できるな

らば，単一状態コミット メントよりも良い性能を示すことが できる．すなわち s2 が COMMITMENT に保存され，SG(s1 ) の探索で多くの時間を浪費するまでに

h(s2 ) の値が最小になればよい．一般に，n が大きいほど s2 が保存される確率は増加する．

一方で，多状態コミット メントは以下の場合において副作用が生じ ることがある．今度は SG(s1 ) のサイ

人工知能学会誌

Vol.14 No.5

7
ズが SG(s2 ) のサ イズより小さい場合を仮定する．単一状態コミット メントの場合は SG(s1 ) の探索を開始

し，そのまま目標状態に至る．しかし多状態コミット

メントでは SG(s1 ) の探索を中断し，SG(s2 ) の探索を開始することで，探索ステップを逆に増大させてし まう可能性がある．

さらに s1 と s2 以外にもその評価値が 同じような選択肢が多数存在するような場合を想定してみよう．このとき n の値が大きいと，冗長な探索となるような選択肢の多くが COMMITMENT に保存され，それらが図6選択されると，全体的な探索ステップ数を大きく増加

迷路とその評価値

させてし まうことが 考えられ る．これは n が 大きすぎる場合のステップ数増加の原因であり，また全状態コ
ミット メントの問題点も説明している．
以上の議論から多状態コミット メントは単一状態コ
ミット メントに比較して，評価値が誤った選択を引き起こす可能性を含んでおり (条件 1)，探索を途中で中断できる (条件 2) ならより良い性能を示す．それではこれらの条件が評価実験で用いた迷路と N-パズルにおいて満たされているかど うかを調べてみることにしよう．
図 6は迷路の一例である．迷路のサイズは 6 6 で，

初期状態は (0,0)，目標状態は (5,5) である．また評価値として目標状態までのマンハッタン距離を用い，そ

図7

15-パズルとその評価値の一部の値はそれぞれのマスの中に記入されている．この評価値は条件 1 を満たしている．すなわち初期状態 (0,0)の子状態には s1 と s2 にそれぞれ該当する (1,0) と (0,1)

ト メントはいずれ COMMITMENT から s2 を選択し，選択である．ところが (0,1) と (1,0) の評価値はともにを発揮する．一方で，図 7で示すように，N-パズルではが存在し，状態 (0,1) を選択することが明らかに正しい

9 であり，誤った選択を引き起こす可能性がある．
しかし，この評価値は条件 2 を満たしていない．すなわ ち (0,1)(= s2 ) の 評 価 値は図 6に も 示 すよ うに
SG(s1 ) 内のいずれの状態の評価値を下回るものではない ．し たがって s2 は n の値をいかに大きくし てもSG(s1 ) の探索中に COMMITMENT リストの中から選択されることはなく，このような性質をもつ迷路問
題では多状態コミット メントはその性能を発揮するこSG(s1 ) から s2 に復帰するので，N-パズルでは効果的同じ評価値を持つ多数の状態が存在するので，大きなn をもつ多状態コミット メントや全状態コミット メン

トは探索範囲が広がりすぎ，探索に時間がかかったり，
目標状態に到達する前に記憶領域を消費してし まう．

6・2 直列化可能な副目標

多状態コミット メントは N-パズルにおいて劇的な性能改善を示した．図 5に示されるように，多状態コミッとができない．

ト メントと単一状態コミット メントの性能差は SG(s1 )ルにおける状態空間グラフの一部を示したものである．

が SG(s1 ) の探索をなか なか抜け出すことができない

次に，図 7は初期状態 A，目標状態 G である 15-パズ

この評価値も条件 1 を満たし ている．すなわち初期状
態 A の子状態 B,C,D,E の評価値がみな同じ 値 (10) であり，どの選択が望ましいかを区別することができな

い．この場合，次節で述べるように B は誤った選択肢
である．そしてこの評価値は条件 2 も満たしている．すなわ ち s1 に該当する B の子状態の評価値は s2 に該当する C のそれよりも大きい．したが って多状態コミッ
Sept. 1999のサイズに依存する．つまり単一状態コミット メントのに対し，多状態コミット メントは早い段階でそこから抜け出すことができるからである．

N-パズ ルに お い て 誤った 選 択が 大き な 性 能 差を
生 むことは 以下のよ うな直 列化可能な副 目標 [Korf 88a],[Newell 72] の概念を導入することにより説明され る．直列化可能な副目標とは , 目標が複数の副目標に分割され , かつある順番で副目標を順に達成する

多状態コミット メント探索とその評価

7

8
場合, 以前の副目標を破壊せずに以降の副目標を達成

表5することが可能であることをいう [Korf 88a]. 例えば ，

24-パズルにおいて副目標レベルを減少させる平均ステッ
プ数
アルゴ リズム

15-パズルでは , 最初に一番下の並びのタイルを正しい位置に並べると, それ以降はこれらのタイルを動かすことなしに目標状態に到達可能である. さらに 一番右の並びのタイルを正しい位置に並べると, これらのタイルを動かすことなしに目標状態に到達可能であり, 残りの問題は 8-パズルと等価となる. 図 8に示すように状態は副目標の達成の度合に応じてレベル付けをすることができる．

したがって N-パズルの探索では達成された副目標を壊さないよ うに状態を選択してゆくことが 望まし い．

RTA*
MSC-RTA*(2)MSC-RTA*(3)MSC-RTA*(4)MSC-RTA*(5)MSC-RTA*(6)ステップ 数

97.9
223.0
665.3
1327.31972.42719.3

れている状態の中から，いずれそうでない選択肢に回復することができる．これは n を大きくすればするほど その効果が発揮されることを示している．しかしながら表 2と表 4が示すように n を大きくしすぎ ると性能

ところが異なるタイル間のマンハッタン距離の和に基は悪化する．これは 6.1 節の最後にも述べたように探の初期状態はすでに level2 の副目標が達成されており，レベルを減少させにくくすることは，逆にそれを増加づく評価値はこのよ うな性質を反映していない．図 7
状態 B の選択はそれを破壊することになる．しかしな

がら評価値は 4 つの子状態が全て同じ 値であり，それ索範囲が広がりすぎ ることによるものであり，副目標
させに くくもするという副作用が生じ ることを示している．

を見分けることができない．そして一旦副目標を破壊するとその回復は容易でないので，状態 B の選択は探索性能の悪化につながることが予想される．一方，多状態コミット メントの場合には COMMITMENT リス

トから他の選択肢に復帰することができるので，B の

7.

関

連

研 究

誤った選択に対する頑健性を向上させる方法として,複数の問題解決器 (エージェント ) により, 並行して問選択は致命的ではない．

題を解く, 協調探索と呼ばれる手法が提案されている.

標の破壊の様子を表 5に示す．多状態コミット メントア

め, いずれかのエージェントが正しい選択をすれば 問以上の議論を確認するために 24-パズルにおける副目

ルゴ リズムにおける副目標レベルを COMMITMENT
リストにおける最大のものと定義する．厳密には，時刻 T におけるアルゴ リズムの副目標レベル SLT は

SLT = maxs2COMMITMENTT SL(s)で定義され る．ここで， COMMITMENTT は時刻 T

における COMMITMENT リスト，SL(s) は状態 s の副目標レベルを表している．n > 1 の場合，この SLT

は時刻 T において展開される状態の副目標レベルとは必ずしも等しくないことに注意していただきたい．アル

ゴリズムの副目標レベルが減少することは COMMIT-

MENT リストによる回復が無効になるほど致命的な選択誤りを行ったことを意味している．表 5に示した「副目標レベルを減少させる平均ステップ数」は探索ステッ

協調探索においては複数のエージェントが存在するた題を効率的に 解くことが でき る. これ までに 制約充

足問題 [Clearwater 91, Hogg 93] や状態空間探索問題[Knight 93, Kitamura 96] に対する適用例が報告されている. 協調探索の一つの問題点は , 重大な選択肢が連続して生じる場合, 探索の初期で誤った選択をしたエー
ジェントはその後の探索に全く貢献しないことである.
文献 [Yokoo 97] は , 複数のエージェントが RTA*アルゴ リズムを並行して実行するマルチエージェント 実時
間 A*アルゴ リズム (Multiagent RTA*: MRTA*) において, 遺伝的アルゴ リズムの淘汰に似た方法を用いて, エージェントを再配置することにより, N-パズル
において劇的な性能改善が可能であることを示している. 本研究は文献 [Yokoo 97] に触発されたものであり ,より単純なアルゴ リズムで , 同様な性能向上が可能でプ数を副目標レベルを減少させた回数で割ることで計あることを示している. また, MRTA*では複数のエー

算され，アルゴ リズムが致命的な選択誤りを行う頻度

ジェントが同一の状態を展開し，冗長な探索を行なうを表している．

可能性が高くなるという問題点があったが，本研究はする頻度が少なくなるということである．すなわちア点は解消されている．例えば ，[Yokoo 97] に おいて，

表 5からわかることは，n が大きければ副目標を破壊

ルゴ リズムが一時的に副目標を破壊するような状態を選択したとしても，COMMITMENT リストに保存さ
8

単一エージェントによる探索であり, そのような問題

MRTA*アルゴ リズムでは 5 エ ージェントが並行処理
して 48-パズルを解くのに平均 35452.7 ステップを要す

人工知能学会誌

Vol.14 No.5

9
3

3

12 13 14 15711
12 13 14 157
8 9 10 11
12 13 14 152 3
6 7
8 9 10 11
12 13 14 15

level 1level 2level 3level 4

図8

副目標の達成ることが報告されている．
（ 全エージェントのステップ

る指針を与えるべきであると考えている．さらに 探索）一方 n = 3 とし た場合の数の和は 177263.5 となる．

の過程で動的に n の値を調整するような手法も興味あ

探索の対象を絞 る古典的な方法とし てビ ーム探索

は解のコストに関する保証がないことを示したが ，こMSC-RTA*は 93822.0 ステップですんでいる．

[Bisiani 92] がある. 従来のビ ーム探索は探索範囲以外のものは完全に切り捨てているため , アルゴ リズムの完全性が保証されないが , 本研究で提案する複数状
態コミット メントの拡張においては, 元のアルゴ リズ
ム (RTA*, WA*) の完全性は保存されている.
探索の対象を限定するもう一つの方法として, Limited Discrepancy Search [Harvey 95, Korf 96] がある. これは, 深さ優先探索をベースとし て, ヒューリス
ティック関数を用いて探索範囲を段階的に広げていく
方法であり, 深さの上限があらかじめ分かっていない

状態空間探索問題よりも , 探索木の深さの上限が自明である制約充足問題等に適している.

A*に おいて, 有望でない状態を OPEN から取り除き, 必要とされる記憶領域を削減するアルゴリズムとして SMA*[Russel 92] がある. 本論文で提案するコミッ

ト メントの拡張は , このような記憶領域を制限する方法と排反ではなく , SMA* と組み合わせて用いることも可能である.
8.

む

す

び

本研究では，探索の範囲を制限する多状態コミット

メントの概念を WA*と RTA*の二つの準最適解探索ア

ルゴ リズムに導入した．そして迷路，N-パズルを用いて実験評価を行い N-パズルでは劇的に性能が改善されることを示した．また本手法がどのような問題に対して効果的であるかに 関する条件を示し，直列化可能な
副目標の視点から N-パズルがそれを満たしていることを示した．
今後の課題としてはさらに別の種類の問題に適用し，本手法の有効性を示すことである．とくに与えられた問題に応じて n の値をど のように調整すべきかに関すSept. 1999

る課題である．また本論文で提案したアルゴ リズムでれを保証するような仕組みをアルゴ リズムに組み込むことも今後の課題となっている．
謝

辞本研究に関して有益なコメントをいただいた京都大学大学院情報学研究科石田亨教授と査読者に感謝の意を表し ます．

◇ 参

考

文 献 ◇

[Bisiani 92] Bisiani, R.: Beam search, In Shapiro, S. C.,ed., Encyclopedia of Arti cial Intelligence, pp.1467{
1468, Wiley-Interscience Publication (1992).
[Clearwater 91] Clearwater, S. H., Huberman, B. A., and
Hogg, T.: Cooperative solution of constraint satisfaction problems, Science, Vol.254, pp.1181{1183 (1991).
[Harvey 95] Harvey, W. D. and Ginsberg, M. L.: Limited discrepancy search, In Proceedings of the Fourteenth International Joint Conference on Arti cial Intelligence, pp.607{613 (1995).
[Hogg 93] Hogg, T. and Williams, C. P.: Solving the really hard problems with cooperative search, In Proceedings of the Eleventh National Conference on Arti cialIntelligence, pp.231{236 (1993).
[Kitamura 96] 北村，寺西，辰巳：マルチエージェント実時間探索における組織化とその評価，人工知能学会誌，Vol.11, No.3,
pp.470{477 (1996).
[Knight 93] Knight, K.: Are many reactive agents better than a few deliberative ones?, In Proceedings of theThirteenth International Joint Conference on Arti cial Intelligence, pp.432{437 (1993).
[Korf 88a] Korf, R. E.: Search in AI: A Survey of Recent Results, In Shrobe, H. E., ed., Exploring Arti cialIntelligence , Morgan-Kaufmann (1988).
[Korf 88b] Korf, R. E.: Optimal Path-Finding Algorithms, In Kanal, L. and Kumar, V. eds., Search in
Arti cial Intelligence , Springer-Verlag (1988).
[Korf 90] Korf, R. E.: Real-time heuristic search, Arti cial Intelligence, Vol.42, No.2{3, pp.189-211 (1990).
[Korf 93] Korf, R. E.: Linear-space best- rst search, Arti cial Intelligence, Vol.62, No.1, pp.41-78 (1993).
[Korf 96] Korf, R. E.: Improved limited discrepancy
search, In Proceedings of the Thirteenth National Con-

多状態コミット メント探索とその評価

910
ference on Arti cial Intelligence, pp.286{291 (1996).
[Newell 72] Newell, A. and Simon, H. A.: Human Problem Solving, Prentice-Hall (1972).
[Pearl 84] Pearl, S.: Heuristics: Intelligent Search
Strategies for Computer Problem Solving, AddisonWesley Publishing Company (1984).
[Russel 92] Russel, S.: Ecient memory-bounded searchmethod, In Proceedings of the Tenth European Conference on Arti cial Intelligence, pp.1{5 (1992).
[Shirai 82] 白井，辻井：人工知能，岩波書店 (1982).
[Yokoo 97] 横尾，北村：淘汰を用いたマルチエージェント実時
間探索の高速化：協調探索への競争の導入，コンピュータソフ
トウェア，Vol.14, No.4, pp.47-55 (1997).

〔 担当編集委員：××○○，査読者：○○×× 〕
著

者

紹

介

北村 泰彦
（正会員）

1983 年大阪大学基礎工学部情報工学科卒業．1988
年同大学院博士課程修了．工学博士．同年，大阪
市立大学工学部電気工学科助手．現在，同情報工学科助教授．分散人工知能，ヒューリスティック探索，情報統合の研究に従事．
電子情報通信学会，情報処理学会，ソフトウェア科学会等の会員．
〈
〉

WWW
ACM,

IEEE, AAAI,

kitamura@info.eng.osaka-cu.ac.jp

横尾
前掲（

真
（正会員）

Vol.14, No.4, p.? ）参照．

宮地 智久

1997 年大阪市立大学工学部情報工学科卒業．1999
年同大学院修士課程修了．同年，住友電気工業（株）
入社．在学中，ヒューリスティック探索の研究に従事．電子情報通信学会会員．

辰巳 昭治
（正会員）

1970 年大阪大学工学部通信工学科卒業．1992 年同大学院修士課程修了．同年川崎重工業入社．1978
年大阪大学大学院博士課程修了．工学博士．豊橋
技科大学を経て，現在大阪市立大学工学部情報工学科教授．統計的パターン認識，意思決定問題，画像処理用並列プロセッサの開発，
向き相互結合網の構成法などの研究に従事．電子情報通信学会，情報処理学会，ソフトウェア科学会，
〈
〉

VLSI

等の会員．

10

IEEE
tatsumi@info.eng.osaka-cu.ac.jp

人工知能学会誌

Vol.14 No.5