D* Algorithm

D*, pronounced D star, is any one of three related incremental search algorithms, all solving assumption based path planning problems in which a robot must navigate to given goal coordinates across unknown terrain, replanning as it discovers new obstacles. The original D* was introduced by Anthony Stentz in 1994, and its name comes from the term Dynamic A*, because the algorithm behaves like A* except that arc costs can change as the algorithm runs. D* and its variants, most often D* Lite by Sven Koenig and Maxim Likhachev, have been widely used for mobile robot and autonomous vehicle navigation, including a prototype tested on the Mars rovers Opportunity and Spirit and the navigation system of the winning entry in the DARPA Urban Challenge.