CPCES: A planning framework to solve conformant planning problems through a counterexample guided refinement

摘要

We introduce cpces, a novel planner for the problem of deterministic conformant planning. cpces solves the problem by producing candidate plans based on a sample of the initial belief state, searching for counter-examples to these plans, and assigning these counter-examples to the sample, until a valid plan has been produced or the problem has been proved unfeasible. On top of providing a means to compute a conformant plan, the sample can also be understood as a justification for the plan being found, or relevant reasons why a plan cannot be found. We study the theoretical properties that cpces enjoys—correctness, completeness, and optimality—and how the several variants of cpces we describe differ in behaviour. Moreover, we establish a theoretical connection between the cpces framework and well-known concepts from the literature such as tags and width. With this connection we prove the worst case complexity for some variants of cpces.