ヒューリスティック探索への
n-状態コミット メントの導入
宮地 智久 y, 北村 泰彦 y, 横尾 真 yy, 辰巳 昭治 yy 大阪市立大学工学部情報工学科
大阪市 住吉区 杉本 3-3-138
e-mail: fmiya,kitamura,tatsumig@kdel.info.eng.osaka-cu.ac.jp
yy NTT コミュニケーション科学研究所
京都府 相楽郡 精華町 光台 2-2

e-mail: yokoo@cslab.kecl.ntt.jp

準最適解を求めるヒューリスティック探索の高速化のため，展開の候補を n-状態に限定する n-状態コミット メ

ントの概念を導入する．対象とするヒューリスティック探索アルゴ リズムとし ては実時間 A*アルゴ リズムと重み付き A*アルゴ リズムであり，これらはそれぞれ 1-状態コミット メント，全状態コミット メント手法であると見なすことができる．2 分木を用いた理論的解析および迷路問題と n-パズル問題を用いた実験的解析でその効果を評価する．
ヒューリスティック探索，コミット メント，準最適解

Introducing n-State Commitment Method Into
Heuristic Searche Algorithms
Tomohisa MIYAJIy, Yasuhiko KITAMURAy, Makoto YOKOOyy, Shoji TATSUMIyy Dept. of Information and Communication Engineering,
Faculty of Engineering, Osaka City University
3-3-138 Sugimoto, Sumiyoshi-ku, Osaka 558 Japane-mail: fmiya,kitamura,tatsumig@kdel.info.eng.osaka-cu.ac.jp
yy NTT Communication Science Laboratories
2-2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02 Japane-mail: yokoo@cslab.kecl.ntt.jp
To improve heuristic searche algorithms for semi-optimalsolutions, we introduce n-state commitment method
which limits the number of candidate states to be expanded to n. We apply the method to Weighted A* (WA*)
algorithm and Real-Time A* (RTA*) algorithm which can be viewed as 1-state commitment and all-statecommitment algrothms respectively, and show the e ects through theoretical analysis using a binary tree andempirical analysis using maze and n-puzzle problems.
heuristic search, commitment, semi-optimal solution

1 まえがき

メント探索を行なっていると見なすことができる．一方で MRTA*では複数のエージェントが同一の状態を展開

人工知能の研究課題の一つに問題解決がある．ゲーム し，冗長な探索を行なう可能性が高くなるという問題点
やパズルは人間が行なう問題解決の典型的なものと考えられ，チェスや囲碁をするプログラムなど が数多く作られた．問題解決は，一般的に状態空間グラフにおける解経路を発見することに定式化することができ，このためがあった．そこで本研究ではマルチエージェントではな
く，従来のコミット メント探索アルゴ リズムを改良することによるシングルエージェント 型の n-状態コミット

メント探索アルゴ リズムを提案する．すなわち，WA*，の手法として探索がある．しかしながら状態空間グラフ

RTA*のそれぞれに最大長さ n のコミット メントリストのサイズが大きくなると単純な探索手法では現実的な時を導入し ，展開の候補はその中から選択するようにして間内に解を求めることが困難になる．そこで問題に関すいる．

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

アルゴ リズムが提案され，その代表的なものに A*アルゴ リズムがある [Pearl84]．

本稿では以下，ヒューリスティック探索の定式化を行なった後，WA*と RTA*アルゴ リズムにおける n-状態
コミット メント探索アルゴ リズムへの修正法について述べる．また同時にこの修正を加えたとしてもアルゴ リズ

A*アルゴ リズムは最適解が得られることを保証するが， ムのもつ完全性の性質が変わらないことも示す．そして，n-状態コミット メント手法の効果を示すため，二分木をを得ることよりも，許容可能な時間内に準最適解を得るこ 用いた理論的解析と，迷路問題と 15 パズルを用いた実実用的な探索アルゴリズムとしては，時間をかけて最適解とが望ましい場合も多い．そのようなヒューリスティッ 験的解析を行ない，その性能を評価する．
ク探索アルゴ リズムとし ては，重み付き A*(Weighted

A*:WA*)[Korf93] アルゴ リズムや実時間 A*(Real-Time
ヒューリスティック探索の定式化
A*:RTA*) アルゴ リズム [Korf90] がある．
WA*と RTA*では展開する状態を決定する手法に特問題は四つ組 hS; O; S0; Gi で表される．ここで S(6= )
徴的な違いがある．WA*は探索木の最前線にある全ては状態の集合，O は状態遷移を示すオペレ ータの集合，の状態を展開候補とし て記憶しているが，RTA*は先に
s0 (2 S) は初期状態，G( S) は目標状態の集合である．
展開した状態に隣接する状態のみに展開候補を絞り込ん
問題は初期状態からオペレータを繰り返し適用して目標でいる．RTA*はヒューリスティック探索におけるコミッ

2

ト メントという視点からはその後の探索の可能性を展開する唯一の状態からの子孫に限定するという意味で 1-状
態コミット メント探索アルゴ リズムと見なすことができる．一方，WA*は探索の可能性を一切限定していないので，全状態コミット メント探索アルゴ リズムと見なすことができる．1
さて，このようなコミット メント 探索アルゴ リズム
は探索に関わるエージェントの数を増加させることにより，その性能が改善されることが報告されている．複数のエージェントが RTA*アルゴ リズムを並行して実行する

マルチエージェント実時間 A*アルゴ リズム (Multiagent

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

例とし て，図 1に迷路問題を示す．迷路問題はスタート (Start) からゴ ール (Goal) へ移動することによって解決される．したがって，迷路問題は障害物のないマスを状態，上下左右への移動をオペレータ，スタートを初期状態，ゴ ールを目標状態と見なすことで定式化できる．
もう一つの例として，図 2に 15 パズル問題を示す．15

パズル問題は n-パズル問題の一種であり，15 個の数字付きタイルとそれらを囲む枠からなる．問題は初期配置
からタイルのスライドを繰り返し，目標とする配置に変更することによって解決される．n-パズル問題はタイル

RTA*:MRTA*)Knight[Knight93] では n-パズルのよ う の配置が状態，タイルのスライドがオペレ ータ，タイル
な問題においてエージェント数の増加が性能向上につなの初期配置が初期状態，目標とするタイルの配置が目標がることを示している．また横尾と北村は，MRTA*に状態となる．

おいてエージェントを再配置することで劇的な性能改善が可能であることを示した [横尾と北村 97]．

は，状態 s，s0 (ジェントのそれぞれが 1-状態コミット メント探索アルゴ

ばれ，初期状態から目標状態への経路を解または解経路

コミット メントの視点からは MRTA*は n 台のエー

リズムを実行しているので，全体として n-状態コミット
1 全ての状態にコミットすることは，どの状態にもコミットしていないこととも等価であるので，このアルゴ リズムを無状態コミットメ
ント探索アルゴ リズムと見なすこともできる．

オペレ ータの適用にコスト (> 0) が定義され る場合

2 S) 間の遷移のコストを c(s; s ) で示す．
0

オペレータの適用により得られる状態の系列は経路と呼と呼ぶ．解経路を構成するオペレータのコストの和を解のコストとする．ある解が存在したとき，それよりも小さいコストをもつ解が存在しなければ，その解を最適解と呼ぶ．

WA  (hS; O; s0 ; Gi)
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: add(open list; successors(s));
5: add(closed list; s);6: if open list =  then return failure;
7: s get min(open list);
8: goto 2;
図 3: WA*アルゴ リズム

隣接する状態が生成済みか否かをいずれかのリストに存

図 1: 迷路問題

在するかど うかで判断できるため，WA*は状態の再生成を避けることができる．

15

14

2

6

10

5

7

11

4

12

1

3

1

2

3

4

5

6

7

8

8

9

10

11

9

12

13

14

15

WA*のアルゴ リズムを図 3に示す．まず初期状態から探索を開始する (1 行目)．隣接する状態を全て生成する (2 行目)．ただし ，過去に生成したことのある状態は生成し ない．隣接する状態に目標状態が 含まれてい13

れば探索は成功したものとする (3 行目)．そうでなければ，隣接する状態をオープンリストに加え (4 行目)，展
開した状態をクローズド リストに加える (5 行目)．もし

図 2: 15 パズル問題
ヒューリスティック探索では ，各状態 s(

オープンリストが空であれば探索は失敗したものとし (6)，そうでなければ，オープンリストの中で最小の2 S) から 目 行目h(s )(s 2 open list) を持つ状態を取り出し ，探索を続標状態までのコストの概算値を与えられており，ヒュー
リスティック関数 h(s) で表される．

3 WA*アルゴリズムへの n, 状態コ
ミット メント の導入

3.1 WA*アルゴリズム

00

行する (7,8 行目)．この一連の動作を 1 ステップと定義する．

[Korf90] で用いられている例 (図 4) で，WA*の動作を簡単に説明する．黒丸が状態，間をつなぐ 枝がオペレー
タ，横の数値がもともとのヒューリスティック関数の値である．初期状態は a であり，オペレータのコストは全て 1 であるものとする．なお，この図では目標状態は示されていない．

A*は状態 s の評価に初期状態から状態 s までのコストの和 (g(s)) と，状態 s から目標状態までのコストのまず，a に隣接する状態 b，c，d を生成する．いずれも概算値 h(s) の和を用いるが，WA*は g(s) と h(s) の比 目標状態ではないので，b，c，d をオープンリストに加え，重を変更できるアルゴ リズムであり，状態 s の評価には a をクローズド リストに加える．オープンリストは空で(1 , W)g(s) + Wh(s) を用いる．このとき，W が h(s) ないので，オープンリストから最小の評価値 (h(b) = 1)
に対する重みである．以下では，W が極端に大きい場 を持つ b を取り出す．ここまでが 1 ステップである．次合を想定し ，評価には h(s) だけを用いる．
に，b に隣接する状態 e，i を生成する (a は展開済みなA*と同じ く WA*もオープンリスト，クローズド リス ので隣接する状態には 含めない)．いずれも目標状態でトと呼ばれる 2 つのリストを用いる．全ての生成された はないので，e，i をオープンリストに加え，b をクロー
状態は一旦オープンリストに保存され，また一度展開された状態はクローズド リストに保存されるため，一度展

ズド リストに加える．オープンリストは空でないので ，
オープンリストから最小の評価値 (h(c) = 2) を持つ c を開した状態は必ずいずれかのリストに存在する．従って， 取り出す．以下同様に c，d，e，i，   と探索を行う．

CWA  (hS; O; s0; Gi)
1: s s0 ;b
2: generate successors(s);1
3: if successors(s) \ G 6=  then return success;a
4: add(commit list; successors(s));
69
5: add(closed list; s);dc
6: while length(commit list) > n do
327:
s get max(commit list);8:
add(open list; s);87
9: while (length(commit list) < n) and10:(open list 6= ) do
11:s
get min(open list);
図 4: 例題
12: add(commit list; s);
3.2 n-状態コミット メント WA*アルゴリズ 13: if (commit list = ) and (open list = ) then
14: return failure;ム
15: s get min(commit list);
WA*はオープンリストに保存された状態から次に展 16: goto 2;
開するものを選択する．n-状態コミット メントでは選択すべき候補を n 状態に限定する．具体的には，コミット
図 5: CWA*アルゴ リズム
e

i

4

5

メントリストと呼ばれるリストを導入し，生成された状

態はオープンリストではなくコミット メントリストに保存する．そし て，コミット メントリストから次に探索を行う状態を選択する．コミット メントリストの長さは n以下に制限され，上限を越えた場合は評価の悪いものか

コミット メントリストの大きさの上限 (n) を無限大にすると，もともとの WA*と等し くなる．

らオープンリストに移し 変える．また，コミット メント
リストが空になった場合は，オープンリストから評価の良いものを移し 変える．なお，クローズド リストに関す, 状態コミットる扱いは WA*と同様である．従って，nメント WA*(n-state Commitment WA*:CWA*) でも一度生成した状態はコミット メントリスト，オープンリス
ト，クローズド リストのいずれかに必ず存在することが保証されている．CWA*のアルゴ リズムを図 5に示す．

3.3 アルゴリズムの完全性
WA*に n, 状態コミット メントを導入し ても完全性

WA*と比較すると，図 3の 4-7 行目が図 5の 4-15 行 が保たれていることを示す．なお，この場合の完全性とは，初期状態から 目標状態に至る経路が存在するとき，目に変更されている．

すなわち，生成した状態はオープンリストではなく， 解経路が得て，停止することを保証するものである．

コミット メントリストに加える (4 行目)．現在の状態は

WA*と同様にクローズド リストに加える (5 行目)．コ
ミット メントリストが大きさの上限を越えていれば，評価値 h(s0 )(s0

WA*の完全性は，初期状態から目標状態への経路が存在し，状態空間が有限であるとき保証されている．これは WA*は一度展開した状態を再展開しないため無限

2 commit list) が最大の状態からオープン ループに陥ることがなく，また，アルゴ リズムが停止す

リストに移し 変える (6-8 行目)．コミット メントリストに空きがあれば，コミット メントリストの上限までオー

プンリストから最小の h(s0 )(s02 open list) を持つ状態

を移し変える (9-12 行目)．コミット メントリスト，オー

る以前では解経路上の状態が少なくとも一つはオープン
リストに保存されているからである．

CWA*も同様に，状態を再展開することがないので無プンリストともに空ならば探索に失敗に終る (13-14 行

限ループには陥らず，解経路上の状態は少なくとも一つ

ントリストの中から次に探索を行う状態を選択する (15る．従って，初期状態から目標状態への経路が存在し ，目)．そして，オープンリストからではなく，コミット メ コミット メントリストあるいはオープンリストに存在す

行目)．

状態空間が有限ならば，CWA*の完全性は保証される．

RTA  (hS; O; s0 ; Gi)
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: update(s);5: if successors(s) =  then return failure;
6: s get min(successors(s));
7: goto 2;
図 6: RTA*アルゴ リズム

4 RTA*アルゴリズムへの n, 状態

CRT A  (hS; O; s0 ; Gi)
1: s s0 ;2: generate successors(s);3: if successors(s) \ G 6=  then return success;
4: update(s);5: add(commit list; successors(s));
6: while length(commit list) > n do
7:s get max(commit list);
8: if commit list =  then return failure;
9: s get min(commit list);
10: goto 2;
図 7: CRTA*アルゴ リズム

コミット メント の導入

して，最小の評価値 h(a) = 3 を持つ a を次に展開する．

4.1 RTA*アルゴリズム

以下同様に評価値を更新しつつ， a から c，c から a，aKorf の提案し た RTA*は，探索し ながらヒューリス から d，   と探索が行われる．
ティック関数の値を更新することが特徴的である．RTA*
4.2 n-状態コミット メント RTA*アルゴリズのアルゴ リズムを図 6に示す．
ム

以下にアルゴ リズムの流れを説明する．まず初期状態

から探索を開始する (1 行目)．そして現在の状態に隣接

1(s 2 successors(s))) の場合，そRTA*は，展開された状態の子孫のみが以後の探索に影響を与える 1-状態コミット メント探索アルゴ リズムである．ここでは，RTA*に n, 状態コミット メントの概の状態より先に探索を進めても目標状態へ到達すること念を導入することにより，コミット メントの範囲を広げする状態を全て生成する (2 行目)．ただし ，状態の評価
値が無限大 (h(s0 ) =0る．例えば，先程の例で b から次に探索を行う状態を選
目標状態が含まれていれば 探索は成功である (3 行目)． 択する際，隣接する a，e，i だけではなく c も候補に入はないので，隣接する状態に含めない．隣接する状態に目標状態が含まれていなければ，h(s) を隣接する状態の中で 2 番目に小さい c(s; s ) + h(s )(s0002 successors(s))に更新する (4 行目)．隣接する状態の数が 1 個以下なられられ，a を展開ではなく c が展開される．

具体的には，CWA*と同様にコミット メントリストを導入し，生成した状態をコミット メントリストに保存す

1 に更新す る．そして，コミット メントリストから次に展開を行う

ばその状態を再展開する意味がないので，る．もし 評価値が1 でない隣接する状態が存在しなけ

れば探索は失敗である (5 行目)．そうでなければ，隣接する状態の中で最小の評価値 h(s0 )(s02 successors(s))

を持つ状態を次に展開する (6,7 行目)．なお，複数の状状態を選択する．コミット メントリストの長さは n に制限され，それを越えた場合は評価値の悪いものから取り除く．

n, 状態コミット メント RTA*(n-state Commitment
態の評価値が同じときはその中からランダムに選択する． RTA*:CRTA*) アルゴ リズムを図 7に示す．
図 4で RTA*の動作を簡単に説明する．まず，a に隣接
RTA*のアルゴ リズムと比較すると，図 6の 5,6 行目
する状態 b，c，d を生成する．いずれも目標状態ではない が図 7の 5-8 行目に変更されている．すなわち，隣接すため，h(a) を更新する．この場合 c(a; b)+h(b) = 1+1 = る状態は一旦コミット メントリストに加えられ る (5 行
2，c(a; c)+h(c) = 1+2 = 3，c(a; d)+h(d) = 1+3 = 4 目)．ただし，コミット メントリスト内で同じ状態の重複となるので，h(a) は 2 番目に小さい 3 に更新される．評価 は許さない．コミット メントリストの大きさが上限を越
値が 1 でない隣接する状態は存在するので，最小の評価 えていれば，評価値 h(s )(s 2 commit list) が最大のも値 (h(b) = 1) を持つ b を次に展開する．次に，b に隣接す のから削除する (6,7 行目)．もしコミット メントリスト
る状態 a，e，i を生成する．いずれも目標状態ではないた が空ならば，探索は失敗に終る (8 行目)．展開はコミッ
め，h(b) を更新する．この場合 c(b; a)+h(a) = 1+3 = 4， ト メントリストに保存されている状態から 選択する (9c(b; e) + h(e) = 1 + 4 = 5，c(b; i) + h(i) = 1 + 5 = 6 と 行目)．なお，コミット メントリストから状態を取り出なるので，h(b) は 2 番目に小さい 5 に更新される．そ す際，同じ 評価値のものがあればランダムに選択する．
00

コミット メントリストの大きさの上限 (n) を 1 とすると，もともとの RTA*と等し くなる．

s0

4.3 アルゴリズムの完全性

s1

s2

T(s 1 )T(s 2 )

RTA*の完全性は全ての状態から目標状態に到達可能，
ヒューリスティック関数の初期値は有限，状態空間が有限の場合に保証されている [Korf90]．

, 状態コミット メントを導入し以下では，RTA*に nても，完全性が保たれていることを示す．まず，RTA*と同じく，各状態に対するヒューリスティック関数の初期値が有限であるので，無限なヒューリスティック値の

図 8: 二分木

障害が目標を取り囲んでアルゴ リズムが失敗で終了する
ことはない．
また，全ての状態から目標状態への経路が存在し，状態空間が有限であるので，無限のループに陥ることはな
い．その理由は以下からなる．状態空間が有限で目標状

 T(s1 ) に目標状態が含まれるか否か．
まず，maxs2T (s1) h(s) < h(s2 ) となる場合を考える．

CWA*はコミット メント リストの中で最小の h(s)(s 2list) を持つ状態から探索を行うので，n がいく
commitできないならば，目標状態を含まない無限ループに陥っらであっても，T (s1 ) の探索が終了するまで s2 が展開さていると考えられる．状態の評価値は隣接する状態の評れることはない．従って，T (s1 ) の探索が終了するまで価値とオペレータのコストの和に更新されるため，更新
T (s2 ) が探索されることはなく，T(s1 ) と T(s2 ) のいずされた評価値は隣接する状態の評価値よりも必ず大きくれに解が含まれていようとも n, 状態コミット メントのなる．よって，ループ内における最小の評価値は一巡す
態への経路が存在するにもかかわらず，目標状態へ到達る毎に確実に増加する．したがってループに含まれる状態の最小の評価値は，いずれそれに含まれない状態の評
価値よりも大きくなり，ループから抜け出すことができる．状態の数は有限であるので，いずれ目標状態にも到達する．この性質は，コミット メントリストの長さに関わらず保たれ，CRTA* の完全性は保証される．

5 理論的解析

効果は期待できない．

次に，maxs2T (s1 ) h(s)

 h(s2 ) かつ，G  T (s1 ) なる場合を考える．この場合，n が大きいと T (s1 ) の探索

によって目標状態に到達する前に s2 がコミット メント

リストから選択されて余分な探索を行う可能性がある．

WA*は CWA*における n = 1 の場合と等しいので，nを小さくすれば，CWA*が WA*よりも少ないステップ数で解を得ることを期待できる．
最後に，maxs2T (s1 ) h(s)

 h(s2 ) かつ，G  T(s2 ) なる場合を考える．T(s1 ) の探索を極力減らし ，できるだ

5.1 CWA*

け早く T (s2 ) で解を見つけたい状況である．n が大きけ

各状態において左の子供の方が右の子供よりも評価値が良いように作られた二分木を考える．そのような二分れば，T(s1 ) の探索が終了する前に s2 がコミットメント

リストから選択されて T(s2 ) の探索が開始される可能性

木の探索において，左右いずれか一方の部分木にしか目がある．これは WA*の方が CWA*よりも適している場

標状態が存在しないような問題を仮定する．この一例と合である．

左の子供 s1 と右の子供 s2 を持ち，また，それぞれの子

5.2 CRTA*

して図 8に示すような s0 を根とする木を考える．s0 は

供も s1 を根とする部分木 T(s1 )，s2 を根とする部分木

まず maxs T (s1 ) h(s) < h(s2 ) なる 場合を考える．
T(s2 ) を持つ．
s0 から s1 と s2 が生成された後，s1 の探索が行われ CWA*と同様に，CRTA*もコミット メント リストの中で最小の h(s)(s 2 commit list) を持つ状態から探索をる．以下では，このような問題において，n, 状態コミッ行うので，n がいくらであっても，T(s1 ) の探索が終了す
ト メントの効果が次の 2 点に大きく依存していることをるまで s2 の探索が行われることはない．従って，T(s1 )示す．
の探索が終了するまで T(s2 ) が探索されることはなく，
 T(s1 ) 中で最大の h(s)(s 2 T(s1 )) が h(s2 ) より小 T (s1 ) と T(s2 ) のいずれに解が含まれていようとも n,
さいか．すなわち maxs T (s1 ) h(s) < h(s2 )．
状態コミット メントの効果は期待できない．
22

表 1: CWA*の迷路問題における実験結果
アルゴ リズム

成功率

ステップ数

解の長さ

100
100
100
100
100
100

391.7
383.0
383.0
383.9
384.2
383.9

170.8
167.7
167.3
167.5
167.6
167.4

CWA* (1)CWA* (2)CWA* (4)CWA* (8)CWA*(12)WA*

次に，maxs2T (s1 ) h(s)

 h(s2 ) かつ，G  T(s1 ) なる場合を考える．このような状況では n はあまり大きくない方が適し ている．そし て，RTA*は CRTA*において n = 1 の場合と等しい．従って，このような状況では，RTA*の方が CRTA*よりも適している．
最後に，maxs2T (s1 ) h(s)

 h(s2 ) かつ，G  T (s2 ) なる場合を考える．この場合，コミット メントリストの上, 状態コミット メン

限が大きい方が適しているため，nトの効果が期待できる．

6 実験的解析
6.1 CWA*
まず，CWA*を用いて迷路問題上で実験を行った．障害物の比率を 40%とし ，入口 (0,0)，出口 (59,59) とする 60x60 の格子状グラフを用いた．各状態のヒューリス

ティック関数には目標状態とのマンハッタン距離を用い，各オペレータのコストは 1 とし た．ランダムに生成した

表 2: CWA*の 15 パズル問題における実験結果
アルゴ リズム

成功率

ステップ数

解の長さ

100
100
100
100
100
100

3940.72274.01578.2
1576.21694.4
1889.01188.81568.7
760.9
529.5
463.6
203.6

CWA* (1)CWA* (2)CWA* (4)CWA* (8)CWA*(12)WA*

表 3: CWA*の 48 パズル問題における実験結果
アルゴ リズム

成功率

ステップ数

解の長さ

38
97
98
100
96
99
10

370374.0
190507.0
134848.0120051.0133266.0
157416.0
189241.9

9495.09470.710180.711138.1
11584.811622.1
3151.0

CWA* (1)CWA* (2)CWA* (3)CWA* (4)CWA* (5)CWA* (6)WA*

また，48 パズル 問題でも実験を行った．ヒューリス

ティック関数など は 15 パズル 問題と同様である．ラン

ダムに生成した 100 個の 48 パズルに対し 各 1 回試行した結果を表 3に示す．なお，実験に使用した計算機には利用可能なメモリ量に限界があるため，各リストに含まれる状態数の和が 150 万を越えた場合，探索が失敗した
ものとみなし ている．

100 個の迷路問題に対し 各 100 回試行した結果を表 1に 48 パズル問題では，WA*ではわずか 1 割の問題でしか解を得ることができなかったのに対し ，n = 4 とし た示す．括弧内の数字は n である．成功率は実験を行った
ときの CWA*は全ての問題で解を得ることができた．ス
問題のうち，何パーセントの問題で解を得ることができ
テップ 数で比較すると，n = 4 の場合，WA*の 2=3 のたかを示す．
ステップ数で解を得ることができた．解の長さに関して
迷路問題では n を増やし ても性能にほとんど 変化がは WA*が極端に良いように見えるが，これは解の短いなく，WA*と比較しても性能の改善は得られなかった．
ものしか発見できないことを表していると考えることも次に，CWA*を用いて 15 パズル問題上で実験を行った．各状態のヒューリスティック関数には各タイルの正しい位置とのマンハッタン距離の和を用い，各オペレ ー

タのコストは 1 とした．ランダ ムに生成し た 100 個のできる．

6.2 CRTA*

15 パズルに対し 各 100 回試行した結果を表 2に示す．
CWA*と同様の条件で迷路問題，15 パズル 問題上で
15 パズル問題上で CWA*を実行すると，n = 8 とし CRTA*を実行した．迷路問題の結果を表 4に，15 パズ
たとき最も少ないステップ数で解を得ることができた． ル問題の結果を表 5に示す．
n を増やすと最終的には WA*の結果に収束するものと 迷路問題では，CRTA*と同様に n を変化させても結思われる．解の長さに関しては，n の増加に対して単調 果はほとんど 変わらず，RTA*と比較しても性能の改善
減少しており，結果とし て WA*より良い解を得ること は得られなかった．
はできなかった．
15 パズルでは，n = 2 としたときステップ数が最小と表 4: CRTA*の迷路問題における実験結果

表 6: CRTA*の 48 パズル問題における実験結果

アルゴ リズム

成功率

ステップ数

解の長さ

RTA*
CRTA* (2)
CRTA* (4)
CRTA* (8)CRTA*(12)

100
100
100
100
100

1340.21352.41352.71350.31318.9

165.1
163.3
163.2
163.4
163.4

RTA*
CRTA* (2)
CRTA* (3)
CRTA* (4)
CRTA* (5)
CRTA* (6)

表 5: CRTA*の 15 パズル問題における実験結果

7 むすび

アルゴ リズム

成功率

ステップ数

解の長さ

RTA*
CRTA* (2)
CRTA* (4)
CRTA* (8)CRTA*(12)

100
100
100
100
100

2647.11380.11442.41712.51812.71049.3
447.1
358.4
334.9
326.1

アルゴ リズム

成功率

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, 状態コミット

本研究では，探索の範囲を制限する nメントの概念を WA*と RTA*の二つのヒューリティック
探索アルゴ リズムに導入した．そし て，二分木を用いた, 状態コミット メントを導入した

理論的解析により，nアルゴ リズムがど のような状況で効果的かを示した．

また，迷路問題，15 パズル問題および 48 パズル問題上で実験的解析を行った．いずれのアルゴ リズムでも迷路問題では性能を改善できなかったが，n-パズル問題ではなり，それ以上に n を増やすとステップ数は単調に増加した．また，解の長さは n を増やす程短くなった．RTA*と比較すると，n = 2 としたとき，CRTA*は RTA*の約半分のステップ 数で解を見つけることができており，解の長さも半分以下になっている．よって，15 パズル問題, 状態コミット メントの導入はにおいて，RTA*への n

性能を改善できた．特に 48 パズル問題において CRTA*

は RTA*の 1=4 以下のステップ数で，CWA*は WA*の

2=3 のステップ 数で解を得ることができた．

今後の課題としては ，理論的解析をより厳密に行い，n, 状態コミット メントの効果を明確にすることが考えられる．

効果的であることが示された．

参考文献
48 パズル問題の結果を図 6に示す．n = 3 とし たときステップ数が最小となり，それ以上に n を増やすとス [Knight93] K.Knight: "Are Many Reactive Agents
テップ数は単調に増加した．RTA*と比較すると，n = 3
Better Than a Few Deliberative Ones?," In Proc.
としたとき，CRTA*は RTA*の 1=4 以下のステップ数でof IJCAI-93, pp.432-437(1993).
解を見つけることができており，解の長さは約 1=10 になっている．従って，48 パズル問題においても，RTA* [Korf90] R.E.Korf: "Real-Time Heuristic Search," Arti cial Intelligence, Vol.42,No.2-3(1990),pp.189への n, 状態コミット メントの導入は効果的であること
211.
が示された．
以上の実験結果から，迷路問題では理論的解析におい, 状態コミット メントの効果が期待できないと考えてnられる maxs2T (s1) < h(s2 ) を満たす状況がほとんど だと考えられる．

[Korf93] R.E.Korf: "Liner-space best- rst search," Arti cial Intelligence, Vol.62,No.1(1993),pp.41-78.
[Pearl84] J. Pearl: "Heuristics," Addison Wesley(1984).

同様に，15 パズル 問題および 48 パズル 問題には，
maxs T (s1 )  h(s2 ) かつ G  T (s2 ) を満たす状況と [横尾と北村 97] 横尾 真, 北村 泰彦: " 淘汰を用いたマ
ルチエージェント 実時間探索の高速化:協調探索へ
maxs T (s1 )  h(s2 ) かつ G  T(s1 ) を満たす状況が多の競争の導入," コンピュータソフトウェア, Vol.14,
く含まれており，前者の状況の方がより多いため，CWA*
No.4(1997),pp.47-55.
よりも CRTA*において n, 状態コミット メントの効果
2
2

がはっきり現れたと考えられる．