Evaluating Temporal Plans in Incomplete Domains

Abstract

Recent work on planning in incomplete domains focuses on constructing plans that succeed despite incomplete knowledge of action preconditions and effects. As planning models become more expressive, such as in temporal planning, the types of incompleteness may not only change, but plans become more challenging to evaluate. The primary difficulty to temporal plan evaluation is accounting for temporal constraints that may not be satisfied under all interpretations of the incomplete domain. In this work, we formulate incomplete temporal plan evaluation as a generalization of the temporal consistency problem, called partial temporal consistency. We present a knowledge compilation approach that is combined with symbolic constraint propagation and model counting algorithms for counting the number of incomplete domain model interpretations under which a plan is consistent. We present an evaluation that identifies the aspects of incomplete temporal plans most impact performance.