A logic-based approach to finding explanations for discrepancies in optimistic plan execution

Eiter, Thomas and Faber, Wolfgang and Erdem, Esra and Senko, Jan (2007) A logic-based approach to finding explanations for discrepancies in optimistic plan execution. Fundamenta Informaticae, 79 (1-2). pp. 25-69. ISSN 0169-2968

[thumbnail of stvkaf01960.pdf] PDF
Restricted to Repository staff only

Download (340kB) | Request a copy


Consider an agent executing a plan with nondeterministic actions, in a dynamic environment, which might fail. Suppose that she is given a description of this action domain, including specifications of effects of actions, and a set of trajectories for the execution of this plan, where each trajectory specifies a possible execution of the plan in this domain. After executing some part of the plan, suppose that she obtains information about the current state of the world, and notices that she is not at a correct state relative to the given trajectories. How can she find an explanation (a point of failure) for such a discrepancy? An answer to this question can be useful for different purposes. In the context of execution monitoring, points of failure can determine some checkpoints that specify when to check for discrepancies, and they can sometimes be used for recovering from discrepancies that cause plan failures. At the modeling level, points of failure may provide useful insight into the action domain for a better understanding of the domain, or reveal errors in the formalization of the domain. We study the question above in a general logic-based knowledge representation framework, which can accommodate nondeterminism and concurrency. In this framework, we define a discrepancy and an explanation for it, and analyze the computational complexity of detecting discrepancies and finding explanations for them. We introduce a method for computing explanations, and report about a realization of this method using DLVK, which is a logic-programming based system for reasoning about actions and change.
Item Type: Article
Uncontrolled Keywords: knowledge representation; reasoning about actions; logic-based planning; explanations; execution monitoring; computational complexity
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Esra Erdem
Date Deposited: 25 Apr 2007 03:00
Last Modified: 26 Apr 2022 08:05
URI: https://research.sabanciuniv.edu/id/eprint/288

Actions (login required)

View Item
View Item