Abstract
This paper introduces SLAFS (Simultaneous Learning and Filtering of Schemas), a tractable algorithm for learning action models in deterministic, partially observable environments. By employing a relational-logical approach and a compact Directed Acyclic Graph (DAG) representation, SLAFS learns complex "if-then" action rules in polynomial time, significantly outperforming previous methods that struggled with scale or required full observability.
What Problem Does This Paper Address?
For an autonomous agent to act intelligently in an unfamiliar environment, it must understand the "physics" of that world—specifically, how its actions change the state of the world. This is relatively straightforward if the agent can see everything (full observability), but it becomes incredibly difficult in partially observable domains (like a robot exploring a building or a web crawler).
In these scenarios, the agent is uncertain about the state of the world both before and after an action. Most existing solutions either don't scale to large environments, assume the agent can see everything, or use "hill-climbing" heuristics that might result in models inconsistent with the actual data. The authors aim to bridge this gap by creating a method that is both exact (it finds all consistent models) and tractable (it runs efficiently).
Methods
The authors propose a relational-logical framework. Instead of learning rules for every specific object (e.g., "Switch-1 turns on Bulb-1"), they learn action schemas (e.g., "Switching $x$ turns on its associated bulb $h(x)$").
Key components include:
- SLAFS Algorithm: This algorithm maintains a "transition belief state"—a logical formula representing all possible world states and transition rules consistent with the history of actions and observations.
- Relational Languages ($SL_0, SL-V, SL-H$): They define several levels of expressivity, ranging from basic STRIPS-like rules to complex schemas involving quantified variables and hidden object functions (e.g., associating a specific switch with a specific bulb).
- DAG Representation: To prevent the logical formulas from growing exponentially as the agent acts, the algorithm represents them as a Directed Acyclic Graph (DAG). Updates are performed by adding nodes and using pointers rather than copying formulas, keeping the update process polynomial in time and space.
- Exact Filtering: Every time an agent makes an observation, the algorithm "filters" the belief state, instantly discarding any transition models that contradict the new evidence.
Datasets
The authors evaluated their algorithm on several classic AI planning benchmarks and synthetic domains, including STRIPS Domains (Block-Worlds, Chess, Driver-log) and ADL/PDDL Domains (Briefcase, Bomb-In-Toilet, Safe, Grid). The experiments ranged from small problems to large domains with thousands of propositional fluents (state variables). They compared SLAFS against propositional learning methods and the ARMS algorithm, a heuristic action-learning system.
Key Insights and Ideas
- Relational Power: Relational structure actually makes learning faster. Because the number of schemas is independent of the number of objects in the world, the algorithm can generalize what it learns about one object to all similar objects immediately.
- Exactness is Tractable: Usually, keeping track of every possible consistent model is considered computationally suicidal. This paper proves that for deterministic domains, you can maintain this "exact" set efficiently using DAGs.
- Independence from Domain Size: In many configurations (like $SL_0$), the time and space complexity of the update do not depend on the total number of objects in the domain, only on the number of predicates and the complexity of the action's preconditions.
Key Results
- Efficiency: The algorithm takes linear time relative to the number of time steps. In Block-World tests, the time and space requirements remained flat even as the number of objects (and thus the state space) increased.
- Rapid Convergence: In most domains, the agent learned over 98% of the possible schemas within just 200 steps.
- Superior Accuracy: When compared to the ARMS algorithm, SLAFS produced models that were strictly consistent with the observation sequence, whereas ARMS occasionally produced approximate models that contradicted the data.
- Generalization: The agent successfully learned hidden relationships, such as which specific switches controlled which light bulbs, without being told the connections beforehand.
Limitations and Future Work
- Deterministic Only: The current logic is strictly deterministic. It cannot handle "noisy" environments where an action might fail randomly or an observation might be incorrect.
- Inference Complexity: While building the DAG is fast (polynomial), querying it (e.g., asking "is it definitely true that the light is on?") is still a SAT problem, which is NP-hard. For very long sequences, even the efficient DAG might become slow to query.
- Noise Robustness: The authors acknowledge that their logical approach is not robust to noise, which is a primary hurdle for applying this to real-world robotics. They suggest that future work should explore how to integrate these relational insights into stochastic (probabilistic) domains.
Summary updated