Execution ordering in AND/OR graphs with failure probabilities

Ghosh, Priyankar ; Chakrabarti, P. P. ; Dasgupta, Pallab (2012) Execution ordering in AND/OR graphs with failure probabilities In: Fifth Annual Symposium on Combinatorial Search, 19-21 July 2012, Niagara Falls, Ontario, Canada.

Full text not available from this repository.

Official URL: http://www.aaai.org/ocs/index.php/SOCS/SOCS12/pape...

Related URL: http://dx.doi.org/10.1007/978-3-642-35101-3_66

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.

Item Type:Conference or Workshop Item (Paper)
Source:Copyright of this article belongs to Association for the Advancement of Artificial Intelligence.
ID Code:101616
Deposited On:12 Dec 2016 11:05
Last Modified:12 Dec 2016 11:05

Repository Staff Only: item control page