KR Conference 2014 Short Paper
Heuristic Guided Optimization for Propositional Planning
- Andreas Sideris
- Yannis Dimopoulos
the new planning system that is described here, shares with PSP the planning as optimization perspective, but it differs in a number of important ways. The first is the incremental goal achievement which, at a high level, works as follows. PSP-H first generates a sub-plan that, starting from the initial state, achieves a subset, of predefined size, of the problem goals. The state that results after the execution of the actions of this sub-plan, becomes the new initial state, and a new sub-plan that satisfies a larger subset of goals is computed. The procedure iterates and links together the subplans that are generated along the way. Therefore, instead of solving the original planning problem, PSP-H solves a series of smaller subproblems. A downside of this greedy approach is that it focuses on maximizing the number of achieved goals in a limited planning horizon, and it ignores completely goals that cannot be achieved within this horizon. In order to overcome the limitations that this would place on the effectiveness of the system, PSP-H is enhanced by a second technique called heuristic guidance, which imposes an additional requirement on the intermediate states that are computed by the PSP-H algorithm. The property that these states need to satisfy is that there must be a relaxed plan from each such state to the final state. PSP-H employs three different relaxation methods that are all based on ignoring some of the problem constraints, but they differ in their strength. The first relaxation method is the well-known delete lists relaxation, whereas the second method ignores all action mutexes. The last relaxation, which is stronger than the first but weaker than the second, ignores action mutexes and uses a subset of the fact mutexes that are heuristically selected. PSP-H is a incomplete and suboptimal planner implemented on top of the PSP system. Our experimental evaluation on a number of domains taken from planning competitions, demonstrates that PSP-H can solve challenging problems, that require long plans. Moreover, a preliminary comparison with Madagascar shows that the new system can solve more problems in some domains, and generate better quality solutions both in term of plan length and number of actions. Some of the techniques employed in PSP-H are similar to those used in other planning systems. For instance, the local optimization method of PSP-H bares some resemblance to the enforced hill-climbing approach of the Planning as Satisfiability is an important approach to Propositional Planning. A serious drawback of the method is its limited scalability, as the instances that arise from large planning problems are often too hard for modern SAT solvers. This work tackles this problem by combining two powerful techniques that aim at decomposing a planning problem into smaller subproblems, so that the satisfiability instances that need to be solved do not grow prohibitively large. The first technique, incremental goal achievement, turns planning into a series of boolean optimization problems, each seeking to maximize the number of goals that are achieved within a limited planning horizon. This is coupled with a second technique, called heuristic guidance, that directs search towards a state which satisfies all goals.