D *

D*
は検索アルゴリズムについてです。デジタル音声およびデータプロトコルの仕様については、D-STARを参照してください
。物理量については、特定の検出率を参照してください
。亜原子粒子については、hexaquarkを参照してください
D *(「Dスター」と発音)は、次の3つの関連する増分検索アルゴリズムのいずれかです。
AnthonyStentzによるオリジナルのD * は、情報に基づいたインクリメンタル検索アルゴリズムです。
Focused D * は、A * と元のD *のアイデアを組み合わせた、AnthonyStentzによる情報に基づくインクリメンタルヒューリスティック検索アルゴリズムです。フォーカスされたD *は、元のD *のさらなる開発から生まれました。
D * Liteのによってインクリメンタルヒューリスティックな検索アルゴリズムであるスヴェンケーニッヒ上に構築され、マキシムLikhachev LPA *、のコンバインアイデアことインクリメンタルヒューリスティック探索アルゴリズムA *と動的SWSF-FP。
3つの検索アルゴリズムはすべて、自由空間の仮定による計画を含む、同じ仮定ベースの経路計画の問題を解決します。この場合、ロボットは未知の地形で指定された目標座標に移動する必要が地形の未知の部分について仮定を立て(たとえば、障害物が含まれていない)、これらの仮定の下で現在の座標から目標座標までの最短経路を見つけます。その後、ロボットはパスをたどります。新しい地図情報(これまで知られていなかった障害物など)を観察すると、その情報を地図に追加し、必要に応じて、現在の座標から指定された目標座標への新しい最短経路を再計画します。目標座標に到達するか、目標座標に到達できないと判断するまで、このプロセスを繰り返します。未知の地形を横断するとき、新しい障害物が頻繁に発見される可能性があるため、この再計画は迅速である必要がインクリメンタル(ヒューリスティック)検索アルゴリズムは、以前の問題の経験を使用して現在の問題の検索を高速化することにより、類似した検索問題のシーケンスの検索を高速化します。目標座標が変更されないと仮定すると、3つの検索アルゴリズムはすべて、A *検索を繰り返すよりも効率的です。
D *とその変種は、移動ロボットや自動運転車の ナビゲーションに広く使用されています。現在のシステムは通常、元のD *またはFocusedD *ではなく、D * Liteに基づいています。実際、Stentzのラボでさえ、一部の実装ではD *ではなくD * Liteを使用しています。このようなナビゲーションシステムには、カーネギーメロン大学で開発された火星探査機オポチュニティアンドスピリットでテストされたプロトタイプシステムと、DARPAアーバンチャレンジの入賞作品のナビゲーションシステムが含まれます。
オリジナルのD *は1994年にAnthonyStentzによって導入されました。D*という名前は「動的A *」という用語に由来します。アルゴリズムの実行時にアークコストが変化する可能性があることを除いて、アルゴリズムはA *と同じように動作するためです。
内容
1 操作
1.1 拡張 1.2 障害物の取り扱い 1.3 別のデッドロックが発生します
2 擬似コード
2.1 展開 2.2 レイズを
3 バリアント
3.1 フォーカスされたD * 3.2 D * Lite
4 最小コストと現在のコスト
5 参考文献
6 外部リンク
操作
D *の基本的な操作の概要を以下に示します。
ダイクストラのアルゴリズムやA *と同様に、D *は、「OPENリスト」と呼ばれる評価対象のノードのリストを保持します。ノードは、いくつかの状態のいずれかを持つものとしてマークされます。
NEW、つまりOPENリストに載ったことがない
OPEN、つまり現在OPENリストにあります
CLOSEDは、OPENリストに含まれなくなったことを意味します
RAISEは、そのコストが前回OPENリストにあったときよりも高いことを示します
LOWERは、そのコストが前回OPENリストにあったときよりも低いことを示します
拡張
このアルゴリズムは、OPENリストからノードを繰り返し選択して評価することで機能します。次に、ノードの変更をすべての隣接ノードに伝播し、それらをOPENリストに配置します。この伝播プロセスは「拡張」と呼ばれます。開始から終了までのパスをたどる正規のA *とは対照的に、D *はゴールノードから逆方向に検索することから始まります。拡張された各ノードには、ターゲットにつながる次のノードを参照するバックポインターがあり、各ノードはターゲットへの正確なコストを認識しています。開始ノードが次に展開されるノードである場合、アルゴリズムが実行され、バックポインターをたどるだけで目標へのパスを見つけることができます。
  拡張が進行中です。終了ノード(黄色)はポイントの一番上の行の中央にあり、開始ノードは一番下の行の中央に赤は障害物を示します。黒/青は拡張ノードを示します(明るさはコストを示します)。緑は、展開されているノードを示します。
  拡張が終了しました。パスはシアンで示されます。
障害物の取り扱い
目的のパスに沿って障害物が検出されると、影響を受けるすべてのポイントが再びOPENリストに配置され、今回はRAISEとマークされます。ただし、RAISEDノードのコストが増加する前に、アルゴリズムはその隣接ノードをチェックし、ノードのコストを削減できるかどうかを調べます。そうでない場合、RAISE状態は、ノードのすべての子孫、つまり、バックポインターを持つノードに伝播されます。次に、これらのノードが評価され、RAISE状態が渡されて、ウェーブが形成されます。RAISEDノードを縮小できると、そのバックポインターが更新され、LOWER状態が隣接ノードに渡されます。これらのRAISE状態とLOWER状態の波は、D *の心臓部です。
この時点で、他の一連のポイント全体が波に「触れる」ことが防止されます。したがって、アルゴリズムは、コストの変更によって影響を受けるポイントでのみ機能します。
  障害物が追加され(赤)、ノードがRAISE(黄色)とマークされました。
  拡張が進行中です。黄色はRAISEとマークされたノードを示し、緑はLOWERとマークされたノードを示します。
別のデッドロックが発生します
今回は、デッドロックをそれほどエレガントに回避することはできません。どのポイントも、目的地へのネイバーを経由して新しいルートを見つけることができません。したがって、彼らはコストの増加を広め続けています。チャネル外のポイントのみを見つけることができ、実行可能なルートを介して目的地につながる可能性がこれは、2つの下部波が発生する方法であり、新しいルート情報では到達不能としてマークされたポイントとして拡大します。
  追加の障害物によってチャネルがブロックされている(赤)
  進行中の拡張(黄色の上昇波、緑色の下降波)
  新しいパスが見つかりました(シアン)
擬似コード
一方、 (!openList 。のisEmpty ()) { 点 = openList 。getFirst (); 展開(ポイント); }
展開
void expand (currentPoint ) { boolean isRaise = isRaise (currentPoint ); 2倍の コスト; 以下のための 各 (隣人 で CurrentPointの。getNeighbors ()) {
場合 (isRaise ) {
場合 (隣接。nextPoint == CurrentPointの) {
隣接。setNextPointAndUpdateCost (currentPoint );
openList 。追加(隣人);
} else {
コスト = 隣人。calculateCostVia (currentPoint );
もし (コスト CurrentPointの。setMinimumCostToCurrentCost ();
openList 。追加(currentPoint ); } }
} else {
コスト = 隣人。calculateCostVia (currentPoint );
もし (コスト 隣接。setNextPointAndUpdateCost (currentPoint );
openList 。追加(隣人); } } } }
レイズを
boolean isRaise (point ) { double cost ; もし (点。getCurrentCost () > 点。getMinimumCost ()) {
ため 、各(隣人 で ポイント。getNeighbors ()) {
コスト = ポイント。computeCostVia (neighbor );
もし (コスト ポイント。setNextPointAndUpdateCost (neighbor ); } } } リターン ポイント。getCurrentCost () > ポイント。getMinimumCost (); }
バリアント
フォーカスされたD *
その名前が示すように、Focused D *はD *の拡張であり、ヒューリスティックを使用して、RAISEとLOWERの伝播をロボットに集中させます。このようにして、A *が一部のノードのコストのみを計算するのと同じ方法で、重要な状態のみが更新されます。
D * Lite
D * Liteは、元のD *またはFocusedD *に基づいていませんが、同じ動作を実装しています。理解が簡単で、より少ないコード行で実装できるため、「D * Lite」という名前が付けられています。パフォーマンス面では、Focused D *と同等またはそれ以上です。D * Liteは、数年前にKoenigとLikhachevによって導入されたLifelong Planning A *に基づいています。D * Lite
最小コストと現在のコスト
D *の場合、現在のコストと最小コストを区別することが重要です。前者は収集時にのみ重要であり、後者はOpenListをソートするため重要です。最小コストを返す関数は、OpenListの最初のエントリであるため、常に現在のポイントまでの最小コストです。
参考文献
^ Stentz、Anthony(1994)、「部分的に既知の環境のための最適で効率的な経路計画」、ロボット工学と自動化に関する国際会議の議事録:3310–3317、CiteSeerX  10.1.1.15.3683
^ Stentz、Anthony(1995)、「リアルタイム再計画のための焦点を絞ったD *アルゴリズム」、人工知能に関する国際合同会議の議事録:1652–1659、CiteSeerX 10.1.1.41.8257
^ ハート、P。; ニルソン、N。; Raphael、B。(1968)、「最小コストパスのヒューリスティック決定の正式な基礎」、IEEETrans。システム。科学とサイバネティックス、SSC-4(2):100–107、doi:10.1109 / TSSC.1968.300136
^ Koenig、S。; Likhachev、M。(2005)、「未知の地形でのナビゲーションのための高速再計画」、Transactions on Robotics、21(3):354–363、CiteSeerX 10.1.1.65.5979、doi:10.1109 / tro.2004.838026
^ Koenig、S。; Likhachev、M。; Furcy、D。(2004)、「Lifelong Planning A *」、人工知能、155(1–2):93–146、doi:10.1016 / j.artint.2003.12.001
^ ラマリンガム、G。; Reps、T。(1996)、「最短経路問題の一般化のためのインクリメンタルアルゴリズム」、Journal of Algorithms、21(2):267–305、CiteSeerX 10.1.1.3.7926、doi:10.1006 / jagm.1996.0046
^ Koenig、S。; スミルノフ、Y。; Tovey、C。(2003)、「未知の地形での計画のためのパフォーマンスの限界」、人工知能、147(1–2):253–279、doi:10.1016 / s0004-3702(03)00062-6
^ 木製、D。(2006)。移動ロボットのためのグラフベースの経路計画(論文)。ジョージア工科大学。
^ Stentz、Anthony(1995)、「リアルタイム再計画のための焦点を絞ったD *アルゴリズム」、人工知能に関する国際合同会議の議事録:1652–1659、CiteSeerX 10.1.1.41.8257
外部リンク
SvenKoenigのWebページ
アンソニー・ステンツのウェブページ”

投稿日:
カテゴリー: D