Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans

Songtuan Lin, Alban Grastien, Rahul Shome, Pascal BercherAAAI 2025 · DOI

TL;DR

This paper introduces a novel approach to automatically correct flawed automated planning domains by leveraging "counter-example" plans. These are plans that are valid in a flawed model but not in the real-world scenario, complementing existing methods that use "positive" plans (valid in the real world but not the flawed model). The proposed method finds the smallest set of domain modifications to ensure all positive plans are valid and all counter-example plans are invalid.

What Problem Does This Paper Address?

Automated planning, a field focused on finding sequences of actions to achieve goals, is powerful but often hindered by the difficulty of accurately modeling real-world problems. Creating these "planning domains" requires expertise and is prone to errors, making the technology less accessible. Existing tools can help fix domains by ensuring "positive" plans (which should work but don't in the flawed model) become valid. However, a critical gap exists: what about "negative" or "counter-example" plans? These are plans that appear valid in the flawed model but are actually impossible or undesirable in reality (e.g., a robot plan that looks feasible in simulation but is physically impossible). This paper addresses the challenge of correcting planning domains by incorporating these crucial counter-example plans, aiming for more robust and accurate domain models.

Methods

The core of the paper is an algorithm that extends existing domain repair techniques to handle both positive and negative plans. The approach is based on an iterative process of identifying "conflicts" – situations where the current domain model leads to incorrect behavior with respect to the provided plans.

  1. Conflict Identification: The algorithm iteratively identifies conflicts. For positive plans, it finds situations where a plan that should be valid is not. For negative plans, it identifies situations where a plan that should be invalid is incorrectly considered valid.
  2. Conflict Representation: Conflicts are represented as sets of "atomic repairs" (modifications to action preconditions or effects). A conflict indicates that at least one repair from a specific set must be applied to resolve the issue.
  3. Minimum Hitting Set: The algorithm then computes a "minimum hitting set" over these conflicts. This hitting set represents the smallest collection of atomic repairs that resolve all identified conflicts.
  4. Iterative Refinement: If the computed hitting set successfully corrects the domain (i.e., all positive plans become valid and all negative plans become invalid), the algorithm terminates. Otherwise, new conflicts are generated based on the current candidate repair set, and the process repeats.

The novelty lies in the formalization and computation of conflicts arising from negative plans, and the integration of these into a unified framework for finding a cardinality-minimum repair set.

Datasets

The paper evaluates its approach on two types of benchmarks:

  1. Randomized Errors on IPC Domains: They used domains from the International Planning Competition (IPC) benchmark suite. For these domains, they randomly introduced errors by either overly relaxing (deleting preconditions, deleting negative effects, adding positive effects) or overly restricting (adding preconditions, adding negative effects, deleting positive effects) action schemas. This resulted in 15 flawed domains.
  2. Bespoke Benchmarks: They also created three handcrafted domains inspired by robotics applications. These include modified versions of BlocksWorld and Gripper domains, focusing on specific geometric or state-related constraints that might lead to counter-example plans.

Key Insights and Ideas

  • The Importance of Counter-Example Plans: The paper strongly argues that negative plans (counter-examples) are as crucial as positive plans for robust domain modeling. Ignoring them can lead to models that accept invalid plans, which is particularly problematic in safety-critical applications like robotics.
  • Unified Repair Framework: The method successfully unifies the repair of both positive and negative plan issues into a single, coherent framework. This is achieved by extending the notion of "conflicts" to encompass both types of plan violations.
  • Cardinality-Minimum Repairs: The focus on finding the smallest set of repairs is key. This ensures that the corrected domain retains as much of the original, intended logic as possible, minimizing unintended side effects.
  • Generalizability: The approach is designed to work with lifted planning domains (handling variables and types) and can modify both preconditions and effects (positive and negative).

Key Results

  • Strong Performance on Randomized Errors: The proposed approach achieved higher precision and recall in fixing domains with randomized errors compared to a baseline method that only considers positive plans. In most domains, their method had better recall.
  • Effective on Bespoke Benchmarks: For handcrafted domains inspired by robotics, the approach achieved 100% precision and 100% recall. This highlights its effectiveness in scenarios where errors are more nuanced and related to real-world constraints.
  • Feasible Runtime: While the approach is more computationally intensive than methods only handling positive plans, it generally completes repairs within 100 seconds, with many instances taking less than 10 seconds. This demonstrates the practical feasibility of the method for interactive modeling assistance.

Limitations and Future Work

  • Computational Complexity: The paper acknowledges that the problem of finding optimal domain repairs is NP-hard, even in the grounded setting. While their approach is efficient enough for practical use, the search space for repairs in lifted domains can be exponential, leading to longer runtimes compared to simpler methods.
  • Randomness in Hitting Set Solvers: The authors note that the randomness in the hitting set solver can lead to different optimal repair sets being returned on different runs. This can affect the precision and recall metrics, which are averaged over multiple runs.
  • Future Work: The authors suggest exploring more efficient conflict generation strategies and potentially integrating their approach with interactive modeling tools to provide faster feedback to users. They also highlight the connection to real-world applications like robotics, implying further research in that direction.

Summary updated

BibTeX
@inproceedings{lin2025told,
  author = {Songtuan Lin and Alban Grastien and Rahul Shome and Pascal Bercher},
  title = {{Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i25.34861},
}
Figure