Sven Koenig, Avrim Blum, Richard Korf, Toru Ishida
On-line search is driven by the need to commit to "actions" before their complete consequences are known. An "action," in this context, can correspond to such diverse things as making a move in a two-player game, moving a robot, or allocating some resource (such as a page in a cache). On-line search can be necessary for a variety of reasons: there may be missing domain knowledge that has to be acquired actively, the domain may be known but so large that it cannot be searched completely in a reasonable amount of time, or it may simply be that the consequences of one’s actions depend on the behavior of some other entity. On-line search can also reduce the sum of planning and execution time.