Planning

In planning systems, actions are functions from states to states. Actions are chosen by an agent, who must construct an ordered sequence of them, transforming a given initial state to a final state. The states are descriptions of the world, and so are represented by propositions in a logical language. It is assumed that within this world, the only changes that occur are those due to the planning agents. The set of states may not be finite, and so the set of pairs of states required to describe the function over its domain may not be finite, yet the function needs to be expressed as compact rules. In the STRIPS planning system [21], actions are realised as a mechanism that checks entailment of a precondition proposition by the given state, and then adds and deletes propositions from a set of conjoined propositions using add and delete lists. The states are described using a simplified language of sets of atomic predicates over objects. The planner typically uses a search algorithm with heuristics to obtain a sequence that takes the agent from its observed initial state to its goal state.

For some problems, planning using STRIPS can be impractical, since it can require searching of very long chains of low-level actions. Hierarchical planning [60] addresses this problem by adding decomposition rules to the planning system. This allows aggregations of steps to be represented as well as more basic steps, producing shorter chains and thereby often reducing the search time. For example, a robot who needs to assemble a car would be able to construct a high level plan that checks for available parts and supplies for each assembly task, before proceeding to planning the individual arm movements that constitute one assembly task. This allows infeasible plans to be rejected before the low-level planning is done. Hierarchical planning proceeds by a combination of decomposition chaining and precondition-effect chaining. In particular, decomposition has emerged as simple and effective representation for dialogue planning rules, and forms the foundation for most dialogue planning and plan recognition models. By using decomposition, the language of dialogue act sequences can be expressed using a context-free grammar. For this reason, sets of plan rules are often called "dialogue grammars".