From Qualitative to Quantitative Dominance Pruning for Optimal Planning

From Qualitative to Quantitative Dominance Pruning for Optimal Planning

Álvaro Torralba

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 4426-4432. https://doi.org/10.24963/ijcai.2017/618

Dominance relations compare states to determine whether one is at least as good as another in terms of their goal distance. We generalize these qualitative yes/no relations to functions that measure by how much a state is better than another. This allows us to distinguish cases where the state is strictly closer to the goal. Moreover, we may obtain a bound on the difference in goal distance between two states even if there is no qualitative dominance.We analyze the multiple advantages that quantitative dominance has, like discovering coarser dominance relations, or trading dominance by g-value. Moreover, quantitative dominance can also be used to prove that an action starts an optimal plan from a given state. We introduce a novel action selection pruning that uses this to prune any other successor. Results show that quantitative dominance pruning greatly reduces the search space, significantly increasing the planners' performance.
Keywords:
Planning and Scheduling: Planning Algorithms
Planning and Scheduling: Search in Planning and Scheduling