D * Liteでパスの方向を定義する

Question

私は現在Sven KoenigのD * Liteアルゴリズムの実装に取り​​組んでいます。 http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf。基本的には、実装を開始する前にすべての詳細を理解しようとしています。アルゴリズムは有向グラフで動作すると思われます。それはPredとSucc関数を定義する方法です。

どのようにグラフの方向を定義し、どのパラメータがグラフの方向を決定するのですか。 gのようないくつかのパラメータの値を使用すべきですか（良い選択ではないようです... の値と一緒にgの値があり、アルゴリズムの更新値）または距離のヒューリスティックな見積もりですか？

Answer 1

D *とD * -liteは両方とも有向グラフと無向グラフで動作します。

グラフはG = (V, E)です。ここで、Vは到達可能な構成（または状態）のリストです。 Eは、頂点間の接続のリストです。有向グラフでは、Eは、ののペアである(u, v)の辺の集合であり、uとvの両方が頂点です。無向グラフでは、Eはのセットであり、順序はである。

無向グラフの計画は、双方向のエッジを持つ有向グラフの計画と同じです。つまり、がエッジの場合(v, u)もエッジになります。

グラフの作成方法はアプリケーションによって異なります。単純なグリッドから順運動学の格子近似のようなもっと複雑な戦略までさまざまです。