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

TL;DR

This paper introduces "hereditary partitions," a novel technique for proving that certain states are unreachable in robot planning problems. This is crucial because traditional theorem provers often fail to report impossibility, instead just getting stuck. The authors implemented this in a program called DISPROVER, which can rigorously demonstrate that a robot goal is impossible to achieve.

What Problem Does This Paper Address?

Imagine you're programming a robot to perform a task. You give it a set of rules (axioms) about its environment and how it can move (operators). If the robot can achieve a goal, a standard "theorem prover" can find a sequence of actions to get there. But what happens if the goal is actually impossible to reach? Traditional systems usually just give up, reporting that they "cannot solve the problem" without explaining why. This is frustrating and unhelpful. The authors argue that it's equally, if not more, important to be able to prove that a task is impossible. This is especially relevant in robotics, where an incorrect assumption about what a robot can do can lead to dangerous or inefficient behavior.

Methods

The core innovation is the concept of hereditary partitions. Think of it like this:

  1. Start with the Goal: Identify key properties (predicates) that define the goal state.
  2. Define Partitions: Divide the entire possible world of states into distinct "partitions" based on these properties. For example, if the goal is for boxes to be next to each other, one partition might be "no boxes are next to each other," another "box 1 and box 2 are next to each other, but box 3 isn't next to box 1 or 2," and so on.
  3. Check Heredity: The crucial step is to determine if these partitions are "closed under legal moves." This means if you start in a state within a particular partition and apply any valid robot action, you will always end up in a state that belongs to the same partition or another defined partition.
  4. Disproof: If the goal state does not belong to any of these defined, closed partitions, then it's impossible to reach. The paper also discusses "bootstrapping," where DISPROVER can expand its set of anchor predicates if an initial disproof attempt fails, to try and find a more robust set of partitions.

This is a generalization of "hereditary properties," where the entire world is just one partition.

Datasets

Not discussed in the paper. The authors use simulated "robot worlds" defined by predicates and operators, similar to those described in existing literature (e.g., [1] and [4]).

Key Insights and Ideas

  • The Value of "No": Proving impossibility is as important as proving possibility, especially for ensuring robust and safe robot behavior.
  • Partitions as a Proof Tool: Hereditary partitions provide a formal, systematic way to demonstrate impossibility, moving beyond ad-hoc model building.
  • Systematic Exploration: DISPROVER systematically generates partitions, ensuring that if a disproof is found, it's rigorous.
  • Cooperation is Key: DISPROVER can work with path-finding programs (like LAWALY) to provide crucial information when the path-finder gets stuck, either by proving impossibility or by suggesting intermediate states.
  • Axiomatization Matters: The way a robot's world is described (its axiomatization) significantly impacts the difficulty of planning and disproving tasks.

Key Results

  • The paper presents a program, DISPROVER, implemented in LISP, that successfully applies the hereditary partitions technique.
  • It provides a disproof for a goal state in a robot world where three boxes must be next to each other, demonstrating the technique's power.
  • It shows examples of DISPROVER cooperating with a planner (LAWALY), where DISPROVER's disproof capabilities help resolve planning deadlocks or confirm impossibility. For instance, in one case, DISPROVER helped LAWALY solve a problem by suggesting splitting it into two sub-problems.
  • DISPROVER found a disproof for the three-box problem in about 7 seconds and another disproof in about 3 seconds.

Limitations and Future Work

  • Bootstrapping Limitations: While DISPROVER can bootstrap its anchor predicates, it can still fail to find a disproof if no new sets of predicates can be generated.
  • LAWALY's Stubbornness: The paper notes that LAWALY can be "stubborn" in its approach, sometimes leading to collaborative failures.
  • Improving Cooperation: The authors are investigating ways for LAWALY to communicate why she failed to find a path, which could help DISPROVER build more adequate anchor predicates.
  • Axiomatization Sensitivity: The effectiveness of both planning and disproving is highly dependent on the chosen axiomatization, suggesting a need for more robust world representations.
  • "Patching" Goals: The authors suggest that "patching" goal descriptions to include implicit consequences (like being in the same room as an object you're on) can simplify problems, though this feels like a workaround rather than a fundamental solution.

Summary updated

BibTeX
@inproceedings{1973proving,
  title = {{Proving the Impossible is Impossible is Possible: Disproofs Based on Hereditary Partitions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1973},
}
Figure