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

Sheila A. McIlraith, Stanford University; Richard Scherl, New Jersey Institute of Technology

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.