Is replanning the same as planning from scratch?

Not necessarily. It may restart search or update previous search results, depending on the method.

Does the goal have to change?

No. The goal can remain fixed while the feasible or preferred route changes.

Can replanning guarantee success in every changing environment?

No. The goal may become unreachable, observations may be wrong, or computation and execution constraints may prevent a valid continuation.

AI Glossary / Graphs and symbolic AI / Intermediate

Online replanning

Definition

Online replanning is the process of revising a plan while an agent is carrying out its task, using new observations or changed conditions. The agent plans from its current situation rather than assuming the original plan remains valid. In robotics, this often means updating a route after discovering an obstacle or a change in travel cost.

What it means

An initial plan reflects what was known when it was made. As execution proceeds, the agent may learn that a passage is blocked, that it has reached a different position than expected, or that a resource is unavailable. Replanning connects those discoveries to the remaining actions.

The original objective may stay the same while the route changes. Replanning is therefore different from abandoning the task. It is also different from ordinary low-level feedback control: correcting a small steering error can follow an existing route, whereas replanning changes the intended route or action sequence.

How it works

The system maintains an estimate of its current state and a model of the environment. A new observation updates that model. A trigger determines whether the remaining plan should be reconsidered, and the planner computes an appropriate continuation from the updated state.

A straightforward method runs a search again from scratch. Incremental methods can retain useful information from earlier searches and update affected parts. D* Lite is a primary example of this approach for graph-based navigation, combining heuristic guidance with reuse of previous search information.

Replanning still requires time and a valid execution policy during computation. A robot may need to stop or follow a separately validated short-term behavior while a new route is being determined. The fact that a planner can update its graph does not by itself solve sensing errors, motion constraints, or collision avoidance during the update.

Three practical examples

Indoor robot: revise the route to a delivery point after detecting a cart blocking an aisle.
Inspection planning: update remaining visits after learning that one access corridor is temporarily unavailable.
Workflow agent: reconsider the unfinished action sequence after a required tool or resource becomes unavailable, while preserving the task's constraints.

Think of it this way

Think of following written directions and finding a closed road. You use your current location and the updated map to choose how to continue, instead of returning mentally to the original departure point.

The analogy is limited because automated replanning must specify how observations change the model, what costs matter, and when execution can safely continue. A newly computed route is only as appropriate as those assumptions.

Worked example

Consider an undirected graph with edges S - A of cost 2, A - G of cost 2, S - B of cost 3, B - G of cost 3, and A - B of cost 2. The agent starts at S and wants to reach G. Initially, S - A - G costs 4 and S - B - G costs 6, so the first route is preferred.

After moving to A and spending cost 2, the agent discovers that A - G is blocked. Replanning from A now compares A - B - G, which costs 2+3=5, with A - S - B - G, which costs 2+3+3=8. It chooses the remaining route through B.

The executed journey S - A - B - G costs 2+2+3=7. A planner that knew the blockage before departure would have chosen S - B - G at cost 6. Thus, selecting the best continuation from current knowledge does not guarantee that the entire executed journey matches the best route chosen with advance knowledge.

The cost already spent reaching A is recorded in total performance, but it cannot be undone. It does not make returning to S preferable when the remaining cost is higher. This is a hand-worked replanning example; it does not trace D* Lite's internal queues or measure the speed of any implementation.

Illustrative case study

Fictional case: a warehouse robot repeatedly receives route updates as a nearby worker moves a cart. The map changes faster than the planner's replacement routes can be usefully executed, leading to frequent stops in simulation.

The team examines observation reliability, change-trigger rules, and the division between local obstacle handling and global route planning. It checks that delayed plans are not applied to an incompatible current state. The case illustrates coordination between components, not a universal trigger rule or a claimed improvement in warehouse throughput.

Common misconceptions and mistakes

Online replanning does not require recomputing every search result after every observation. Some changes do not affect the current plan, and incremental algorithms can reuse relevant information.

It also does not imply a globally optimal executed journey in an unknown environment. Earlier decisions were made with less information, and exploration may incur unavoidable extra cost.

Do not assume that graph-path optimality guarantees safe physical movement. Robot geometry, timing, dynamics, and sensing uncertainty require appropriate models and validation. Finally, repeatedly issuing a new plan without coordinating it with execution can create inconsistency rather than responsiveness.

Business use

Replanning helps organizations use automation where information arrives during execution. It can reduce dependence on perfectly accurate initial plans and make disruptions explicit parts of the workflow.

Useful operating requirements include which changes trigger planning, the maximum acceptable delay, how partial progress is preserved, and what happens when no valid continuation exists. Logs should connect observations, model changes, selected plans, and actual actions so that failures can be diagnosed. Evaluation should include the total executed cost as well as the cost of each newly computed continuation.

Check your understanding

Why does the example's final journey cost 7 when a fully informed initial route would cost 6?

Answer: The agent already traveled to A before discovering the blockage. Replanning chooses the best remaining route but cannot remove the cost of that earlier action.

Related terms

Online search
Execution monitoring
Motion planning
incremental search
D* Lite
current-state estimation
dynamic environment
path cost

Learn next

Modify one edge in a small route graph after the traveler has moved. Recalculate from the current state and separately track sunk travel cost. Then study incremental heuristic search to understand how earlier computation can be reused.

Incremental heuristic search

Sources

Sven Koenig and Maxim Likhachev, D* Lite: https://idm-lab.org/bib/abstracts/papers/aaai02b.pdf — incremental heuristic replanning for navigation as new obstacles become known.

Russell and Norvig, author-hosted search chapter: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap04.pdf — interleaving action, observation, and search. Graph values and scenarios above are original illustrations.

Previous: Online optimization Next: Online search