Der
D*-Algorithmus ist ein Suchalgorithmus. Es handelt sich um eine Erweiterung des
A*-Algorithmus und somit einen direkten „Nachfahren“ des
Dijkstra-Algorithmus. Sowohl A* als auch der Dijkstra-Algorithmus sind in ihrer Grundform unflexibel und können auf Veränderungen im Graphen während oder nach der Expansion nicht reagieren. In beiden Fällen kann der Anwender alle Ergebnisse verwerfen und nochmal von vorne beginnen. Gerade bei Arbeiten mit Robotern oder Agenten unter realen Bedingungen (begrenzte Sensorreichweite, unbekannte Umgebung) kommt es vor, dass große Karten ständig aktualisiert werden.
Anthony Stentz entwickelte an der
Carnegie Mellon University eine Möglichkeit, A* so zu modifizieren, dass er mit den neuen Anforderungen funktioniert.