D* / D* Lite

A graph-search algorithm that, as the map changes while a robot moves, patches only the affected part to quickly recompute the shortest path.

D* was proposed by Anthony Stentz in 1994 — the name comes from ‘Dynamic A*’ — and in 2002 Sven Koenig and Maxim Likhachev built on LPA* to propose the simpler D* Lite, which is more widely used today. It handles navigation when the map isn't fully known in advance: the robot first plans a route from what it knows (treating unexplored areas as passable by default), then discovers new obstacles with its sensors as it drives. Plain A* has to search from scratch every time; the D* family instead searches backward from the goal to the start and keeps the cost values from the previous round, so when the cost of some edges changes, only the affected nodes need patching, making replanning fast. According to Wikipedia, navigation systems based on it were prototyped on the Mars rovers Spirit and Opportunity, and it was also used on the self-driving car that won CMU's entry in the DARPA Urban Challenge. It's a global planner, commonly paired with a local planner such as DWA.

ExampleA warehouse mobile robot plans a route through a certain aisle using an old map, but partway through, its lidar discovers the aisle blocked by a pallet. Once the costmap updates, D* Lite only updates the cost of nodes near the blocked cell to produce a detour, without rerunning A* over the entire map.

Also called

Dynamic A*, Focused D*, Incremental Replanning

Related

A* Search · Dijkstra's Algorithm · Replanning · Path Planning · Global Planning and Local Planning · Costmap

Sources

Wikipedia: D*
Koenig & Likhachev, D* Lite (AAAI 2002)