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.