TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 9647

Control of Search in AI Planning

( Nov 18 – Nov 22, 1996 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/9647

Organizers
  • J. Headler
  • J. Koehler




Goals of this Dagstuhl Seminar

In the field of artificial intelligence, ”planning” is defined as designing the behavior of some entity that acts, either an individual, a group, or an organization. The output is some kind of blueprint for behavior, which we call a plan. There are a wide variety of planning problems, differentiated by the types of their inputs and outputs. Typically, planning problems get more and more difficult as more flexible inputs are allowed and fewer constraints on the output are required. As this flexibility increases, the space of possibilities needing to be explored by the planning algorithm grows extremely quickly (usually exponentially).

The goal of this workshop was to provide a specific focus on controlling this search. This problem is the essence of the planning problem, and it arises regardless of which specific planning methodology is used (nonlinear planning, deductive planning, hierarchical planning, etc.) - in all of these controlling an exponentially growing search space is a central problem. In all planning formalizations, it is critical that some sort of knowledge (heuristic or otherwise) is used to make reasonable decisions at any of the many choice points which arise in planning. Such choice points can concern:

  • ordering of subgoals
  • selection of operators/control structures
  • resolution of conflicts/threats by different techniques
  • choosing between differing commitment strategies
  • selecting/choosing the right control regime

In all of these cases, picking the right control knowledge can result in an algorithm that is able to identify and prune many dead-end branches of the search space before the algorithm explores them, ideally while preserving the soundness and completeness of the planner. However, designing search control approaches is difficult and it is often impossible to ensure various qualitative and quantitative properties of the “controlled algorithms”.

The workshop brought together over 30 participants from Europe, America, Asia, and Australia representing a large part of the planning community. The programme consisted of invited survey talks, short presentations of participants, working group sessions, and a general discussion about the empirical evaluation of planning systems. We had invited talks on search control in deductive planning, structural categorization of planning domains and problems, dynamic planning, and search problems and techniques from operations research. The working groups addressed in detail the questions of different search spaces, domain based features and domain analysis, and search control in dynamic real time domains. This report contains the abstracts of presentation and invited talks as well as a summary of the working group sessions.


Participants
  • J. Headler
  • J. Koehler