実時間探索 (Real-Time Search)

Presentation on theme: "実時間探索 (Real-Time Search)"— Presentation transcript:

1 実時間探索 (Real-Time Search)
認知システム論　探索（4） 先を読んで知的な行動を選択するエージェント 実時間探索 (Real-Time Search) 　実時間探索　 　RTA*アルゴリズム 　LRTA*アルゴリズム 　エージェントは，環境の中に存在し，センサーによって環境の情報を知覚し，知能によって行動を決定し，アクチュエータによってその行動を実行する．前回までの探索エージェント（探索アルゴリズム）の設計においては，原則として環境の情報が事前にすべて既知であることを仮定していた．すなわち，どういう状態でどういう行動をとると状態がどう遷移するのかをすべて既知としていた．これは，エージェントが，環境から切り離された状態で行動の決定を行うことができることを意味している．このような設定の探索問題を，オフライン探索問題という． 　それに対し，環境の情報が事前には未知であるときの探索問題をオンライン探索問題という．オンライン探索の特徴は，環境の情報を逐次的に取得しつつ，行動の決定（計算）と実際の行動（実行）を交互に行うことを繰り返しながら目標状態に到達することを目指す点にある．特に，一定時間内にすばやく行動を決定する必要がある場合の探索を実時間探索(real-time search)という．今回は，その基礎となるアルゴリズムであるRTA*及びそれに環境を学習する機能を付加したアルゴリズムであるLRTA*について学ぶ．

2 準備：探索エージェント 知覚 (percepts) エージェント 環 境 意思決定(decision) 行為(action) 手，足
とるべき行為を 決定する 知覚 (percepts) エージェント センサー 目，耳 問題解決器 知能 環　境 意思決定(decision) 　すでに学んだように，人工知能技術が開発するエージェントは，環境の中に置かれ，環境から得られる情報を知覚し，その情報に基づいて自らのとるべき行為を決定し，そして実際にその行為を実行して環境に影響を与える，というサイクルを繰り返すものである．特に，探索によって問題解決を行うエージェントの場合，環境を構成する世界は探索問題としてモデル化され，エージェントは，探索アルゴリズムによって，自らのとるべき行動を決定する． 行為(action) アクチュエータ 手，足

3 １．実時間探索 (1/3) 探 索 実 行 探 索 実 行 探 索 実 行 探 索 実 行
これまで学んだ探索（オフライン探索）は， 時間をかけて解を見つけた後に実行する 探　　　索 実　行 時間 実時間探索（オンライン探索）は， 一定時間内の先読み探索と実行を交互に繰り返す 　今回学ぶ「オンライン探索」に対して，これまで学んだ探索を「オフライン探索」という．「オフライン」(off-line)という言葉は，エージェントが環境から切り離されて問題解決をする状況を表現している．実際，オフライン探索においては，環境に関するすべての情報が，事前にエージェントに与えられる．エージェントは十分に時間をかけて探索を行い，（できれば最適な）解を見つけ，その後に，その解を実行する．すなわち，探索は１度だけ徹底的に行われ，その後，初期状態から目標状態に至る（最適）解を構成する一連の行為が計画的に実行される． 　それに対して，「オンライン」(online)という言葉は，エージェントと環境が接続されており，両者が相互作用し得る状況を表現している．実際，オンライン探索においては，環境に関する情報のすべてが事前にエージェントに与えられるのではなく，エージェントと環境が相互作用することによって，環境情報が少しずつエージェントに開示されることを想定している．そして，現在までに知ることができた部分的な環境情報に基づく局所的な先読み探索と，その結果得られる不完全な解から決定される行為の実行を交互に繰り返す．したがって，１つ１つの行為はその場その場で動的に決定されるものであり，事前に計画的に定まっているものではない．特に，局所的な先読み探索に使用できる時間が（比較的小さな）一定時間であるようなオンライン探索を「実時間探索」(real-time search)という． 探　索 実　 行 探　索 実　行 探　索 実　行 一定時間内 一定時間内 一定時間内

4 ミニミニ探索によって，一定時間の間，先読みをし，行動を決定
実時間探索(2/3) ミニミニ探索によって，一定時間の間，先読みをし，行動を決定 ヒューリスティック関数 h の値 7 5 1 4 8 12 b c d 3 16 12 2 スタート 8 a e 8 5 3 3 ゴール 　実時間探索が行う一定時間の先読みをミニミニ探索(minimin search)という．「ミニミニ」(mini-min)という言葉は，「最小値」(minimum)のうちからさらに最小値を求める操作が，数式で書くと min min となることから付けられている．「ゲーム理論」などの良く知られる学問分野では，同様な由来を持つ言葉として，「ミニマックス」(mini-max)などが知られている． 　ミニミニ探索は，基本的には，探索の深さを一定の値に制限した深さ優先探索である．探索木の先端ノード（葉ノード）n には，Ａ*アルゴリズムと同様に，f(n) = g(n) + h(n) によって評価値 f(n) を与える．h(n) はヒューリスティック関数であり，ノードn から目標状態までの最短経路のコストの見積り（推定コスト）を表す．Ａ*アルゴリズムとやや異なる点は，g(n) が表すのはエージェントの「現在の状態」からノード n までの経路コストであって，Ａ*アルゴリズムのときのような「初期状態」からのコストではないことである．これは，実時間探索では，探索と実行を交互に行いながら状態が変化していくので，常に現在の状態を初期状態と考えて探索を行う必要があるからである． 　ミニミニ探索は，ノードの評価値を探索木の親ノードに伝播する．親ノードは，自分のすべての子ノードの評価値のうちの最小値を自分自身に対する評価とし，それをさらに自分の親に伝播する．このプロセスを繰り返すと，いつかは探索木の先端ノードの評価値の最小値が探索木の根ノード（すなわち，現在の状態）に伝播されることとなる．エージェントは，自分の現在の状態を表す根ノードの子ノードのうち，最小の評価値を伝播してきたものを選択して，その状態に遷移するような行為を実行する． 　（このスライドはアニメーションになっている．） 4 14 11 g h f 11 2 4 6 5 3

5 実時間探索(3/3) 最適性はない：最適な行動を探索できない リアルタイム性：迅速に行動を選択できる
環境適応性：未知の環境，動的に変化する環境に適している 未経験の行動をとる（探索空間を探査する）することによって，現在の状態の周辺の情報がわかってくる 　実時間探索には，次のような特徴がある． 　(1) 最適性がない． 　事前に環境の全情報を与えられないので，最適解を求めることができない． 　(2) リアルタイム性がある． 　局所的な先読みを（短い）一定時間に限定することによって，次に行うべき行為を迅速に決定することができる． 　(3) 環境適応性がある． 　オフライン探索の場合，事前に最適解を計算したとしても，後にそれを実行する段階で環境が変化していたら，その解は役に立たないかもしれない．たとえば，環境の変化の例として，オペレータのコストがある時点で変化することなどもあり得る．実時間探索は，オンライン探索なので，環境が変化しても，その都度，新しい情報を取得しながら探索することができるので，オフライン探索よりは環境の変化に追従しやすいといえる．また，全く未知の環境においても行為を決定することができる．

6 ２．RTA*アルゴリズム(1/4) Real-Time Heuristic Search x
Step １．現在の状態xの各隣接状態nに対して， 以下の関数f(n)を計算する． ただし，g(x,n)はxからnへのコストとする． 　　　　f(n) = g(x,n) + h(n) h=7 f=10 3 h=8 　実時間探索アルゴリズムの基礎的なものとして，RTA*アルゴリズムを学ぼう．この名前の「RT」は Real-Time の頭文字であり，A*はすでに学んだオフライン探索のA*アルゴリズムから取っている． 　RTA*アルゴリズムは，A*アルゴリズムと同様に，ノード n から目標状態に至る最短経路コストの見積り（推定コスト）を表すh(n) を用いる． 各 h(n) の「初期値」は，A*アルゴリズムと同様に，システム設計者または利用者によって適切に与えられているものとするが，初期値以外の値に関して，アルゴリズムの実行が進むにつれて，h(n) の値が動的に変更されていく点が異なる．具体的には，つぎに述べる３つのステップを繰り返す．ミニミニ探索によって生成した探索木の先端（葉）ノードのそれぞれがノード n である．ただし，簡単のために，以下では，ミニミニ探索による先読みは，１ステップ先までと仮定する．すなわち，現在のノードに隣接したノードのそれぞれをノード n とする． 　第１ステップでは，現在の状態 x の各隣接状態 n に対して，x から n へ進むオペレータ（辺）のコスト g(x, n)と状態 n から目標状態までの見積りコスト h(n) の和を求め，f(n) とする．この f(n) の値は，現在の状態 x から隣接ノードn を経由して目標状態へ至る最短経路コストの見積りである． 　このスライドの例では，２通りの n について，f = = 10 と f = = 9 を計算している． x h=5 4 簡単のため， 先読みは１ステップ先まで と仮定する f=9

7 最小の f 値を持つノードへ進む前に もとのノードに戻ってくるときのために h の値を更新する
RTA*アルゴリズム(2/4) Step ２．h(x)の値を以下のように更新する． 　　　　h(x) ← ２番目に小さいf(n) ２番目に小さいf(n) ２番目に小さいf(n) h=7 h=7 f=10 3 3 f=10 h=8 h=10 x x h=5 h=5 4 4 　第２ステップでは，第１ステップで求めた f(n) のうちで，「２番目に小さいもの」の値を，現在状態 x のヒューリスティクス値 h(x) とする． h(x)は，本来，x から目標状態までの最短経路コストの見積りであるから， f(n) のうちの「最小値」とすべきものである．実際，後に学ぶ LRTA* アルゴリズムではそのようにする．しかし，RTA*アルゴリズムでは， ２番目に小さいものとするのである．その理由は，第３ステップを見てから説明する． 　この例では，f = 9 が最小値， f = 10 が２番目に小さい値なので，h(x) = 8 を更新して， h(x) = 10 としている． f=9 f=9 最小のf(n) 最小の f 値を持つノードへ進む前に もとのノードに戻ってくるときのために h の値を更新する

8 f はもう不要． 後戻りするときのコストは，4+10=14 となる．
RTA*アルゴリズム(3/4) Step ３．最小のf(n)を与える状態nに遷移する． 候補が複数存在するときはランダムに選択する． h=7 h=7 3 f=10 3 h=10 h=10 x x 最小のf(n) h=5 h=5 4 4 f=9 　第３ステップは，「実行」ステップである．エージェントは，第１ステップで求めた f(n) のうちで最小値を与える状態 n に遷移するような行為を行う．（候補が複数存在するときはランダムに選択する．）そして，状態 n をあらためて現在状態 x とみなして，第１ステップからの処理を繰り返す． 　この例では，f = 9 を与える状態に遷移している． 　第２ステップで， f(n) のうちで「２番目に小さいもの」の値を h(x) とした理由は，次ステップ以降で，エージェントが状態 x に後戻りしたときの準備である．そのときには，今度は「２番目に小さいもの」の方に遷移させるためである．この例では，もしエージェントがもとの状態に戻るなら，今度はさきほど f = 10 を与えたノードに進むことになるので，その見積コストは，f = = 14 になる． f はもう不要． 後戻りするときのコストは，4+10=14 となる．

9 RTA*アルゴリズム(4/4) 準最適解 11 7 5 9 1 9 9 4 8 10 b c d 3 15 2 14 8 11 8 a 5
hの値 準最適解 11 7 5 9 1 9 9 4 8 10 b c d 3 15 2 14 8 11 8 a 5 3 3 e 8 11 目標状態 初期状態 5 f g h 11 2 4 6 5 3 　このスライドは，エージェントが，RTA*を用いて初期状態から目標状態まで進む様子をアニメーションで示している．得られた解 a→b→c→g→h→d→e は最適解ではないことに注意しよう．

10 RTA*の計算量 空間計算量：移動回数に対して線形 訪問済みの状態のリスト、miniminは深さ優先探索 時間計算量：移動回数に対して線形
　　　 探索の深さが定数、一回の移動のための探索も定数 　RTA*アルゴリズムは，空間計算量も時間計算量も，移動回数に対して線形となる． 　空間計算量が線形である理由は，必要とする記憶が，訪問済みの状態ごとの h の値だけで良いことと，ミニミニ探索は深さ優先探索であることによる． 　時間計算量が線形である理由は，１回の移動ごとに，探索時間が一定であることによる．

11 RTA*の完全性(1/3) 定理 RTA*の完全性 状態空間が有限 経路コストが正 ヒューリスティック値が有限
あらゆる状態から目標状態へ到達可能 必ず解を発見する 　RTA*アルゴリズムは，完全性の性質を持っている．すなわち，状態空間が有限で，経路コストが正で，ヒューリスティック値(h)が有限で，かつ，あらゆる状態から目標状態へ到達可能ならば，RTA*ルゴリズムは必ず解を発見する．

12 RTA*の完全性 (2/3) 例外 s s g 3 2 1 g 状態空間が有限でない 目標状態へ到達可能でない 1 1 1 1 1 1
g s 1 2 1 s 1 1 　１つ前のスライドで，完全性の条件が４つ示されていた．それらの条件が１つでも成り立たないと，完全性が失われることを見ておこう．（このスライドと次のスライドは，アニメーションになっている．） 　状態空間が有限でない場合は，この１つめの例のように，解を発見できない反例が存在する． 　目標状態へ到達可能でない場合は，２つめの例のように，間違った選択に基づく行為を取り消すことができないので，解を発見できなくなる可能性が生じる． 1 g 1

13 RTA*の完全性(3/3) 例外 s g s g 1 2 ∞ 経路コストが正でない ヒューリスティック値が有限でない
2 1 ヒューリスティック値が有限でない s g ∞ 　経路コストが正でない場合には，３つめの例のように，サイクルを何周しても h の値が増加せず，このサイクルから抜け出せない例が存在する．（コスト 0 の部分を 1 に変更すると，このサイクルを抜け出ることができる．） 　ヒューリスティック値に無限大（∞）を許すと，４つめの例のように，目標状態へ至る経路コストが常に無限大となって解を発見できない例を作ることができる．

14 RTA*の性能評価(1/3) n-パズル ５ ４ ８ ６ １ ２ ７ ３ ５ ４ ８ ６ １ ２ ７ ３ 初期状態 １ ２ ３ ８ ４ ５
目標状態 ５ ４ ８ ６ １ ２ ７ ３ 　スライディングタイルパズル（ｎ-パズル：ｎ＝８，１５，２４）を例題として，RTA*アルゴリズムの性能を調べてみる．ただし，推定コスト(h)は，各タイルの正しい位置までのマンハッタン距離の和とする．（「マンハッタン距離」については，前回のA*アルゴリズムのスライドを参照のこと．） 推定コスト： 各タイルの正しい位置までのマンハッタン距離の和

15 RTA*の性能評価(2/3) 最適解の長さ 8 puzzle ： 22 15 puzzle ： 53 24 puzzle ： 100程度
1000 最適解の長さ 8 puzzle ： 22 15 puzzle ： 53 24 puzzle ： 100程度 800 24 puzzle 発見した解の長さ 600 Solution Length 400 15 puzzle 200 8 puzzle 　最適解の長さは，８パズルで２２，１５パズルで５３である．ミニミニ探索の先読みの深さを深くしていくと，ときどき例外があるものの，発見する解の長さは短くなり，最適解の長さに近づいていく． 5 10 15 20 25 Search Horizon 先読みの深さ

16 RTA*の性能評価(3/3) 計算と実行のトレードオフ スライディングタイルパズルの場合
ミニミニ探索を深くすると１回の移動のための計算量は増大、移動回数は減少 最適な探索の深さは問題に依存する スライディングタイルパズルの場合 実行時間(ミニミニ探索＋移動)は探索の過程で生成した状態数に比例 ミニミニ探索の最適な深さは 8パズルが1、15パズル・24パズルが2 実際の実行時間はそれぞれ 0.1秒、0.5秒、2.5秒以下（20MHz） 　しかし，ミニミニ探索（先読み）の深さを深くすると，解の長さ（すなわち移動回数）は減少するが，１回の状態遷移のための計算量が増大するというトレードオフが生じる．したがって，移動回数が少ないからと言って，目標状態に到達するのに要する時間が少ないわけではない．その意味でのミニミニ探索の最適な探索の深さは問題に依存する． 　スライディングタイルパズルの場合，ミニミニ探索＋移動に要する全体の実行時間は，探索の過程で生成した状態数に比例すると仮定し，実験的に最適な深さを調べてみると，最適な深さは，８パズルでは１，１５パズルと２４パズルでは２となる．実際の実行時間は数秒以内である．したがって，オフライン探索で最適解を見つけてからまとめて状態遷移をするよりも，高々２ステップ先までの先読みを用いた実時間探索の方が，総合的な意味で性能が高い可能性もある．

17 ３．LRTA*アルゴリズム(1/4) 同じ問題を連続して解く RTA*では… 同じ問題空間、同じ目標状態の集合
Learning RTA* 同じ問題を連続して解く 同じ問題空間、同じ目標状態の集合 訪問済みの状態の推定コスト(h)を次の試行に保持 RTA*では… 問題を一度だけ解く場合には適している 推定コストとして２番目に小さい評価値を格納 hの値が，過大評価となってしまう 　次に，RTA*をやや修正したLRTA* (Learning RTA*)アルゴリズムについて学ぶ． 　人工知能の分野では，エージェントに対して，全く同じ問題を何度も解かせることをさせる場合がある．エージェントが賢い人間ならば，これはつまらないことで，人間は２回目には簡単に問題を解いてしまう．それは人間の学習能力が高いからである．しかし，エージェントが他の動物なら，この実験は，その動物の学習能力を調べるのに意義がある．心理学の分野の実験で，マウスを使って，迷路をスタートからゴールまでたどらせるものがある．マウスは，最初は試行錯誤によって，ゴールにたどり着く．１度ゴールに到達した経験にもかかわらず，マウスは同じ迷路の２度目の試行においても試行錯誤をしてゴールに到達する．しかし，このような試行を何度も繰り返すうちに，マウスはいつか，迷わずにゴールに到達することができるようになる．これは，マウスがこの問題を「学習」できたことを表している． 　また，エージェントのかわりに人間を考えた場合であっても，人間は２回目以降には１回目と異なる選択を行ったりして，もっと質の良い解を見つけたりするかもしれないので，これは意義のある問題設定である． 　そこで，実時間探索が終了したときに，アルゴリズムの中で得られた h 関数の値を保存し，次回に同じ問題を解くときに，その値を各 h の初期値として用いることにしよう． 　しかし，RTA*は，推定コストとして「２番目に小さい」評価値を h に格納するので，h の値は正しい推定コストよりも過大な値となってしまう．したがって，RTA*は，問題を１度だけ解く場合には適しているのだが，何度も解く場合には適していないと考えられる．

18 LRTA*アルゴリズム(2/4) １．現在の状態xの各隣接状態nに対して、以下の関数f(n)を計算する。ただし、g(x,n)はxからx’へのコスト。 　　　　f(n) = g(x,n) + h(n) ２．h(x)の値を以下のように更新する。 　　　　h(x) ← min f(n) ３．最小のf(n)を与える状態nに遷移する。 　　（候補が複数存在するときはランダムに選択する） n 　それに対し，LRTA*アルゴリズムは，何度も同じ問題を解くうちに，正しい推定コストを「学習」する能力を持っている．その具体的な内容は，このスライドにあるように，第２ステップだけがRTA*と異なっている． 　RTA*では，「２番目に小さい値」をh(x)に格納していたのに対して，LRTA*は，すなおに「最小値」をh(x)に格納する．このことによって，h(x)の値をRTA*よりも正確に学習することができるのである．

19 LRTA*アルゴリズム(3/4) a b c d a b c d 6 7 5 1 1 5 1 1 1 2 3 5 1 1 5 1 1 1
　RTA*とLRTA*の動作の違いをこのスライド（アニメーション）で理解しよう． 　RTA*の例では，エージェントは，初期状態 b から，h(b)を 1 から 6 に変更して c に移動し，次に， h(c)を 1 から 7 に変更して d に移動する． 　LRTA*の例では，エージェントは，初期状態 b から，h(b)を 1 から 2 に変更して c に移動し，次に， h(c)を 1 から 3 に変更して b に移動する．（この後どうなるか，続けてみよ．） 1 1 1 a b c d

20 LRTA*アルゴリズム(4/4) 完全性 収束性 解が存在すれば必ず発見できる 問題空間が有限 経路コストが正
初期ヒューリスティック値が許容的 あらゆる状態から目標状態へ到達可能 楽観的 　LRTA*の理論的性質をまとめておく． 　まず，RTA*の完全性と同様な条件のもとでの完全性があるので，解が存在すれば必ず発見できる． 　LRTA*の特徴的な性質は「収束性」である．スライドに示した４つの条件が成り立っているとしよう．４つの条件うちの１つに，「初期ヒューリスティック値が許容的」という条件が含まれていることに注意しよう．すなわち，各状態に対する h の初期値が，正しい推定コスト h* を超えないように設定されていなければならない．適切な初期値が設計できなければ，h = 0 とすれば，この条件は満足される． 　これらの条件のもとで，同じ問題を何度も解かせる試行を繰り返すことにより，最適経路上の各状態の推定コスト h は，正確な値 h* に収束する．これは，エージェントがこの問題を最適に解くことができるように学習に成功したことを意味する。実際，いったん，そのように収束すれば，それ以降は，エージェントはその推定コスト h (=h*)を用いたLRTA*アルゴリズムにより，道を間違えることなく，最適経路をたどって目標状態に到達することができるようになるのである． 試行を繰り返すことにより、 最適経路上の各状態の推定コストは正確な値に収束する