Reasoning about Sensing Actions and Reactivity

Tran Cao SonAAAI 1999 · OpenReview

Abstract

This research addresses the fundamental challenge of integrating high-level action theories with low-level reactive control in autonomous agents. Historically, reasoning about sensing actions—actions that modify an agent's knowledge rather than the physical environment—has been difficult to formalize. This paper introduces a new semantics for the action description language $\mathcal{A}_K$ based on "knowledge states" (k-states), where a k-state is defined as a pair $\langle s, \Sigma \rangle$ representing the actual world state and the set of possible states. By proving the soundness of various approximations of $\mathcal{A}_K$ and translating domain descriptions into extended logic programs, this work provides a rigorous framework for automatically generating reactive control modules from formal action theories. This approach bridges the gap between deliberate planning and the rapid execution required in dynamic environments.

Introduction: The Deliberative-Reactive Divide

In artificial intelligence and robotics, agents are typically categorized into two camps: deliberate and reactive. Deliberate agents utilize complex action theories to formulate plans, a process that is often computationally expensive (NP-complete) and too slow for real-time response. Conversely, reactive agents rely on simple "if-then" rules to act quickly. However, these reactive rules are frequently hand-coded and lack a formal, provable connection to the agent’s underlying knowledge of the world.

A central difficulty in bridging these two paradigms is the formalization of sensing actions—such as checking if a door is locked or reading a sensor value. Unlike physical actions, sensing actions do not change the state of the world; they change the agent's internal state of knowledge. This paper proposes a unified framework that allows reactive control modules to be derived directly from formal theories of action, ensuring that fast-acting agents remain grounded in logical consistency.

Formalizing Knowledge: The k-state Semantics

To reason about sensing, the author introduces a new semantics for the high-level action description language $\mathcal{A}_K$. The core innovation is the knowledge state (k-state), represented as $\langle s, \Sigma \rangle$:

  • $s$: The actual state of the world.
  • $\Sigma$: The set of all possible states the agent considers possible.

In this framework, a sensing action acts as a filter. It does not alter $s$, but it prunes the set $\Sigma$ by removing states that are inconsistent with the sensor's findings. This allows for a precise mathematical definition of when an agent "knows" a fluent: when that fluent holds true in every state within $\Sigma$. This semantics, denoted as $\models_K$, provides a robust foundation for proving the correctness of agent behavior under uncertainty.

Computational Framework and Soundness

A significant contribution of this work is closing the "soundness gap" in existing action languages. Previous research by Baral and Son proposed various approximations ($\models_a$) for the semantics of $\mathcal{A}_K$ to make computation more tractable. This paper provides the formal proofs necessary to show that these approximations are sound with respect to both the new k-state semantics and the earlier LTM semantics (proposed by Lobo, Taylor, and Mendez).

To make these theories executable, the author translates domain descriptions in $\mathcal{A}_K$ into extended logic programs. By utilizing answer set semantics, the agent can compute its knowledge state after a sequence of actions. This translation transforms abstract logical reasoning into a concrete computational task, allowing agents to maintain an accurate internal model of the world as they interact with it.

Synthesizing Reactivity: Automated Control Modules

The ultimate goal of this research is the automated construction of reactive control modules. A control module is defined as a set of condition-action rules (e.g., "if condition $\alpha$ is met, execute sequence $\gamma$"). Rather than requiring human engineers to anticipate every possible scenario, the author develops algorithms that use existing planners to generate these rules automatically.

These modules are designed to be:

  1. Theory-Driven: Derived directly from the formal action theory.
  2. Goal-Oriented: Guaranteed to achieve a specific goal given the initial state and available actions.
  3. Reactive: Capable of providing immediate responses without re-planning from scratch during execution.

Practical Validation and Future Work

The theoretical foundations of this work were validated through participation in the AAAI’96 and AAAI’97 robot competitions. The author’s team applied these principles to tasks such as "Scheduling a meeting" and "Tidy Up," winning third and first prize, respectively. These results demonstrate that formal reasoning about sensing is not just a theoretical exercise but a practical necessity for high-performing autonomous systems.

Future research directions include:

  • Integration with ConGolog: Extending the logic programming language ConGolog with new constructs to handle temporal constraints and partial ordering of actions.
  • Statistical Bridging: Exploring the correspondence between this logical formalism and Partially Observable Markov Decision Processes (POMDPs), potentially unifying symbolic AI with statistical decision theory.
  • Implementation Refinement: Completing the software framework for the automated construction of control modules to reduce the computational overhead of the generation phase.

By providing a sound mathematical link between high-level deliberation and low-level reaction, this work moves closer to the goal of creating agents that are both intelligent and responsive.

Summary updated

Abstract

This thesis focuses on the problem of reasoning about sensing actions and the relationship between action theory and reactive control. The first approach to reasoning about sensing actions is due to Moore1. He used the possible world semantics to represent knowledge and treated the accessible relation between world models as a fluent. Later, Hass proposed another way of formulating sensing actions using first order logic. Moore’s formulation was then adapted to reasoning about sensing actions in situation calculus by Scherl and Levesque. In 1997, Lobo, Taylor, and Mendez extended the language , a high-level action description language of Gelfond and Lifschitz, to allow sensing actions and called the new language K . Lobo et al. defined the semantics of K , which will be denoted by LTM hereafter, by situation transition functions, which are extensions of the state transition functions of . Baral and Son proposed different approximations for the semantics of K , denoted by a 2. However, it was not clear whether there is a situation calculus counterpart of K , as Kartha proved for , or not. Another question was to prove the soundness of a with respect to LTM . We will present a new approach to reasoning about sensing actions in K , in which transition functions are defined over knowledge states (or k-states). A k-state is a pair s Σ where s is a state and Σ is a set of states. Intuitively, s represents the real state of the world and Σ represents the possible states of the world in which an agent thinks it may be in. We denote the new semantics by K and prove that Kartha’s results can be extended to domains with sensing actions. More importantly, we prove the soundness of the different approximations of K , a, with respect to K and LTM. To compute K , we translate domain descriptions in K into extended logic programs where the answer set semantics of the latter coincides with K . It is also expected that our formalism corresponds to POMDP (Partial Observable Markov Decision Process), a well-known statistical approach to reasoning about sensing actions. Theories of actions can be used to model deliberate agents which achieve their goals by repeatedly (a) making observa-
BibTeX
@inproceedings{son1999reasoning,
  author = {Tran Cao Son},
  title = {{Reasoning about Sensing Actions and Reactivity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
  url = {https://openreview.net/forum?id=ryZ9ETxdbB},
}
Figure