ConAn: Contrastive Analysis for State-Space Exploration

This project will introduce 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.

This project is set to start on Fall 2024 and it will last for 5 years. There is currently one PhD student position open!, see call here.

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.

Highlighted related publications:

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)

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.