Proving the Impossible is Impossible is Possible: Disproofs Based on Hereditary Partitions

Laurent Siklóssy, John W. Roach

Abstract

In robot planning, identifying unreachable goals is as critical as finding valid action sequences. This paper introduces DISPROVER, a system developed at the University of Texas at Austin in 1973. DISPROVER utilizes "hereditary partitions" to formally demonstrate when a state is unattainable, preventing planners from entering infinite loops when faced with impossible tasks.

Introduction

Early AI planning systems were primarily designed to find solutions. However, when presented with an impossible goal—such as a robot attempting to be in two locations simultaneously—these systems often failed to terminate or provided unhelpful error messages. The authors argue that a formal method for disproof is essential for robust autonomous systems. By rigorously proving that a goal lies outside the "attainable world," a robot can avoid wasting resources on unsolvable subgoals.

The DISPROVER System and Hereditary Partitions

The core of DISPROVER's methodology is the concept of hereditary partitions, a generalization of hereditary properties. A hereditary property is a state characteristic that remains invariant under all legal moves. For instance, in the mutilated checkerboard problem, the parity of covered squares is a hereditary property that makes a full tiling impossible.

DISPROVER extends this by partitioning the state space into sets closed under legal operators. The algorithm follows these steps:

  1. Partitioning: It defines partitions based on "anchor predicates" derived from the goal state.
  2. Operator Application: It checks if any legal move can transition the system from a partition where the goal predicate is false to one where it is true.
  3. Disproof: If the goal state is not contained within any partition reachable from the initial state, the goal is mathematically proven impossible.
Hereditary partitions for the Three-Box Problem.

If an operator appears capable of reaching the goal, DISPROVER employs a "bootstrapping" mechanism, adding the preconditions of that operator as new anchor predicates to refine the partitions and attempt the disproof again.

Experimental Evaluation

The system was evaluated on several classic AI domains:

  • The Three-Box Problem: Proving that three boxes cannot be arranged in a triangle when only linear "next-to" moves are possible. DISPROVER achieved this disproof in just 7 seconds on a CDC 6600.
  • The Lightswitch Problem: A scenario involving a robot, a box, and a lightswitch. The system proved the impossibility of certain state transitions in 3 seconds using only three partitions.
Initial and final states in a robot world simulation.

Furthermore, DISPROVER was integrated with LAWALY, a path-finding program. When DISPROVER failed to disprove a goal, it provided diagnostic information—identifying potential "bridge" states—that helped LAWALY solve previously intractable problems.

Conclusion and Future Work

DISPROVER demonstrates that "proving the impossible" is computationally feasible and highly beneficial for planning systems. By closing the state space through hereditary partitions, it addresses the "Category C" problem of formulas that are neither theorems nor negations in standard logic.

However, the system's effectiveness is highly sensitive to the initial axiomatization of the world. Future research directions include improving the communication between provers and disprovers to handle more complex subgoals and refining bootstrapping techniques to manage larger state spaces without hitting memory limits.

Summary updated

BibTeX
@inproceedings{siklossy1973proving,
  author = {Laurent Siklóssy and John W. Roach},
  title = {{Proving the Impossible is Impossible is Possible: Disproofs Based on Hereditary Partitions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1973},
}
Figure