Proceedings

What Makes You Special? Contrastive Heuristics Based on Qualified Dominance

Rasmus G. Tollund, Kim G. Larsen, Alvaro Torralba

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 8652-8660.

https://doi.org/10.24963/ijcai.2025/962

Keywords

  • Search: S: Heuristic search
  • Planning and Scheduling: PS: Planning algorithms
  • Planning and Scheduling: PS: Theoretical foundations of planning
  • Planning and Scheduling: PS: Search in planning and scheduling

Abstract

In cost-optimal planning, dominance pruning methods discard states during the search that are dominated by others. However, the binary nature of pruning fails to exploit information when we cannot prove that a state is fully dominated. To this end, we introduce qualified dominance, an automatic method that given a pair of states s,t synthetizes a finite state automaton that represents a language of plans from s that are dominated by t. This not only explains why s cannot be pruned, but also can be used to improve the heuristic function to guide the search. This results in a new type of heuristic, which we call contrastive heuristics, that are dependent on the search performed so far. We provide the theoretical foundation for showing that contrastive heuristics can be used to find optimal plans even when their more informative estimates are not admissible.

Rasmus G. Tollund, Kim G. Larsen, and Álvaro Torralba. 2025. What Makes You Special? Contrastive Heuristics Based on Qualified Dominance. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 8652–8660. https://doi.org/10.24963/ijcai.2025/962
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards