■

書き残してた部分を。本題のARA*について。
f( )=g( ) +ε*h( )。係数εの値によって探索速度と経路精度の調整ができる。得られる経路の精度は最悪でも本来の最短路のε倍に抑えられる。

ARA*はこの性質を利用して、最初に大きい係数εで素早く初期経路を見つけて、その後に次第にεを小さくしていくことによって経路を改良していく手法。

特徴っぽい部分。

• 各探索サイクルでεの値が変化しても、既に展開されたノードのg()の値は変化しないから以前に展開されたノードは再利用できる。
• A*では、以前展開したノードが再度展開、記録されていたg()の値より新しいg()の方が小さかった場合、g()を置き換えて、再度OPENリストに入れる操作が必要だった。これは最短経路を得るために必要な操作であって、最悪でも経路長ε倍って条件を満たすためには必要ない。よって、g()を置き換える代わりに、INCONSリスト(inconsistency)ってのに突っ込んでおいて次のサイクルで処理させる。

主に探索→実行がReal-Timeで必要とされる、ロボットのMotion Planningなんかが想定されてるんだろうけど、要するに動き出すまでの探索時間を短縮することが目的なわけで、素のA*より初期の探索に時間がかからず動き始ることができるって所が利点のはず。
比較対照としては、裏でA*の探索させとく間に、ゴールの方向に歩かせといて探索が終わったら現在地との間で補完する。ってのだろうけど。
これと比較してARA*のメリットがそれほどないんでは？ってのが。まず初期探索のコストの問題。素のA*よりは速いにしてもやっぱり重い処理だと思う。
次にεが大きいと始点に近い部分の解が甘い(はず)なのでεを減らしながら経路を補完してくと、ふらふらした動きになる気が。

読む人いるんだろうか、これ。どうもうまくまとまらない。もう少し読みやすくならないものか。