D* - 百科事典

D*（「Dスターアイ」）は以下の3つの関連する増分検索アルゴリズムのいずれかです：

元のD*は、アンソニー・ステンツによって提案された知識ベースの増分検索アルゴリズムです。
フォーカスD*は、アンソニー・ステンツが提案した知識ベースの増分ヒューリスティック検索アルゴリズムで、A*と元のD*のアイデアを組み合わせています。フォーカスD*は元のD*のさらなる発展から生まれました。
D* Liteは、スヴェン・コニッグとマキシム・リカチャェフが提案した増分ヒューリスティック検索アルゴリズムで、A*とダイナミックSWSF-FPのアイデアを組み合わせたLPA*に基づいています。

これら3つの検索アルゴリズムは同じ仮定ベースのパスプランニング問題を解決します。これは、ロボットが未知の地形で特定の目標座標に進むことを仮定しています。この仮定では、未知の地形の一部について推測を行います（例えば、障害物がないと仮定）。そして、現在の座標から目標座標への最短経路を見つけます。ロボットはその経路に従います。新しい地図情報（例えば、以前に知られていなかった障害物）が観測された場合、その情報を地図に追加し、必要に応じて、現在の座標から目標座標への新しい最短経路を計画します。そして、目標座標に到達するまでこのプロセスを繰り返します。未知の地形を通過する際に、新しい障害物が頻繁に発見されるため、この再計画は速く行う必要があります。増分（ヒューリスティック）検索アルゴリズムは、前の問題の経験を利用して、現在の問題の検索を速めることで、似たような検索問題のシーケンスの検索を高速化します。目標座標が変わらないと仮定すると、これら3つの検索アルゴリズムはA*の繰り返し検索よりも効率的です。

D*とその変種は、モビルロボットと自律車のナビゲーションに広く使用されています。現在のシステムは、通常、元のD*やフォーカスD*ではなくD* Liteに基づいています。実際、ステンツの研究所でも、一部の実装ではD*ではなくD* Liteを使用しています。このようなナビゲーションシステムには、マーズ・ローバー・オプトイユニティとスピリットでテストされたプロトタイプシステムや、カーネギーメロン大学で開発されたDARPA都市挑戦優勝チームのナビゲーションシステムが含まれます。

元のD*は1994年にアンソニー・ステンツによって紹介されました。名前の由来は「ダイナミックA*」であり、アルゴリズムはA*に似ていますが、アーカスコストがアルゴリズムの実行中に変化することがあります。

オペレーション
D*の基本的なオペレーションは以下に示します。

DijkstraのアルゴリズムやA*のように、D*は評価するノードのリスト、つまり「OPENリスト」を維持します。ノードは以下のいくつかの状態のいずれかを持っています：

NEW: 初めてOPENリストに追加されたことを意味します
OPEN: 現在OPENリストに含まれています
CLOSED: OPENリストから削除されました
RAISE: 最後にOPENリストに含まれていた時よりもコストが高いことを意味します
LOWER: 最後にOPENリストに含まれていた時よりもコストが低いことを意味します

= 扩張 =
このアルゴリズムは、OPENリストからノードを選択し、それを評価し、その変更をすべての隣接ノードに伝播し、それらをOPENリストに追加することで動作します。この伝播プロセスは「拡張」と呼ばれます。標準のA*とは異なり、D*は目標ノードから逆方向に検索を開始します。これは、実際にはすべての可能な開始ノードに対してA*の最適経路を計算することを意味します。拡張された各ノードには、ターゲットに向かう次のノードを参照するバックポインタがあり、各ノードはターゲットへの正確なコストを知っています。次に拡張されるのは開始ノードである場合、アルゴリズムが完了し、バックポインタに従って目標に向かう経路を見つけることができます。

= 障害物処理 =
目標経路に障害物が検出された場合、影響を受けたすべてのポイントが再度OPENリストに追加され、この時「RAISE」マークされます。しかし、RAISEDノードのコストが増加する前に、アルゴリズムはその隣接ノードを確認し、ノードのコストを減少させられるかどうかを調べます。もしできない場合、RAISE状態はすべてのノードの後裔に伝播され、これらのノードは評価され、RAISE状態が波のように伝播されます。RAISEDノードが減少できる場合、そのバックポインタが更新され、LOWER状態が隣接ノードに伝播されます。これらのRAISEとLOWER状態の波がD*の核です。

この段階までに、多くの他のポイントが波によって「触れない」ことが防げます。そのため、コストの変更に影響を受けたポイントのみをアルゴリズムが処理します。

= 再度のデッドロック =
この場合、デッドロックを巧妙に回避することはできません。どのポイントも目的地への新しいルートを通じて新しいルートを見つけることができません。そのため、コストの増加を続けます。ルートが有効であるかどうかを通じて目的地に到達できるポイント以外は見つかりません。これにより、新しいルート情報で「到達不可能」とマークされたポイントに対応する2つのLOWER波が発生します。

ポリシーコード


= Expand =


= Check for raise =


キャラクター =


= Focused D* =
名前からも分かるように、フォーカスD*はロボットに向けてRAISEとLOWERの伝播を焦点化するヒューリスティックを使用するD*の拡張です。このようにして、重要な状態のみが更新され、A*が一部のノードのコストを計算するのと同じように処理されます。

= D* Lite =
D* Liteは元のD*やフォーカスD*に基づいていませんが、同じ行動を実現しています。理解しやすく、コードの行数も少なくて済むため、「D* Lite」と名付けられました。パフォーマンス的には、フォーカスD*と同じかそれ以上に優れており、D* Liteは数年前にコニッグとリカチャェフによって紹介されたLifelong Planning A*に基づいています。

最小コスト対現在コスト
D*においては、現在のコストと最小コストの区別が重要です。前者は収集時のみ重要であり、後者はOPENリストのソートに必須です。最小コストを返す関数は、常に現在のポイントへの最も低いコストを示し、それはOPENリストの最初のエントリです。

参考文献
外部リンク
Sven Koenigのウェブページ
Anthony Stentzのウェブページ