Proceedings

Fault-Tolerant Planning under Uncertainty

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 2350-2355.

© 2013 International Joint Conferences on Artificial Intelligence

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.

  1. [Bonet and Geffner, 2003] Blai Bonet and Hector Geffner. Labeled RTDP: Improving the convergence of real-time dynamic programming. In Proceedings of the Interna- tional Conference on Automated Planning and Scheduling, pages 12-21, 2003.
  2. [Brenner and Nebel, 2009] Michael Brenner and Bernhard Nebel. Continual planning and acting in dynamic multi- agent environments. Autonomous Agents and Multi-Agent Systems, 19(3):297-331, 2009.
  3. [desJardins et al., 1999] Marie E. desJardins, Edmund H. Durfee, Charles L. Ortiz, and Michael J. Wolverton. Con- tinual planning and acting in dynamic multiagent environ- ments. AI Magazine, 20(4):13-22, 1999.
  4. [Dubash et al., 1992] Rumi M. Dubash, I-ling Yen, and Farokh B. Bastani. Fault tolerant process planning and control. In Proceedings of the Sixteenth Annual Interna- tional Computer Software and Applications Conference, pages 188-193, 1992.
  5. [Ginsberg, 1989] M. L. Ginsberg. Universal planning: an (almost) universally bad idea. AI Magazine, 10(4):40-44, 1989.
  6. [Hansen and Zilberstein, 1998] Eric A. Hansen and Shlomo Zilberstein. Heuristic search in cyclic AND/OR graphs. In Proceedings of the Fifteenth National Conference on Ar- tificial Intelligence, pages 412-418, Madison, Wisconsin, 1998.
  7. [Hansen and Zilberstein, 2001] Eric A. Hansen and Shlomo Zilberstein. LAO*: A heuristic search algorithm that finds solutions with loops. Artificial Intelligence, 129(1-2):35- 62, 2001.
  8. [Horvitz, 2001] Eric Horvitz. Principles and applications of continual computation. Artificial Intelligence, 126(1- 2):159-196, 2001.
  9. [Jensen et al., 2004] Rune M. Jensen, Manuela M. Veloso, and Randal E. Bryant. Fault tolerant planning: To- ward probabilistic uncertainty models in symbolic non- deterministic planning. In Proceedings of the Four- teenth International Conference on Automated Planning and Scheduling, pages 335-344, 2004.
  10. [Meuleau and Smith, 2003] Nicolas Meuleau and David E. Smith. Optimal limited contingency planning. In Pro- ceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pages 417-426, 2003.
  11. [Puterman, 1994] Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming.
  12. [Schoppers, 1987] Marcel J. Schoppers. Universal plans for reactive robots in unpredictable environments. In Proceed- ings of the Tenth International Joint Conference on Artifi- cial Intelligence, pages 1039-1046, 1987. IJCAI
  13. [Sutton and Barto, 1998] Richard S. Sutton and Andrew G. Barto. Introduction to Reinforcement Learning. MIT Press, Cambridge, MA, USA, 1998.
  14. [Zilberstein, 1996] Shlomo Zilberstein. Using anytime algo- rithms in intelligent systems. AI Magazine, 17(3):73-83, 1996.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards