Towards Certified Unsolvability in Classical Planning

Gabriele RögerIJCAI 2017 · DOI

TL;DR

This paper tackles the challenge of verifying that a planning problem has no solution, a task that's currently difficult to trust. The authors propose a framework for "unsolvability certificates" that allow independent verification, building upon the concept of inductive sets and suggesting a more flexible proof system to integrate various planning techniques.

What Problem Does This Paper Address?

Classical planning systems aim to find a sequence of actions (a plan) to reach a desired goal state from an initial state, or to prove that no such plan exists. While verifying a found plan is relatively straightforward, verifying that a task is unsolvable is much harder. If a planning system claims a task is unsolvable, it's difficult for an external party to trust this claim, especially in real-world applications where bugs or malicious intent could lead to false negatives. This lack of verifiable proof for unsolvability discourages the use of such systems in critical scenarios. The International Planning Competition's focus on proving unsolvability (UIPC) highlights this need for reliable verification.

Methods

The paper introduces the concept of unsolvability certificates that can be generated alongside the claim of unsolvability. These certificates must be:

  • Complete: A certificate exists for every unsolvable task.
  • Efficiently Generatable: Creating a certificate should not add excessive overhead to the planning algorithm.
  • Efficiently Verifiable: Checking a certificate should be computationally feasible.
  • General: Applicable to a wide range of planning algorithms.

The core idea revolves around inductive sets. An inductive set of states is one where any action applied within a state in the set leads to another state within the same set. If such a set contains no goal states and includes the initial state, then the task is proven unsolvable. The paper discusses representing these sets using logical formulas (like BDDs or Horn clauses) for efficiency.

To address limitations of monolithic certificates, the authors discuss conjunctive and disjunctive certificates, which factorize the proof into multiple component sets. They also propose a more flexible rule-based proof system that can integrate different formalisms and perspectives (forward/backward search) to create a more comprehensive and adaptable verification framework.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "Trust Gap" in Unsolvability: The paper clearly articulates why verifying unsolvability is a critical and currently unmet need in planning.
  • Inductive Sets as a Universal Concept: The idea of inductive sets provides a unifying theoretical basis for proving unsolvability, bridging different planning approaches.
  • Formalizing Proofs for Unsolvability: Moving beyond just finding certificates, the proposal for a rule-based proof system suggests a structured way to combine evidence from various sources.
  • Bridging Representation Formalisms: The discussion on conjunctive/disjunctive certificates and the proposed proof system aims to overcome the challenge of integrating certificates generated using different logical representations (e.g., BDDs vs. Horn clauses).

Key Results

The paper presents a theoretical framework and conceptual ideas rather than empirical results with concrete numbers. The key findings are:

  • Identification of inductive sets as a promising concept for general unsolvability certificates.
  • Discussion of formalisms (BDDs, Horn formulas, 2-CNF) suitable for representing these certificates.
  • Introduction of conjunctive and disjunctive certificates to handle complex proofs.
  • A proposal for a flexible rule-based proof system to integrate diverse verification components.

Limitations and Future Work

The authors acknowledge that their proposed proof system is still in its early stages and requires formalization. A key challenge is defining a suitable set of rules and representation formalisms that ensure both efficient generation/verification and completeness/generality. Future work will focus on formalizing this proof system and exploring its practical implementation. The paper also notes that current certificate approaches have limitations when it comes to arbitrary combinations of planning techniques.

Summary updated

BibTeX
@inproceedings{roger2017towards,
  author = {Gabriele Röger},
  title = {{Towards Certified Unsolvability in Classical Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/738},
}
Figure