Abstract
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 DLV