Abstract
N-SAM is a novel algorithm designed to learn "safe" action models for numeric planning directly from observed trajectories. In environments characterized by continuous variables, N-SAM employs convex hulls to define preconditions and linear regression to model effects. This approach guarantees that any plan generated using the learned model is executable in the real world, providing a critical safety net for mission-critical systems where trial-and-error is not an option.
Introduction
In automated planning, an agent relies on an action model to understand how its interactions change the state of the world. Traditionally, these models—often defined in PDDL—are hand-coded by experts, a process that is both labor-intensive and prone to error. While machine learning offers a path to automate model acquisition, most existing methods lack safety guarantees. A slightly inaccurate learned model can lead a planner to propose actions that fail or cause damage during execution.
Previous work introduced Safe Action Model (SAM) learning for discrete, Boolean environments. However, many real-world applications involve numeric planning, where states are described by continuous variables such as fuel levels, coordinates, or weights. N-SAM (Numeric Safe Action Model) addresses this challenge by learning numeric boundaries safely, ensuring the model is never overly optimistic about an action's applicability.
Methodology
N-SAM decomposes the learning process into three distinct components:
- Boolean Learning: It leverages established SAM techniques to manage the discrete aspects of actions.
- Numeric Preconditions via Convex Hulls: To determine when an action is safe, N-SAM analyzes all observed states where the action was successfully executed. It constructs a convex hull around these points. Due to the properties of convexity, any state within this hull is guaranteed to be a safe starting point, provided the underlying real-world precondition is also convex.
- Numeric Effects via Linear Regression: The algorithm models how an action modifies variables using linear regression. To maintain safety, N-SAM only commits to an effect if it has sufficient data to uniquely determine it; otherwise, the action is marked as "unsafe" to prevent erroneous predictions.
The framework assumes linear inequalities for preconditions and linear combinations for effects. Furthermore, N-SAM can be extended to nonlinear domains (e.g., involving acceleration) by mapping polynomial terms into a higher-dimensional linear space.
Experimental Evaluation
The researchers evaluated N-SAM across 12 standard numeric planning benchmarks, primarily sourced from the 3rd International Planning Competition (IPC3). The domains include:
- Logistics and Transport: Depot, Driverlog, Zenotravel.
- Resource Management: Rovers, Satellite, Settlers, UMT.
- Specialized Tasks: Farmland, Counters, Plant-watering, Sailing.
The algorithm was trained on varying numbers of trajectories (sequences of states and actions) and tested on its ability to solve new, unseen problems within these domains.
Results and Analysis
N-SAM demonstrated a high success rate, often solving over 50% of problems with fewer than 60 training trajectories. In domains like Farmland and Driverlog, the success rate approached 100%.
A key highlight of the results is the Zero Error Effects. Due to the conservative nature of the safety guarantees, the Mean Squared Error (MSE) for learned numeric effects was 0.0 across all tests. This indicates that whenever N-SAM identified an effect, it was perfectly accurate. Furthermore, the algorithm operates in polynomial time relative to the number of observations, ensuring computational feasibility.
Discussion: The Safety-Completeness Trade-off
N-SAM operates on a conservative principle: it is better to decline an action than to guess incorrectly. The model begins as highly restrictive and becomes more "complete" as more data is observed. The paper also provides a theoretical proof that safe numeric model learning is impossible without geometric assumptions like convexity, justifying the algorithm's design.
However, N-SAM currently requires prior knowledge of "relevant variables"—knowing which variables influence an action's preconditions and effects. While this is easier than manual PDDL coding, it remains a dependency on human input.
Conclusion and Future Work
N-SAM provides a robust framework for learning safe numeric models in continuous domains. Future research will focus on automating feature selection to remove the "relevant variables" requirement, supporting conditional effects, and adapting the algorithm to handle noisy or partially observable data common in real-world sensor environments.
Summary updated