Real-Time Search (Past)

Key Members

石田 亨, (新保 仁)

Project Objective

初期のプランニング・アルゴリズムは, オフライン探索が主流であった. しかし1980年代の中頃から, 自律移動ロボットや実時間システムのための プランニングに興味が集まるにつれて, 定数時間の探索結果を基に判断を 下し, 行動しながら探索を続ける実時間探索が研究されるようになった.

オフライン探索では, 計画が完全に求まるまで問題空間の展開を続ける. 問題 空間は実世界の完全なモデルであるという仮定をおくため, 長時間を探索に費やしても, 得られた計画は有効である. これに対して実時間探索では, 定数時間の探索を行ない, その結果得られた判断を物 理的世界にコミット(即ち実行)する. この枠組は, 以下の新たな応用の可能性を開くものである.

このように実時間探索は, 実世界のモデル化が可能であるという 古典的探索の枠組の中に留まりながらも, 未知あるいは刻々 変化する実世界での問題解決に向けて一歩を踏み出したものと言える.

Research Results

古典的な探索では完全な行動計画を実行前に求めるが, 実時間探索では定数時間の 探索を行ない, 得られた部分的な計画を直ちに実行する. この計画-実行サイク ルを繰り返すことを通じて経験を蓄積し最終的に目標に到達する. 我々はこの実時間探索を, 自立エージェントの問題解決に適するよう拡張しよ うと試みた.

1.
移動目標探索: 動的環境での行動プランニング

問題解決過程で問題そのものは変化しな いことを前提としてきた.一方,探索アルゴリズムに基礎を置くプラニング分野で は,動的に変化する環境を対象とする研究が盛んに行なわれていた. 探索アルゴリズムが, その実行過程で, 問題そのものが変化する場合を 取り扱うことができれば, 動的環境でのプラニング研究に寄与するところが 大きいと考えた.

そこで第一歩として, 問題解決過程で目標が変化する場合を取り上げ, 移動する目標を追跡する移動目標探索(MTS: Moving Target Search)アルゴリズムを提案した. MTSでは目標が探索実行中に移動するため, 指数オーダの時間を 必要とするオフライン探索を用いることができない. そこで実時間探索を 拡張するアプローチをとった. MTSの実行例を図16に示す. MTSアルゴリズムは完全(completeness)である. 即ち,もし移動する目標よりも追跡する問題解 決器の速度が大きければ, そして問題空間が有限で目標に到達する経路が 存在するならば, たとえどのような形状の問題空間であっても, 最終的に問題解決器 は目標に到達する [1,2,3,5].

 

 


図 15: MTSの実行例

2.
実時間両方向探索: 動的環境での協調問題解決

次に実時間探索に基づく両方向探索を考えた. 実時間両方向探索では, 初期状態と目標状態から出発した 2つの問題解決器が, 常に他方の問題解決器を目指して移動する. このため, BHFFA等のオフライン探索に基づくアルゴリズム とは異なり, 協調に要する計算コストが定数時間で抑えられる. 探索の先端(search frontier)が広がる心配がないからである. 反面,定数時間の探索結果を基に判断をコミットするため,無駄な移動が生じ易 いという欠点がある.

我々はまず, 集中制御と分散制御による2種の実時間両方向 探索アルゴリズムを提案した. また実時間単/両方向探索の 性能測定を, 典型的な例題である迷路と15パズルを用いて行った. 得られた結果は興味深い. 実時間両方向探索は単方向探索に比べ, 迷路では 移動回数を増大させてしまうものの, 15パズルでは逆にこれを減少させる. 問題に依存したこの振舞いの原因は, 両方向化による問題空間の推定地形の変 化にあることが分かった. 実験を通じて, 複数の問題解決器の存在が問題空間を変化さ せること, 及び問題空間を決定す る問題解決組織の重要性が理解された [4,7,8].

  

  
図 16: LRTA* と εδ-searchの性能比較

3.
1#12#2-探索: 学習効率の改善

LRTA*をはじめとする実時間探索アルゴリズムのもう一つの特徴は, 問題解決を繰り返すと最適解に収束するという 学習機能にある. それにもかかわらず, 実時間探索に関する議論は, 全て初回の 問題解決に終始しており, 収束に関する研究はほとんど報告されていなかった. そこで, 初回の問題解決性能ではなく, 2回目以降の学習性能, 収束性能に注目して研究を進めた. 実際, 代表的な実時間探索アルゴリズムであるLRTA*を 繰り返し実行すると, (1) 全ての最適解を追求し続ける, (2) 学習による漸次的な効率改善が保証されない, などの問題があることが分 かった.

上記の問題を解決するため, 我々は2種の実時間 探索アルゴリズムを考案した. 1#1-探索は準最適な解を許容するための ものである. 2#2-探索は上界値を用いて探検(exploration)が過剰とならないよう 制御を行うことを意図している. この上界値は, 初回の問題解決結果から得られ, 下界値と同様に2回目以降の問題解決過程で真の値に近づいていく. 1#1-探索と2#2-探索の有効性を, ランダムに生成された 迷路の例題を用いて実証した [6,9,10]. その結果を図17に示す.

4.
実時間探索の収束性を理論的に考察し, これまで試みられてた証明を整理体系化した [13,15].

上記の研究成果は国際学会誌の招待論文[14]となると共に, 一連の成果をまとめたも のがKluwer Academic Publisherから出版されている [11].

References

1.
Toru Ishida and Richard E. Korf, ``Moving Target Search,'' IJCAI-91, pp. 204-210, 1991.

2.
Toru Ishida, ``Moving Target Search with Intelligence,'' AAAI-92, pp. 525-532, 1992.

3.
石田 亨, ``移動目標探索アルゴリズムとその性能改善,'' 人工知能学会誌, Vol. 8, No. 6, pp. 760-769, 1993.

4.
石田 亨, ``実時間両方向探索の経験,'' 認知科学の発展, Vol. 7, pp. 5-33, 1994.

5.
Toru Ishida and Richard E. Korf, ``Moving-Target Search: A Real-Time Search for Changing Goals,'' IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 17, No. 6, pp. 609-619, 1995.

6.
水野智文, 石田 亨, ``実時間探索の学習特性の評価,'' 人工知能学会誌, Vol. 10, No. 2, pp. 306-313, 1995.

7.
Toru Ishida, ``Two is not Always Better than One: Experiences in Real-Time Bidirectional Search,'' International Conference on Multi-Agent Systems (ICMAS-95), pp. 185-192, 1995.

8.
Toru Ishida, ``Real-Time Bidirectional Search: Coordinated Problem Solving in Uncertain Situations,'' IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, No. 6, pp. 617-628, 1996.

9.
Toru Ishida and Masashi Shimbo, ``Improving the Learning Efficiencies of Realtime Search,'' National Conference on Artificial Intelligence (AAAI-96), pp. 305-310, 1996.

10.
石田 亨, 新保 仁, ``実時間探索による経路学習,'' 人工知能学会誌, Vol. 11, No. 3, pp. 411-419, 1996 (10周年記念論文賞).

11.
Toru Ishida, Real-Time Search for Learning Autonomous Agents, Kluwer Academic Publishers, 1997.

12.
松原 繁夫, 石田 亨, ``実時間探索に副目標生成機能を組み込んだ実時間プランニング,'' 人工知能学会誌, Vol. 12, No. 1, pp. 90-99, 1997.

13.
新保 仁, 石田 亨, ``実時間探索の収束性について,'' 人工知能学会誌, Vol. 13, No. 4, pp. 631-638, 1998.

14.
Toru Ishida, ``Real-Time Search for Autonomous Agents and Multi-Agent Systems,'' Journal of Autonomous Agents and Multi-Agent Systems, Invited Paper, Kluwer Academic Publishers, Vol. 1, pp. 139-167, 1998.

15.
新保 仁, 石田 亨, ``Moving-Target Search の完全性: 評価関数が一貫性を欠く場合'' 人工知能学会誌, Vol. 14, no. 2, pp. 342-348, 1999.



Top
Page
Free
Software
Publications Members Location Related
Servers