D*

D* (「D スター」と発音) は、次の 3 つの関連する増分検索アルゴリズムのいずれかです。

  • オリジナルのD* [ 1 ]は、アンソニー・ステンツによる情報に基づいた増分探索アルゴリズムです。
  • Focused D* [ 2 ]は、Anthony Stentzによる情報に基づいた増分ヒューリスティック探索アルゴリズムであり、A* [ 3 ]とオリジナルのD*のアイデアを組み合わせたものです。Focused D*は、オリジナルのD*をさらに発展させたものです。
  • D* Lite [ 4 ]は、スヴェン・ケーニッヒとマキシム・リハチェフによる増分ヒューリスティック探索アルゴリズムで、 LPA* [ 5 ]を基盤としています。LPA *は、A*と動的SWSF-FPのアイデアを組み合わせた増分ヒューリスティック探索アルゴリズムです。[ 6 ]

これら 3 つの探索アルゴリズムはすべて、同じ仮定に基づく経路計画問題を解決します。これには、ロボットが未知の地形で指定された目標座標まで移動しなければならない自由空間仮定[ 7 ]を使用した計画も含まれます。地形の未知の部分について仮定を立て (たとえば、障害物がないこと)、これらの仮定の下で現在の座標から目標座標までの最短経路を見つけます。次に、ロボットはその経路をたどります。新しいマップ情報 (以前は未知だった障害物など) を観測すると、その情報をマップに追加し、必要に応じて、現在の座標から指定された目標座標までの新しい最短経路を再計画します。目標座標に到達するか、目標座標に到達できないと判断するまで、このプロセスを繰り返します。未知の地形を横断する場合、新しい障害物が頻繁に発見される可能性があるため、この再計画は高速である必要があります。増分 (ヒューリスティック) 探索アルゴリズムは、以前の問題の経験を使用して現在の問題の検索を高速化することにより、同様の探索問題のシーケンスの検索を高速化します。目標座標が変化しないと仮定すると、3 つの検索アルゴリズムはすべて、繰り返しの A* 検索よりも効率的です。

D*とその派生型は、移動ロボットや自律走行車のナビゲーションに広く利用されている。現在のシステムは、オリジナルのD*やFocused D*ではなく、D* Liteをベースにしているのが一般的である。実際、Stentzの研究室でさえ、一部の実装ではD*ではなくD* Liteを使用している。[ 8 ]このようなナビゲーションシステムには、火星探査車オポチュニティとスピリットでテストされたプロトタイプシステムや、 DARPAアーバンチャレンジの優勝作品のナビゲーションシステムなどがあり、どちらもカーネギーメロン大学で開発された。

オリジナルのD*は1994年にアンソニー・ステンツによって導入されました。D*という名前は「Dynamic A*」という用語に由来しており、[ 9 ]、このアルゴリズムは実行時にアークコストが変化する点を除けばA*のように動作するからです。

手術

D* の基本的な操作の概要は以下のとおりです。

ダイクストラ法やA*と同様に、D*は評価対象となるノードのリスト（「OPENリスト」と呼ばれる）を保持します。ノードは、以下のいずれかの状態としてマークされます。

  • NEW、つまりOPENリストに一度も掲載されていない
  • OPEN、つまり現在OPENリストに載っている
  • CLOSED（クローズ）は、OPENリストに載っていないことを意味します。
  • RAISEは、そのコストが前回OPENリストに載っていたときよりも高いことを示します。
  • LOWER は、前回 OPEN リストに掲載されていたときよりもコストが低いことを示します。

拡大

このアルゴリズムは、OPENリストからノードを反復的に選択し、評価することで機能します。次に、ノードの変更をすべての隣接ノードに伝播させ、それらをOPENリストに追加します。この伝播プロセスは「拡張」と呼ばれます。開始から終了までパスをたどる標準的なA*とは異なり、D*は目標ノードから逆方向に探索することから始まります。つまり、このアルゴリズムは実際には、あらゆる可能性のある開始ノードに対してA*の最適パスを計算していることになります。[ 10 ]拡張された各ノードには、目標ノードにつながる次のノードを指すバックポインタがあり、各ノードは目標ノードまでの正確なコストを知っています。開始ノードが次に拡張されるノードになった時点でアルゴリズムは終了し、バックポインタをたどるだけで目標ノードへのパスを見つけることができます。

  • 拡張進行中。終了ノード（黄色）は上段のポイント列の中央、開始ノードは下段のポイント列の中央にあります。赤は障害物、黒/青は拡張ノード（明度はコスト）を示します。緑は拡張中のノードを示します。
    拡張進行中。終了ノード（黄色）は上段のポイント列の中央、開始ノードは下段のポイント列の中央にあります。赤は障害物、黒/青は拡張ノード（明度はコスト）を示します。緑は拡張中のノードを示します。
  • 拡張が完了しました。パスは水色で表示されます。
    拡張が完了しました。パスは水色で表示されます。

障害物処理

意図した経路上に障害物が検出されると、影響を受けるすべてのポイントが再びOPENリストに追加され、今度はRAISEとマークされます。RAISEDノードのコストが増加する前に、アルゴリズムは隣接するノードをチェックし、そのノードのコストを削減できるかどうかを調べます。削減できない場合、RAISE状態はすべての子孫ノード、つまりそのノードへのバックポインタを持つノードに伝播されます。これらのノードは評価され、RAISE状態が渡され、ウェーブが形成されます。RAISEDノードを削減できる場合、そのバックポインタが更新され、隣接するノードにLOWER状態が渡されます。これらのRAISE状態とLOWER状態のウェーブがD*の中核です。

この時点で、他の一連の点全体が波に「触れる」ことが防止されます。したがって、アルゴリズムはコストの変化の影響を受ける点のみに作用します。

  • 障害物が追加され (赤)、ノードに RAISE (黄色) のマークが付けられています。
    障害物が追加され (赤)、ノードに RAISE (黄色) のマークが付けられています。
  • 拡張中です。黄色は「RAISE」とマークされたノード、緑は「LOWER」とマークされたノードを示します。
    拡張中です。黄色は「RAISE」とマークされたノード、緑は「LOWER」とマークされたノードを示します。

再び行き詰まりが発生

今回は、デッドロックをそれほど巧みに回避することはできません。どの点も、隣接する点を経由して目的地への新しい経路を見つけることができません。そのため、コストの増加は伝播し続けます。チャネルの外側にある点だけが発見され、そこからは実行可能な経路を経由して目的地に到達できます。こうして2つの下波が発生し、到達不可能とマークされた点が新たな経路情報によって拡大します。

  • 追加の障害物によってブロックされたチャネル（赤）
    追加の障害物によってブロックされたチャネル（赤）
  • 拡大進行中（上昇波は黄色、下降波は緑）
    拡大進行中（上昇波は黄色、下降波は緑）
  • 新しいパスが見つかりました（シアン）
    新しいパスが見つかりました（シアン）

擬似コード

while ( ! openList . isEmpty ()) { point = openList . getFirst (); expand ( point ); }

拡大する

void expand ( currentPoint ) { boolean isRaise = isRaise ( currentPoint ) ; double cost ; for each ( neighbor in currentPoint.getNeighbors ( ) ) { if ( isRaise ) { if ( neighbor.nextPoint == currentPoint ) { neighbor.setNextPointAndUpdateCost ( currentPoint ) ; openList.add ( neighbor ) ; } else { cost = neighbor.calculateCostVia ( currentPoint ) ; if ( cost < neighbor.getCost ( ) ) { currentPoint.setMinimumCostToCurrentCost ( ) ; openList.add ( currentPoint ) ; } } } else { cost = neighbor.calculateCostVia ( currentPoint ) ; if ( cost < neighbor.getCost ( ) ) { neighbor.setNextPointAndUpdateCost ( currentPoint ) ; openList.add ( neighbor ) ; } } }​​​​​​​​​

昇給を確認する

boolean isRaise ( point ) { double cost ; if ( point . getCurrentCost () > point . getMinimumCost ()) { for each ( neighbor in point . getNeighbors ()) { cost = point . calculateCostVia ( neighbor ); if ( cost < point . getCurrentCost ()) { point . setNextPointAndUpdateCost ( neighbor ); } } } return point . getCurrentCost () > point . getMinimumCost (); }

変種

集中D*

その名前が示すように、Focused D*はD*の拡張版であり、ヒューリスティックを用いてRAISEとLOWERの伝播をロボットに集中させます。これにより、A*が一部のノードのコストのみを計算するのと同様に、重要な状態のみが更新されます。

D* ライト

D* LiteはオリジナルのD*やFocused D*をベースにしていませんが、同じ動作を実装しています。より理解しやすく、より少ないコード行数で実装できるため、「D* Lite」という名前が付けられています。パフォーマンス面では、Focused D*と同等かそれ以上です。D* Liteは、数年前にKoenigとLikhachevによって導入されたLifelong Planning A*をベースにしています。D * Lite

最小コストと現在のコスト

D*の場合、現在のコストと最小コストを区別することが重要です。前者は収集時にのみ重要であり、後者はOpenListをソートするため重要です。最小コストを返す関数は、OpenListの最初のエントリであるため、常に現在の点までの最小コストとなります。

参考文献

  1. ^ Stentz, Anthony (1994)、「部分的に既知の環境における最適かつ効率的な経路計画」、国際ロボティクス・オートメーション会議論文集：3310– 3317、CiteSeerX  10.1.1.15.3683
  2. ^ Stentz, Anthony (1995)、「リアルタイム再計画のためのフォーカスD*アルゴリズム」、人工知能に関する国際合同会議論文集：1652–1659、CiteSeerX 10.1.1.41.8257 
  3. ^ハート、P.; ニルソン、N.; ラファエル、B. (1968)、「最小コストパスのヒューリスティック決定のための形式的基礎」、IEEE Transactions on Systems Science and Cyber​​netics、SSC-4 (2): 100– 107、doi : 10.1109/TSSC.1968.300136
  4. ^ Koenig, S.; Likhachev, M. (2005)、「未知の地形でのナビゲーションのための高速再計画」、IEEE Transactions on Robotics、21 (3): 354– 363、CiteSeerX 10.1.1.65.5979、doi : 10.1109/tro.2004.838026、S2CID 15664344  
  5. ^ケーニッヒ, S.; リハチェフ, M.; ファーシー, D. (2004)「生涯計画A*」人工知能, 155 ( 1– 2): 93– 146, doi : 10.1016/j.artint.2003.12.001
  6. ^ Ramalingam, G.; Reps, T. (1996)、「最短経路問題の一般化のための増分アルゴリズム」、Journal of Algorithms、21 (2): 267– 305、CiteSeerX 10.1.1.3.7926、doi : 10.1006/jagm.1996.0046 
  7. ^ケーニッヒ、S.; スミルノフ、Y.; トーヴィー、C. (2003)、「未知の地形での計画の性能限界」、人工知能、147 ( 1–2 ): 253– 279、doi : 10.1016/s0004-3702(03)00062-6
  8. ^ Wooden, D. (2006).移動ロボットのためのグラフベース経路計画（論文）. ジョージア工科大学.
  9. ^ Stentz, Anthony (1995)、「リアルタイム再計画のためのフォーカスドD*アルゴリズム」、人工知能に関する国際合同会議論文集：1652–1659、CiteSeerX 10.1.1.41.8257 
  10. ^マーフィー、ロビン R. (2019). AIロボティクス入門（第2版）。ブラッドフォードの本。 14.5.2項。ISBN 978-0262038485。
「 https://en.wikipedia.org/w/index.php?title=D*&oldid=1315962800」より取得