Reasoning about sensing actions and its application to diagnostic problem solving

This thesis presents a new approach to reasoning about sensing actions and its application to diagnostic problem solving. We begin with the definition of an action description language [special characters omitted] that allows reasoning about actions and their effects in the presence of incomplete information and sensing actions. To define the semantics of [special characters omitted], we introduce a notion of a combined state, which plays the same role of state in reasoning about actions when complete information about the environment is available. The semantics of [special characters omitted] is then defined by transition functions, which map pairs of actions and combined states into combined states. We prove the equivalence between [special characters omitted] and other approaches to reasoning about sensing actions such as the situation calculus approach of Scherl and Levesque and the high level action description language approach of Lobo et al. We compute the entailment relation defined by domain descriptions in [special characters omitted], denoted by [special characters omitted], by translating domain descriptions into semantics equivalently extended logic programs. Since the search space associated to [special characters omitted] is very large, several sound approximations of [special characters omitted] are proposed. These approximations differ from each other by the number of levels in which reasoning by cases is done. We argue that actions and narratives play an important role in diagnostic problem solving. In formalizing diagnostic problem solving, we extend [special characters omitted], a high-level action description language for specifying and reasoning about narratives, with static causal laws, sensing actions, and observable fluents. We also define a notion of diagnostic plans, whose goal is to single out a diagnosis among multiple alternatives