TY - GEN
T1 - Incremental lower bounds for additive cost planning problems
AU - Haslum, Patrik
PY - 2012
Y1 - 2012
N2 - We present a novel method for computing increasing lower bounds on the cost of solving planning problems, based on repeatedly solving and strengthening the delete relaxation of the problem. Strengthening is done by compiling select conjunctions into new atoms, similar to the P* m construction. Because it does not rely on search in the state space, this method does not suffer some of the weaknesses of admissible search algorithms and therefore is able to prove higher lower bounds for many problems that are too hard for optimal planners to solve, thus narrowing the gap between lower bound and cost of the best known plan, providing better assurances of plan quality.
AB - We present a novel method for computing increasing lower bounds on the cost of solving planning problems, based on repeatedly solving and strengthening the delete relaxation of the problem. Strengthening is done by compiling select conjunctions into new atoms, similar to the P* m construction. Because it does not rely on search in the state space, this method does not suffer some of the weaknesses of admissible search algorithms and therefore is able to prove higher lower bounds for many problems that are too hard for optimal planners to solve, thus narrowing the gap between lower bound and cost of the best known plan, providing better assurances of plan quality.
UR - http://www.scopus.com/inward/record.url?scp=84866437576&partnerID=8YFLogxK
M3 - Conference contribution
SN - 9781577355625
T3 - ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling
SP - 74
EP - 82
BT - ICAPS 2012 - Proceedings of the 22nd International Conference on Automated Planning and Scheduling
T2 - 22nd International Conference on Automated Planning and Scheduling, ICAPS 2012
Y2 - 25 June 2012 through 29 June 2012
ER -