The reuse of multiple cases to solve a single planning problem presents a promise of better utilization of past experience over single‐reuse planning, which can lead to better planning performance. In this paper, we present the theory and implementation of CBPOP, and show how it addresses the multi‐reuse planning problems. In particular, we present novel approaches to retrieval and refitting. We also explore the difficult issue of when to retrieve in multi‐reuse scenarios, and we empirically compare the results of several solutions we propose. Results from our experiments show that the best ranking function for pure generative planning is not necessarily the best ranking function for multi‐reuse planning. The surprising result in the reuse scenarios is that the single‐goal case library performed better than larger case libraries consisting of solutions to multi‐goal problems.

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.

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. These works have shown heuristic algorithms which assume that the mergeability of two actions can be determined by considering only the actions themselves. In this paper, we show that it is often that case that the surrounding actions in the plan must also be considered when determining the mergeability of two or more actions; therefore, the context in which the actions are used affects their mergeability. To address this problem, we have 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 applies to a class of planning domains, called decomposable domains, which consist of actions that follow all or some portion of a type sequence. Merging is performed hierarchically by action type. 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. A novel approach is presented for removing cyclic dependencies 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 and a greedy‐based algorithm for computing the minimum cost cover. We support the theoretical analysis of these algorithms with experimental data to show that the greedy approach is near‐optimal and efficient.