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:
- Theory-Driven: Derived directly from the formal action theory.
- Goal-Oriented: Guaranteed to achieve a specific goal given the initial state and available actions.
- 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