Introduction
In automated planning, an agent relies on a symbolic model—typically expressed in the Planning Domain Definition Language (PDDL)—to predict how its actions will alter the state of the world. While these models are foundational to AI planning, manually authoring them is a labor-intensive and error-prone process. This has led to the development of algorithms that learn action models directly from observed trajectories. However, most existing approaches prioritize "completeness" (learning as many effects as possible) over "soundness" (ensuring learned effects are strictly true). In mission-critical domains such as autonomous surgery or self-driving vehicles, an unsound model can lead to catastrophic failures if the agent executes an action it incorrectly believes to be safe.
This paper introduces Conditional-SAM, the first algorithm designed to safely learn action models that incorporate complex features like conditional and universal effects. By enforcing a strict safety constraint, Conditional-SAM ensures that any plan generated using the learned model is guaranteed to be valid in the underlying environment.
The Challenge of Conditional and Universal Effects
Previous Safe Action Model (SAM) learning algorithms were limited to simple STRIPS-like actions. They struggled with two common PDDL features:
- Conditional Effects: Effects that only occur if a specific condition is met (e.g., "If a patient has a specific allergy, this medication causes a reaction").
- Universal Effects: Effects that apply to all objects of a certain type simultaneously (e.g., "When an elevator reaches a floor, all passengers for that floor exit").
Learning these context-dependent rules safely is difficult because the learner must distinguish between a condition that always triggers an effect and one that only coincidentally appeared in the training data.
Methodology: The Conditional-SAM Framework
Conditional-SAM extends the SAM framework by employing a conservative inductive learning strategy. The algorithm begins with a maximally general hypothesis—assuming every possible literal could be a precondition or a condition for an effect—and systematically prunes these possibilities based on observed state transitions.
Key Technical Components
- Inductive Pruning Rules: The framework utilizes four specific rules to eliminate impossible preconditions and antecedents by analyzing what did not occur during observed trajectories.
- Bounded Antecedents: The authors prove a "no free lunch" theorem: learning safe conditional effects is fundamentally intractable without constraints. To address this, they introduce a bound ($n$) on the maximum number of literals in an effect's condition. This makes the learning process tractable while remaining expressive enough for most practical domains.
- Lifted and Universal Learning: The algorithm learns "lifted" models (parameterized rules) and handles
foralleffects by tracking how actions influence sets of objects in a single step.
Experimental Evaluation
The researchers evaluated Conditional-SAM across six PDDL domains from the International Planning Competition (IPC) that utilize conditional effects: CityCar, Nurikabe, Maintenance, Briefcase, Miconic, and Satellite. Training data consisted of trajectories generated by state-of-the-art planners (Fast Downward and Fast-Forward) across 100 problems per domain.
Results and Semantic Recall
The evaluation focused on semantic recall—the measure of whether the learned model allows the agent to take the same actions in the same states as the ground-truth model.
- Perfect Solving: In the Satellite, Maintenance, and Miconic domains, the learned models achieved 100% success in solving test problems.
- High Accuracy: Even in complex domains like CityCar and Briefcase, semantic recall reached approximately 0.99, indicating the learned models were nearly identical to the ground truth in terms of action applicability.
- Complexity Bottlenecks: In the Nurikabe domain, which features complex conditions ($n=3$), the algorithm was highly conservative. This resulted in a more restrictive model that required significantly more data to solve test problems, highlighting the trade-off between safety and model completeness.
Discussion and Future Work
Conditional-SAM demonstrates that it is possible to learn complex PDDL models without sacrificing the safety guarantees required for high-stakes applications. A key insight of the work is the distinction between syntactic and semantic accuracy; a learned model does not need to look exactly like the original PDDL code as long as it behaves identically in practice.
Limitations
Despite its success, the current framework has limitations:
- Disjunctive Antecedents: It does not currently support "OR" conditions in effects, as this would exponentially increase computational complexity.
- Noise Sensitivity: The algorithm assumes perfect, noise-free observations, which is rarely the case in real-world robotics.
- Scaling with $n$: While effective for small $n$, the approach remains sensitive to the complexity of the conditions being learned.
Future research will focus on extending the framework to handle numeric conditions and noisy sensor data, further bridging the gap between symbolic planning and real-world execution.
Summary updated