A Hybrid Linear Programming and Relaxed Plan Heuristic for Partial Satisfaction Planning Problems

J. Benton, Menkes van den Briel, Subbarao Kambhampati

The availability of informed (but inadmissible) planning heuristics has enabled the development of highly scalable planning systems. Due to this success, a body of work has grown around modifying these heuristics to handle extensions to classical planning. Most recently, there has been an interest in addressing partial satisfaction planning problems, but existing heuristics fail to address the complex interactions that occur in these problems between action and goal selection. In this paper we provide a unique admissible heuristic based on linear programming that we use to solve a relaxed version of the partial satisfaction planning problem. We incorporate this heuristic in conjunction with a lookahead strategy in a branch and bound algorithm to solve a class of over-subscribed planning problems.

Subjects: 1.11 Planning; Please choose a second document classification

Submitted: Jun 28, 2007

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.