Algorithms for Generating Ordered Solutions for Explicit AND/OR Structures : Extended Abstract

1 Introduction

Traditionally AND/OR graphs [Nilsson, 1980] have been used in problem reduction search for solving complex problems, logical reasoning, theorem proving, etc. Over the last decade there has been a renewed research interest towards applying AND/OR structures in a wide variety of other areas like planning with uncertainty [Russell and Norvig, 2003], graphical models [Dechter and Mateescu, 2007], web service composition [Lang et al., 2005], solution sampling and counting [Gogate and Dechter, 2008], model based programming [Elliott, 2007], etc. However, the problem of generating alternative solutions which has been studied for ordinary graphs extensively [Nilsson, 1998; Eppstein, 1998; 1990; Chegireddy and Hamacher, 1987], has not been deeply studied for AND/OR graphs and the approaches related to these topics are often not obvious.

An ordered set of solutions of an explicit AND/OR DAG can be used to develop useful variants of the AO* algorithm. Currently in AO*, only the minimum cost solution is computed whereas several variants of the A* algorithm exist, where solutions are often sought within a factor of cost of the optimal solution. These approaches were developed to adapt the A* algorithm for using inadmissible heuristics, leveraging multiple heuristics, generating solutions quickly within bounded sub-optimality, [Ebendt andDrechsler, 2009; Chakrabarti et al., 1989; Pearl, 1984], etc. Similar techniques can be developed for AO* search if ordered set of potential solutions are made available. An initial algorithm for generating k-best solutions for AND/OR DAGs has been proposed in [Elliott, 2007] in the context of model based programming. For graphical models, which can be expressed using AND/OR structures, ordered sets of solutions are useful [Flerova and Dechter, 2011; 2010]. In the domain of service composition, the primary motivation behind providing a set of alternative solutions ordered by cost is to offer more choices, while trading off the specified cost criterion (to a limited extent) in favor of other 'unspecified' criteria (primarily from the standpoint of quality) and algorithms have been developed for generating a ranked set of solutions for the service composition problem [Shiaa et al., 2008].

∗This paper is an extended abstract of the JAIR publication [Ghosh et al., 2012]

The existing method [Elliott, 2007] (will be referred to as BU henceforth) works bottom-up by computing k-best solutions for the current node. We present a best first search algorithm, named Alternative Solution Generation (ASG) for generating an ordered set of solutions. The proposed algorithm maintains a list of candidate solutions, initially containing only the optimal solution, and iteratively generates the next solution in non-decreasing order of cost by selecting the minimum cost solution from the list. In each iteration, this minimum cost solution is used to construct another set of candidate solutions, which is again added to the current list. We present two versions of the algorithm, namely, (i) Basic ASG (will be referred to as ASG henceforth) : This version of the algorithm may construct a particular candidate solution more than once; (ii) Lazy ASG or LASG : A variant of ASG that constructs every candidate solution only once.

We use a compact representation, named signature, for storing the solutions. From the signature of a solution, the actual explicit form of that solution can be constructed through a top-down traversal of the given DAG. This representation allows the proposed algorithms to work in a top-down fashion starting from the initial optimal solution. Unlike the existing approach, our proposed algorithms are interruptible in nature, i.e., our algorithms can be stopped at any point of time during the execution and the set of ordered solutions obtained so far can be observed and subsequent solutions will be generated when the algorithms are resumed again. Moreover, if an upper limit estimate on the number of solutions required is known a priori, our algorithms can be further optimized using that estimate. We have used randomly constructed trees and DAGs as well as domains including the 5-peg Tower of Hanoi problem, the matrix-chain multiplication problem and the problem of finding the secondary structure of RNA as test domains. Experimental results show that our proposed algorithms outperform the existing approach by a large margin in terms of the memory used and time required for generating a specific number of ordered solutions for different domains.

2 Background and Proposed Algorithms

In this paper we use Gαβ = 〈V, E〉 to denote an AND/OR directed acyclic graph where V is the set of nodes, and E is the set of edges. The nodes of Gαβ with no successors are called terminal nodes. The non-terminal nodes of Gαβ are of two types - i) OR nodes and ii) AND nodes . The start (or root) node of Gαβ is denoted by vR. OR edges and AND edges are the edges that emanate from OR nodes and AND nodes respectively. We use the standard notion of solution graph, S(vq), rooted at any node vq ∈ V [Martelli and Montanari, 1973]. By a solution graph S of Gαβ we mean a solution graph with root vR.

We present our algorithms using the notion of alternating AND/OR trees which offer a succinct representation. Also, the correctness proofs are much simpler for alternating AND/OR trees. Formally, an alternating AND/OR tree, ˆ Tαβ = 〈V,E〉, is an AND/OR tree with the restriction that there is an alternation between the AND nodes and the OR nodes. Every child of an AND node is either an OR node or a terminal node, and every children of an OR node is either an AND node or a terminal node. We have shown in [Ghosh et al., 2012] that every AND/OR tree can be converted to an equivalent alternating AND/OR tree with respect to the solution space. The notion of cost is as follows. In Gαβ, every edge eqr ∈ E from node vq to node vr has a finite nonnegative cost ce(〈vq, vr〉) or ce(eqr). Similarly every node vq has a finite non-negative cost denoted by cv(vq). We use the notion of additive costs for given solution graph S [Martelli and Montanari, 1973].

Definition 2.a [Cost of a Solution Graph] For every node vq in S, C(S, vq) denotes the cost of the solution graph, S(vq). The cost of a solution S is C(S, vR) which is also denoted by C(S). We denote the optimal solution below every node vq as opt(vq). Therefore, the optimal solution of the entire AND/OR DAG Gαβ, denoted by Sopt, is opt(vR). The cost of the optimal solution rooted at every node vq in Gαβ is Copt(vq). The cost of the optimal solution Sopt of Gαβ is denoted by Copt(vR) or, alternatively, by Copt(Sopt). ⊓ ⊔

The existing method, BU [Elliott, 2007], works with the input parameter k, i.e., the number of solutions to be generated have to be known a priori. Also this method is not inherently incremental in nature, thus does not perform efficiently when the solutions are needed on demand, e.g., first initial 20 solutions are needed, then the next 10 are needed. In this case the first 20 solutions will have to be recomputed again while computing next 10 solutions, i.e., from the 21st solution to the 30th solution. We address these limitations in our proposed approach. In this paper, we present our proposed algorithms for alternating AND/OR trees for brevity. The details of the changes required for handling AND/OR DAGs are presented in detail in [Ghosh et al., 2012].

2.1 Core Concepts and Definitions

Our proposed ASG algorithm works top-down using edge markings, to generate the next best solutions from the previously generated solutions. ASG works iteratively - it generates the next best solution based on the previously generated solutions. Thus, we first compute the optimal solution, and subsequently generate other solutions from the already generated solutions. The following terminology and notions are used to describe the ASG algorithm. In the context of AND/OR trees, we use eq to denote the edge that points to the vertex vq. Our algorithm has been developed on the notion of - (a) marking of an OR edge, (b) swap option and swap operation and (b) the implicit representation of a solution. Next, we briefly describe the concepts.

Definition 2.b [Aggregated Cost] In an AND/OR DAG Gαβ, the aggregated cost, ca, for an edge eij from node vi to node vj, is defined as : ca(eij) = ce(eij) +Copt(vj). ⊓ ⊔

Definition 2.c [Vopt and Eopt] For any solution graph Sm of an AND/OR DAG Gαβ, we define a set of nodes, Vopt(Sm), and a set of OR edges, Eopt(Sm), as:

1. Vopt(Sm) = {vq ∣∣ vq in Sm and solution graph Sm(vq) is identical to the solution graph opt(vq)}
2. Eopt(Sm) = {epr ∣∣ OR edge epr in Sm, and vr ∈ Vopt(Sm)}

Clearly, for any node vq ∈ Vopt(Sm), if vq is present in Sopt, then the solution graph Sm(vq) is identical to the solution graph Sopt(vq). Also C(Sm, vq) = Copt(vq) ⊓ ⊔

Marking of an OR edge. The notion of marking an OR edge is as follows. For an OR node vq, L(vq) is the list of OR edges of vq sorted in non-decreasing order of the aggregated cost of the edges. We define δ(i,i+1) as the difference of the cost of OR edge ei and ei+1, where ei and ei+1 emanate from the same OR node vq, and ei+1 is the edge next to ei in L(vq). Consider a solution, Scur, containing the edge ei = (vq, vi), where ei ∈ Eopt(Scur). We mark ei with the cost increment which will be incurred to construct the next best solution from Scur by choosing another child of vq.

Definition 2.d [Swap Option] A swap option σij is defined as a three-tuple 〈ei, ej, δij〉 where ei and ej emanate from the same OR node vq, ej is the edge next to ei in L(vq), and δij = ca(ej) - ca(ei). Also, we say that the swap option σij belongs to the OR node vq. ⊓ ⊔

Consider the OR node vq and the sorted list L(vq). It may be observed that in L(vq) every consecutive pair of edges forms a swap option. Therefore, if there are k edges in L(vq), k-1 swap options will be formed. At node vq, these swap options are ranked according to the rank of their original edges in L(vq). We present an example of an alternating AND/OR tree in Figure 1. The terminal nodes are represented by a circle with thick outline. AND nodes are shown in the figures with their outgoing edges connected by a semi-circular curve in all the examples. The edge costs are shown by the side of each edge within an angled bracket. The cost of the terminal nodes are shown inside a box. For every non-terminal node vq, the pair of costs, cv(vq) and Copt(vq), is shown inside a rectangle. The optimal solution below every node is shown using by thick dashed edges with an arrow head. The marks corresponding to OR edges e2, e3, e9, e11, and e13 are [e2 : 5], [e3 : 1], [e9 : 3], [e11 : 4], and [e13 : 3]. Similarly, the corresponding swap options are : σ(2,3) = 〈e2, e3, 5〉, σ(3,4) = 〈e3, e4, 1〉, σ(9,10) = 〈e9, e10, 3〉, σ(11,12) = 〈e11, e12, 4〉, and σ(13,14) = 〈e13, e14, 3〉.

Definition 2.e [Swap Operation] Swap operation is defined as the application of a swap option σij = 〈ei, ej, δij〉 to a solution Sm that contains the OR edge ei in the following way:

1. Remove the subtree rooted at vi from Sm. Let the modified tree be S′m. Edge ei is the original edge of σij.
2. Add the subtree opt(vj) to S′m, which is constructed at the previous step. Let the newly constructed solution be S′′m. Edge ej is the swapped edge of σij.

Intuitively, a swap operation constructs a new solution S′m from Sm and the cost of S′m is increased by δij compared to cost of Sm. ⊓ ⊔

Our proposed algorithms use a swap option based compact representation, named signature, for storing the solutions. Intuitively, any alternative solution can be described as a set of swap operations performed on the optimal solution Sopt. It is interesting to observe that while applying an ordered sequence of swap options, 〈σ1, · · · , σk〉, the application of each swap operation creates an intermediate alternative solution. For example, when the first swap option in the sequence, σ1, is applied to the optimal solution, Sopt, a new solution, say S1, is constructed. Then, when the 2nd swap option, σ2, is applied to S1, yet another solution S2 is constructed. Let Si denote the solution obtained by applying the swap options, σ1, · · · , σi, on Sopt in this sequence.

Suppose the swap option σj belongs to a node vpj . Now it is important to observe that the application of σj on Sj-1 to construct Sj, invalidates the application of all other swap options that belong to an OR edge in the path from the root node to vpj in the solution Sj . This is because in Sj the application of any such swap option which belongs to an OR edge in the path from the root node to vpj would make the swap at vpj redundant. In fact, for each swap option σi belonging to node vpi , where 1 ≤ i ≤ j, the application of all other swap options that belong to an OR edge in the path from the root node to vpi is invalidated in the solution Sj for the same reason. This condition restricts the set of swap options that can be applied on a particular solution.

Definition 2.f [Order Relation ˆR] We define an order relation, namely ˆR, between a pair of swap options as follows.

1. If there is a path from vi to vr in ˆ Tαβ, where ei and er are OR edges, σqi and σrj are swap options, then (σqi, σrj) ∈ ˆR.
2. If σpq = 〈ep, eq, δpq〉 and σrt = 〈er, et, δrt〉 are two swap options such that vq = vr, then (σpq, σrt) ∈ ˆR.

Implicit Representation of the Solutions. We use an implicit representation for storing every solution other than the optimal one. These other solutions can be constructed from the optimal solution by applying a set of swap options to the optimal solution in the following way. If (σi, σj) ∈ ˆR, σi has to be applied before σj. Therefore, every solution is represented as a sequence ˆΣ of swap options, where σi appears before σj in ˆΣ if (σi, σj) ∈ ˆR. Intuitively the application of every swap option specifies that the swapped edge will be the part of the solution.

Definition 2.g [Signature of a Solution] The minimal sequence of swap options corresponding to a solution, Sm, is defined as the signature, Sig(Sm), of that solution. It may be noted that for the optimal solution Sopt of any alternating AND/OR tree ˆ Tαβ, Sig(Sopt) = {}, i.e., an empty sequence. It is possible to construct more than one signature for a solution, as ˆR is a partial order. It is important to observe that all different signatures for a particular solution are of equal length and the sets of swap options corresponding to these different signatures are also equal. Therefore the set of swap options corresponding to a signature is a canonical representation of the signature. Henceforth we will use the set notation for describing the signature of a solution.

Definition 2.h [Swap List] The swap list corresponding to a solution Sm, L(Sm), is the list of swap options that are applicable to Sm. Let Sig(Sm) = {σ1, · · · , σm} and ∀i, 1 ≤ i ≤ m, each swap option σi belongs to node vpi . The application of all other swap options that belong to the OR edges in the path from the root node to vpi is invalidated in the solution Sm. Hence, only the remaining swap options that are not invalidated in Sm can be applied to Sm for constructing the successor solutions of Sm.

It is important to observe that for a swap option σi, if the source edge of σi belongs to Eopt(Sm), the application is not invalidated in Sm. Hence for a solution Sm, we construct L(Sm) by restricting the swap operations only on the edges belonging to Eopt(Sm). Moreover, this condition also ensures that the cost of a newly constructed solution can be computed directly form the cost of the parent solution and the δ value of the applied swap option. To elaborate, suppose solution S′m is constructed form Sm by applying σjk. The cost of S′m can be computed directly form C(Sm) and σjk as : C(S′m) = C(Sm) + δjk if ej ∈ Eopt(Sm). ⊓ ⊔

Definition 2.i [Successors and Predecessors of a Solution] The set of successors and predecessors of a solution Sm is :

1. Succ(Sm) = {S′m ∣∣ S′m can be constructed from Sm by applying a swap option that belongs to the swap list of Sm}

2.2 ASG algorithm

In our ASG algorithm, we maintain a list, Open, which initially contains only the optimal solution Sopt. At any point of time Open contains a set of candidate solutions from which the next best solution in the non-decreasing order of cost is selected. At each iteration the minimum cost solution (Smin) in Open is removed from Open and added to another list, named, Closed. The Closed list contains the set of ordered solutions generated so far. Then the successor set of Smin is constructed and any successor solution which is not currently present in Open as well as is not already added to Closed is inserted to Open. However as a further optimization, we use a sublist of Closed, named TList, to store the relevant portion of Closed such that checking with respect to the solutions in TList is sufficient to figure out whether the successor solution is already added to Closed. It is interesting to observe that this algorithm can be interrupted at any time and the set of ordered solutions computed so far can be obtained. Also, the algorithm can be resumed if some more solutions are needed. We briefly mention the key lemma and theorems.

Definition 2.j [Solution Space DAG(SSDAG)] The solution space DAG of an AND/OR tree ˆ Tαβ is a directed acyclic graph (DAG), Gs = 〈V, E〉, where V is the set of all possible solutions of the AND/OR tree ˆ Tαβ, and E is the set of edges which is defined as:

Lemma 2.1. For any alternating AND/OR tree ˆ Tαβ, for every node of the SSDAG of ˆ Tαβ, ASG algorithm generates the solution corresponding to that node. ⊓ ⊔

Theorem 2.1. ∀Sj ∈ V, Sj is generated by ASG algorithm only once and in the non-decreasing order of costs while ties among the solutions having same costs are resolved arbitrarily in the favour of predecessor solutions. ⊓ ⊔

2.3 LASG algorithm

Although ASG algorithm adds a solution to Closed only once, a particular solution may be present in the successor set of more than one solutions. Thus it is necessary to check whether a particular solution Si is already present in Open or TList before adding Si to Open. We present a lazy version of ASG, LASG, which avoids this checking for duplicates using the notion of native swap options. Conceptually, the native swap options for a solution Sq are the swap options that become available immediately after applying σij, but were not available in the predecessor solution of Sq.

We use the notion of solution space tree which is conceptually a sub-tree of a spanning tree of the solution space DAG and the spanning trees of the solution space DAGs are complete solution space trees. In LASG, instead of using the entire swap list of a solution to construct all successors at once and then add those solutions to Open, the native swap options are used for constructing a subset of the successor set. This subset consists of only those solutions that are currently not present in Open and thus can be added to Open without comparing with the existing entries in Open. The construction of each remaining successor solution S′m of Sm and subsequently the insertion of S′m to Open is delayed until every other predecessor solution of S′m is added to Closed. In LASG, the solution space tree T s is maintained to determine when every other predecessor of S′m is added to Closed.

Theorem 2.2. The solution space tree constructed by LASG algorithm is complete. ⊓ ⊔

Complexity : We briefly compare the complexities of our proposed algorithms, ASG and LASG with the existing approach BU. For BU algorithm, the time complexity of generating the c best solutions for an AND/OR tree is O(nαβ.c. log c) and the space complexity is O(nαβ.c), where nαβ denotes the number of nodes in the AND/OR tree. Whereas, the space complexity of both ASG and LASG algorithm is O(nαβ.c). The time complexity of LASG is O(c.nαβ) which is log c factor better than BU. When an additional hash-map is used to reduce the time overhead of duplicate checking, the time complexity of ASG becomes O(nαβ + √nαβ.(c. lg c+c. lg nαβ)), which is asymptotically lower than both LASG and BU. It is important to note that, using the additional hash map does not change asymptotic space complexity of ASG, although the exact space requirement is doubled.

3 Summary of Experimental Results

We have used randomly constructed trees and DAGs as well as some well-known problem domains including the 5-peg Tower of Hanoi problem, the matrix-chain multiplication problem and the problem of finding the secondary structure of RNA as test domain. For the randomly constructed trees, LASG runs upto 20 times faster than the existing approach BU. For randomly constructed DAGs, the the running time of LASG is upto 100 times lower than the running time of BU and between ASG and BU, the running times are comparable. Also, for randomly constructed DAGs, the space requirement is upto 5 times lower on average for ASG compared to BU; LASG requires around 50% of the space required by ASG. We have also empirically shown that, if the number of solutions to be generated is known a priori, ASG and LASG can be further optimized in terms of running time.

For 5-peg tower of Hanoi, matrix-chain multiplication and secondary structure of RNA, the performances of ASG and LASG are similar. For 5-peg tower of Hanoi problem LASG runs around two times faster on average than BU. Whereas, for matrix-chain multiplication and secondary structure of RNA the running time of LASG is two orders of magnitude better on average than the running time of BU and the space requirement of LASG is one order of magnitude better on average than that of BU. Details of the experimental results as well as the analysis based on the size of Open are presented in [Ghosh et al., 2012].