Computing Superior Counter-Examples for Conformant Planning

Xiaodi Zhang, Alban Grastien, Enrico ScalaAAAI 2020 · DOI

Abstract

Conformant planning involves finding a plan that works across all possible initial states, a task made difficult by the exponential state space. This paper introduces SUPERB, a planner that optimizes the counter-example guided refinement (CEGAR) process by selecting "superior" counter-examples. These states are chosen to reveal multiple logical constraints or "tags" simultaneously, maximizing information gain per iteration. Experimental results demonstrate that SUPERB significantly reduces the number of iterations required to find a valid plan, achieving substantial speed-ups and scaling more effectively than existing baselines on both standard and new multi-agent benchmarks.

Introduction

In conformant planning, an agent must achieve a goal despite uncertainty about the initial state of the world. Because the number of possible initial states grows exponentially with the number of variables, exhaustive checking is infeasible. A common approach, exemplified by the baseline planner gCPCES, uses a small sample of initial states to generate a candidate plan. If the plan fails for a different initial state (a counter-example), that state is added to the sample, and the plan is refined. However, random counter-examples often provide redundant information, leading to excessive iterations. The authors of this paper address this by identifying the most informative counter-examples to minimize planning cycles.

Methodology: Tags and Superiority

The core innovation of SUPERB is the concept of superiority among counter-examples, defined through tags:

  • Tags: These represent specific contingencies or subgoals—logical combinations of initial variables that determine plan success.
  • Superiority: A counter-example is considered superior if it exhibits more previously unaddressed tags than alternative counter-examples.

Instead of selecting the first counter-example found by a SAT solver, SUPERB employs an iterative procedure called compute-optimal-counter-example. This algorithm repeatedly queries the SAT solver to find states that cover all currently identified tags plus at least one additional new tag. This ensures that each planning iteration provides the maximum possible amount of new information to the planner, effectively solving multiple contingencies at once.

Experimental Setup

The authors evaluated SUPERB against the gCPCES baseline and the state-of-the-art heuristic planner T1 using:

  • Standard Benchmarks: Including DISPOSE, BOMB, COINS, UTS, and BLOCKWORLD.
  • MAWALLGRID: A new multi-agent benchmark introduced in this work. It features agents with unknown starting positions moving in turns, designed to test the planner's ability to handle decomposable, "non-horizontal" problem structures where multiple independent contingencies exist.

Key Results

SUPERB demonstrates significant performance gains over the baseline across multiple metrics:

Iteration Reduction and Speed

By selecting superior counter-examples, SUPERB drastically reduces the number of iterations needed to converge on a valid plan. For instance, in the BOMB domain, the number of iterations dropped from 61 to just 3, contributing to a speed-up of nearly two orders of magnitude in some instances.

Table 1: Performance comparison showing planning time, iterations, and sampling time across standard domains.

Scaling and Robustness

In the DISPOSE domain, SUPERB's iteration count remained constant even as the complexity (number of objects) increased, whereas the baseline's iterations grew significantly. Furthermore, in the new MAWALLGRID domain, SUPERB successfully solved large instances where the T1 planner timed out (TO), highlighting its effectiveness in highly constrained environments with complex dependencies.

Table 2: Detailed scaling results for the MAWALLGRID and DISPOSE domains, showing iteration stability and comparison with T1.

Discussion and Future Work

While SUPERB excels in complex, decomposable problems, it can incur slight overhead in simpler "horizontal" problems where only one primary contingency exists. In these cases, the additional SAT checks required to find superior counter-examples may not be offset by iteration savings. Future research directions include automating the identification of redundant tags and integrating superior counter-example selection with heuristic search techniques to further enhance performance across a broader range of planning tasks.

Summary updated

BibTeX
@inproceedings{zhang2020computing,
  author = {Xiaodi Zhang and Alban Grastien and Enrico Scala},
  title = {{Computing Superior Counter-Examples for Conformant Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6558},
}
Figure