IJCAI-2009 Tutorial

Computing Explanations in Problem Solving:
A Review of Formal Approaches

Barry O'Sullivan and Ulrich Junker

General Information

Presented at : IJCAI-2009 Conference, Tutorial MP2
Presenter : Barry O'Sullivan
Date and time : Monday, July 13, 2009; 1:30pm - 5:30pm
Location : Pasadena Conference Center, California

Tutorial Materials)

Tutorial slides: available in pdf format (updated 13/07/2009).


This tutorial has received support from Science Foundation Ireland (Grant Number 05/IN/I886).

The collaboration between the speakers benefits from support provided by European Science Foundation-funded COST Action IC0602 on Algorithmic Decision Theory.


Generating explanations of the results of problem solving has always been an important objective of artificial intelligence (AI) research, but has been traditionally addressed by specialized techniques. Explanations are critically important in interactive systems such as web-based product configurators, personal assistants, expert systems, and model development tools. Moreover, explanation techniques can improve the quality of results in test generation, software verification, and decomposition methods in combinatorial optimization.

This tutorial addresses a broad AI audience and seeks to lay a general foundation for explanation generation, which is valid for a large range of AI problems (product configuration, multi-criteria optimization, constraint satisfaction, satisfiabililty, recommender systems, case-based reasoning, diagnosis, debugging, ontological reasoning, etc.). It exploits the fact that explanations developed for different kinds of problems have a similar form and can be computed with similar means.

The tutorial assumes basic knowledge in problem solving and automated reasoning, e.g. constraint satisfaction, when motivating explanation problems. The presentation of the explanation problems themselves and their algorithms is self-contained.

The tutorial will be of interest to students and established researchers alike. Given the ubiquity of explanation problems, this tutorial crosses boundaries between many subfields of AI. Industrialists will also find this tutorial useful, since explanation generation is of considerable commercial value in many domains.


Barry O'Sullivan is Associate Director of the Cork Constraint Computation Centre, Science Foundation Ireland Principal Investigator, President of the Association for Constraint Programming, Chairman of the Artificial Intelligence Association of Ireland, Coordinator of the European Research Consortium for Informatics and Mathematics (ERCIM) Working Group on Constraints, and a member of the Executive Council of the Management Science Society of Ireland. His research interests include real-world applications of artificial intelligence, constraint programming and optimisation technologies.

Ulrich Junker received his Ph.D. from the University of Kaiserslautern (1992). He has significant experience in explanation generation, starting with research on truth maintenance systems and model-based diagnosis. His pioneering work on QuickXplain paved new directions for explanation generation in constraint programming, product configuration, and other fields. He is a distinguished scientist at ILOG.