---
title: "What Makes You Special? Contrastive Heuristics Based on Qualified Dominance"
authors:
  - "Rasmus G. Tollund"
  - "Kim G. Larsen"
  - "Alvaro Torralba"
doi: "10.24963/ijcai.2025/962"
url: "https://ijcai.org/proceedings/2025/962"
pdf: "https://ijcai.org/proceedings/2025/0962.pdf"
venue: "Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"
year: 2025
pages: "8652-8660"
track: "Main Track"
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"
---

# What Makes You Special? Contrastive Heuristics Based on Qualified Dominance

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

*Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence*, pages 8652-8660. DOI: [10.24963/ijcai.2025/962](https://doi.org/10.24963/ijcai.2025/962)

## 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.