D* Lite
Incremental pathfinding that cheaply repairs a route when the map changes instead of searching again from scratch.
A robot exploring unknown terrain only discovers obstacles once it reaches them. D* Lite searches backward from the goal and keeps the search tree's costs around; when an edge suddenly gets more expensive — a door turned out to be shut — only the nodes whose distance to the goal actually changes get updated. The rest of the earlier work is reused, which is dramatically faster than rerunning A* every time the world shifts.
Sven Koenig and Maxim Likhachev published it in 2002 as a cleaner rewrite of Anthony Stentz's D* (1994), built on top of their Lifelong Planning A*. Variants have steered real field robots; the canonical use is an agent that plans optimistically and replans whenever its sensors contradict the map.