A Brief Summary of Planning and Scheduling

The problem of planning, in AI, is to find a path through a state space from a specified initial state to a state that satisfies certain specified goal conditions. The state space is described in terms of the propositions that hold in each state and, for metric domains, the values of the metric variables. The transitions between states are determined by the legal actions of the domain. In classical planning, only single actions may be used in a transition, while in more complex domains concurrent actions are allowed, subject to conditions on their possible interactions.

An important aspect of planning is that it is usual to separate the planning strategies and systems from the domain descriptions that are used for planning. That is, a planner is intended to be a general solution to planning problems, applied to specific domains and problem instances by being supplied with a description of the domain and problem. This description is a model of the problem to be solved, indicating under what conditions actions may be applied and the effects of applying them. The model can therefore be used to predict the consequences of applying an action in a state and, hence, be used to construct the paths through state space ahead of execution. The models also play the role of making apparent what choices are available to a planner at each state.

The broad architecture of a planning system is therefore as illustrated below.

There is a strong relationship between V&V and P&S: both communities typically rely on search in spaces defined by the structures of models in order to solve their respective problems. The models of state-transition systems used for planning are very similar to those used in many model-based verification and validation systems (for example, hybrid automata have been proposed as a model for planning problems). This workshop is intended to be the first step in promoting a more regular exchange of ideas, languages and algorithms between these communities.