Reshaping Diverse Planning

Michael Katz, Shirin SohrabiAAAI 2020 · OpenReview

Abstract

The need for multiple plans has been established by various planning applications. In some, solution quality has the predominant role, while in others diversity is the key factor. Most recent work takes both plan quality and solution diversity into account under the generic umbrella of diverse planning. There is no common agreement, however, on a collection of computational problems that fall under that generic umbrella. This in particular might lead to a comparison between planners that have different solution guarantees or optimization criteria in mind. In this work we revisit diverse planning literature in search of such a collection of computational problems, classifying the existing planners to these problems. We formally define a taxonomy of computational problems with respect to both plan quality and solution diversity, extending the existing work. We propose a novel approach to diverse planning, exploiting existing classical planners via planning task reformulation and choosing a subset of plans of required size in post-processing. Based on that, we present planners for two computational problems, that most existing planners solve. Our experiments show that the proposed approach significantly improves over the best performing existing planners in terms of coverage, the overall solution quality, and the overall diversity according to various diversity metrics.

Introduction

In many real-world AI applications, a single "optimal" plan is often insufficient. Whether the context is malware detection, risk management, or accounting for complex user preferences, decision-makers require a set of alternative solutions that are both high-quality and significantly distinct from one another. This field, known as diverse planning, has historically lacked standardized problem definitions and metrics, leading to a "Wild West" environment where fair comparison between planners was nearly impossible.

Existing diverse planners typically modify internal search heuristics to favor diversity. However, this approach is technically challenging, often metric-specific, and prone to generating minor reorderings of the same plan rather than fundamentally different strategies. This paper addresses these challenges by introducing a formal taxonomy and a novel, planner-agnostic approach called "Forbid Iterative" (FI).

A Formal Taxonomy of Diverse Planning

To bring order to the field, the authors define a hierarchy of computational problems based on plan quality and solution diversity. This taxonomy ranges from Satisficing (finding $k$ plans) to Bounded (finding $k$ plans within specific cost or diversity thresholds) and Optimal (finding the absolute best set of $k$ plans according to a given metric).

Hierarchy of diverse planning computational problems, illustrating the relationships between satisficing, bounded, and optimal problem variants.

By classifying existing planners within this framework, researchers can ensure they are comparing "apples to apples" regarding solution guarantees and optimization criteria.

The Forbid Iterative (FI) Approach

The proposed FI approach shifts the focus from modifying the planner's internal logic to reformulating the planning task itself. The process follows three main steps:

  1. Generation: A standard, off-the-shelf classical planner finds an initial plan.
  2. Task Reformulation: The planning problem is modified to explicitly "forbid" the specific multiset of actions used in the previous plan. This forces the planner to find a "set-different" solution in the next iteration, effectively ignoring simple reorderings.
  3. Selection: This process repeats until a large pool of plans is generated. A simple greedy algorithm then selects the most diverse subset of size $k$ from this pool.

This "black box" approach allows FI to leverage any advancement in classical satisficing planning. For the experiments, the authors utilized the state-of-the-art MERWIN planner. Furthermore, by separating generation from selection, the system gains flexibility; diversity metrics can be changed in post-processing without re-running the expensive planning phase.

Experimental Evaluation

The FI approach was evaluated against a benchmark of 1276 tasks across 40 domains from the International Planning Competitions (IPC), restricted to STRIPS domains with uniform action costs. The researchers also introduced a new quality metric, $Q_c$, which compares each plan in a set to the best-known $k$ plans, offering a more robust measure of overall solution quality than traditional averages.

The results demonstrate that FI significantly outperforms specialized diverse planners such as DLAMA, DIV, and MQA across multiple dimensions.

Experimental results comparing FI against other planners across different values of k, showing superior performance in coverage, quality (Qc), and various diversity metrics.

As shown in the table, FI achieved substantially higher coverage. For $k=5$, FI solved 1143 problems, nearly doubling the coverage of the next best competitor, MQAts (615). This trend continued as $k$ increased. Additionally, FI consistently scored higher across all diversity metrics (stability, state, and uniqueness) and the $Q_c$ quality metric.

Conclusion and Future Work

The Forbid Iterative approach represents a significant step forward in diverse planning by providing a flexible, high-performance framework that leverages existing classical planning technology. While highly effective, the authors identify several avenues for future research. The current greedy selection process could be replaced with more sophisticated algorithms to further optimize diversity. Additionally, while FI excels at satisficing and bounded problems, solving for mathematical "diversity-optimality" (optD-k) remains a major computational challenge. Future work may also explore alternative task reformulation strategies beyond forbidding action multisets to further enhance the variety of generated plans.

Summary updated

Abstract

The need for multiple plans has been established by various planning applications. In some, solution quality has the predominant role, while in others diversity is the key factor. Most recent work takes both plan quality and solution diversity into account under the generic umbrella of diverse planning. There is no common agreement, however, on a collection of computational problems that fall under that generic umbrella. This in particular might lead to a comparison between planners that have different solution guarantees or optimization criteria in mind. In this work we revisit diverse planning literature in search of such a collection of computational problems, classifying the existing planners to these problems. We formally define a taxonomy of computational problems with respect to both plan quality and solution diversity, extending the existing work. We propose a novel approach to diverse planning, exploiting existing classical planners via planning task reformulation and choosing a subset of plans of required size in post-processing. Based on that, we present planners for two computational problems, that most existing planners solve. Our experiments show that the proposed approach significantly improves over the best performing existing planners in terms of coverage, the overall solution quality, and the overall diversity according to various diversity metrics.
BibTeX
@inproceedings{katz2020reshaping,
  author = {Michael Katz and Shirin Sohrabi},
  title = {{Reshaping Diverse Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=vKTyfKoqZU},
}

Loading related content...

Figure