TLDR: The paper introduces SYNTH, a novel algorithm for learning lifted STRIPS+ action models from incomplete state-action traces. Unlike traditional methods that assume full observability, SYNTH can infer action preconditions and effects even when states are missing predicates (e.g., the “blank” tile in a puzzle) and actions have implicit arguments (e.g., “move” without specifying source/destination). This approach, validated across various domains, offers a more realistic and scalable solution for AI model learning, bridging classical planning and model-based reinforcement learning.
Teaching artificial intelligence systems how the world works, specifically how actions change states, is a fundamental challenge. Traditionally, this has been approached using models like STRIPS, which assume a complete and explicit understanding of both the environment’s state and the actions being performed. However, real-world scenarios are rarely so straightforward.
Imagine a robot learning to navigate a room. It might observe itself moving ‘up’ or ‘left’, but the full STRIPS model would require it to explicitly know and state its current and next precise coordinates. Similarly, in a sliding-tile puzzle, a STRIPS model needs to track the ‘blank’ tile’s position, even if a human player only focuses on the numbered tiles. These examples highlight a crucial gap: observed actions and states are often incomplete, lacking all the detailed arguments and predicates a full STRIPS model demands.
Introducing STRIPS+ and the SYNTH Algorithm
A recent research paper, Learning Lifted Action Models From Traces of Incomplete Actions and States, introduces a novel approach to tackle this problem. The authors, Niklas Jansen, Jonas G¨osgens, and Hector Geffner, propose a new language called STRIPS+ and an accompanying learning algorithm named SYNTH. STRIPS+ extends the traditional STRIPS framework by allowing certain action arguments and state predicates to be ‘implicit’ or unobserved in the input data. This makes the learning problem significantly more realistic, bridging the gap between classical AI planning and model-based reinforcement learning, where models are often learned from sparse or partial observations.
The core idea behind SYNTH is to learn these implicit arguments and missing predicates from traces of incomplete actions and states. For instance, an action like ‘move’ might not explicitly state ‘move from location A to location B’. Instead, SYNTH learns to infer ‘location A’ and ‘location B’ as implicit arguments by constructing ‘queries’ – sequences of precondition expressions that uniquely identify these missing pieces of information within the observed state. This process is designed to be ‘stratified’, meaning it builds up these complex understandings step-by-step, ensuring that each new piece of inferred information is uniquely determined by what has already been established.
How SYNTH Works
SYNTH operates in three main phases: first, it learns the ‘binding preconditions’ that uniquely identify the implicit variables (the ‘z’ variables in their notation). Second, it learns additional preconditions that use these bindings but don’t further constrain their values. Finally, it learns the effects of the actions. The algorithm is robust; it can even learn from states where crucial predicates, like the ‘blank’ tile’s position in a puzzle, are entirely absent from the observations, as long as they can be inferred from other available information.
The researchers rigorously tested SYNTH across a variety of existing STRIPS domains, including Blocks World, Delivery, Driverlog, Gripper, Hanoi, Logistics, Miconic, and different versions of the Sliding-Tile Puzzle. They converted these domains into STRIPS+ by making many explicit action arguments implicit, effectively simulating real-world incomplete data. The results were highly promising, with SYNTH achieving a 100% verification rate across all tested domains. This means the learned models accurately replicated the behavior of the hidden, complete models.
Also Read:
- New AI Planning Method Learns General Goals from Past Solutions
- Navigating Complex Tasks with Tree-Guided Diffusion
Real-World Implications
A significant finding was that the actions in the training traces contained, on average, only half the arguments of the original STRIPS actions. Yet, SYNTH successfully recovered all the ‘redundant’ (determined) STRIPS action arguments and even identified additional implicit arguments that were not explicitly part of the original STRIPS definition but were useful for understanding the domain. For example, in the Gripper domain, SYNTH learned to identify ‘the other room’ or ‘the other gripper’ even if these weren’t directly used in the action’s preconditions or effects.
Furthermore, SYNTH demonstrated its ability to learn from incomplete states. In domains like the c-puzzle, it successfully learned the action model even when the ‘blank’ predicate was entirely removed from the state observations. This was achieved by inferring the blank’s position through negated preconditions, such as ‘the cell without a tile’.
This research marks a significant step forward in AI’s ability to learn complex action models from more realistic, incomplete data. By moving beyond the assumption of fully observable states and actions, SYNTH offers a scalable and robust solution that has broad implications for developing more adaptable and intelligent AI systems, particularly in areas like robotics and autonomous planning where perfect information is a luxury.
