Hierarchically merging plans in decomposable domains

Recent works in domain-independent plan merging have shown that the optimal plan merging problem is NP-hard, and heuristic algorithms have been proposed to generate near-optimal solutions. We have developed a plan merging methodology that merges partial-order plans based on the notion of plan fragments. In contrast to previous works, mergeability classes no longer necessarily form a partition over the set of actions in the input plans. This methodology applies to a class of planning domains which are decomposable. We also investigate the previously unexplored notion of alternative actions in domain-independent plan merging, which can improve the quality of the resulting merged plan, and a novel approach is presented for removing cyclic dependencies that may result during the plan merging process. We provide theoretical analyses of several algorithms for computing the minimum cost cover of plan fragments, a central component of the methodology. We support the theoretical analysis of these algorithms with experimental data to show that a greedy approach is near-optimal and efficient.