Abstract
A significant challenge in applying planning technology to real-world problems lies in obtaining a planning model that accurately represents the problem's dynamics. Numeric Safe Action Models Learning (N-SAM) is a recently proposed algorithm designed to learn the preconditions and effects of actions from observations in domains involving both discrete and continuous state variables. While N-SAM is guaranteed to output a "safe" action model—ensuring that generated plans are applicable and achieve their goals—it requires a substantial number of observations for each action. This paper introduces N-SAM, an enhanced version that maintains safety guarantees while enabling learning from as few as one observation. Through subspace projection, N-SAM achieves optimal sample complexity. Empirical studies across benchmark domains demonstrate that N-SAM* significantly increases the number of solvable problems compared to the original N-SAM, particularly in data-scarce environments.
Introduction
In automated planning, an action model serves as the fundamental map defining what an agent can do (preconditions) and the resulting state changes (effects). For mission-critical systems like autonomous rovers or industrial robotics, the accuracy of this model is paramount. If a learned model is even slightly inaccurate, an agent might generate a plan that appears valid but fails during execution, potentially leading to catastrophic results.
While learning models from observations is a well-established field, most research has focused on discrete variables. Real-world applications, however, are inherently numeric, involving variables like fuel levels, distances, and battery life. N-SAM* bridges this gap by providing a framework for learning safe numeric models even when data is scarce.
The Challenge of Safe Numeric Learning
The primary hurdle in numeric action model learning is Safety. A "safe" learner must be pessimistic; it should only permit an action in states where it is mathematically certain the action is valid based on prior evidence.
Previous iterations, such as the original N-SAM algorithm, required at least $n+1$ affine independent observations (where $n$ is the number of variables) to learn an action. In a complex domain with 20 variables, the agent would need 21 specific examples before it could even attempt to use that action in a plan. This "data hunger" makes N-SAM impractical for large-scale domains where certain actions may be rarely observed.
Methodology: N-SAM and the N-SAM* Innovation
The researchers built upon the Safe Action Model (SAM) framework, extending it into the numeric realm through two primary algorithmic approaches:
1. N-SAM (The Foundation)
N-SAM treats observed valid states as points in a high-dimensional space. It calculates the Convex Hull of these points—an "envelope" of safety. Because the underlying physics and logic of most planning domains form convex sets, any state inside this hull is guaranteed to be safe. For effects, the algorithm utilizes linear regression to map how numeric variables change post-action.
2. N-SAM* (The Subspace Innovation)
To solve the low-data problem, N-SAM introduces the Gram-Schmidt process to project available data into a lower-dimensional subspace. When there are insufficient points to form a full-dimensional convex hull, N-SAM learns preconditions within this restricted subspace. This allows the AI to use an action safely even if it has only been observed once, by restricting its application to the specific conditions (or linear combinations thereof) it has already encountered. This makes N-SAM* the "strongest" possible safe learner, as it identifies the largest possible safe set of states given the available evidence.
Experimental Evaluation
The algorithms were evaluated using a broad suite of benchmarks, primarily derived from the International Planning Competition (IPC), including:
- Standard Domains: Depots, Driverlog, Rovers, Satellite, and Zenotravel.
- Numeric-Specific Benchmarks: Counters, Farmland, Sailing, and a Minecraft-inspired domain.
- Complexity Variants: The study included "Polynomial" domains (e.g., Driverlog-P) where preconditions and effects involve squared or cubed variables, handled via feature engineering.
Key Results and Insights
- Guaranteed Safety: Consistent with theoretical proofs, both N-SAM and N-SAM produced zero inapplicable plans*. In contrast, the state-of-the-art baseline, PlanMiner, frequently produced plans that failed in execution—sometimes with failure rates as high as 100% in specific domains.
- Superior Coverage in Low Data: N-SAM demonstrated a clear advantage in data-sparse scenarios. In the Zenotravel domain, N-SAM solved 75% of test problems after seeing only a few trajectories, whereas the original N-SAM failed to solve any problems because it had not yet reached the $n+1$ observation threshold.
- Computational Efficiency: The algorithms scale linearly with the number of observations, ensuring they remain practical for large datasets.
- Sensitivity to Precision: The authors noted that while 4 decimal places of precision are sufficient for effective planning, lower precision (1 or 2 digits) leads to accumulated rounding errors that significantly degrade the agent's ability to solve problems.
Conclusion and Future Work
N-SAM* represents a significant step forward in safe machine learning for automated planning. By framing preconditions as a geometric problem and employing subspace projection, it allows agents to act reliably from the very first observation.
However, limitations remain. The current model assumes linear or polynomial relationships and may struggle with arbitrary non-linear functions like logarithms. Furthermore, the extreme pessimism required for safety can lead to a "completeness gap," where the agent fails to find a plan even if one exists. Future research will focus on online learning, where agents actively explore to expand their "safety envelope," and exploring methods to slightly relax safety guarantees in exchange for increased problem-solving coverage.
Summary updated