Computing Superior Counter-Examples for Conformant Planning

In a counter-example based approach to conformant planning, choosing the right counter-example can improve performance. We formalise this observation by introducing the notion of "superiority" of a counter-example over another one, that holds whenever the superior counter-example exhibits more tags than the latter. We provide a theoretical explanation that supports the strategy of searching for maximally superior counter-examples, and we show how this strategy can be implemented. The empirical experiments validate our approach. Introduction Conformant planning is the problem of finding a robust plan despite uncertainty in the initial state (Smith and Weld 1998) . This problem is EXPSPACE-COMPLETE (Haslum and Jonsson 1999). One of the aspects that make it hard is the fact that the number of possible initial states is exponential in the number of state variables; this exponential burden makes brute-force enumeration impractical. We are interested in a recent approach proposed by Grastien and Scala (2017; 2018) and dubbed gCPCES, that addresses this specific issue. In gCPCES, a candidate plan is computed based on a small number of initial states (the sample) that are assumed to be representative of the planning problem. The validity of this plan for the complete problem is then tested. If the plan is found invalid, a counterexample (i.e., an initial state for which the plan is invalid) is generated and added to the sample, since this counterexample is clearly representative of some relevant aspect of the planning problem. This process is repeated until a conformant plan is discovered or it is proved that the problem yields no solution. Notwithstanding its simplicity, this counter-example guided search works well in practice since it generates only relevant counter-examples. In the general framework, a large freedom is left to gCPCES for choosing the counter-example. This freedom however can bring the planner to enrich the sample in a manifestly suboptimal way, as we illustrate in Section 3. There are, instead, good choices that can make the planner converge much faster. In this paper we show how some counter-