Paper Info
Title
A Hybrid Linear Programming and Relaxed Plan Heuristic for Partial Satisfaction Planning Problems
Abstract
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 ex- isting 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 plan- ning problems.
Year
Venue
Keywords
2007
ICAPS
branch and bound algorithm,linear program
Field
DocType
Citations 
Mathematical optimization,Branch and bound,Business system planning,Heuristic,Computer science,Admissible heuristic,Heuristics,Linear programming,Scalability
Conference
18
PageRank 
References 
Authors
0.95
10
3
Name
Order
Citations
PageRank
J. Benton11559.45
Menkes Van Den Briel218311.68
Subbarao Kambhampati33453450.74