1999 AAAI Spring Symposium on

Search Techniques for Problem Solving under Uncertainty and Incomplete Information

Call for Participants
Organizers
Important Dates
Information for Participants
Symposium Papers
Schedule
Symposium Summary to AAAI


Call for Papers

To build practical AI systems, one has to address issues related to uncertainty and incomplete information.  Uncertainty and incomplete information can result from various sources, including actuator and sensor noise, reasoning with approximate models, limited communication bandwidth, and insufficient domain understanding.

This symposium will focus on the selection of search strategies for problem solving under uncertainty and incomplete information, where the large number of contingencies can create large search spaces. Therefore, system performance ultimately depends largely on the efficiency of the selected search strategies.  Using appropriate search strategies can significantly increase system performance by exploiting problem-specific knowledge and restricting the search to the right regions of the search spaces to find satisfactory solutions quickly.

The main purpose of the symposium is to bring together researchers and practitioners from areas such as planning, heuristic search, robotics, constraint satisfaction, game playing, and information gathering.  We want to discuss when and how traditional search techniques (such as state-space search and local search) should be applied; how uncertain and incomplete information can be exploited to control search processes; whether there is a difference in principle between reasoning with deterministic and probabilistic representations of uncertain and incomplete information (for example, with constraint networks or belief networks); how the level of uncertainty affects problem complexity; how different search paradigms (such as heuristic search and dynamic programming) can be combined to provide additional pruning power; and how the structure of search spaces can be exploited to speed up search. We also intend to explore how these search strategies can be applied across domains and application areas, and speculate on promising future search strategies.

The symposium will consist of one or 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 application domains.

All types of papers are sought, including papers describing theory, algorithms, applications, systems, performance measures, and other issues related to search strategies for problem solving under uncertainty and incomplete information.  Papers on work in progress are encouraged.  Other interested participants should send a short description of their research interests with a list of relevant publications.  Suggestions for panel and group discussions are also welcome.

Submission in postscript format should be sent, electronically, to zhang@isi.edu.  Authors should follow the general AAAI submission guidelines (see Author Instruction for details). The maximum length should be limited to six pages, in AAAI format.


Organizers

Weixiong Zhang (Cochair), (USC/ISI, zhang@isi.edu)
Sven Koenig (Cochair), (Georgia Tech, skoenig@cc.gatech.edu)
Tom Dean (Brown, tld@cs.brown.edu)
Rina Dechter (UC Irvine, dechter@ics.uci.edu)
Subbarao Kambhampati (Arizona State, rao@asu.edu)
Lydia Kavraki (Rice, kavraki@cs.rice.edu)
Craig Knoblock (USC/ISI, knoblock@isi.edu)
Shlomo Zilberstein (U Mass, shlomo@cs.umass.edu)


Important Dates

Abstract or paper due: October 30, 1998
Camera-ready version due: January 29, 1999
Spring symposium: March 22-24, 1999, Stanford University.


Information for Participants

Invited participants must do the following:

By January 29, 1999, send camera-ready copy of your papers or statements of work, electronically and prefeered in postscript format, to zhang@isi.edu.

By January 29, 1999, send signed "Permissions to Distribute" forms, which can be obtained here, in hard copy, to,

        Weixiong (Wayne) Zhang
        Information Sciences Institute
        University of Southern California
        4676 Admiralty Way, Suite 1001
        Marina del Rey, CA 90292, USA

        Voice: (310) 822-1511 x735
        Fax: (310) 822-0751
        zhang@isi.edu

(In case you are not sure if the form will reach the above address by the due date, please fax me the form first.)

If you have special needs on Audio-Visual equipment, send an Audio-Visual Form, which can be retrieved from here, along with the "Permissions to Distribute" forms.

(Your papers will be organized into a complete working note, and be sent, along with the "Permissions to Distribute" forms, to AAAI.  So, it is important to send your papers and the forms to Weixiong Zhang by the due date!)

Other important dates you may want to remember or know:

For other information, such as travel and hotel, see here.


Symposium Papers

PSIPOP: Planning with sensing over partially closed worlds
by Tamara Babaian and James Schmolze

A Genetic search in policy space for solving Markov decision processes
by Danny Barash

Using selective-sampling simulations in Poker
by Darse Billings, Denis Papp, Lourdes Pena, Jonathan Schaeffer, and Duane Szafron

Search control methods in Deep Blue
by Murray Campbell, A. Joseph Hoane, Jr. and Feng-hsiung Hsu

Controlling the parameters of parallel search using uncertainty reasoning
by Diane Cook and Piotr Gmytrasiewicz

Learning situation-dependent rules: Improving planning for an incompletely modeled domain
by Karen Haigh and Manuela Veloso

Interval processing for search control under incomplete data
by Pham Hong Hanh

Solving Markov decision problems using heuristic search
by Eric A. Hansen and Shlomo Zilberstein

Extended abstract: Learning search strategies
by Daishi Harada and Stuart Russell

Robot sonar mapping by Bayesian search
by Kenneth Harris and Michael Recce

Branch-and-bound with mini-bucket heuristics
by Kalev Kask and Rina Dechter

Overview and examples of real-time search in unknown or nondeterministic domains
by Sven Koenig

Divide-and-conquer bidirectional search
by Richard Korf

Stochastic sampling and search in belief updating algorithms for Bayesian networks
by Yan Lin and Marek J. Druzdzel

C-MAXPLAN:  Contingent Planning in the MAXPLAN framework
by Stephen M. Majercik

Incremental data-driven refinement of knowledge
by Robert Morris and Ibrahim El-far

Strategic search: A new paradigm for complex game playing - Application to the game of Go
by Regis Moneret

Partial order evaluation in game tree search, and its application to analyzing Semeai in the game of Go
by Martin Muller

Search techniques for learning probabilistic models of word sense disambiguation
by Ted Pedersen

Attributes of the invertive problems
by Semyon D. Savransky

Direct policy search and uncertain policy evaluation
by Jurgen Schmidhuber and Jieyu Zhao

Manufacturing planning under uncertainty and incomplete information
by Yury Smirnov

Efficient planning through separate resource scheduling
by Biplav Srivastava and Subbarao Kambhampati

Searching stochastically-generated mulit-abstraction-level design spaces
by Louis Steinberg

Learning to plan probabilistically
by Ron Sun and Chad Sessions

Truncated and anytime depth-first branch-and-bound: A case study on the ATSP
by Weixiong Zhang
 


Symposium Schedule (Tentative)

Monday, March 22, 1999

Opening Remarks (9:00 am - 9:10 am)
by Weixiong Zhang

Search in Stochastic Domains - Markov Model

Invited Talk: Frontiers and Horizons: Directions in Search and Action under Uncertainty (9:10 am - 10:00 am)
by Eric Horvitz

Solving Markov decision problems using heuristic search (10:00 am - 10:20 am)
by Eric A. Hansen and Shlomo Zilberstein

A Genetic search in policy space for solving Markov decision processes (10:20 am - 10:40 am)
by Danny Barash

Direct policy search and uncertain policy evaluation (10:40 am - 11:00 am)
by Jurgen Schmidhuber and Jieyu Zhao

11:00 am - 11:10 am: Break

Search Control through Uncertainty Reasoning

Extended abstract: Learning search strategies (11:10 am - 11:30 am)
by Daishi Harada and Stuart Russell

Controlling the parameters of parallel search using uncertainty reasoning (11:30 am - 11:50 am)
by Diane Cook and Piotr Gmytrasiewicz

Interval processing for search control under incomplete data (11:50 am - 12:10 am)
by Pham Hong Hanh

12:10 pm - 12:30 pm: Panel discussions - Search Control in Stochastic Domains (Moderator: Shlomo Zilberstein)

12:50 pm - 2:00 pm: Lunch

Search in Stochastic Domains - Bayesian Networks

Featured Talk: Combining search and inference in automated reasoning (2:00 pm - 2:50 pm)
by Rina Dechter

Branch-and-bound with mini-bucket heuristics (2:50 pm - 3:10 pm)
by Kalev Kask and Rina Dechter

Stochastic sampling and search in belief updating algorithms for Bayesian networks (3:10 pm - 3:30 pm)
by Yan Lin and Marek J. Druzdzel

3:30 pm - 3:40 pm: Break

Learning Control Rules and World Models

Learning situation-dependent rules: Improving planning for an incompletely modeled domain (3:40 pm - 4:00pm)
by Karen Haigh and Manuela Veloso

Robot sonar mapping by Bayesian search (4:00 pm - 4:20 pm)
by Kenneth Harris and Michael Recce

Search techniques for learning probabilistic models of word sense disambiguation (4:20 pm - 4:40 pm)
by Ted Pedersen

4:40 pm - 5:00 pm: Panel discussions - Search and Learning in Stochastic Domains (Moderator: Karen Haigh)

6:00 pm - 7:00 pm:  Reception
 

Tuesday, March 23, 1999

Planning with Uncertainty and Incomplete Information

Manufacturing planning under uncertainty and incomplete information (9:00 am - 9:20 am)
by Yury Smirnov

Learning to plan probabilistically (9:20 am - 9:40 am)
by Ron Sun and Chad Sessions

C-MAXPLAN:  Contingent Planning in the MAXPLAN framework (9:40 am - 10:00 am)
by Stephen M. Majercik

PSIPOP: Planning with sensing over partially closed worlds (10:00 am - 10:20 am)
by Tamara Babaian and James Schmolze

10:20 am - 10:30 am: Break

Resource Allocation and Performance

Overview and examples of real-time search in unknown or nondeterministic domains (10:30 am - 10:50 am)
by Sven Koenig

Efficient planning through separate resource scheduling (10:50 am - 11:10 am)
by Biplav Srivastava and Subbarao Kambhampati

Searching stochastically-generated mulit-abstraction-level design spaces (11:10 am - 11:30 am)
by Louis Steinberg

Divide-and-conquer bidirectional search (short presentation) (11:30 am - 11:40 am)
by Richard Korf

Truncated and anytime depth-first branch-and-bound: A case study on the ATSP (short presentation) (11:40 am - 11:50 am)
by Weixiong Zhang

Miscellaneous

Incremental data-driven refinement of knowledge (short presentation) (11:50 am - 12:00 pm)
by Robert Morris and Ibrahim El-far

Attributes of the invertive problems (short presentation) (12:00 pm - 12:10 pm)
by Semyon D. Savransky

12:10 pm - 12:30 pm: Panel discussions - Real World Problems and Resource Constraints (Moderator: Sven Koenig)

12:50 pm - 2:00 pm: Lunch

Search Control in Computer Games

Invited Talk - Search control methods in Deep Blue (2:00 pm - 2:50 pm)
by Murray Campbell, A. Joseph Hoane, Jr. and Feng-hsiung Hsu (Murray Campbell will give the talk)

Using selective-sampling simulations in Poker (2:50 pm - 3:10 pm)
by Darse Billings, Denis Papp, Lourdes Pena, Jonathan Schaeffer, and Duane Szafron

Partial order evaluation in game tree search, and its application to analyzing Semeai in the game of Go (3:10 pm - 3:30 pm)
by Martin Muller

Strategic search: A new paradigm for complex game playing - Application to the game of Go (3:30 pm - 3:50 pm)
by Regis Moneret

3:50 pm - 4:10 pm: Panel discussions - Search Control in Computer Games (Moderator: Jonathan Schaeffer)

4:10 pm - 5:00 pm: Open discussion - Common Problems, Techniques, and Future Directions (Moderator: Weixiong Zhang)

6:00 pm - 7:00 pm:  Plenary session (speaker: Shlomo Zilberstein)


Symposium Summary to AAAI

by Sven Koenig, Shlomo Zilberstein and Weixiong Zhang

Many real-world systems have to perform robustly in the presence of uncertainty. The AAAI Spring Symposium on Search Techniques for Problem Solving under Uncertainty and Incomplete Information, chaired by Weixiong Zhang and Sven Koenig, covered topics such as how to search different representations of uncertain information (including belief networks and Markov models), how to explore and map unknown environments, how to use learning and reasoning about uncertainty to improve search performance, and how to allocate resources under uncertainty. Application domains included manufacturing, linguistics, genetics, robotics, design, scheduling, health care, coding theory, constraint satisfaction, and games such as chess, poker, go, and tetris.

Eric Horvitz, Rina Dechter, and Murray Campbell (representing all of IBM's Deep Blue chess team) gave invited talks. Common themes of their presentations as well as the presentations by the other participants were the need to use non-uniform search techniques to cope with the search complexity in the presence of uncertainty, including combining search methods that run in software and hardware, combining simulation and search, combining learning and search, interleaving search with action executions, and using multiple abstraction levels with different evaluation functions during the search. It was also discussed how to generalize the scalar evaluation functions often used by heuristic search methods to intervals (using either total or partial orderings), probability distributions, or tuples of values that can be used in conjunction with possibly non-additive multi-attribute utility functions. Other issues included non-myopic search control, the selection of search methods based on domain properties, and the development of standard search architectures and tool. Despite the impressive progress, the general feeling was that we are just beginning to understand the hard issues involved in search control under uncertainty and incomplete information.  These issues will remain at the core of artificial intelligence research.