Hierarchial Plan Merging with Application to Process
Planning
Department of Electrical and Computer Engineering
University of Arizona
Tucson, Arizona 85721
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 established, the continued
merging of the plan fragments in one node can take place independently of
plan fragments in other nodes on that level. This provides a decomposition
or divide-and-conquer 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.