Hierarchical Plan Merging with Application to Process Planning

Abstract

We have developed a domain-independent systematic methodology for plan merging at the various levels of plan abstraction. This method manifests itself in the hierarchical plan graph where each level contains a complete, partially merged plan. The principle advantage of this approach is that, once external interactions between nodes on a given level have been estab.lished, the continued merging of ~he plan fragments in one node can take place zndependently of plan fragments in other nodes on that level. This provides a decomposition or divide-andconquer approach to plan merging. Another advantage to this decomposition approach is that replanning effort is minimized in the presence of the selection of alternative actions at some level of the hierarchical plan graph. Only those plan fragments which are in the same branch as the alternative selection need be considered for replanning. Also, an algorithm is proposed which takes a bilateral approach to breaking cyclic dependencies between nodes in the hierarchical plan graph. We demonstrate the utility of this hierarchical approach to plan merging through examples in .the process planning domain.