Peter Norvig on Online Search - Dictionary of Arguments
Norvig I 147
Online search/Norvig/Russell: The term “online” is commonly used in computer science to refer to algorithms that must process input data as they are received rather than waiting for the entire input data set to become available. >Search algorithms/Norvig.
Offline algorithms: compute a complete solution before setting foot in the real world and then execute the solution.
Online search agents: an online search agent interleaves computation and action: first it takes an action, then it observes the environment and computes the next action. Online search is a good idea in dynamic or semi-dynamic domains - domains where there is a penalty for sitting around and computing too long. Online search is also helpful in nondeterministic domains because it allows the agent to focus its computational efforts on the contingencies that actually arise rather than those that might happen but probably won’t. Online search is a necessary idea for unknown environments. The agent faces an exploration problem and must use its actions as experiments in order to learn enough to make deliberation worthwhile. An online search problem must be solved by an agent executing actions, rather than by pure computation. E.g., the agent cannot determine RESULT(s, a) except by actually being in s and doing a.
Norvig I 148
Competitive ratio: Typically, the agent’s objective is to reach a goal state while minimizing cost. (Another possible objective is simply to explore the entire environment.) The cost is the total path cost of the path that the agent actually travels. It is common to compare this cost with the path cost of the path the agent would follow if it knew the search space in advance—that is, the actual shortest path (or shortest complete exploration). In the language of online algorithms, this is called the competitive ratio; we would like it to be as small as possible.
Norvig I 149
Environment: After each action, an online agent receives a percept telling it what state it has reached; from this information, it can augment its map of the environment. The current map is used to decide where to go next. (See below random walk.)
Offline search agents: can expand a node in one part of the space and then immediately expand a node in another part of the space, because node expansion involves simulated rather than real actions.
An online algorithm, on the other hand, can discover successors only for a node that it physically occupies. To avoid traveling all the way across the tree to expand the next node, it seems better to expand nodes in a local order. Depth-first search (>Search algorithms/Norvig) has exactly this property because (except when >backtracking) the next node expanded is a child of the previous node expanded. (>Genetic algorithms/Norvig).
Norvig I 150
Hill-climbing search: Like depth-first search, hill-climbing search has the property of locality in its node expansions. (…) because it keeps just one current state in memory, hill-climbing search is already an online search algorithm! Unfortunately, it is not very useful in its simplest form because it leaves the agent sitting at local maxima with nowhere to go. Moreover, random restarts cannot be used, because the agent cannot transport itself to a new state.
Random walk: Instead of random restarts, one might consider using a random walk to explore the environment. A random walk simply selects at random one of the available actions from the current state.
Norvig I 153
Learning: 1st. the agents learn a “map” of the environment—more precisely, the outcome of each action in each state—simply by recording each of their experiences.
2nd. the local search agents acquire more accurate estimates of the cost of each state by using local updating rules, as in LRTA∗._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010