Constraint partitioning for solving planning problems with trajectory constraints and goal preferences

The PDDL3 specifications include soft goals and trajectory constraints for distinguishing high-quality plans among the many feasible plans in a solution space. To reduce the complexity of solving a large PDDL3 planning problem, constraint partitioning can be used to decompose its constraints into subproblems of much lower complexity. However, constraint locality due to soft goals and trajectory constraints cannot be effectively exploited by existing subgoal-partitioning techniques developed for solving PDDL2.2 problems. In this paper, we present an improved partition-and-resolve strategy for supporting the new features in PDDL3. We evaluate techniques for resolving violated global constraints, optimizing goal preferences, and achieving subgoals in a multi-valued representation. Empirical results on the 5^th International Planning Competition (IPC5) benchmarks show that our approach is effective and significantly outperforms other competing planners.