Capturing (Optimal) Relaxed Plans with Stable and Supported Models of Logic Programs (Extended Abstract)

Masood Feyzbakhsh Rankooh, Tomi JanhunenIJCAI 2024

Introduction

In the field of Artificial Intelligence (AI) planning, the objective is to determine a sequence of actions that transitions a system from an initial state to a desired goal state. A fundamental technique used to guide search algorithms in this domain is relaxed planning. In a relaxed planning problem, the negative effects of actions are ignored—meaning actions can add facts to the world but never delete them. The cost of an optimal solution to this relaxed problem, denoted as $h^+$, serves as a powerful heuristic for solving the original, non-relaxed problem. However, calculating $h^+$ is NP-equivalent, necessitating efficient computational methods. While Boolean satisfiability (SAT) and Integer Programming (IP) have been the traditional workhorses for this task, this research explores the potential of Answer Set Programming (ASP) to provide superior performance.

Methodology: Logic Programming Encodings

The core contribution of this work is the development of three distinct logic programming encodings for relaxed planning problems. These encodings leverage the strengths of modern ASP solvers, such as CLASP, which are optimized for searching through logical models.

  1. Stable Model Encoding ($P$): The researchers established a mathematical bijection between the sets of actions in a relaxed plan and the stable models of a specific logic program. This encoding relies on the "minimality" property of stable models, which naturally aligns with the goal of finding optimal (minimum cost) plans.
  2. Causal Supported Model Encoding ($P_c$): While stable models are inherently supported, the converse is not always true due to the potential for logical cycles. By introducing an acyclicity constraint—implemented via compact vertex elimination graphs—the authors enable the use of supported model semantics. This encoding follows a "causal" flow: Preconditions $\to$ Actions $\to$ Effects.
  3. Diagnostic Supported Model Encoding ($P_d$): This novel approach reverses the logical direction, performing "diagnostic inference": Effects $\to$ Actions $\to$ Preconditions. By reasoning backward from the goal, this encoding aims to prune the search space more effectively.

Performance Evaluation

To evaluate these encodings, the researchers conducted an extensive empirical study using a massive benchmark from the standard STRIPS planning repository. The dataset comprised 2,212 problem instances across 84 diverse domains. The ASP-based methods were compared against a state-of-the-art Integer Programming (IP) solver utilizing the high-performance IBM ILOG CPLEX optimizer.

Results and Discussion

The experimental results demonstrate a clear advantage for the ASP-based diagnostic encoding. As shown in the performance comparison below, the $P_d$ encoding consistently solves more problems than the IP solver across various time limits, particularly in the short-to-medium time range.

Performance comparison of different ASP encodings ($P_d$, $P_c$, $P$) against the state-of-the-art Integer Programming (IP) solver. The diagnostic encoding ($P_d$) demonstrates superior speed and scalability.

Key findings from the evaluation include:

  • Superior Scalability: The diagnostic encoding ($P_d$) not only solves problems faster but also handles a larger total number of instances within the 1800-second timeout compared to all other tested methods.
  • Directional Efficiency: The significant performance gap between the causal ($P_c$) and diagnostic ($P_d$) encodings highlights that the direction of logical inference is crucial. Reasoning backward from the goal appears to be a much more efficient strategy for relaxed planning.
  • Semantic Impact: Both supported model encodings ($P_c$ and $P_d$) significantly outperformed the basic stable model encoding ($P$). This confirms that the additional complexity of enforcing acyclicity to utilize supported semantics is well-justified by the resulting performance gains.

Conclusion and Future Work

This research establishes a robust link between AI planning and logic programming, demonstrating that optimal relaxed plans can be efficiently captured as stable or supported models. The introduction of the diagnostic encoding ($P_d$) provides a new state-of-the-art method for calculating the $h^+$ heuristic, outperforming traditional Integer Programming approaches.

While highly effective, the efficiency of the supported model encodings depends on the vertex elimination order used to maintain acyclicity. Future work will explore alternative graph-theoretic heuristics beyond the "minimum degree" approach. Additionally, while this work focuses on delete-free planning, extending these logical frameworks to handle general planning problems with negative effects remains a promising avenue for research.

Summary updated

BibTeX
@inproceedings{rankooh2024capturing,
  author = {Masood Feyzbakhsh Rankooh and Tomi Janhunen},
  title = {{Capturing (Optimal) Relaxed Plans with Stable and Supported Models of Logic Programs (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}

Loading related content...

Figure