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

*(English)*Zbl 1451.68248Summary: 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.

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.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

PDF
BibTeX
XML
Cite

\textit{A. Grastien} and \textit{E. Scala}, Artif. Intell. 284, Article ID 103271, 38 p. (2020; Zbl 1451.68248)

Full Text:
DOI

##### References:

[1] | Albore, A.; Palacios, H.; Geffner, H., Compiling uncertainty away in non-deterministic conformant planning, (Nineteenth European Conference on Artificial Intelligence (ECAI-10) (2010)), 465-470 · Zbl 1211.68392 |

[2] | Albore, A.; Ramírez, M.; Geffner, H., Effective heuristics and belief tracking for planning with incomplete information, (21st International Conference on Automated Planning and Scheduling (ICAPS-11) (2011)) |

[3] | Barrett, C.; Stump, A.; Tinelli, C., The smt-lib standard version 2.0 (2010), Technical report |

[4] | Blum, Avrim; Furst, Merrick L., Fast planning through planning graph analysis, Artif. Intell., 90, 1-2, 281-300 (1997) · Zbl 1017.68533 |

[5] | Bonet, B., Conformant plans and beyond: principles and complexity, Artif. Intell., 174, 245-269 (2010) · Zbl 1207.68344 |

[6] | Bonet, B.; Geffner, H., Planning with incomplete information as heuristic search in belief space, (Fifth International Conference on AI Planning Systems (AIPS-00) (2000)), 52-61 |

[7] | Bonet, B.; Geffner, H., Planning as heuristic search, Artif. Intell., 129, 1-2, 5-33 (2001) · Zbl 0971.68146 |

[8] | Bonet, B.; Palacios, H.; Geffner, H., Automatic derivation of memoryless policies and finite-state controllers using classical planners, (ICAPS (2009)) |

[9] | Brafman, R.; Shani, G., Replanning in domains with partial information and sensing actions, J. Artif. Intell. Res., 45, 565-600 (2012) · Zbl 1253.68295 |

[10] | Bryant, R., Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., 35, 8, 677-691 (1986) · Zbl 0593.94022 |

[11] | Bryce, Daniel; Kambhampati, Subbarao; Smith, David E., Planning graph heuristics for belief space search, J. Artif. Intell. Res., 26, 35-99 (2006) · Zbl 1182.68225 |

[12] | Bylander, T., The computational complexity of propositional STRIPS planning, Artif. Intell., 69, 1-2, 165-204 (1994) · Zbl 0821.68065 |

[13] | Cimatti, A.; Roveri, M., Conformant planning via symbolic model checking, J. Artif. Intell. Res., 13, 305-338 (2000) · Zbl 0963.68195 |

[14] | Cimatti, A.; Roveri, M.; Bertoli, P., Conformant planning via symbolic model checking and heuristic search, Artif. Intell., 159, 127-206 (2004) · Zbl 1086.68591 |

[15] | Clarke, E.; Grumberg, O.; Jha, S.; Lu, Y.; Veith, H., Counterexample-guided abstraction refinement, (Twelfth International Conference on Computer-Aided Verification (CAV-00) (2000)), 154-169 · Zbl 0974.68517 |

[16] | Darwiche, A.; Marquis, P., A knowledge compilation map, J. Artif. Intell. Res., 17, 229-264 (2002) · Zbl 1045.68131 |

[17] | De Moura, L.; Bjørner, N., Z3: an efficient smt solver, (International Conference on Tools and Algorithms for the Construction and Analysis of Systems (2008), Springer), 337-340 |

[18] | Egly, U.; Kronegger, M.; Lonsing, F.; Pfandler, A., Conformant planning as a case study of incremental QBF solving, Ann. Math. Artif. Intell., 80, 21-45 (2017) · Zbl 1409.68253 |

[19] | Grastien, A.; Scala, E., Intelligent belief state sampling for conformant planning, (26th International Joint Conference on Artificial Intelligence (IJCAI-17) (2017)), 4317-4323 |

[20] | Grastien, A.; Scala, E., Sampling strategies for conformant planning, (28th International Conference on Automated Planning and Scheduling (ICAPS-18) (2018)), 97-105 |

[21] | Grastien, A.; Scala, E., Verifying the validity of a conformant plan is co-NP-complete (2018) |

[22] | Haslum, P.; Jonsson, P., Some results on the complexity of planning with incomplete information, (Fifth European Conference on Planning (ECP-99) (1999)), 308-318 |

[23] | Hoffmann, J.; Brafman, R., Conformant planning via heuristic forward search: a new approach, Artif. Intell., 170, 507-541 (2006) · Zbl 1131.68525 |

[24] | Hoffmann, J.; Nebel, B., The ff planning system: fast plan generation through heuristic search, J. Artif. Intell. Res., 14, 253-302 (2001) · Zbl 0970.68044 |

[25] | Huang, J.; Darwiche, A., The language of search, J. Artif. Intell. Res., 29, 191-219 (2007) · Zbl 1183.68232 |

[26] | Kautz, H.; Selman, B., Pushing the envelope: planning, propositional logic, and stochastic search, (Thirteenth Conference on Artificial Intelligence (AAAI-96) (1996)), 1194-1201 |

[27] | Korf, R. E., Macro-operators: a weak method for learning, Artif. Intell., 26, 1, 35-77 (1985) · Zbl 0562.68071 |

[28] | Kronegger, M.; Pfandler, A.; Pichler, R., Conformant planning as a benchmark for QBF solvers, (International Workshop on Quantified Boolean Formulas (QBF-13) (2013)), 1-5 |

[29] | Kurien, J.; Nayak, P.; Smith, D., Fragment-based conformant planning, (Sixth International Conference on AI Planning Systems (AIPS-02) (2002)), 153-162 |

[30] | Little, I.; Thiébaux, S., Probabilistic planning vs. replanning, (ICAPS Workshop on IPC: Past, Present and Future (2007)) |

[31] | McDermott, D.; Ghallab, M.; Howe, A.; Knoblock, C.; Ram, A.; Veloso, M.; Weld, D.; Wilkins, D., PDDL - the Planning Domain Definition Language (1998), Technical report |

[32] | Minton, S., Quantitative results concerning the utility of explanation-based learning, Artif. Intell., 42, 2, 363-391 (1990) |

[33] | Nguyen, K.; Tran, V.; Son, T. C.; Pontelli, E., On computing conformant plans using classical planners: a generate-and-complete approach, (22nd International Conference on Automated Planning and Scheduling (ICAPS-12) (2012)), 190-198 |

[34] | Palacios, H.; Geffner, H., Compiling uncertainty away in conformant planning problems with bounded width, J. Artif. Intell. Res., 35, 623-675 (2009) · Zbl 1183.68584 |

[35] | Rintanen, J., Constructing conditional plans by a theorem-prover, J. Artif. Intell. Res., 10, 323-352 (1999) · Zbl 0916.68139 |

[36] | Rintanen, J., Expressive equivalence of formalisms for planning with sensing, (Thirteenth International Conference on Automated Planning and Scheduling (ICAPS-03) (2003)), 185-194 |

[37] | Rintanen, J., Asymptotically optimal encodings of conformant planning in QBF, (22nd Conference on Artificial Intelligence (AAAI-07) (2007)), 1045-1050 |

[38] | Rintanen, J., Regression for classical and nondeterministic planning, (Eighteenth European Conference on Artificial Intelligence (ECAI-08) (2008)), 568-572 |

[39] | Madagascar, J. Rintanen, Scalable planning with sat, (Proceedings of the 8th International Planning Competition (IPC-2014) (2014)), 21 |

[40] | Rintanen, J.; Heljanko, K.; Niemelä, I., Planning as satisfiability: parallel plans and algorithms for plan search, Artif. Intell., 170, 12-13, 1031-1080 (2006) · Zbl 1131.68099 |

[41] | Scala, E.; Torasso, P., Deordering and numeric macro actions for plan repair, (24th International Joint Conference on Artificial Intelligence (IJCAI-15) (2015)), 1673-1681 |

[42] | Smith, D.; Weld, D., Conformant graphplan, (Fifteenth Conference on Artificial Intelligence (AAAI-98) (1998)), 889-896 |

[43] | Taig, R.; Brafman, R., Compiling conformant probabilistic planning problems into classical planning, (ICAPS (2013)), 197-205 |

[44] | To, S. T.; Cao Son, T.; Pontelli, E., A generic approach to planning in the presence of incomplete information: theory and implementation, Artif. Intell., 227, 1-51 (2015) · Zbl 1346.68181 |

[45] | Tran, V.; Nguyen, K.; Son, T. C.; Pontelli, E., A conformant planner based on approximation: CpA(H), ACM Trans. Intell. Syst. Technol., 4, 2, 36:1-36:38 (2013) |

[46] | Tu, P. H.; Son, T. C.; Gelfond, M.; Morales, A. R., Approximation of action theories and its application to conformant planning, Artif. Intell., 175, 79-119 (2011) · Zbl 1230.68185 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.