Publication

An efficient algorithm for searching implicit AND/OR graphs with cycles

Journal Article (2000)

Journal

Artificial Intelligence

Pages

1-30

Volume

124

Number

1

Doc link

http://dx.doi.org/10.1016/S0004-3702(00)00063-1

File

Download the digital copy of the doc pdf document

Abstract

We present an efficient AO*-like algorithm that handles cyclic graphs without neither unfolding the cycles nor looping through them. Its top-down search strategy is based on Mahanti and Bagchi's CF, whereas its bottom-up revision process is inspired in Chakrabarti's REV*. However, important modifications have been introduced in both algorithms to attain a true integration and gain efficiency. Proofs of correctness and completeness are included. Up to our knowledge, the resulting algorithm --called CFC REV*-- is the most efficient one available for this problem.

Categories

artificial intelligence.

Author keywords

AND/OR graphs, assembly/dissassembly problems, cyclic graphs, heuristic search

Scientific reference

P. Jiménez and C. Torras. An efficient algorithm for searching implicit AND/OR graphs with cycles. Artificial Intelligence, 124(1): 1-30, 2000.