Algorithms for generating ordered solutions for explicit AND/OR structures

Ghosh, P. ; Sharma, A. ; Chakrabarti, P. P. ; Dasgupta, P. (2012) Algorithms for generating ordered solutions for explicit AND/OR structures Journal of Artificial Intelligence Research, 44 . pp. 275-333. ISSN 1076-9757

Full text not available from this repository.

Official URL: http://jair.org/papers/paper3576.html

Abstract

We present algorithms for generating alternative solutions for explicit acyclic AND/OR structures in non-decreasing order of cost. The proposed algorithms use a best first search technique and report the solutions using an implicit representation ordered by cost. In this paper, we present two versions of the search algorithm - (a) an initial version of the best first search algorithm, ASG, which may present one solution more than once while generating the ordered solutions, and (b) another version, LASG, which avoids the construction of the duplicate solutions. The actual solutions can be reconstructed quickly from the implicit compact representation used. We have applied the methods on a few test domains, some of them are synthetic while the others are based on well known problems including the search space of the 5-peg Tower of Hanoi problem, the matrix-chain multiplication problem and the problem of finding secondary structure of RNA. Experimental results show the efficacy of the proposed algorithms over the existing approach. Our proposed algorithms have potential use in various domains ranging from knowledge based frameworks to service composition, where the AND/OR structure is widely used for representing problems.

Item Type:Article
Source:Copyright of this article belongs to Association for the Advancement of Artificial Intelligence.
ID Code:101115
Deposited On:09 Mar 2018 10:15
Last Modified:09 Mar 2018 10:15

Repository Staff Only: item control page