A Quantitative Theory for Plan Merging

David E. Foulser, Ming Li, Qiang Yang

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 well-behaved approximation algorithms are applicable for optimizing general plans with large sizes.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.