2007 · 27 citations · 13 references
BusinessDecision SciencesMarkov Decision ProcessesPath PlanningSchedulingConstraint SatisfactionHeuristic OptimizationHeuristic SearchInteger ProgrammingAdmissible HeuristicsHeuristicsLinear Programming RelaxationsLookahead MechanismsScalable Planning Algorithms
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 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.
13
Graphical Models for Preference and Utility
Fahiem Bacchus, Adam J. Grove · arXiv (Cornell University) · 2013 · 225 citations · Full text