Does real-time search find the shortest route immediately?

Not generally. Limited lookahead can produce detours even when the method eventually reaches a goal under its assumptions.

Why remember heuristic updates?

They can prevent the system from repeatedly treating an already explored region as more promising than the evidence supports.

Does limiting search expansions guarantee a deadline?

Only if the time required for those expansions and the surrounding work is also appropriately bounded or controlled.

AI Glossary / Graphs and symbolic AI / Intermediate

Real-time search

Definition

Real-time search is a family of search methods that limit the computation performed before an agent commits to its next action. Planning and execution are interleaved: the agent looks ahead, acts, and then searches again from its new situation. In AI terminology, the emphasis is on timely action selection rather than completing an entire solution path before movement begins.

What it means

An agent may be unable to wait while a large search finishes. Real-time search addresses that problem by making decisions using a limited view of the state space and a heuristic estimate of what lies beyond it.

This changes the performance question. A method that begins acting quickly can still follow a longer route or revisit states. Both planning effort and the cost of executed actions matter. The term is not synonymous with searching a live website, returning current news, or merely running an ordinary search algorithm on a fast computer.

How it works

At the current state, inspect a bounded local region. Evaluate candidate actions using known local costs and heuristic estimates for more distant outcomes. Choose an action, execute it, and repeat from the resulting state.

Learning variants revise heuristic values as they encounter evidence that their earlier estimates were too optimistic. Learning Real-Time A*, or LRTA*, is a classic example. Such updates can make later visits or repeated problem-solving trials more informed.

The precise update rule, lookahead budget, and guarantees vary by algorithm. A bound on node expansions is not automatically a fixed bound on elapsed time if expansion costs vary. Completeness and convergence also rely on assumptions about the state space, available actions, and reachability, rather than following from the word real-time alone.

Three practical examples

Game navigation: an agent selects its next move after a limited local search rather than pausing for a complete route calculation.
Puzzle research: a solver alternates small lookahead searches with committed moves and studies how learned estimates change later trials.
Robot simulation: a planner balances time spent deciding against distance traveled, using a controlled model to compare different lookahead budgets.

Think of it this way

Think of walking through a large building while consulting only a small portion of the map at each junction. You can start moving sooner, but the local view may lead you down an unhelpful corridor. Remembering that corridor improves later decisions. The analogy omits formal assumptions: real-time search methods use explicit states and update rules, and not every building permits the backtracking their guarantees may require.

Worked example

Consider an undirected unit-cost graph with connections S - A, S - B, and B - G. G is the goal. A is a dead-end branch connected only to S. Initially set all heuristic values to zero. Use a one-step learning rule: set the current value to the larger of its old value and one plus the smallest successor value, then move to a successor with that smallest value. Break the initial tie at S in favor of A.

At S, both successors have value zero. Set S's value to one and move to A. At A, the only successor is S with value one. Set A's value to two and return to S.

Back at S, A has value two and B has value zero. S's value remains one and the agent moves to B. At B, G has value zero while S has value one. Set B's value to one and move to G.

The executed path is S, A, S, B, G: four actions. The shortest possible route S, B, G uses two. The method acted after only local computation, but its first trial paid for an exploratory detour.

On another trial retaining the learned values, S prefers B's value one to A's value two and can take the two-action route. This specific trace demonstrates learning in a tiny graph; it is not a universal bound on first-trial or repeated-trial performance.

Illustrative case study

Fictional case: Bracken Games compares navigation methods for simulated characters. The team first measures how quickly each character starts moving, then notices that the fastest-starting method sometimes walks farther.

Researchers add route length, revisits, and total completion time to their evaluation. They also distinguish a first encounter with a map from a later encounter using retained heuristic values. Different lookahead budgets are compared under the same map and movement rules.

The case illustrates a fairer evaluation design. It claims no measured frame-rate gain or proof that one method is best for every game environment.

Common misconceptions and mistakes

Do not assume a short planning pause means a short overall task. The worked example starts promptly but doubles the first route's action count.

Do not confuse a heuristic update with discovering the exact remaining distance everywhere. Learning is selective and can remain incomplete.

Avoid treating backtracking as free when actions represent physical travel or costly operations. Also check what happens if actions cannot be reversed or some reachable states have no route to the goal. Assumptions used for a search theorem must match the application before its guarantee is repeated in product claims.

Business use

For a business evaluating autonomous planning, compare the delay before each action with total task cost. Report the frequency and effect of revisits, the memory used for learned values, and performance when conditions differ from earlier trials.

In the graph example, a second trial benefits from retained information. A demonstration that reports only later trials would conceal the initial detour. Clear reporting separates those settings and identifies whether the system is expected to reuse the same environment or face new tasks continually.

Check your understanding

Why does S choose B on its second visit in the example?

Answer: A's learned value is two while B's remains zero, so the one-step rule now judges B more promising.

Related terms

Heuristic search
Online search
LRTA*
limited lookahead
backtracking
heuristic learning
planning cost
execution cost

Learn next

reverse the initial tie-breaking choice and compare the trace. Then add another dead-end branch and examine how the heuristic values change. Study the assumptions behind LRTA* before extending the toy rule to irreversible or stochastic actions.

Sources

Primary sources: Sven Koenig, “Real-Time Heuristic Search: Research Issues”: https://idm-lab.org/bib/abstracts/papers/aips-workshop98.pdf Richard Korf, author-maintained publication abstracts: https://web.cs.ucla.edu/~korf/publications.html The relevant learning-rule and performance passages were read. The graph trace and Bracken Games case are original illustrations.

Previous: Real-Time Machine Learning Next: Realization