Execution Ordering in AND/OR Graphs with Failure Probabilities
DOI:
https://doi.org/10.1609/socs.v3i1.18246Keywords:
AND/OR Graph, Penalty, Atomic TaskAbstract
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.