A Framework for Searching AND/OR Graphs with Cycles
  Search in cyclic AND/OR graphs was traditionally known to be an unsolved
problem. In the recent past several important studies have been reported in
this domain. In this paper, we have taken a fresh look at the problem. First, a
new and comprehensive theoretical framework for cyclic AND/OR graphs has been
presented, which was found missing in the recent literature. Based on this
framework, two best-first search algorithms, S1 and S2, have been developed. S1
does uninformed search and is a simple modification of the Bottom-up algorithm
by Martelli and Montanari. S2 performs a heuristically guided search and
replicates the modification in Bottom-up's successors, namely HS and AO*. Both
S1 and S2 solve the problem of searching AND/OR graphs in presence of cycles.
We then present a detailed analysis for the correctness and complexity results
of S1 and S2, using the proposed framework. We have observed through
experiments that S1 and S2 output correct results in all cases.
