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, andBLOCKWORLD. - 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.
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.
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