Completeness-Preserving Dominance Techniques for Satisficing Planning

Completeness-Preserving Dominance Techniques for Satisficing Planning

Álvaro Torralba

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4844-4851. https://doi.org/10.24963/ijcai.2018/673

Dominance pruning methods have recently been introduced for optimal planning. They compare states based on their goal distance to prune those that can be proven to be worse than others. In this paper, we introduce dominance techniques for satisficing planning. We extend the definition of dominance, showing that being closer to the goal is not a prerequisite for dominance in the satisficing setting. We develop a new method to automatically find dominance relations in which a state dominates another if it has achieved more serializable sub-goals. We take advantage of dominance relations in different ways; while in optimal planning their usage focused on dominance pruning and action selection, we also use it to guide enforced hill-climbing search, resulting in a complete algorithm.
Keywords:
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Search in Planning and Scheduling
Planning and Scheduling: Planning and Scheduling