Theory and algorithms for plan merging

摘要

Merging operators in a plan can yield significant savings in the cost to execute a plan. This paper provides a formal theory for plan merging and presents both optimal and efficient heuristic algorithms for finding minimum cost merged plans. The optimal plan merging algorithm applies a dynamic programming method to handle multiple linear plans and is extended to partially ordered plans in a novel way. Furthermore, with worst-case and average-case complexity analysis and empirical tests, we demonstrate that efficient and well-behaved approximation algorithms are applicable for optimizing plans with large sizes.