Exploiting abstractions in cost-sensitive abductive problem solving with observations and actions

• Published in: Ai communications 2014, Vol.27 (3), p.245-262
• Main Authors: Torta, Gianluca, Anselma, Luca, Theseider Dupré, Daniele
• Format: Article
• Language: English
• Subjects: Algorithms; Diagnosis; Hypotheses; Iterative methods; Object recognition; Proposals; Representations; Tasks
• ISSN: 0921-7126
• DOI: 10.3233/AIC-140593

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. Some proposals address the problem based on a task-independent representation of a domain which includes an ontology or taxonomy of hypotheses and observations. In this paper we rely on the same type of representation, and we point out the role of abstractions in an iterative abduction process. At each iteration, as in model-based diagnosis and troubleshooting, our algorithm chooses to perform further observations or actions taking into account their costs and the likelihood of candidate hypotheses. The main goal of the algorithm is to ensure discrimination among hypotheses and, more importantly, to perform the appropriate actions for the case at hand. We discuss an implementation of the proposed method and report experimental results that support the conclusion that abstractions are indeed useful for the considered task.