Robustness in probabilistic temporal planning

Flexibility in agent scheduling increases the resilience of temporal plans in the face of new constraints. How-ever, current metrics of flexibility ignore domain knowl-edge about how such constraints might arise in practice, e.g., due to the uncertain duration of a robot’s transition time from one location to another. Probabilistic tempo-ral planning accounts for actions whose uncertain dura-tions can be modeled with probability density functions. We introduce a new metric called robustness that mea-sures the likelihood of success for probabilistic tempo-ral plans. We show empirically that in multi-robot plan-ning, robustness may be a better metric for assessing the quality of temporal plans than flexibility, thus reframing many popular scheduling optimization problems