Synthesis of Fault Tolerant Plans for Non-Deterministic Domains

Rune Møller Jensen, Manuela M. Veloso, Randal E. Bryant

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


Non-determinism is often caused by infrequent errors that make otherwise deterministic actions fail. In this paper, we introduce fault tolerant planning to address this problem. An n-fault tolerant plan is guaranteed to recover from up to errors occurring during its execution. We show how optimal n-fault tolerant plans can be generated via the strong universal planning algorithm. This algorithm uses an implicit search technique based on the reduced Ordered Binary Decision Diagram (OBDD) that is particularly well suited for non-deterministic planning and has outperformed most alternative approaches. However, the OBDDs used to represent the blind backward search of the strong algorithm often blow up. A heuristic version of the algorithm has recently been proposed but is incapable of dynamically guiding the recovery part of the plan toward error states. To address this problem, we introduce two specialized algorithms 1-FTP (blind) and 1-GFTP (guided) for 1-fault tolerant planning that decouples the synthesis of the recovery and nonrecovery part of the plan. Our experimental evaluation includes 7 domains of which 3 are significant real-world cases. It verifies that 1-GFTP efficiently can handle non-local fault states and demonstrates that it due to this property can outperform guided fault tolerant planning via strong planning. In addition, 1-FTP often outperforms strong planning due to an aggressive expansion strategy of the recovery plan.
Original languageEnglish
Title of host publication Proceedings of the 13th International Conference on Automated Planning and Scheduling (ICAPS-03) Workshop on Planning under Uncertainty and Incomplete Information
Number of pages10
PublisherAAAI Press
Publication date2003
Publication statusPublished - 2003


Dive into the research topics of 'Synthesis of Fault Tolerant Plans for Non-Deterministic Domains'. Together they form a unique fingerprint.

Cite this