1U-05 多状態コミット メント実時間 A*アルゴリズムの性能解析y
宮地 智久*, 北村 泰彦*, 横尾 真**, 辰巳 昭治**大阪市立大学工学部情報工学科, **NTT コミュニケーション科学研究所

1. はじめに準最適解を求めるヒューリスティック探索である多状態コミット メント実時間 A*アルゴリズム (Multi-StateCommitment Real-Time A* Algorithm:MSC-RTA*)
は，展開する状態を 1 つの状態に絞り込んでしまう 1
状態コミット メント探索である実時間 A*アルゴリズ
ム (Real-Time A* Algorithm:RTA*) よりも効率的な探索を行うことが示されている [2] ．しかし，問題のどのような性質が MSC-RTA*の性能に影響を与えているのかは十分に説明されていなかった．以下では，MSCRTA*の解析を行い，MSC-RTA*が有効な問題の性質を解明する．また，そのような性質を持つ人工モデルを作成し，シミュレーション実験によって検証を行う．

MSC-RTA*は 15 パズル問題では n = 2 としたときRTA*の約半分の展開数で，円盤の数を 10 としたハノイの塔問題でも n = 15 としたとき RTA*の半分以下の展開数で解を得ることができた．しかし，迷路問題ではRTA*よりも多くの展開数を必要とした (n > 1)．このように問題によって MSC-RTA*の効果が異なるのはなぜか？それぞれの問題の状態空間を調べ，MSC-RTA*と RTA*の動作を比較した結果，原因は副目標の保持と再展開の回数にあると予想される．

2.1. 副目標の保持目標が複数の副目標に分割でき，かつ副目標を順に達成する際に以前の副目標を保持したままで以降の副目標を達成できるとき，その問題は直列化可能な副目

2. MSC-RTA*
代表的な 1-状態コミット メント探索である RTA*[1]は一定の先読み探索と移動を交互に行う．RTA*は状態列化可能な副目標を持っている．副目標は破壊されるを展開して隣接する状態を生成し，次に展開する状態しなければならないため，副目標を保持できるかが展を隣接する状態の中で最小の f (s; s ) = c(s; s ) + h(s )000を持つものに決定する．ここで，c(s; s ) は状態 s から0状態 s0 へのコスト，h(s0 ) は状態 s0 から目標状態までのコストの推定値である．探索は目標状態を生成したとき終了する．RTA*はクローズド リストを用いないが，次の状態を展開する前に h(s) を隣接する状態の中で二番目に小さい f (s; s00 ) に更新することでアルゴリズムの完全性を保証している．

MSC-RTA*と RTA*の違いは，コミット メントリス
トを用いるかどうかである．MSC-RTA*において隣接する状態は一旦コミット メントリストに追加され，次に展開する状態はコミット メントリストから選択される．MSC-RTA*はパラメータとしてコミット メントリストの大きさの上限 n を持ち，コミット メントリストが n よりも大きくなると，評価値の大きい状態から取り除かれる．n = 1 の MSC-RTA*は RTA*と等価である．

Performance Analysis of Multi-State Commitment RealTime A* Algorithm. Tomohisa Miyaji*, Yasuhiko Kitamura*,
Makoto Yokoo**, Shoji Tatsumi*. *Faculty of Engineering, Osaka City University, **NTT Communication ScienceLaboratories.
y標を持つという．15 パズル問題やハノイの塔問題は直こともあり，もう一度達成するには多くの状態を展開開数を大きく左右する．

RTA*は展開する状態が 1 つに絞り込まれているため，一度副目標を破壊するような状態を選択するだけで副目標を保持できなくなる．しかし，MSC-RTA*は副目標を破壊するような状態を選択したとしてもコミッ
ト メントリストの中に副目標が破壊されていない状態が残っている限り，いずれ副目標を破壊する前の状態から探索を再開することができるため，副目標が保持される．従って，直列化可能な副目標を持つ問題では，

MSC-RTA*は RTA*より少ない展開数で解が得られると考えられる．

2.2. 再展開数の減少

MSC-RTA*や RTA*は状態の再展開が起こり得るアルゴリズムである．従って，同じ領域を探索しても再展開の回数が少なければ，結果として少ない展開数で解が得られる．MSC-RTA*が状態の再展開を抑制する仕組みを説明するための例として，隣接する状態が全て展開済みである状況を考える．RTA*は隣接する状態のみから次に展開する状態を選択するため，必ず状態の再展開が起こる．しかし，MSC-RTA*では隣接するPage 1

状態よりも小さい評価値を持つ未展開の状態がコミッ
ト メントリストに存在すればその状態が次に展開されるため，再展開は生じない．
ハノイの塔問題は同じような評価値を持つ状態が密集した領域を持っている．そのような領域では，一度でも展開した状態の評価値は必ず未展開の状態よりも大きくなるため，MSC-RTA*の再展開数は RTA*よりも少なくなる．また，ヒューリスティックな評価関数にゴールへのマンハッタン距離を用いた迷路問題では MSC-RTA*は RTA*よりも再展開数が多くなる．これは袋小路の奥ほど評価値が小さくなる傾向があり，MSCRTA*が，袋小路の状態の評価値がコミット メント リスト内で最小でなくなるまで，袋小路の状態を何度も再展開するためである．

3. 人工モデル

再展開が起こりやすい．大きさが 30230 の人工モデルで 10,000 回試行した結果を表 2 に示す．MSC-RTA*

は RTA*の 4 分の 1 しか再展開を行わず，RTA*より少ない展開数で解を得ることができた．これは未展開の状態は全て h(s) = 1 だが，一度でも展開した状態では h(s) > 1 となるため，MSC-RTA*ではコミット メントリストに未展開の状態がある限り再展開は起こらないからである．
Start

Start
22221111111111112221111111111111222111111111111122211111111111112221111111111111222111111111111122211111111111112222111111111111以上のことを確かめるため，2 つの人工モデルを作成し，シミュレーション実験によって検証を行った．
まず，直列化可能な副目標を持つ人工モデルとして，中央の障害物によって h(s) の初期値が異なる 2 つの領域に分割された迷路問題を作成した (図 1 左) ．左上が初期状態であり，右下が目標状態である．障害物の左側の領域から右側の領域に移動することで副目標は達成されるが，副目標を達成する経路は 2 つしかないた

Goal

Goal

図 1. 人工モデル
表 1. 副目標を持つモデルにおける実験結果
副目標を保持できアルゴリズムなかった問題の数

展開数

RTA*
3353 1075.7
MSC-RTA*(n = 5)
202 597.4(a) 副目標を保持できなかった問題の数と展開数

め，副目標を保持できなかった場合，もう一度達成する保持できた

保持でき場合なかった場合には多くの状態を展開しなければならない．大きさがアルゴリズムより少ない展開数で解を得ている．この人工モデルで

RTA*
708.7
1803.2
MSC-RAT*(n = 5)573.2
1770.4(b) 副目標保持の可否による展開数の相違
表 2. 全て同じ初期値のモデルにおける実験結果

30230 の人工モデルで 10,000 回試行した際に副目標を保持できなかった問題の数と展開数の平均値を表 1(a)に示す．MSC-RTA*は RTA*の 16 分の 1 の問題でしか副目標の保持に失敗しておらず，結果として RTA*

MSC-RTA*が RTA*よりも遥かに副目標を保持しやすい理由の 1 つに，障害物の左側の領域では h(s) = 2
だが，右側の領域では h(s) = 1(< 2) であるため，たとえ副目標を破壊するような状態を選択したとしても，副目標を破壊されていない状態がコミット メントリス
トに残りやすく，副目標の保持が容易であることも挙げられる．また，表 1(b) はこの人工モデルおいて探索中に副目標を保持できた場合と保持できなかった場合の展開数を示しており，副目標を保持できなかった場合は保持できた場合の 2 倍以上の状態を展開しなければならないことが分かる．
次に，もう一つの人工モデルとして，障害物を含まない迷路問題を作成し，各状態の h(s) の初期値を全て 1 とした (図 1 右) ．この人工モデルではヒューリスティックが目標状態に関する情報を全く示さないためアルゴリズム

RTA*
MSC-RTA*(n = 5)

再展開数

展開数

453.5 1161.6
115.8 708.1

4. むすび人 工モデ ル 上 の シ ミュレ ー ション 実 験 によって ，MSC-RTA*が RTA*より副目標を保持しやすく，再展開の回数も少ないため，RTA*より少ない展開数で解が得られることを示した．

参考文献[1] Korf，R. E. 1990. Real-time heuristic search.
Arti cial Intelligence, 42(2-3):189-211.
[2] 宮地 智久, 北村 泰彦, 横尾 真, 辰巳 昭治. 1998.
ヒューリスティック探索への n-状態コミット メントの導入. 信学技報, AI97-58.

Page 2