Abstract
Tracking the state of a world under partial observability is a fundamental challenge in AI. When actions are observed without full parameterization—such as knowing a move occurred in a game of Kriegspiel without knowing which piece moved—traditional logical filtering suffers from combinatorial explosion. This paper introduces a symbolic approach to Observed-Action Reasoning (OAR) that utilizes new logical constants as placeholders for unknown objects. By deferring the resolution of these identities, the proposed Param-STRIPS algorithms achieve quadratic update times and linear growth in belief state size, rendering long-term state tracking tractable in complex, high-dimensional domains.
Introduction
In many real-world AI scenarios, from robotics to strategic gaming, agents must operate with imperfect information. A specific instance of this is Partially Observed Actions, where an agent knows an action type occurred (e.g., a piece was moved or a block was picked up) but lacks specific parameters (e.g., which piece or which block).
The challenge, termed Observed-Action Reasoning (OAR), involves updating a "belief state"—the set of all possible world states—after a sequence of such fuzzy observations. Standard approaches, such as SATPlan or traditional logical filtering, typically encounter a combinatorial explosion. If an action has $n$ possible parameters and $t$ steps are observed, the number of possible states can grow exponentially ($n^t$). In domains like Kriegspiel (blind chess), this makes state tracking impossible after only a few moves.
Symbolic Filtering Methodology
The authors propose a shift from explicit state tracking to symbolic tracking. Instead of branching for every possible value of an unknown parameter, they introduce new logical constants to serve as placeholders for these unknowns. This allows the agent to reason about the consequences of an action without immediately deciding which object was involved.
Two primary algorithms are presented:
- Param-STRIPS-1:1: Optimized for "one-to-one" actions where each state has a unique predecessor and successor.
- Param-STRIPS-Term: A general version for STRIPS domains that maintains a compact "complex-literal" format.
To maintain logical completeness, the algorithms incorporate two critical mechanisms:
- Implied Preconditions: The system automatically adds the preconditions of an observed action to the belief state. For instance, knowing a
move(?x, ?y)occurred implies that?xwas at a starting position and?ywas vacant. - Equality Constraints: The system tracks equalities and inequalities between new constants and known objects. This prevents representation explosion while ensuring that subsequent actions can be resolved logically.
Experimental Evaluation
The algorithms were benchmarked in two distinct environments:
- Blocks-world: A standard AI planning domain. Tests involved up to 30 blocks and sequences of 150 actions to evaluate scalability.
- Kriegspiel: A notoriously difficult domain for state tracking due to the high branching factor (over 10,000 possible actions per step).
Results and Performance Analysis
The symbolic approach demonstrated significant improvements in both efficiency and scalability. For a sequence of $t$ partially observed actions, the update time was found to be $O(t^2 \cdot |\phi_0|)$, where $\phi_0$ is the initial belief state size.
In the Blocks-world domain, the filtering time per step grew quadratically as predicted, while the total number of blocks had minimal impact on performance. In Kriegspiel, the algorithm successfully tracked sequences of 35 moves. In a scenario where a single unspecified move could represent over 65,000 grounded actions, the symbolic approach rendered the problem tractable for the first time.
While updating the belief state is efficient, the authors noted that inference (querying the belief state, e.g., "Is the Queen at square A1?") remains the primary bottleneck. Although inference time grew slower than expected, it remains the limiting factor for extremely long sequences. To mitigate this, the authors utilized a specialized equational model finder called Paradox, which outperformed standard first-order logic provers.
Conclusion
By treating unknown action parameters as symbolic placeholders rather than branching possibilities, this research provides a scalable framework for reasoning under uncertainty. The linear growth of the belief state representation allows for long-term tracking in domains previously considered inaccessible. Future work may extend these methods beyond STRIPS to handle stochastic effects or apply them to narrative interpretation, where symbolic constants could represent unresolved pronouns in a text.
Summary updated