動的迷路における観測と経路探索手法
北村泰彦

鈴東智*

辰巳昭治

大阪市立大学大学院工学研究科
kitamura@info.eng.osaka-cu.ac.jp
あらましWWW 情報源はそれぞれが自律分散的に管理され，不定期に更新が行われるので，WWW 情報源を利用した問題解決はその問題空間が変化する動的問題解決とみなすことができる．動的問題解決はエージェントの問題空間の観測と探索が繰り返し行われることにより実行される．本論文では，動的問題解決を動的迷路の経路探索問題として定式化を行い，観測対象決定と解導出手法の提案を行う．提案方式は問題空間の変化の速度に応じて適切な解導出ができることを示す

Observation and Path Finding Method for Solving Dynamic Maze
Yasuhiko Kitamura, Satoshi Suzuhigashi, and Shoji Tatsumi
Graduate School of Engineering, Osaka City University
Abstract Since WWW information sources are managed in an autonomous and distributed manner, data
updates in the sources are performed asynchronously. When we consider a problem solving task thatinvolves WWW information sources, it can be regarded as a dynamic problem solving in which the problem
space is dynamically changing in the course of finding solutions. A dynamic problem can be solved by anagent that interleaves finding solution paths with observing the problem space. In this paper, we formalize adynamic problem solving as a path finding process in a dynamic maze and propose a method for observing
the problem space and finding solution paths. Our method shows good performance according to thechanging speed of problem space.

1

はじめに時間に限り，変化しない静的な問題と捉える事で探索を行う．

今日，インターネットは社会に急速に普及しており，中でも WWW（World Wide Web）は，個人やグルー本研究では，一定時間，問題を固定するのではなく，プの情報発信，研究教育，電子商取引など様々な目的確率を用いて問題空間を予測しながら探索を行う手法のために利用されている．WWW 情報源はそれぞれがにより動的問題解決を試みる．問題空間の状態を全て自律分散的に管理されているため，不定期かつ非同期調べてから解くのでは，発見した解が問題空間の変化に更新が行われる．そこで WWW 情報源を利用した問により利用できなくなっている恐れがある．そこで観題解決を考えた場合，問題空間が変化する動的問題解測対象となる状態の決定が重要となるため，過去の観決と見なすことができる．

測結果の新鮮さを表す信頼度，解の重要度を表す期待値を用いて観測対象を決定する．

問題解決の手法として様々な探索アルゴリズムが考案されているが，その多くは静的問題を扱ったもので問題解決とは，問題空間を有向グラフで表現するとある．近年では，自律ロボットなどの分野で実時間にき，初期状態を表す節点から目標状態を表す節点に至おけるプランニングや意思決定に興味が集まり，実時る経路を発見することである．そこで本研究では，動間探索[2, 3, 4]という手法が注目されている．実時間探的状態空間グラフとして，状態が変化する迷路，即ち索では定数時間の先読み探索を行い，その結果得られ動的迷路を定義し，観測対象決定と解導出の手法を提た判断により行動を決定する．つまり動的問題を定数案し，その評価を行う．

*

現在は NTT ドコモ関西

1

2

動的迷路
(1) 目的はスタート座標からゴール座標までの経路を動的問題とは，時間の経過とともに問題空間が変化発見することである．

する問題のことであり，頻繁に更新されるインターネ
ット上の WWW 情報源を用いて行われる問題解決は(2) 座標の観測には一定時間がかかる．

その一例である[1]．本論文では，動的問題を動的迷路(3) 一度に一つの座標についてしか観測できない．

として以下のように定義する．

(4) 一度調べた障害物の有無に関する情報は記憶（キャッシュ）できる．
(5) 迷路について，サイズ，迷路内を占める障害物のz

X×Y サイズの格子状迷路である．

z

障害物は座標単位で存在する．

割合，障害物の存在時間の確率分布を予め知ってz障害物があればその座標には移動できない．

いる．

z

隣り合う座標間の移動コストは全て１である．

z

迷路内の障害物の割合は決まっている．

z

障害物は不定期に発生，消滅を繰り返す．

3

観測対象決定と解導出
動的迷路においてエージェントが観測すべき座標を決定し，解を導出する手法について述べる．
動的迷路では，障害物を避けながらスタート座標からゴール座標までの経路を求めることが問題となる．

3.1 定義

2.1

3.1.1

解

スタート座標を(0,0)，ゴール座標を(2,2)とする図 1

事実の信頼度

事実の信頼度とは，エージェントが観測し，キャッの迷路では，シュした事実（障害物の有無）がどのくらい正しいも経路A1 : (0,0) − (0,1) − (1,1) − (2,1) − (2,2)のであると信頼できるかを確率で表したものである．

経路A2 : (0,0) − (0,1) − (0,2) − (0,3) − (1,3) − ( 2,3) − ( 2,2)キャッシュされた情報は，キャッシュした直後は完全経路A3 : (0,0) − (0,1) − (0,2) − (1,2) − (2,2)に信頼でき，キャッシュされてから時間が経てば経つはいずれもスタート座標とゴール座標を結ぶ経路であほど信頼できないものに変わっていく．事実の信頼度

る． A1 , A2 のように経路上に障害物が無いとき，そを導出する関数の特徴として，れは解となる．しかし， A3 のように一つでも障害物の存在する経路は解とはならない．また A1 , A2 を比較すると， A1 の方が A2 よりも距離が短く良い解といえる．解の中で最も距離が短い解を最適解と呼ぶ．

zキャッシュしてからの時間に依存する．

z

経過時間 t =0 のとき１となる．

zt が増加すると単調に減少し０に収束していく．

が挙げられる．また，信頼度は変化の激しいものを対象としてキャッシュするならば急速に０に収束し，殆ど変わらないものが対象であれば収束は非常に緩やかになる．
動的迷路では，障害物の存在時間は正規乱数により決定されることをエージェントは知っており，平均値µ ，標準偏差 σ はエージェントに与えられるものとしているので，正規乱数の確率密度関数を用いて信頼度導出関数を定義する．

f (t ) =図 1 解の例

2.212πσ− (t − µ )2σ 22exp

上式に示す確率密度関数 f (t)は生成されてから t 時間後に消滅する障害物の分布を表している．障害物が生エージェントの持つ情報成された後， t1 時間後にもその障害物が存在している

動的迷路において解探索を行うエージェントを以下

確率を F (t1 ) とするとのように定義する．

2

F (t1 ) = 1 −t1f について何もキャッシュされていない時

0

エージェントは f については何の情報も有していな∫ f (t )dtい．つまり迷路内での障害物のない割合となる．障害物の存在時間が負の値になる事はない．
つまりe( f ) = 1 − Ob が利用可能確率となる．

0∫ f ( f )dt = 0 なのでf が利用可能とキャッシュされている時−∞利用可能確率は何もキャッシュされていない時よりもt1∫ f (t )dt= f (t )dt − f (t )dt∫∫= f (t )dt∫F (t1 ) = 1 −高くなるはずである．キャッシュからの経過時間が０で信頼度 r ( f ) の値が１の場合，障害物がないという事

−∞

∞

t1−∞
∞

−∞

実は間違いなく正しいので利用可能確率は１となる．

e( f ) = (1 − Ob ) − (1 − Ob ) × r ( f )= (1 − Ob ) × (1 − r ( f ))t1

逆に，キャッシュから十分に時間が経過しているととなる．次に，時刻 t 2 における事実をキャッシュしたr ( f ) は０となり，キャッシュされていない場合と同じという確率は上式よりな の で 利 用 可 能 確 率 の 値 は 1 − Ob と な る ． よ っ てF (t 2 )∫e( f ) = (1 − Ob ) + Ob × r ( f ) となる．

∞

F (t )dt

f が利用不可とキャッシュされている時−∞利用可能の時と同様で，事実がキャッシュされた直後と表される．障害物の生成後，どれだけの時間経過しには e( f ) の値は０になり，時間が経過すると 1 − Ob にてから観測がなされるかは等確率である．しかし時刻収束する．よって

t 2 の時点ではキャッシュする対象が F (t 2 ) しか残ってないことになり式が導かれる．

3.1.3

時刻 t 2 にキャッシュした事実が， T 時間 (T ≥ t 2 ) 後

静的な質

静的な質とは変化する事実に依存しない解の質を表にも正しい確率は

す．０〜１の間に正規化したものを用い，１のときがF (t 2 + T )F (t 2 )最良解であり，０の時が最悪解である．
動的迷路では，スタート座標とゴール座標，障害物である．信頼度はある事実について，の割合についての知識をエージェントが有しているので，経路の距離を考えることにより静的な質が得られ（時刻 t にキャッシュされた確率）×る．ある解候補となる経路 A に対して（かつそれが T 時間後にも正しい確率）

静的な質 : Qs ( A ) = 1 −を全ての時刻 t について積分すればよいので，となり，事実の信頼度は経過時間 T の関数となる．

F (t + T ) 
事実 f の信頼度 : r ( f ) =×dt
F (t ) 0  ∞F (t )dt
 − ∞
∫数）が少ないほど，質が良いと考えられ Q s ( A) の値は∫高くなる．移動距離が 0 である解は最良解とみなせる

ので Qs ( A) の値は１になり，全ての障害物のない座標∞=座標の総数 − 障害物の数と定義できる．経路の移動距離（経路上で通る座標のF (t )∞


経路上で通る座標の数∫∫ F (t )dt
F (t )dt

を通っていくような経路は最悪解となるため Qs ( A) のT∞値は０になる．

−∞

3.1.4
3.1.2

解の期待値

解がどれだけ有用で，かつ利用できるものであるかを利用可能確率期待値として表す．解を A ，その解で利用する事実をある一つの座標に関してキャッシュされた事実 fに基づき，その座標に障害物がなく移動することが可

f1 , f 2 ,⋅ ⋅ ⋅, f n としたとき，解 A の期待値は以下のように能な確率を利用可能確率 e( f ) とする．迷路内におけ表される．

期待値 : E ( A ) = Qs ( A ) × e( f1 ) × e( f 2 ) × ⋅ ⋅ ⋅ × e( f n )る障害物の割合を Ob とすると以下のように定義できる．

3

e( f1 ) × e( f 2 ) × ⋅ ⋅ ⋅ × e( f n )静的な質が良く，解全体の利用可能確率が高いほど期待値は高くなる．エージェントが提示解を決定する時には期待値を用いることとする．

3.1.5

3.4 アルゴリズムの実行例
図 2 に示すように，(0,0)をスタート座標 S，(2,2)を解の信頼度

ゴール座標 G，当初，障害物が(1,0)，(1,1)にある３×キャッシュした内容から求めた解がどれだけ信頼で４の迷路を例として用いる．

きるかを表す解の信頼度を以下のように定義し，観測まず，何も観測されていない状況でオープンリスト

対象解の決定に利用する．解を A ，その解で利用するにある S が展開され，(0,1)と(1,0)が得られたとしよう．

事実を f1, f 2 ,⋅ ⋅ ⋅, f n としたとき，ここで座標 (1,0) を経由する解の観測スコア導出につ解の信頼度 : R ( A) = min r ( f )いて説明する．

f ∈A

スタート座標から(1,0)までの移動距離が 1，(1,0)か= min {r ( f1 ), r ( f 2 ), ⋅ ⋅⋅, r ( f n )}らゴール座標までのマンハッタン距離が 3，障害物のつまり，利用した動的な事実の信頼度のうちで最小のある座標の（推定）数が 2 であるので，その経路の静ものを信頼度とする．

3.1.6

的な質は

()

Qs n(1,0 ) = 1 −

観測スコア(1 + 3)(12 − 2)

= 0.6

観測は，期待値が高く，かつ信頼度が低い解から行うべきである．そこで解 A を観測の対象とすべきかどとなる．

うかを表す観測スコアは以下のように定義される．

次にその経路上の各座標の利用可能確率であるが，観測スコア : S ( A) = E ( A) × (1 − R ( A))

スタート座標から (1,0) を経由してゴール座標に至る経路の長さは 5 と推定される．(0,0)に関しては障害物

3.2 観測対象決定手法

が存在しないが，他の座標については，障害物が存在するという事実はまだ観測されていないとする．その観測スコアの高い解が優先して観測されるので，ノード毎に観測スコアを導出し，その値の大きいものか場合，経路の利用可能確率は 1 ⋅ (1 − Ob ) = (5 / 6) とら展開していく．探索の方法は A(A*)アルゴリズムになる．期待値は4()(4)

E n(1,0 ) = Q s n(1,0 ) × (5 6)4準拠する．観測対象となる経路を探索により求め，その経路の中で利用可能確率が最小の事実について観測= 0.6 × (5 6)4= 0.289を行う．例えば，ある解 A に用いる事実 f1, f 2 , f3 の利用可能確率がそれぞれe( f1 ) = 0.50, e( f 2 ) = 1.00, e( f 3 ) = 0.90となる．
信頼度 R については，観測されていない座標が存在であるときには， f1 が観測の対象となる．

するので 0 である．したがって観測スコアは以上より(3.3 解導出手法)() ((S n (1,0 ) = E n (1,0 ) × 1 − R n (1,0 )提示すべき解は質が良く，かつ利用できるものであ))= 0.6 × (5 6)4 × (1 − 0)
= 0.289

る．そこで提示解の候補の決定は期待値を評価値とした探索により行う．これには観測対象の決定と同様，A(A*)アルゴリズムを利用した．となる．

キャッシュを用いた探索では，必ず解が導出される

その後，提示経路を得るまでの観測を行う．まず図が，障害物の配置によっては正しい解が存在しない場

2 に示される A1 の経路が選択される．何もキャッシュ合がある．また，提示解の候補となる経路について観されていない状況では最短経路（移動距離が４）の期測が不十分であったとき，その解が正しいのかその時待値は全て同じであるので，ここで A1 の経路が選択さ点で判断できない．これらのような場合は解を提示すれることに特別な意味はない．A1 が観測対象経路となべきではない．そこで，提示解の候補となった解の利り，(1,0)が調べられる（どの座標についても利用可能

用可能確率を求め，0.5 以上であればその解を提示し，確率が等しいときにはスタート座標に近い座標の観測

そうでなければ提示できる解が無いと返す．

を行うものとする）．そして(1,0)に障害物がないとい解に利用する事実を f1 , f 2 ,⋅ ⋅ ⋅, f n としたとき，解の利う事実がキャッシュされる．次の探索でも A1 が選択さ用可能な確率は以下のようにして得られる．

4

れ，(1,0)が調べられて(1,0)に障害物があるという事実

では， A4 の経路が選択され(1,3), (2,3)について順に観がキャッシュされる．

測される．その後， A5 の経路が新たな観測の対象となり観測が進んでいく．

経路 A1 に障害物があると観測されたので，次に経路A2 が選択され，(0,1)が調べられる．ここで(0,1)に障経路 A3 発見後の観測は以上のように行われるが，変害物が無いという事実がキャッシュされる．次の探索化率によっては A4 , A5 と観測対象が変わっていく途

でも A2 が選択され，(1,1)が調べられて，障害物がある

中で A3 の信頼度が下がり，そちらの再観測に移る場合という事実がキャッシュされる．

もある．

次からの探索では A1 ， A2 の経路が利用できないの

4 実験
4.1 実験方法

で経路 A3 が選択される．そして順に(0,2), (1,2), (2,2)に障害物が無いという事実がキャッシュされる．
これまでの観測により A3 上の座標が全て利用可能

動的迷路を用いたシミュレーションを行い，FIFOであり，かつ質の良い解とわかったため， A3 という確方式，S=E 方式と提案方式との比較を行った．なお，かな解が提示されるようになる．

迷路内の障害物の割合を 20％とし，(0,0)をスタート座標，その対角の位置にある座標をゴール座標とした．
FIFO(first in first out)方式 最も古い事実から観測を行う方式．キャッシュしてからの経過時間のみを考慮するので観測スコアは以下のように計算する．
S FIFO ( A) = 1 − R ( A)

S=E 方式

最も重要なものから観測を行う方式．提示解において重要となる要素は期待値であるので観測スコアは以下のようになる．

SE = E
S=E×(1−Ｒ)提案方式

図 2 観測対象となる経路解の期待値と信頼度をともに考慮する方式．障害物の変化が速い場合にはすでに得られている解の再観測を行い，遅い場合には他の経これ以後の観測は障害物の変化の速さによって変わ路を探索する．ってくる．
変化の速い時

観測結果によるキャッシュを用いて提示解を導出し，観測間隔時間と比べて障害物の変化するスピードが速その提示解についての評価を行う．評価基準としては

いときには経路 A3 の信頼度が小さな値となるため，観測すべき経路として選択され続ける．信頼度 R = 0 とz成功率：提示解が正しい解である割合

すると観測スコアはz最適率：提示解がその時点での最適解である割合

S = E × (1 − R )= E × (1 − 0)を用いた．
ひとつの動的迷路に対して１万回の観測をし，解提=E示を行う．これを５つの動的迷路に対して行う．となり， A3 の再観測が行われる．
変化の速い時4.2

障害物の変化が遅いときには経路 A3 の信頼度は１に変化の速さによる違い変化の速さを表すものとして変化率を用いる．変化近い値となる．信頼度 R = 1 とすると観測スコアは率は一観測時間の間に障害物が移動する確率とする．

S = E × (1 − R )= E × (1 − 1)

障害物の存在時間の平均を µ ，観測にかかる時間を tとしたとき，=0
変化率 :となり，再観測は不必要になる．そこで観測範囲が拡大されることになり，オープンリストに残っている他と定義する．のノードが取り出されて探索が進められる．この場合

5t2µS=E×(1−Ｒ)提案方式

仮に問題空間を与える情報源の平均更新時間が全て成功率では S=E としたとき１日であるとすれば，約 6.94 秒に一度観測を行う場合と比べ劣ってはいるが，比較的近い結果を得ている．に変化率は 1.0E-4 となる．

最適率では，３方式の中で最も良い結果といえる．これは発見解が信頼できるときに，別の解を探すような4.3観測を行うため，FIFO 方式のように成功率と最適率

実験結果

図 3 に 8×8 の動的迷路における成功率，図 4 に同に大きな差を生じさせないものと考えられる．

動的迷路における最適率のグラフを示す．
変化率が 0.1 まで増加すると３方式とも同じ値に収束している．これはどの方式も変化に全く対応できず，解提示を行えないからである．

5

おわりに本研究では動的迷路問題の解決のため，迷路のどの座標の状態を調べるかという観測対象の決定に注目し，信頼度，期待値を用いることで観測対象の決定を行った．提案方式の特性として，FIFO 方式に比べて変化の増大に対応した経路探索を行うことができ，ま図 3 8×8 の動的迷路における成功率

た S=E 方式に比べて変化の遅い場合でも最適解を得られることが分かった．
WWW 情報源を問題空間とする問題解決として，複数の WWW 情報源を組み合せて利用する事で情報の利用価値を高めるという WWW 情報統合等が考えられる．WWW 情報統合等で大量のユーザを想定した場合，通信路負荷が大きな問題となるように思われる．
効率的な観測を行う意義は単に動的変化に対応するのみでなく，不必要な観測を行わないことに繋げる事ができ，通信路負荷対策にも利用できる可能性があるように思われる．
今後の課題として，信頼度，期待値以外の効率良い

図 4 8×8 の動的迷路における最適率観測を決定するための要素の導入，またシミュレーシ
ョンではなく WWW 情報統合等，実在する WWW 情FIFO 方式z

報源を熱かった問題解決への応用が必要である．

変化率が高いとすぐに提示解の精度が落ちる
全ての事実を取得している間に迷路が変わっ文献ており，誤った解を提示しやすくなっているz[1] 北村泰彦，野田知哉，辰巳昭治．動的情報メディ最適率と成功率が一致している

エータのための知的情報収集手法，電子情報通信学

多くの事実を集めた中から解提示を行うので

会論文誌 D-I, J84-D-I(8):1256-1265, 2001.

解が正しいときには最適となる[2] 北村泰彦, 寺西憲一, 辰巳昭治, “マルチエージェ

S=E 方式z

変化率が高くても精度は比較的悪くならない

ント実時間探索における組織化とその評価 ,” 人工

提示解が観測対象となり，その再観測を行うの知能学会誌, 11(3):470-477, 1996.
[3]で誤った解を提示する可能性が低くなる
zR.E.

Korf,

“Real-time-heuristicsearch,”

Artificial Intelligence,42(2-3):189-211,1990.

最適率と成功率に差が見られる[4] Toru Ishida, ``Real-Time Bidirectional Search:

発見解の再観測に従事するため，迷路の変化によってもっと良い解が存在するようになってCoordinated

いたとしてもそちらを探すような観測を行わ

Situations,''

IEEE

Transactions

on

ないので正しい解を得られるが質が悪くなり

AnalysisandMachineIntelligence,やすい

18(6):617-628, 1996.

6

ProblemSolvingin

Uncertain
Pattern