Splicing Plans to Achieve Misordered Goals

Abstract

Most parallel planners are sensitive to the order in which goals and activity preconditions are specified. A wrong ordering can easily cause a solution to be missed. Permuting goals and preconditions on failure in hopes of finding a soluble order is in general computationally unacceptable. Plan splicing is a solution to this problem. Splicing is a violent conflict resolution procedure which involves the cutting of assertion dependencies, recursive demotion or excision of selected activities around the cut, and reinsertion of deachieved goals back into the middle of the planner's goal stack so that they can be replanned later to mend the plan around the splice. In a planner, after an excision it is further necessary to relieve the temporal stress induced on surviving activities by the activities which were excised. This is an important capability for two reasons: first, because the order of achievement can of course not always be known in advance, and secondly because it is desirable to be able to present goals in priority order.