■

前、書いてたのをもう少し突っ込んで調べてみた。
・LPA*(Lifelong Planning A*) 別名Incremental A*。
Incremental Searchってのは以前の探索結果を利用して再計算の量を減らす手法の名前らしい。この手法をA*に適用したものがLPA*。以前通れた場所が通れなくなったり、みたいな環境の変化に対して、以前の探索結果を再利用して経路を探索する。

http://www.cc.gatech.edu/fac/Sven.Koenig/fastreplanning.html
Javaアプレットによるデモがあるので見るのがわかりやすい。確かに環境が変化した時の再計算量がかなり減ってる。

以下、LPA*の欠点。ざっと眺めただけなんで間違ってるかも。

• 以前の探索結果を保存しとく分のメモリが必要
• 環境が変化するたびに一々探索結果を更新しないといけない。A*なら必要になったら再探索すればいいだけ。
• 再計算時のスタート地点とゴール地点が同じことが前提？リアルタイムで進行してると既に以前の探索結果にそって移動開始してるわけで…現在地からゴールまでの最短路じゃないと。

結論。使い道が思いつかない。これ以上調べるのはやめて他をあたってみよう。

追記：
LPA*をゲームに使ってる例はあるのか？と思って調べてみた。
http://www.gamedev.net/community/forums/topic.asp?topic_id=185572
A*系のアルゴリズムについての情報がGoogleで探しにくいのはどうにかならんのか…