Fault-Tolerant Planning under Uncertainty

Luis Pineda, Yi Lu, Shlomo Zilberstein, and Claudia V. Goldman. Fault-Tolerant Planning under Uncertainty. Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI), 2350-2356, Beijing, China, 2013.

Abstract

A fault represents some erroneous operation of a system that could result from an action selection error or some abnormal condition. We formally define error models that characterize the likelihood of various faults and consider the problem of fault-tolerant planning, which optimizes performance given an error model. We show that factoring the possibility of errors significantly degrades the performance of stochastic planning algorithms such as LAO*, because the number of reachable states grows dramatically. We introduce an approach to plan for a bounded number of faults and analyze its theoretical properties. When combined with a continual planning paradigm, the k-fault-tolerant planning method can produce near-optimal performance, even when the number of faults exceeds the bound. Empirical results in two challenging domains confirm the effectiveness of the approach in handling different types of runtime errors.

Bibtex entry:

@inproceedings{PLZGijcai13,
  author	= {Luis Pineda and Yi Lu and Shlomo Zilberstein and Claudia V. Goldman},
  title		= {Fault-Tolerant Planning under Uncertainty},
  booktitle     = {Proceedings of the Twenty-Third International Joint Conference on
                   Artificial Intelligence},
  year		= {2013},
  pages		= {2350-2356},
  address       = {Beijing, China},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/PLZGijcai13.html}
}

shlomo@cs.umass.edu
UMass Amherst