AAAI Publications, Eighth Symposium on Abstraction, Reformulation, and Approximation

Font Size: 
Abductive Problem Solving with Abstractions
Gianluca Torta, Daniele Theseider Dupré

Last modified: 2009-10-22


Several explanation and interpretation tasks, such as diagnosis, plan recognition and image interpretation, can be formalized as abductive and consistency reasoning. The interpretation task is usually executed for the purpose of performing actions, e.g., in diagnosis, repair actions or therapy. In some cases actions are the only or the main way for discriminating among alternative explanations. Some proposals address the problem based on a task-independent representation of a domain which includes an ontology or taxonomy of hypotheses and actions. In this paper we rely on the same type of representation, and we point out the role of abstractions in an iterative process where, like in model-based diagnosis and troubleshooting, further observations or actions are proposed to achieve the overall goal of discriminating among candidate hypotheses and, more importantly, performing the appropriate actions for the case at hand. Discrimination is performed up to an appropriate level which depends on the cost of actions (e.g. repair actions or therapy) to be taken based on the results of abduction, and on the cost of additional observations, which should be balanced with the benefits, in terms of more suitable actions, of better discrimination. Abstractions have a significant impact on this trade-off, given that the cost of observing the same phenomenon at different levels of abstraction may be quite different, and choosing a generic action, without information on which specific instance is most appropriate, is, in general, suboptimal.


Abduction; abstractions; action cost; observation cost

Full Text: PDF