D*算法是一種用於機器人路徑規劃的啟發式方法，它特別適用於部分未知環境的情況。該算法結合了局部規劃的特點，即僅在已知部分地形的情況下進行規劃，並對未知部分進行假設。在規劃過程中，D*算法為每個節點維護兩個代價值：k[s]和h[s]。其中，k[s]表示從起點到該節點的實際代價，而h[s]表示從該節點到目標節點的估計代價。
D*算法的初始階段使用Dijkstra算法從終點向起點搜尋，以找到一條從起點到終點的路徑。與傳統Dijkstra算法不同，D*算法在搜尋時維護了兩個代價值，並且在搜尋過程中不斷更新這些值。當機器人沿著路徑前進時，如果遇到新的障礙物，算法會將該節點的h值更新為無窮大，表示該節點不可達。然後，算法會重新規劃路徑，直到找到新的可行路徑或者確定無法到達目標。
D*算法的增量式特性使其能夠在觀察到新的地圖信息時快速重新規劃路徑。這種增量搜尋算法利用以往問題的經驗來加快對當前問題的搜尋，從而提高了對相似搜尋問題序列的效率。D*算法的這種特性使其適用於動態環境或部分未知環境中，其中地圖信息可能會隨著時間而變化。
當前的系統通常基於D* Lite實現，而不是最初的D*或Focussed D。D* Lite是D*算法的一個變種，它進一步最佳化了算法的性能，使其更適合實際套用。例如，D* Lite算法在美國國防部高級研究計劃局的城市挑戰賽中獲勝的導航系統中得到了套用。
總結來說，D*算法是一種增量啟發式搜尋算法，它通過維護節點的實際和估計代價來找到從起點到終點的最短路徑。在遇到新的障礙物時，算法能夠快速重新規劃路徑，以適應環境的變化。