Does online search mean searching the web?

Not in this entry. It means interleaving problem-solving computation with actions and observations.

Why can it cost more than offline planning?

The agent may need to physically explore unsuccessful alternatives before learning which route reaches the goal.

Is a complete map always the objective?

No. Reaching a particular goal and mapping the entire reachable environment are different tasks with different costs.

AI Glossary / Graphs and symbolic AI / Intermediate

Online search

Definition

Online search is problem solving that interleaves computation with actions and observations in an environment. The agent may need to act to discover which states or routes are available, then use what it learns to choose its next action. In this classical AI sense, online search means interactive exploration, not simply using an internet search engine.

What it means

An agent in an unfamiliar building cannot necessarily calculate a complete route from a perfect map. It may know how to move and recognize its destination, yet not know which door leads where. Actions therefore have two roles: making progress and revealing information.

Unlike exploring a simulated search tree, exploring the real environment has consequences. Going down the wrong corridor takes time, consumes resources, and may require physical backtracking. A search method suitable for a computer's internal graph does not automatically work well when each expansion requires real movement.

How it works

The agent observes its current state, identifies available actions, chooses one, and records the result after execution. It can build or refine a model as it proceeds. Its next decision depends on both the task and the information accumulated so far.

Some methods systematically try unexplored actions and return to earlier states when necessary. Others use estimated distances or costs to guide exploration. The exact guarantees depend on assumptions about state recognition, reversibility, action costs, and whether the goal remains reachable.

An irreversible action can be especially important. If an unknown doorway leads to a region from which the goal cannot be reached, trial and error may permanently fail. Assuming that exploration is safe is a mathematical simplification that must not be silently transferred to a physical application.

Three practical examples

Building exploration: a robot discovers passage connections while trying to reach a marked destination.
Simulated maze learning: an agent records the results of moves instead of receiving the full map at the start.
Interactive problem solving: a software agent learns which permitted transitions are available through observed responses, provided those exploratory actions are appropriate for the application.

Think of it this way

Think of navigating a maze by walking through it with a notebook. The notebook grows as you travel, and returning from a dead end means actually walking back.

The analogy has limits because not all environments permit easy backtracking or reliable recognition of places already visited. A real agent must also consider energy, time, uncertainty, and the consequences of actions that cannot be reversed.

Worked example

Suppose an agent starts at S in an unknown undirected graph. Every edge costs 1. The actual graph contains S - A, A - C, S - B, and B - G, where G is the goal. C is a dead end. The agent does not initially know these connections beyond its locally available actions.

Assume its action ordering chooses A before B and it follows a depth-first exploration strategy. Its executed sequence is S→A→C→A→S→B→G. That is six edge traversals and total cost 6.

With the complete graph known in advance, a planner could choose S→B→G at cost 2. The exploration run therefore costs three times the fully informed shortest route in this particular example. The extra cost comes from discovering and leaving the unsuccessful branch.

Reversibility matters: C→A and A→S must be possible for this trace. If entering C were irreversible, the assumed strategy could become trapped. The calculation also assumes exact state recognition, so the agent knows it has returned to S. This original hand trace illustrates one action ordering; it is not a general bound on online-search performance or a claim that depth-first exploration always uses three times the optimal cost.

Illustrative case study

Fictional case: a team evaluates an exploration agent only by counting how many internal decisions it makes. One version appears efficient but repeatedly travels long distances between already visited locations.

The team adds actual movement cost, repeated traversals, and recovery behavior to its evaluation. It separates map-building objectives from reaching one destination, because those tasks can favor different exploration choices. The case illustrates how a suitable performance measure changes the assessment, not a reported robot experiment or a measured efficiency gain.

Common misconceptions and mistakes

Online search is not the same as online inference. The latter usually means computing a prediction on request; online search concerns action and observation during problem solving.

It does not require the agent to start with no knowledge at all. An agent may know movement rules, recognize goals, or possess part of a map while still needing exploration.

Do not treat computational backtracking as free physical backtracking. Nor should success in a reversible maze be assumed to transfer to an environment with cliffs, one-way transitions, or costly actions. The model's exploration assumptions determine which claims are justified.

Business use

Online search is relevant when automation must operate without a complete advance model. It helps frame the cost of acquiring information through action and the limits of comparing an exploring agent with one given the full answer in advance.

Business evaluation should include time to goal, resources spent exploring, reliability of observations, and consequences of unsuccessful actions. Before deployment, teams should identify which exploratory actions are allowed and which require additional safeguards or information. A method that eventually succeeds in a simplified environment may still be unsuitable when its exploration cost or failure modes are unacceptable.

Check your understanding

Why does the worked example count C→A as part of search cost?

Answer: The agent physically entered C and must travel back to continue exploring. The return is an executed action, not just removing a node from a computer's search stack.

Related terms

Offline search
Exploration
Online replanning
Heuristic search
Competitive ratio
reversible action
state recognition
safely explorable environment

Learn next

Draw an unknown maze and reveal only the exits from the agent's current location. Record every physical move, including returns. Compare the resulting travel cost with the shortest path after revealing the full map, and inspect how a different action order changes the result.

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, author-hosted search chapter, Section 4.5: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap04.pdf — online search, physical backtracking, and exploration assumptions. The retrieved chapter uses older-edition pagination. The graph, traversal counts, and business scenario are original teaching examples.

Previous: Online replanning Next: Online Store