■

さらに続き。A*についてが長くなりすぎた。
今まで書いてきたのは静的な探索(off-line Search)について。
この用途ではほぼA*が最適ってことで間違いない。
次に動的な環境での探索について。静的な探索では経路を探索中に探索空間が変化しないことを仮定していた。要するに探索が終了してから得られた経路に沿って実際に動き出していた。
仮に移動中も探索空間が変化する中で最適な経路を得ようとすると、変化を認識するたびにA*による再探索を行う必要がある。で、この最探索の時間が許容できるか、ってのが問題になってくる。A*はそれぼど軽い処理ではないので探索が終了するまで多少時間がかかる。変化を認識してから探索が終わるまで、いちいちその場で止まってるのは致命的。
まあ人間でも予定外の出来事が起こったら次の行動まで多少の思考時間が必要だろうけど。
ともかくこの再探索にかかる時間をできるだけ減らしたい。で、どうするか。

後はまとまってないので適当にメモ書き。
あとユーザーの操作に対する応答性の問題(ゲームの場合)結局入力に対してはそれっぽい動かしといて後から計算されて得られた経路と補完させればいいか。ゲームの場合、厳密に「最適」であることよりも「最適っぽくみえて気持ちよく操作できる」ことが大事なんだろう、多分。

前回の探索情報を経路の再計算のときに利用するのがIncremental Search。代表例LPA*。ただこれは上記の静的な探索の側の気が。経路に沿って移動中に探索空間が変化することは想定されてないと思うし。

探索にかかる時間が常に一定なのがReal-time Search
代表例RTA*(Real-time A*)、LRTA*(Learning Real-time A*)。ただこれA*なのかなぁ…別に得られる経路が最適ってわけじゃないし。あんま関係なさげ。

D*(Dynamic A*)
他の経路探索アルゴリズムが探索空間に関する完全な情報を持っていることを仮定しているのに対して、D*は得られる探索空間の情報が不完全である、という下での探索を行う。センサー付きのロボット等。得られた情報によって経路の修正を行う。最近の論文ではglobal constraintを考慮に入れたCD*(constraint D*)がある。まだ内容さっぱり理解できないけど。