Action Model Learning with Guarantees

Brendan Juba, Diego Aineto, Enrico Scala

TL;DR

This paper introduces a novel framework for learning action models in AI planning, leveraging "version spaces" to efficiently represent all possible solutions. It demonstrates how to extract both "sound" (guaranteed correct) and "complete" (guaranteed to find a plan if one exists) action models from these spaces, offering a flexible approach to learning domain dynamics.

What Problem Does This Paper Address?

Automating the creation of action models, which describe how actions affect the world, is a major bottleneck in AI planning. Manually defining these models is tedious and error-prone. While many approaches learn action models from demonstrations, they often focus on specific types of models or handle partial observability. This paper tackles the problem of learning action models in the fully observable setting, but with a strong theoretical focus on guaranteeing specific properties of the learned models: soundness and completeness. This is crucial for building reliable AI systems that can plan effectively.

Methods

The core of this work is the application of version spaces, a machine learning technique for representing the set of all hypotheses consistent with a set of training examples. The authors adapt this to action model learning by treating action preconditions and effects as hypotheses.

  • Version Space Representation: For each action, they maintain two version spaces: one for its preconditions and one for its effects. These spaces are defined by lower (L) and upper (U) boundaries, which compactly represent all consistent hypotheses.
  • Online Learning Algorithm (VSLAM): The paper proposes an online algorithm that processes demonstrations sequentially, updating the L and U boundaries of the version spaces. This algorithm efficiently captures all possible action models consistent with the given demonstrations.
  • Sound and Complete Models: The key innovation lies in how they extract specific types of action models from the computed version spaces:
  • Sound Models: These are derived from the lower bounds of the version spaces. They guarantee that any action taken according to the learned model will be correct with respect to the true (unknown) model. This ensures safety but might miss some valid plans.
  • Complete Models: These are derived from the upper bounds of the version spaces. They guarantee that if a plan exists for the true model, the learned model will also find one. This is achieved by using a more expressive, non-deterministic action model representation.

Datasets

The authors evaluate their approach on four standard AI planning domains: BLOCKS, SATELLITE, MICONIC, and DRIVERLOG. They use publicly available generators to create 20 random problems for each domain. To create demonstrations, they first solve these problems using the LAMA planner and then collect transitions from the resulting plans as positive demonstrations. Negative demonstrations are generated by randomly trying actions in states encountered during plan execution. They also introduce "modified domains" which enlarge the hypothesis space by adding extra parameters to actions, leading to more distinct and less overlapping demonstrations.

Key Insights and Ideas

  • Version Spaces as a Unified Framework: The paper elegantly shows how version spaces can unify the representation of all possible solutions to an action model learning problem, providing a theoretical foundation for understanding the solution space.
  • Soundness vs. Completeness Trade-off: The work formalizes the well-known trade-off between sound and complete models. Sound models are pessimistic (safe but potentially restrictive), while complete models are optimistic (find plans if they exist, but might be less precise).
  • Extracting Guarantees: The most significant insight is the direct method to extract sound and complete models from the version space boundaries. This provides a principled way to obtain models with desired properties.
  • Complementarity of Sound and Complete Models: The experimental results suggest that neither sound nor complete models universally dominate. They offer complementary strengths, with complete models often performing better early in learning and sound models later, depending on the domain and data distribution.
  • Handling Negative Demonstrations: The framework explicitly leverages negative demonstrations (action failures) to refine the learned models, particularly for the complete models.

Key Results

The paper's main contribution is theoretical, establishing the framework and algorithms for learning sound and complete action models with guarantees. Empirically, they demonstrate:

  • The VSLAM algorithm can learn sound and complete action models.
  • The f1-score (a measure of precision and recall) of both sound and complete models improves as more training demonstrations are provided.
  • The performance of sound and complete models varies across domains and depends on the ratio of positive to negative demonstrations. Complete models tend to perform better with more balanced datasets, while sound models excel in imbalanced ones.
  • Complete models often show an advantage in the earlier stages of learning, while sound models may be outperformed later.

Limitations and Future Work

  • Fully Observable Setting: The current work focuses on fully observable environments. A significant future direction is extending the framework to handle partial observability, which is a more common scenario in real-world AI planning.
  • Expressive Action Models: The paper suggests exploring more expressive action models, such as those with numeric state variables or disjunctive preconditions, by leveraging version space algebra.
  • Noisy Demonstrations: The authors plan to investigate handling noisy demonstrations, building on existing work in version spaces.
  • Active Learning: They propose exploring the role of version spaces in active learning, specifically by focusing on the region between the L and U boundaries where uncertainty is highest, to accelerate convergence.

Summary updated

Abstract

This paper studies the problem of action model learning with full observability. Following the learning by search paradigm by Mitchell, we develop a theory for action model learning based on version spaces that interprets the task as search for hypothesis that are consistent with the learning examples. Our theoretical findings are instantiated in an online algorithm that maintains a compact representation of all solutions of the problem. Among these range of solutions, we bring attention to actions models approximating the actual transition system from below (sound models) and from above (complete models). We show how to manipulate the output of our learning algorithm to build deterministic and non-deterministic formulations of the sound and complete models and prove that, given enough examples, both formulations converge into the very same true model. Our experiments reveal their usefulness over a range of planning domains.
BibTeX
@inproceedings{juba2024action,
  author = {Brendan Juba and Diego Aineto and Enrico Scala},
  title = {{Action Model Learning with Guarantees}},
  booktitle = {Kr},
  year = {2024},
  doi = {10.24963/kr.2024/75},
}
Figure