Enhancing Numeric-SAM for Learning with Few Observations

Argaman Mordoch, Shahaf S. Shperberg, Roni Stern, Brendan Juba

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

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 that addresses this challenge. It is an algorithm designed to learn the preconditions and effects of actions from observations in domains that may involve both discrete and continuous state variables. N-SAM has several attractive properties. It runs in polynomial time and is guaranteed to output an action model that is safe, in the sense that plans generated by it are applicable and will achieve their intended goals. To preserve this safety guarantee, N-SAM must observe a substantial number of examples for each action before it is included in the learned action model. We address this limitation of N-SAM and propose N-SAM*, an enhanced version of N-SAM that always returns an action model where every observed action is applicable at least in some state, even if it was only observed once. N-SAM* does so without compromising the safety of the returned action model. We prove that N-SAM* is optimal in terms of sample complexity compared to any other algorithm that guarantees safety. An empirical study on a set of benchmark domains shows that the action models returned by N-SAM* enable solving significantly more problems compared to the action models returned by N-SAM.
BibTeX
@misc{mordoch2023enhancing,
  author = {Argaman Mordoch and Shahaf S. Shperberg and Roni Stern and Brendan Juba},
  title = {{Enhancing Numeric-SAM for Learning with Few Observations}},
  year = {2023},
  eprint = {2312.10705},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.10705},
}

Loading related content...

Figure