TY - JOUR
T1 - CPCES
T2 - A planning framework to solve conformant planning problems through a counterexample guided refinement
AU - Grastien, Alban
AU - Scala, Enrico
N1 - Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2020/7
Y1 - 2020/7
N2 - 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. Finally, we show how CPCES can be used in a more incremental fashion by learning sequencing of actions from the previous plan being found. Such a technique mimics the use of macro-operators, widely used in automated planning to speedup resolution. Our theoretical analysis is accompanied with a thorough experimental evaluation of the (many) possible incarnations of CPCES. This not only proves our theoretical findings from an empirical perspective, but also shows that CPCES is able to handle problems that have been traditionally hard to solve by the existing conformant planners, whilst remaining competitive over “easier” conformant planning problems. Importantly, CPCES is able to prove many unsolvable conformant planning problems as such, extending substantially the reach of conformant planners.
AB - 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. Finally, we show how CPCES can be used in a more incremental fashion by learning sequencing of actions from the previous plan being found. Such a technique mimics the use of macro-operators, widely used in automated planning to speedup resolution. Our theoretical analysis is accompanied with a thorough experimental evaluation of the (many) possible incarnations of CPCES. This not only proves our theoretical findings from an empirical perspective, but also shows that CPCES is able to handle problems that have been traditionally hard to solve by the existing conformant planners, whilst remaining competitive over “easier” conformant planning problems. Importantly, CPCES is able to prove many unsolvable conformant planning problems as such, extending substantially the reach of conformant planners.
KW - Classical planning
KW - Conformant planning
KW - Propositional satisfiability
UR - http://www.scopus.com/inward/record.url?scp=85082683324&partnerID=8YFLogxK
U2 - 10.1016/j.artint.2020.103271
DO - 10.1016/j.artint.2020.103271
M3 - Article
SN - 0004-3702
VL - 284
JO - Artificial Intelligence
JF - Artificial Intelligence
M1 - 103271
ER -