Learning Safe Numeric Action Models

Argaman Mordoch, Brendan Juba, Roni Stern

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:

  1. Boolean Learning: It leverages established SAM techniques to manage the discrete aspects of actions.
  2. 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.
  3. 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.
Overview of the N-SAM learning process, utilizing convex hulls for safe preconditions and linear regression for numeric effects.

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%.

Performance of N-SAM across various planning domains, showing the average number of problems solved as the number of training trajectories increases.

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

Abstract

Powerful domain-independent planners have been developed to solve various types of planning problems. These planners often require a model of the acting agent's actions, given in some planning domain description language. Yet obtaining such an action model is a notoriously hard task. This task is even more challenging in mission-critical domains, where a trial-and-error approach to learning how to act is not an option. In such domains, the action model used to generate plans must be safe, in the sense that plans generated with it must be applicable and achieve their goals. Learning safe action models for planning has been recently explored for domains in which states are sufficiently described with Boolean variables. In this work, we go beyond this limitation and propose the NSAM algorithm. NSAM runs in time that is polynomial in the number of observations and, under certain conditions, is guaranteed to return safe action models. We analyze its worst-case sample complexity, which may be intractable for some domains. Empirically, however, NSAM can quickly learn a safe action model that can solve most problems in the domain.
BibTeX
@inproceedings{mordoch2023learning,
  author = {Argaman Mordoch and Brendan Juba and Roni Stern},
  title = {{Learning Safe Numeric Action Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i10.26424},
}
Figure