Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Online search agents

Online search agents are agents that interleave planning and action without a complete model of the world, using local percepts and learning (heuristic updates) to find goals in unknown or partially known state spaces.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Online search agents are used in real systems where the agent cannot know the whole world in advance or where acting and sensing must alternate (robots exploring unknown terrain, network routing with dynamic information, interactive game agents). They let an agent make decisions using only local percepts and a memory, updating its knowledge while it acts.

Key ideas

Start with definitions (each bold term defined before use):

  • Percept: the raw input from the environment at one time step (example: a robot's sensor readings). Units: none (symbolic or numeric).
  • State: a complete description of the world the agent cares about; derived (possibly) from a history of percepts by the agent. Units: none.
  • Action: an operation the agent can perform that may change the state. Units: none.
  • Model: a function the agent uses to predict the result of actions. An offline (model-based) agent has a complete model of the state space (transition function), while an online agent does not require full knowledge and acts with partial or no model.
  • Online search agent: an agent that alternates between sensing and acting and may update an internal representation (memory) and heuristic estimates from experience. The agent must choose actions based only on the current percept and its memory; it cannot explore arbitrarily without executing actions.
  • Heuristic function h(n): an estimate of the cost from node n (state n) to a goal. Admissible heuristic means h(n) ≤ true minimal cost to a goal from n for all n. Consistent (monotone) heuristic means for every action a from n to n': h(n) ≤ c(n,a,n') + h(n').
  • Path cost g(n): the cost to reach state n from the start following the actions taken. Units: same as action costs (e.g., seconds, metres, energy units).

Principles and assumptions used by online agents:

  1. The agent may have unknown successor states (transition function partially or fully unknown), but percepts let it identify the current state when states are observable; if states are not directly observable the agent must maintain beliefs (we will assume states are observable for these notes).
  2. The environment is usually assumed deterministic for basic online search analysis; stochastic actions require other algorithms (not covered here).
  3. The state space is finite or effectively finite for convergence proofs. Additionally, to guarantee completeness for online DFS/LRTA*, assume there are no dead-end states and that actions are reversible (or the graph is undirected) so the agent can backtrack.

Algorithms and properties described to the level expected in exams:

  • Online Depth-First Search (Online DFS): the agent moves along a path until it reaches a dead end (no unvisited successors) or the goal, then backtracks by executing physical moves. The agent must remember visited states along the current trial to avoid immediate cycles. Draw a directed graph with nodes labelled S (start), A, B, G (goal). Label arcs with costs. To show Online DFS behaviour: draw the agent moving and crossing out visited edges on the drawing.

  • Learning Real-Time A* (LRTA*): an online heuristic-search algorithm. LRTA* maintains a heuristic table h(s) for all states s encountered. At current state s, LRTA* evaluates for each action a leading to neighbor s' the estimated cost c(s,a,s') + h(s'). It sets h(s) := min_a [c(s,a,s') + h(s')] and then selects an action that minimizes c(s,a,s') + h(s'). Then it executes the chosen action, observes new state, and repeats. LRTA* therefore updates h values on the fly and is designed to work with limited planning before acting.

Exact update rule (stated as universities do): for current state s and set of actions A(s) giving neighbors s',

h(s) <- max( h(s), min_{a in A(s)} [ c(s,a,s') + h(s') ] ).

(We include max with current h(s) to keep h values non-decreasing when implementations use that.)

Properties commonly stated: LRTA* is an online, real-time algorithm: planning per step is limited (only local neighbors considered), memory is used to store h-values, and heuristic improves with experience. Under standard assumptions (finite state space, deterministic actions, positive costs, no dead ends, and reversible actions or an undirected state graph), LRTA* will reach a goal from the start state and its h-values are non-decreasing (with the max-update form). The exact optimality and convergence conditions are listed under "verify" because rigorous proofs require careful statements.

Diagram to draw for LRTA* derivation: draw a state s with arrows to neighbors s1, s2, s3; label edge costs c(s,s1)=2, c(s,s2)=5, c(s,s3)=1 and write h(s1)=3, h(s2)=1, h(s3)=4; then show computation of min_a [c + h] and update h(s).

Comparison with offline A*: Offline A* uses full model to explore a frontier (open list) and finds an optimal path when h is admissible. LRTA* uses local lookahead and updates heuristics; it is more suitable when actions must be executed as planning proceeds.

Assumptions and when statements apply: when we say "LRTA* finds a path" we mean under finite deterministic state spaces with a reachable goal, no dead ends, and reversible actions (or an undirected graph); when we say "heuristics are non-decreasing" we mean with the max update form.

Formulas

f(n) = g(n) + h(n) where f(n) is the estimated total cost through node n (units: same as costs, e.g., seconds). Applies in A* style searches.

g(n) = cost from the start state to node n following the executed path (units: cost units). Applies for any path-cost measure.

h(n) = heuristic estimate of cost from n to goal (units: cost units). h must be admissible if you want offline optimality guarantees.

h(s) <- min_{a in A(s)} [ c(s,a,s') + h(s') ] where c(s,a,s') is cost of action a from s to s' (units: cost units). This is the core LRTA* update (some variants use max with current h(s)).

Δh = min_{a in A(s)} [ c(s,a,s') + h(s') ] - h(s) is the incentive to increase h(s) based on the best neighbor estimate at s. Units: cost units.

Worked examples

Example 1 — Online DFS on a small graph (exam-style model answer)

Graph (draw this): Nodes: S, A, B, G. Edges: S->A (cost 2), S->B (cost 3), A->G (cost 5), B->A (cost 1), B->G (cost 10). Start S, goal G.

Agent uses Online DFS: always pick lowest alphabetical successor first (rule: A before B). Memory: visited on current trial.

Steps:

  1. At S, successors A, B. Choose A (rule). Move S->A (cost 2). Path cost so far g=2.
  2. At A, successors: G. Move A->G (cost 5). g becomes 2+5=7. Goal reached. Stop.

Final path: S-A-G with total cost 7 units. If the agent had chosen B first it would have explored B, then maybe backtracked and found A later; Online DFS executes moves physically, so backtracking costs are added if required.

Example 2 — LRTA* numeric update (step-by-step)

State graph (draw): s0(start) connects to s1 and s2. Edges: s0->s1 cost 2, s0->s2 cost 4. s1->G cost 5. s2->G cost 1. Initial heuristic values (student-given): h(s0)=3, h(s1)=3, h(s2)=2, h(G)=0. All costs in cost units.

Step 1 (at s0): compute for neighbors

  • option s1: c + h = 2 + 3 = 5
  • option s2: c + h = 4 + 2 = 6 min = 5. Update h(s0) <- min = 5 (or max(current, min) if using non-decreasing rule => h(s0)=5). Choose action to s1. Execute s0->s1 (cost 2). g so far = 2.

Step 2 (at s1): neighbors: G only. c + h = 5 + 0 = 5. Update h(s1) <- 5 (was 3). Choose action s1->G and execute (cost 5). Total cost = 2+5 = 7. Goal reached.

Heuristic table after one trial: h(s0)=5, h(s1)=5, h(s2)=2, h(G)=0.

Final answer: agent reached G with cost 7 units and updated heuristics as above.

(If the agent had selected s2 initially, it would have seen cheaper immediate connection to G but different updates could occur; LRTA* learns through trials.)

Example 3 — Model-answer question (theory)

Question: Explain why an online agent may be preferred over offline search in real robots.

Model answer (brief): Offline search requires a complete transition model and time to explore the state space before acting; in real robots this is often impossible because the environment is unknown or changing, sensing is noisy, and actions take time. An online agent can act quickly using local percepts, update its model, and handle dynamic changes. A trade-off: online agents may make suboptimal moves early but can adapt and learn heuristics for better future performance.

Common mistakes

  • Assuming LRTA* is immediately optimal; it typically improves heuristics over trials and may not yield the shortest path on the first trial.
  • Using an inadmissible heuristic claim when proving optimality for offline A* or implying the same optimality for online LRTA* without conditions.
  • Omitting the condition that states must be observable (or else belief maintenance is needed) when describing online agents.

For your exam

Typical question types: definitions (define online agent, heuristic, admissible), short notes (compare online vs offline search), derivations (show LRTA* update computation), numericals (simulate small graphs, compute updated h-values and final path cost), diagrams (draw the graph and label path, show LRTA* updates), and proofs (show h-values non-decreasing with the max-update rule; sketch completeness proof in finite deterministic graphs).

What full-marks answers include:

  • Precise definitions of terms used.
  • Clear assumptions (deterministic, observable states, finite state space) before giving guarantees.
  • Correct pseudo-code or step-by-step simulation with costs carried through and final bold numeric answer with units.
  • For proofs, state base cases and induction hypothesis, and reference the update rule explicitly.

Quick check

  1. Define an online search agent in two lines.
  2. Write the LRTA* local update used at a state s.
  3. Why does Online DFS add extra cost compared to offline DFS?

Answers: 1) An online search agent is an agent that interleaves sensing and acting without complete model knowledge, choosing actions based on current percepts and memory; it updates knowledge during execution. 2) h(s) <- min_{a in A(s)} [ c(s,a,s') + h(s') ] (optionally replaced by max(h(s), min_... ) to keep non-decreasing). 3) Because it physically executes moves and must backtrack by action when it discovers dead-ends, so backtracking costs are real and included in total path cost.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?