Description: AAAI-97 Workshop on On-Line Search

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.

The on-line search paradigm underlies many applications and has been independently investigated in

artificial intelligence (single-agent search and two-player games),
robotics (path planning and execution), 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 (including anytime algorithms), on-line algorithms and competitive analysis, real-time heuristic search, reinforcement learning, robot exploration techniques, and sensor-based planning.

The AAAI workshop on On-Line Search is intended to bring together researchers from different fields who investigate on-line search approaches. Our goal is to learn about the different methods, assumptions, and results, and to enable the transfer of ideas between the different fields.

Questions that we hope to see addressed during the workshop include, but are not limited to

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.

We are especially interested in the trade-offs between

thinking versus acting, and
acting to exploit existing knowledge versus acting to acquire further knowledge.

We are also interested in applications of on-line search algorithms as well as empirical and formal results that explain how properties of the tasks and domains influence the behavior and efficiency of on-line search algorithms.

The workshop will consist of two invited talks, followed by short presentations and longer discussions, in an atmosphere that encourages the interaction of researchers with different backgrounds. There will be plenty of opportunity to discover common ground between different fields and to speculate on how methods from one field could be applied to another.

You can also retrieve a flier (in Postscript) that contains similar information.

maintained by skoenig+@cs.cmu.edu; last updated on November 15, 1996