What Sensing Tells Us: Towards a Formal Theory of Testing for Dynamical Systems

Knowledge Representation and Reasoning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Reasoning about Actions and Time

Just as actions can have indirect effects on the state of the world, so too can sensing actions have indirect effects on an agent’s state of knowledge. In this paper, we investigate what sensing actions tell us, i.e., what an agent comes to know indirectly from the outcome of a sensing action, given knowledge of its actions and state constraints that hold in the world. Building on this foundation, we define the notion of a test, a complex action designed to achieve a knowledge goal. We show how such tests can be computed, or alternately, how they can be specified as complex actions. To this end, we propose a formalization of the notion of testing within a dialect of the situation calculus that includes knowledge and knowledge-producing actions. Realizing this formalization requires addressing the ramification problem for knowledge-producing actions. We formalize simple tests as sensing actions. Complex tests are described in the logic programming language Golog. We examine what it means to perform a test, and how the outcome of a test affects an agent’s state of knowledge. Finally we discuss the issue of selecting tests to confirm, refute, or discriminate a space of hypotheses. The work presented in this paper is relevant to a number of application domains including diagnostic problem solving, natural language understanding, plan recognition, and active vision.