ConAn: Contrastive Analysis for State-Space Exploration

This project introduces a new concept to guide search in AI Planning: Contrastive Analysis. The key idea is to give AI tools the ability to understand what the advantages and disadvantages of each alternative are. My hypothesis is that this ability is a fundamental skill for decision making and could change the way current AI systems make decisions.

This project is funded by the prestigious Sapere Aude grant, funded by the "Danmarks Frie Forskningsfond" (DFF). You can read the information about the project in DFF webpage here.

Rasmus G. Tollund and Maria Fernanda Salerno have joined the project as PhD Students.

A PostDoc position will be opened soon. Keep an eye on AAU vacant positions page if you are interested.

Objectives of the project:

Our vision is to introduce new search algorithms for sequential-decision making that are able to compare states during the search. Some specific objectives of the project are:

How to compare states? We aim to introduce new methods based on simulation relations in order to compare states during the search in different ways, and obtain information even when a state is not strictly better than another.
Design of new heuristic search algorithms that are optimally efficient. This will help us to understand what are the possibilities of Contrastive Analysis.
Extending these ideas from Classical Planning to Probabilistic Planning and Markov Decision Processes.
Introducing new algorithms that are able to reason at the lifted level and learn in order to compare states more effectively.

Publications of the project:

M.F. Salerno, D. Fišer and A. Torralba Finding a Dominating State in a Haystack: Efficient Data Structures for Dominance Pruning, Proceedings of the 36th International Conference on Automated Planning and Scheduling (ICAPS'26)

M.F. Salerno, D. Fišer and A. Torralba Beyond Pruning: Leveraging Dominance Re- lations for Heuristic Propagation, Proceedings of the 36th International Conference on Automated Planning and Scheduling (ICAPS'26)

R. G. Tollund and A. Torralba Dominance Pruning and Heuristics in Optimal Adver- sarial Non-Deterministic Planning, Proceedings of the 40th Anual AAAI Conference on Artificial Intelligence (AAAI’26)

D. Speck, J. Seipp and A. Torralba Symbolic search for cost-optimal planning with expressive model extensions, Journal of Artificial Intelligence Research 82 (JAIR)1349-1405 (PDF)

A. Wilhelm and A. Torralba Conditional Dominance Analysis for Classical Planning, ECAI'25.

R. G. Tollund, K. G. Larsen and A. Torralba What Makes You Special? Contrastive Heuristics Based on Qualified Dominance,IJCAI'25.

What we already know:

We have already developed "dominance" methods, that are able to identify whether a state is better than another in order to accomplish a certain goal. Using this to prune "bad" states during the search, we can already get a significant speed-up in many different planning applications. However, we have already observed that this is not the only way of comparing states. With "quantitative dominance" we can already provide bounds on how much better/worse a state is compared to another, greatly extending the possibilities of these methods. But there are many other alternatives yet to discover.

Some previous works on the topic:

A. Torralba and J. Hoffmann, Simulation-Based Admissible Dominance Pruning, IJCAI , 2015. (PDF) (slides)
A. Torralba, From Qualitative to Quantitative Dominance Pruning, IJCAI, 2017. (PDF) (slides)
A. Torralba, On the Optimal Efficiency of A* with Dominance Pruning, AAAI, 2021. (PDF) (slides) (poster) (AAAI talk) (HSDIP talk)
A. Torralba, Reshaping State-Space Search: From Dominance to Contrastive Analysis, Invited talk for New Faculty Highlights, AAAI , 2023. (PDF)