Must the physical world change?

No. Discovering an obstacle can change the agent's model even if the obstacle was already present.

Does every update require restarting search?

No. Incremental methods can reuse appropriate prior information, though the benefit depends on the problem and change.

Is the old route always invalid after an update?

No. It may remain feasible and optimal, remain feasible but suboptimal, or become infeasible.

AI Glossary / Graphs and symbolic AI / Intermediate

Dynamic search problems

Definition

Dynamic search problems are search problems whose relevant description changes over time, such as changing edge costs, newly discovered obstacles, or a moving start state. A solver must update or replace its earlier solution when those changes matter. In AI path planning, incremental search methods can reuse previous computation instead of solving every revised problem entirely from scratch.

What it means

A route that was best under one map may become expensive or impossible after an update. The change might reflect a real event, such as a blocked passage, or improved knowledge of a world that was already that way. Either can require a revised search problem.
This entry uses the AI planning sense of the phrase. In data-structure theory, dynamic search can instead refer to queries over a changing stored set. The two meanings share the idea of updates but involve different problems, algorithms, and performance guarantees.

How it works

Represent the current problem with states, available transitions, costs, a start, and a goal. When an update arrives, identify which parts of that representation have changed. A simple approach runs the search again. An incremental approach retains suitable search information and repairs values affected by the update.
Algorithms such as D* Lite are designed for particular classes of changing path-planning problems. Reuse does not mean treating every old result as valid: dependencies and consistency conditions determine what must be reconsidered. A changing problem also needs an execution policy, because the agent may act while new information continues to arrive.

Three practical examples

A mobile robot updates its route when a passage previously believed open is observed to be blocked.
A simulated network planner revises a least-cost path after a link's modeled cost increases.
A route-planning benchmark compares fresh searches with incremental repair across a sequence of related graph updates.

Think of it this way

Think of editing an itinerary after one connection changes. Much of the old itinerary may still be useful, but every affected onward connection must be checked. The analogy is limited because search algorithms maintain explicit values and dependencies; casually keeping unchanged-looking sections does not prove that the revised route remains feasible or optimal.

Worked example

Consider a graph with two routes from S to G. Route S-A-G has edge costs 2 and 2, totaling 4. Route S-B-G has costs 1 and 5, totaling 6. Initially, S-A-G is the cheaper route.
Now the cost of A-G rises from 2 to 8. The first route costs 2 + 8 = 10, while the second remains 1 + 5 = 6. A correct revised search should prefer S-B-G. If A-G is removed entirely, the first route is infeasible rather than merely expensive.
Suppose the agent has already traveled from S to A when the update occurs. The new start is A, so comparing the original S-based totals is no longer enough. If A-S is available with cost 2, a route A-S-B-G costs 2 + 1 + 5 = 8. Without that reverse edge, this detour may not exist. This example shows why edge changes and the agent's current state both matter. It illustrates the problem, not the exact internal update sequence of D* Lite.

Illustrative case study

At fictional Meadow Routes, a prototype displays a route computed before a newly reported closure. The team adds a versioned map update and checks whether the displayed path uses an affected edge. It then compares full replanning with an incremental method on a recorded sequence of simulated changes.
The evaluation includes changes discovered after the agent moves. This fictional case illustrates stale-solution handling and fair comparison, without claiming a measured runtime improvement or that every update requires the same amount of repair.

Common misconceptions and mistakes

Dynamic search is not synonymous with dynamic programming. Dynamic programming refers to exploiting subproblem structure; the word dynamic does not imply a changing external problem in that context.
Nor does incremental repair guarantee less work for every update. A small local change can affect many candidate routes, and some changes make old information unhelpful. A path optimal under the current graph is not necessarily optimal against unknown future changes. Distinguish known updates, uncertain predictions, and adversarial events. These require different models and can support different guarantees.

Business use

Businesses using search in changing environments should define what triggers replanning, which data version supports each result, and what happens while an update is processed. Compare solution quality and response time across complete update sequences. Include stale-data tests and failure cases where no route remains. If actions are costly or irreversible, account for the current execution state rather than repeatedly optimizing from the original starting point. Keep mathematical optimality claims tied to the specific current model.

Check your understanding

In the worked graph, A-G changes to cost 3 rather than 8. Must the preferred route from S change?

Answer: No. S-A-G would cost 5, still less than S-B-G's cost 6. The result must be reassessed, but a changed input does not necessarily mean a changed answer.

Related terms

Online search
Shortest Paths
Incremental search
replanning
D* Lite
edge cost
dynamic environment
shortest path
model update
they can be combined

Learn next

Add a third route to the worked graph and consider one cost increase and one decrease. Identify which old comparisons become invalid, then distinguish the work needed to verify the old answer from the work needed to find a new one.

Sources

Koenig and Likhachev, D* Lite, original AAAI paper: https://idm-lab.org/bib/abstracts/papers/aaai02b.pdf Likhachev and colleagues, Anytime Dynamic A*: An Anytime, Replanning Algorithm, original conference abstract: https://aaai.org/papers/icaps-05-027-anytime-dynamic-a-an-anytime-replanning-algorithm/

Previous: Dynamic range Next: Dynamic SQL