Planning with Abstraction Based on Partial Predicate Mappings

Abstract

Planning with abstraction has been studied to perform an efficient planning, and consists of processes for making abstraction, searching an abstract plan, and instantiating the abstract plan to obtain a final plan at a concrete level. If an abstract plan cannot be instantiated to any plan at the concrete level, it is no use obtaining the final plan. To avoid such an instantiation failure, each abstract plan must be instantiated to one or more concrete plans. This requirement is called Downward-Solution Property(DSP), and a system satisfying it has been already proposed by J. D. Tenenberg. However the very severe constraint in abstracting operators is assumed to satisfy DSP. As a result, only few abstract operators might be used for searching an abstract plan. This means that the planning ability at abstract level is decreased to satisfy DSP. The purpose of this paper is to make the framework proposed by Tenenberg more flexible, still preserving DSP. For this purpose, the notion of a partial predicate mapping is introduced. A partial predicate mapping corresponds to a refinement of inheritance hierarchy used in abstracting operators. After partitioning a given concrete operator set, a partial predicate mapping is computed for each subset, and operators of the subset being instances under the partial predicate mapping are abstracted. Using abstract operators thus obtained, searching an abstract plan is carried out followed by an instantiation process. This paper contains some experimental results, and shows that the technique using partial predicate mappings is useful for improving planning process. Furthermore a theoretical result is also presented. It is shown that the proposed system satisfies DSP.