Simultaneous Planning for Sets of Initial States

Abstract

We describe a planning algorithm which can handle a set of initial problem states simultaneously. Our aim is to construct a single plan which represents optimal operator sequences for all possible states of a given problem. Goals are expressed by conjunctions of predicates. Dependencies between subgoals are determined by a model-based approach. Optimal (i.e. shortest) operator sequences can be achieved by taking account of side eeects. Simultaneous planning is achieved by a generalized notion of production rules: For each predicate deened in the problem deenition language there is a conditional expression which describes how to proceed if the predicate is already fulllled for a problem state and how to proceed if this predicate is not fulllled. In the rst case, the planner continues recursively with the predicates not yet regarded. In the second case, an operator-together with its preconditions and its eeects-is provided, which is to be applied to fullll the predicate. The planner proceeds recursively with the remaining predicates, adding any predicates that were given as preconditions of the operator. Planning terminates successfully if all problem states are covered and/or if all predicates have been processed. The resulting plan is a binary tree with predicates as nodes, operators as arc labels and problem states as leafs. Such plans can be interpreted as conditional programs. Furthermore, this kind of plans can be generalized to recursive programs by an inductive program synthesis approach. We thank Baback Parandian, Thomas Wierczoch and J urgen Winkler who contributed to this work during their participation on a student project and Mark M uller for technical support.

Topics

    0 Figures and Tables

      Download Full PDF Version (Non-Commercial Use)