AN APPROACH FOR MERGING PLANS HIERARCHICALLY IN DECOMPOSABLE DOMAINS

Recent works in domain-independent plan merging have shown that the op timal plan-merging problem is NP-hard, and heuristic algorithms have b een proposed to generate near-optimal solutions. These works have show n heuristic algorithms which assume that the mergeability of two actio ns can be determined by considering only the actions themselves. In th is paper, we show that it is often that case that the surrounding acti ons in the plan must also be considered when determining the mergeabil ity of two or more actions; therefore, the context in which the action s are used affects their mergeability. To address this problem, we hav e developed a plan-merging methodology that merges partial-order plans based on the the notion of plan fragments, which encapsulate actions with the context in which they are being utilized. This methodology ap plies to a class of planning domains, called decomposable domains, whi ch consist of actions that follow all or some portion of a type sequen ce. Merging is performed hierarchically by action type. We also invest igate the previously unexplored notion of alternative actions in domai n-independent plan merging, which can improve the quality of the resul ting merged plan. A novel approach is presented for removing cyclic de pendencies that may occur during the plan-merging process. A key part of the methodology is the computation of a minimum cost cover of plan fragments. We provide theoretical analyses of two optimal algorithms a nd a greedy-based algorithm for computing the minimum cost cover. We s upport the theoretical analysis of these algorithms with experimental data to show that the greedy approach is near-optimal and efficient.