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.
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:
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
Opening Remarks (9:00 am - 9:10 am)
by Weixiong Zhang
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
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
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
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
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
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
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
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)
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.