Inductive Certificates of Unsolvability for Domain-Independent Planning

Salomé Eriksson, Gabriele Röger, Malte HelmertIJCAI 2018 · DOI

TL;DR

This paper introduces "inductive certificates" – a formal, verifiable way to prove that a planning problem is unsolvable. Unlike simply trusting a planner's claim of unsolvability, these certificates can be independently checked, offering a robust solution to the problem of verifying negative planning results.

What Problem Does This Paper Address?

Automated planning systems aim to find a sequence of actions to achieve a goal from an initial state. When a planner finds a solution, it's easy to verify by executing the plan. However, when a planner claims a problem is unsolvable, there's no independent way to confirm this; we have to trust the planner's internal workings. This lack of verifiable proof for unsolvability is a significant gap, especially as detecting unsolvable problems is becoming increasingly important in planning research. The authors tackle this by proposing a formal, verifiable method to prove unsolvability.

Methods

The core contribution is the concept of inductive certificates. An inductive set of states is one where, once you enter it, you can never leave it, regardless of the actions taken. An inductive certificate is a specific type of inductive set that meets three criteria:

  1. It contains the initial state of the planning problem.
  2. It does not contain any goal states.
  3. It is inductive (i.e., any action applied to a state within the set results in another state within the same set).

If such a set exists, it logically proves unsolvability: any plan must start in the initial state (which is in the set), can never leave the set (because it's inductive), and therefore can never reach a goal state (because the set contains no goal states). The paper also discusses how these certificates can be represented efficiently using BDDs, 2-CNF, or Horn formulas, and how they can be generated by existing planning techniques. They further introduce composite certificates (disjunctive and conjunctive) to handle cases where a single formula might not be compact enough.

Datasets

Not discussed in the paper. The paper focuses on a general framework for planning tasks and does not rely on specific datasets for training or evaluation. The experiments use a collection of unsolvable planning tasks, including those from the Unsolvability IPC.

Key Insights and Ideas

  • Formalizing Unsolvability: The most significant insight is the formalization of unsolvability proofs through inductive certificates. This moves beyond trusting opaque planner outputs to a verifiable, logical deduction.
  • The Power of "Traps": The concept of inductive sets acting as "traps" is crucial. These sets, once entered, guarantee that the planner cannot escape to a goal state, providing a clear mechanism for proving unsolvability.
  • Bridging Planning and Verification: The work elegantly connects planning (finding paths) with verification (proving non-existence of paths) by providing a common, verifiable output for unsolvable problems.
  • Efficiency is Key: The paper emphasizes that these certificates are not just theoretically sound but also practically useful because they can be generated with polynomial overhead by planners and verified efficiently.

Key Results

  • Soundness and Completeness: Inductive certificates are proven to be sound and complete, meaning a planning task is unsolvable if and only if an inductive certificate exists for it.
  • Efficient Verification: Verification of an inductive certificate can be performed in time polynomial to the size of the certificate representation and the planning task.
  • Practical Generation: The paper demonstrates that state-of-the-art planning techniques (like forward search with heuristics) can generate these certificates with reasonable overhead.
  • Experimental Validation: Experiments with the Fast Downward planner showed that it could detect a significant number of unsolvable tasks and generate verifiable certificates for a substantial portion of them. For A with hmax, 136 out of 212 detected unsolvable tasks yielded verifiable certificates. For A with hM&S, 191 out of 223 tasks did.

Limitations and Future Work

  • Composite Certificate Formalism Restriction: A limitation for composite certificates is that all constituent sets must be represented in the same formalism. The authors suggest an extension towards a flexible proof system to address this.
  • Proof of Concept Implementation: The experimental implementation is described as a "proof of concept" and could be further optimized.
  • Future Work: The authors point to extensions for more flexible proof systems and the application of these concepts to other areas of AI.

Summary updated

BibTeX
@inproceedings{eriksson2018inductive,
  author = {Salomé Eriksson and Gabriele Röger and Malte Helmert},
  title = {{Inductive Certificates of Unsolvability for Domain-Independent Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/730},
}
Figure