Computing Superior Counter-Examples for Conformant Planning
Computing Superior Counter-Examples for Conformant Planning
Zhang, X, Grastien, A & Scala, E 2020, ‘Computing Superior Counter-Examples for Conformant Planning’, The Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI-20).
We address the problem of conformant planning, i.e., finding a sequence of actions that is guaranteed to lead to a specified objective despite uncertainty on the initial state, or proving that no such sequence exists. The difficulty of this task comes from the large number of initial states that needs to be considered, which is potentially exponential in the number of uncertain variables. Our work builds on our existing planner, CPCES. In this approach, the complexity of the problem is tamed by intertwining two procedures: first candidate plans are generated that are guaranteed to be valid for a certain number of initial states that are considered representative of the problem; the second procedure search counter-examples for which the plan is not valid, and adds these counter-examples to the list of representative initial states. In this work we show how to analyse the structure of the problem and the relation between the different state variables, to help generate better counter-examples, i.e., counter-examples that will guarantee that fewer counter-examples will be needed in the future. This is beneficial for two reasons: first, it accelerates the procedure as fewer iterations are necessary to compute a valid plan. Second, as the set of representative counter-examples can be used as a justification for the plan (it illustrates all initial states that the procedure needed to take into account in order to produce a valid plan), our improvement allows to generate explanations for the plan that are more compact and easier to interpret.