Execution Ordering in AND/OR Graphs with Failure Probabilities

Abstract

In this paper we consider finding solutions for problems represented using
AND/OR graphs, which contain tasks that can fail when executed. In our  
setting each node represent an atomic task which is associated
with a failure probability and a rollback penalty. This paper
reports the following contributions - (a) an algorithm for finding the
optimal ordering of the atomic tasks in a given solution graph which minimizes
the expected penalty, (b) an algorithm for finding the optimal ordering in
the presence of user defined ordering constraints, and (c) a counter example
showing the lack of optimal substructure property for the problem of
finding the solution graph having minimum expected penalty, and a
pseudo-polynomial algorithm for finding the solution graph with minimum
expected penalty.