On-Line Search
Papers from the AAAI Workshop
Sven Koenig, Chair
Technical Report WS-97-10
134 pp., $30.00
ISBN 978-1-57735-041-5
[Add to Cart] [View Cart]
On-line search is driven by the need to commit to "actions" before their complete consequences are known, where an "action" can correspond to such diverse things as making a move in a two-player game, moving a robot, or allocating a page in a cache. On-line search can be necessary for a variety of reasons: there may be missing domain knowledge, 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.
The on-line search paradigm has been independently investigated in artificial intelligence (single-agent search and two-player games), robotics (path planning), and theoretical computer science, among others. This has resulted in the development of a variety of on-line search approaches including assumptive planning, deliberation scheduling and anytime algorithms, on-line algorithms and competitive analysis, real-time heuristic search, reinforcement learning, robot exploration techniques, and sensor-based planning.
Questions addressed by the workshop include
- What information to gather in the limited time available,
- When to stop collecting information and commit to an action, and
- What action to commit to given the information collected.