Online Search

search

Definition

Online Search

Online search involves an agent interleaving computation (planning) and action execution. It decides on the next action, performs it, observes the outcome, and then plans the subsequent action. This method is employed when the environment is unknown, dynamic, or when the agent lacks complete information, forcing it to explore and make decisions incrementally (“search as you go”).

Online vs. Offline

Online is different from offline search in the following aspects:

• can’t “jump” in the search space to states
• follow “real” actions
• must go from state $s$ to “physical” successor state $s^{\prime }$ ⇒ local expansion

Example

Puzzle

Ingredients:

• $\text{ACTIONS}(s)$: set of actions doable in state $a$
• $c(s,a,s^{\prime })$: cost of taking action $a$ in $s$ with result $s^{\prime }$
• $\text{IS-GOAL}(s)$: goal test
• (optional) $h(s)$: heuristic

whether $s^{\prime }\in \text{RESULT}(s,a)$ may be unknown.

Problems:

• Goal achievement: reach some goal from initial state (e.g., escape from a maze)
• Explore environment: learn $\text{RESULT}$, state space $S$ (e.g., map building)
• Model building: learn $\text{ACTIONS},\text{RESULT},S$

Dead end states (no goal reachable) are unavoidable in all state space (which action too choose in $A$). Consider safe explorability: some goal is reachable from any state, e.g. maze, 8-puzzle, vacuum world.

Performance:

• Competitive ratio: cost of path travelled / optimal path cost
• Characteristics: size of the state space (not shallowest goal)