D*

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

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

これら 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 とマークされたノードを示し、緑は LOWER とマークされたノードを示します。

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

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

openList .isEmpty ()の間、pointをopenList .getFirst ()で展開します。 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 (); }  
     
        
            
              
                
                
            
        
    
       

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

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

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

• スヴェン・ケーニッヒのウェブページ
• アンソニー・ステンツのウェブページ