A Quantitative Theory for Plan Merging

Merging operators in a plan can yield significant savings in the cost to execute a plan. Past research in planning has concentrated on handling harmful interactions among plans, but the understanding of positive ones has remained at a qualitative, heuristic level. This paper provides a quantitative study for plan optimization and presents both optimal and approximate algorithms for finding minimum-cost merged plans. With worst and average case complexity analysis and empirical tests, we demonstrate that efficient and wellbehaved approximation algorithms are applicable for optimizing general plans with large sizes.

Authors

• David E. Foulser Ming Li

Keywords

No keywords are indexed for this paper.