Depth-First Memory-Limited AND/OR Search and Unsolvability in Cyclic Search Spaces

1 Introduction

When cost-optimal heuristic search cannot memorize the examined search space effectively, depth-first search (DFS) is often preferred to best-first search (BFS), e.g., [Korf, 1985]. Depth-first memory-limited search (DFMLS) combines DFS with a transposition table (TT). DFMLS thus caches previous search results and reuses them for the nodes revisited during search [Plaat et al., 1996; Reinefeld and Marsland, 1994]. When the TT is full and new results need to be saved, existing TT entries are replaced with new entries [Nagai, 1999].

Bonet and Geffner's Bounded Learning DFS (BLDFS) algorithm (2005a; 2005b) keeps revising lowerbounds of the optimal solution by a series of depth-first searches limited by a threshold that is explicitly set at the root, until finding the optimal solution. During search, the revised lowerbounds are saved in the TT. BLDFS often outperforms BFS algorithms such as AO* [Nilsson, 1980] and CFCREV ∗ [Jim´enez and Torras, 2000]. Although BLDFS can be regarded as DFMLS, its theoretical properties assume monotonic lowerbounds in the TT [Bonet and Geffner, 2005b]: the TT requires unlimited capacity with consistent heuristics in use. This assumption does not hold when the search space is larger than the TT and TT entries need to be replaced. In this case, the effect is equivalent to using an inconsistent heuristic.

RBFAOO [Kishimoto and Marinescu, 2014] is a depth-first memory-limited AND/OR search algorithm based on ideas of Recursive Best-First Search (RBFS) [Korf, 1993] with the TT. It was shown to be complete (with respect to solvable or unsolvable instances) if the search space is a finite DAG.

We focus on optimal DFMLS on finite cyclic AND/OR search spaces where a solution must be cycle-free, assuming an additive state model as well as inconsistent heuristics and/or a limited size TT. First, we outline new challenging issues that arise under these relaxed assumptions, such as returning suboptimal solutions due to the TT and cycles. These issues are not considered in the previous work of Bonet and Geffner (2005a; 2005b) and Kishimoto and Marinescu (2014). Akagi et al. (2010) raise similar issues but analyzed them for OR search. We then develop a generic approach to prove unsolvability with cycles, and apply it to RBFAOO and a BLDFS variant. Eriksson et al. (2017; 2018a; 2018b) have studied proving unsolvability, but their approach is specific to OR search.

Furthermore, we present theoretical properties of our approach and show that, if a solution exists, then an optimal solution cost can eventually be found with limited memory. In addition, our approach can also prove the unsolvability of some instances in a cyclic search space but, in some other unsolvable instances, the technique may fail due to an infinite loop. While Akagi et al. (2010) consider the same assumptions, their theoretical results are for IDA*+TT, which is OR search. Our new theoretical results hold for two algorithms of different behaviors in more general scenarios than those of Akagi et al. (2010) and Bonet and Geffner (2005a; 2005b). Moreover, as a corollary, our analysis additionally includes RBFS+TT, which is a different OR search compared to IDA*+TT.

Finally, we validate our theoretical analysis with experiments in domain-independent nondeterministic planning, showing that there are instances that require our approach to prove unsolvability, and that the ability to find optimal solution costs is preserved for solvable instances.

2 Preliminaries

We consider a state model with fully-observable states and nondeterministic actions. A tuple 〈S,A, s0, ST 〉 defines the problem space, where S is a finite set of states, so ∈ S is an initial state, A is a finite set of actions, and ST ⊆ S is a set of terminal states. Unlike Bonet and Geffner (2005a), we allow the case where ST is empty, for instances with no solution. A(s) ⊆ A denotes a set of applicable actions to a non-terminal state s. Each action a ∈ A(s) returns a set of successor states denoted by Fs,a ⊆ S. If Fs,a has more than one state, action a is nondeterministic. Otherwise, a is deterministic. The cost of a transition from state s with action a, denoted by c(s, a), is assumed c(s, a) > 0 and discretized to an integer for any a and s. For simplicity, the costs for a terminal state (aka a goal in [Bonet and Geffner, 2005a]) and a deadend state are 0 and ∞, respectively. Our results can easily be generalized for terminal states with non-negative costs.

Similarly to Bonet and Geffner (2005a), we map this state model into an AND/OR graph G. An OR node is labeled by a state s. An AND node is labeled by the set of states reached by an action a, namely Fs,a. The root of G is an OR node labeled by the initial state s0. The children of an OR node s are AND nodes corresponding to the applicable actions A(s) in state s, and the children of an AND node Fs,a are the OR nodes corresponding to the states in Fs,a. The edge cost from OR node s to AND node Fs,a is c(a, s), while the edge cost from an AND node to an OR node is 0.

Definition 1 (solution tree). Given an AND/OR graph G, a solution tree ST is a subtree of G such that: (1) the root node of ST is the initial state s0, (2) for each internal OR node n in ST, one of n's children is in ST, (3) for each internal AND node n in ST , all of n's children are in ST , and (4) all tip nodes in ST are terminal nodes (goals).

While Bonet and Geffner (2005a) introduce BLDFS for the max state model (MAX), we consider here the additive state model (ADD) of Bonet and Geffner (2005a) where the cost of a solution tree ST is defined as the sum of the edge costs in ST . An optimal solution has a minimal cost.

We can support the MAX with small changes. Yet, focusing on the ADD in our setting is essential, because RBFAOO and BLDFS face new challenges discussed in Section 3.

Each node n in ST is associated with a value V (n) capturing the optimal solution cost of the subtree rooted at n. V (n) can be computed recursively based on the values of n's successors: OR nodes by minimization, AND nodes by summation. The ADD model has applications such as the (dis)assembly domain [Jim´enez and Torras, 2000] and web service composition [Liang and Su, 2005]. Chemical synthesis planning [Heifets and Jurisica, 2012] is a remarkable example, when the objective is minimizing the reaction cost.

Path p = s0, a0 → · · · → sk-1, ak-1 → sk indicates a path from the initial state s0 to an OR node sk by a sequence of actions a0, · · · , ak-1. Path p = s0, a0 → · · · → sk, ak leads to an AND node Fsk,ak from s0 by a sequence of actions a0, · · · , ak. Path p + a indicates a path that extends p with action a leading to an AND node Fn,a, where n is an OR node reached by path p. Analogously, p + s extends path p by adding an OR child of an AND node reached by path p.

A cyclic path has si = sj for some i ̸= j. The search space can contain cyclic paths, but a solution tree has no cyclic path. If no cycle-free solution tree exists, the solution cost is ∞.

Since we solve a minimization task, the algorithms we present attempt to improve a lowerbound L of the optimal solution cost C ∗ .

When L = C ∗ , the solution is proven optimal. To prove unsolvability, it is sufficient to ensure that L > U, where U is an upperbound of the optimal solution. While computing good U values is an important topic of research, in this paper, we assume that such U cannot be calculated, and the algorithms need to explicitly prove L = ∞.

We say that an algorithm has an infinite loop if it runs forever without finding C ∗ or proving L = ∞. We assume that ∞- k < ∞ holds, where k is a small number. In the actual implementation, a large finite number is often used to represent ∞. We assume that V (n) ≪ ∞- k holds if an optimal solution exists, and that no algorithm can gradually increase L to ∞- k in finite time if no solution exists.

RBFAOO and BLDFS

These algorithms maintain at each node n a lowerbound q(n) (called a q-value) on V (n). During search, they improve and cache in the TT q(n) which is calculated by backing up the qvalues of n's children, until proving q(r) = V (r) at the root r or q(r) = ∞ (i.e., no solution). For an admissible heuristic h, q(n) is computed as:

1. q(n) = 0, if n is a terminal OR node.
2. q(n) = h(n), if n is a non-terminal tip node.
3. q(n) =mina∈A(n)(c(n, a)+q(Fn,a)), if n is an internal OR node and Fn,a is an AND child of n.
4. q(Fn,a) = ∑s∈Fn,a q(s), if Fn,a is an internal AND node and s is an OR child of Fn,a.

Let th(n) be a threshold at node n. Both algorithms examine a subtree rooted at node n in a depth-first manner until th(n) < q(n) holds or n is solved optimally (termination condition). RBFAOO employs a local threshold controlling mechanism that initially sets th(r) = ∞- 1 at the root r. It updates q(n) at node n using q-values of n's children. If a termination condition holds, it backtracks to n's parent. Otherwise, it selects a child to examine further. For q′ (Fn,a) = c(n, a) + q(Fn,a), let q′ (Fn,a1 ) and q′ (Fn,a2 ) be the smallest and second smallest values among the list of values of n's children. If n has only one child, q′ (Fn,a2 ) = ∞. RBFAOO selects a child as follows:

• At an OR node n, select Fn,a1 with a new threshold th(Fn,a1 ) = min(th(n), q′ (Fn,a2 )) - c(n, a1).
• At an AND node Fn,a, select any unsolved child s with a new threshold th(s) = th(Fn,a) - q(Fn,a) + q(s).

BLDFS employs a global threshold controlling scheme that gradually increases the threshold at the root. In each iteration, it sets th(r) = q(r) at the root r. At an OR node n, if a child Fn,a holds q′ (Fn,a) ≤ th(n), it examines Fn,a with th(Fn,a) = th(n) - c(n, a). At an AND node, it updates the threshold in the same way as RBFAOO, which is also described in [Bonet and Geffner, 2005a].

3 Challenges under Relaxed Assumptions

In the ADD model with a consistent heuristic and unlimited TT capacity, BLDFS can always return an optimal solution in finite time if one exists in the finite cyclic search space. This property is based on the fact that BLDFS does not need to generate an action leading to a repeated state, since it never enters into a cycle [Bonet and Geffner, 2005b]. However, when using an inconsistent heuristic, even with an unlimited TT, BLDFS may enter into a cycle. If the TT is updated without carefully considering that repeated state, BLDFS may lead to a suboptimal solution.

Example with Inconsistent Heuristic

In the example shown in Figure 1(left), both BLDFS and RBFAOO enter into a cycle when using an admissible, inconsistent heuristic whose values are shown in the figure. The optimal solution opt is A → C → D → B → E → F with solution cost 54. BLDFS sets th(A) = h(A) = 50. If it does not detect a repeated state, th(A) is large enough to reach B again via path p1 = A → B →D → B. In case of RBFAOO, th(B) = q′ (C) - c(A, A → B) = 40. As in the case of BLDFS, th(B) is large enough to revisit B via p1.

Now assume that BLDFS generates no action forming a cycle. Then, it incorrectly returns a suboptimal solution sopt = A → B → E → F with cost 62, since it searches in the following order: (1) Reach D via p2 = A → B → D; (2) No action is available at D, since D → B is not generated since a cycle is formed. The value of ∞ (i.e., deadend) is mistakenly saved in the TT for D; (3) Reach C via A → C, and backup the value of ∞ of D to C; (4) The only reachable path to a goal is now sopt. RBFAOO suffers from the same issue. It reaches D via p2 first and does not generate D → B.

The pathmax heuristic does not resolve the issue in our example, since it is still an inconsistent heuristic [Holte, 2010].

In the ADD model, Bonet and Geffner (2005b) ensure an algorithmic equivalence between LDFS with no explicit threshold (i.e., use q(n) as a threshold for node n) and BLDFS with an explicit threshold. However, the equivalence no longer holds in our relaxed setting. For example, assume that an OR node n has one AND node m that has two successors s1 and s2, where h(n) > c(n, m)+h(s1)+h(s2) due to an inconsistent heuristic. Then, LDFS has an issue of setting up a threshold that is large enough to strictly improve q(n) or solve n after LDFS finishes examining s1 or s2. Hence, the explicit threshold of BLDFS is necessary even in the ADD.

Example with Consistent Heuristic and Limited-Size TTs

If existing TT entries are overwritten with the lowerbounds of new nodes, the heuristic estimates in the TT become inconsistent. This is equivalent to using an inconsistent heuristic.

We show an example only for RBFAOO, since an example for BLDFS can be constructed analogously. The heuristic shown in Figure 1(left) becomes consistent by replacing h(A) = h(C) = 50 with h(A) = h(C) = 0. In this case, RBFAOO first reaches D via p3 = A → C → D → B, and only generates action B → E (i.e., B → D forms a cycle). Then, RBFAOO backtracks to A and stores improved q-values, i.e., q(B) = 51, q(D) = 52, and q(C) = 53, based on h(E) = 50. Next, it examines B. Assume now that q(B) and q(D) are removed from the TT before B is examined. Then, it reaches D via p2, since th(B) = q′ (C) - c(A, A → B) = 43 is large enough. It stores the value of ∞ in the TT entry of D since D → B forms a cycle. If the TT never removes D, RBFAOO cannot reach a goal via opt.

One straightforward way to be able to return an optimal solution with Figure 1 (left) is to perform so-called unfolding cycles (keep examining a node), even if it encounters a repeated state. While this approach returns an optimal solution if one exists, it cannot prove unsolvability of a problem instance that involves cycles such as Figure 1(right).

4 Boosting Ability to Prove Unsolvability

We introduce a generic approach to proving unsolvability, even for limited TTs and inconsistent heuristics, and combine it with RBFAOO and BLDFS with an ADD model. The heuristic h must be admissible, but can be inconsistent.

Generic Principles

The suboptimal solution returned in the example from Section 3 is caused by saving in the TT a value of ∞ calculated by a cycle which holds only for that path. We bypass this incorrectness by extending TTs to separately save two types of values: q-values and r-values.

Since the q-value of a node n, q(n), described in Section 2, is a path-independent lowerbound on the node's cost, it is retrieved at n via any path. An r-value for a node n reached via a path p, r(n, p), is a path-specific lowerbound. The value r(n, p) is retrieved only when n is reached by path p. Since r-values take into account that a repeated state is a deadend, r(n, p) is computed as follows:

1. r(n, p) = 0, if n is a terminal OR node and p does not form a cycle.
2. r(n, p) =∞, if n is an OR node and p forms a cycle.
3. r(n, p) = h(n), if n is a non-terminal tip node.
4. r(n, p) = mina∈A(n)(c(n, a) + r(Fn,a, p + a)), if n is an internal OR node and Fn,a is an AND child of n.
5. r(Fn,a, p) = ∑s∈Fn,a r(s, p + s), if Fn,a is an internal AND node and s is an OR child of Fn,a.

When a search reaches a node n via a path p, and further explores the space rooted at n, it uses a threshold to control the search underneath. Both q(n) and r(n, p) get updated based on the search results. Because of the definition of the state model, a repeated node is always an OR node. If the search expands n and generates a child ch that belongs to path p, then ch is a repeated node. It is a deadend along this path, and not expanded further along this path. When updating q(n) and r(n, p), we set r(ch, p+a+ch) = ∞. However, computing q(n) uses q(ch), as shown in Section 2, as q is a path-independent estimation.

When n is reached via a new path p′ , q(n) is used to reduce duplicate search effort. In addition, since q(n) is more conservative than r(n, p′ ), we set r(n, p′ ) = q(n) if r(n, p′ ) <

Algorithm 1 RBFAOOr: RBFAOO with our approach

Require: Root node root

• 1: root.th =∞-1
• 2: r = RBFAOOSearch(root)
• 3: return r

q(n). This update is not uncommon, since r(n, p′ ) = h(n) when n is reached via p′ for the first time.

Threshold for r-values. Typical DFMLS updates thresholds based on the q-value. In contrast, we adjust a threshold based on the r-value. The node to examine is selected by the smallest r-value at each OR node, and the threshold is updated to observe an improvement of the r-value as an indication of search progress. While Akagi et al. (2010) use this idea, they apply it only to IDA*+TT, and do not store r-values in the TT.

Reuse of proof trees. If a node n is optimally solved, then typical DFMLS marks n as solved and saves it in the TT. When n is reached via any path, n is regarded as solved without re-examining the search space rooted at n. However, care must be taken in this approach to ensure that no implicit cycles are created [Campbell, 1985; Kishimoto and M¨uller, 2004]. For example, assume a node n is saved in the TT as solved, and n's solution tree has a node c. If c is removed from the TT, n is reached by a path p, and p contains c, then regarding n via p as solved is not correct due to a cyclic path c · · · → n · · · → c. We avoid implicit cycles by checking both q-values and r-values when marking a node as solved. Assume that a node n via path p is solved or proven a deadend. If q(n) = r(n, p), the TT entry for q(n) marks the flag as solved. This is used as a path-independent solution. If q(n) ̸= r(n, p), the TT entry for r(n, p) marks the flag as solved, which is reused only for n via path p. Theorem 4 in Section 5 ensures the correctness.

Space saving in the TT. The TT is typically implemented as a hash table, and has a fixed number of entries to store information on nodes. Compared to the TTs which take only q-values, our approach manages q- and r-values of each node. To save the TT entries, if r(n, p) = q(n), only q(n) is saved. Otherwise, in addition to the TT entry for q(n), another TT entry is used to save r(n, p). When r(n, p) is retrieved but no information is available except q(n), q(n) is used for r(n, p).

Combination with RBFAOO

Algorithms 1-4 show a combination of our approach with RBFAOO, denoted by RBFAOOr. We omit the overestimation technique [Kishimoto and Marinescu, 2014], as automatically setting an efficient overestimation parameter in cyclic search spaces remains open. The essential differences from original RBFAOO, using the r-values instead of q-values, are highlighted in bold. Algorithm 2 focuses on searching for a solution. Method FromTT (Algorithms 3 and 4) retrieves from TT: r(n, p) where p is a path to reach n, q(n), and a flag whether n is solved. If p forms a cycle due to n, then set r(n, p) = ∞. If the TT has no entry for q(n) or r(n, p), use h(n). Also, FromTT returns q(n) for r(n, p) if r(n, p) < q(n).

Node n is a 3-field tuple: a threshold th, a flag slvd and a path path to reach n. The flag is true if n is solved or proven

Algorithm 2 RBFAOOSearch with our approach

Require: Node n

• 1: if (HasNoChildren(n)) then 2: q = Evaluate(n) //Terminal node/deadend 3: SaveInTT(n, q, q) //Store search result 4: return q 5: GenerateChildren(n) 6: if (n is an OR node) then 7: loop 8: (Fn,a, r, r2, q) = BestChild(n) 9: SaveInTT(n, r, q) 10: if (n.th < r ∨ n.slvd) then 11: break 12: Fn,a.th =min(n.th, r2) - c(n, a); Fn,a.path = n.path + a 13: RBFAOOSearch(Fn,a) 14: else 15: loop 16: (r, q) = Sum(n) //n is an AND node 17: SaveInTT(n, r, q) 18: if (n.th < r ∨ n.slvd) then 19: break 20: (s, rs) = UnsolvedChild(n) 21: s.th = n.th - (r - rs); s.path = n.path + s 22: RBFAOOSearch(s) 23: return r

Algorithm 3 BestChild

Require: Node n

• 1: n.slvd = ⊥ (⊥ stands for false)
• 2: r = r2 = q =∞; chbest = undefined
• 3: for (each child Fn,ai of n) do
• 4: (rchi , qchi , fchi ) = FromTT(Fn,ai )
• 5: qchi = c(n, ai)+qchi ; rchi = c(n, ai) + rchi ; q = min(q, qchi )
• 6: if (rchi < r ∨ (r = rchi ∧ ¬n.slvd)) then
• 7: r2 = r; r = rchi ; chbest = Fn,ai ; n.slvd = fchi
• 8: else if (rchi < r2) then
• 9: r2 = rchi
• 10: return (chbest, r, r2, q)

unsolvable. A node n also has state information, to enable to retrieve q(n) from the TT. SaveInCache saves in the TT an r(n, p), q(n), and whether n via p is solved.

Examining a node n includes a check whether n has children or not. If not (lines 1-4 in Algorithm 2), the Evaluate method sets n.slvd = ⊤ and checks if n is a terminal or a path-independent deadend (i.e., deadend unrelated to cycles). The q-value is set to 0 for a terminal node and to ∞ for a deadend, and so is the r-value. These values are saved in the TT. Lines 7-13 and 15-22 show respectively the cases when n is an OR node or an AND node, which have similar steps:

• Update the q-value and r-value for n, based on the values of the children (see lines 8 and 16, and Algorithms 3-4).
• Perform the backtracking test (lines 10-11 and 18-19). RBFAOOr backtracks to n's parent if either n.th < r(n, p) or n.slvd = ⊤ holds.
• Select a child s (lines 8 and 20) otherwise. At OR nodes, s = Fn,a is the child with the smallest r-value among unsolved children (method BestChild). At AND nodes,

Algorithm 4 Sum

Require: Node n

1: n.slvd = ⊤ (⊤ stands for true) 2: r = q = 0 3: for (each child chi of n) do 4: (rchi , qchi , fchi ) = FromTT(chi) 5: q = q + qchi ; r = r + rchi ; n.slvd = n.slvd ∧ fchi 6: n.slvd = n.slvd ∨ r =∞

• 7: return (r, q)

Algorithm 5 BLDFSr: BLDFS variant with our approach

Require: Root node root

• 1: root.slvd = ⊥; root.r = h(n)
• 2: while ¬root.slvd do
• 3: root.th = root.r
• 4: BLDFSDriver(root)
• 5: return root.r

choose any unsolved child s. Then, update th(s) (lines 12 and 21), and recursively examine s (lines 13 and 22).

A small yet efficient change to the original RBFAOO is to store q(n) in the TT, immediately after it is updated (lines 9 and 17). This is necessary to quickly back-propagate a larger q-value involving repeated states. Bonet and Geffner (2006) use a similar idea for an MDP version of LDFS.

RBFAOOr correctly handles the example shown in Figure 1 left. RBFAOOr reaches B, via A → B, updates q(B) = min(1 + h(E), 1 + h(D)) = 1, then reaches D via p1 = A → B → D. It generates a cycle p1 + B, and stores r(D, p1) = ∞ due to the cycle. On the other hand, it sets q(D) = 1 + q(B) = 2. It updates r(B,A → B) = min(1 + r(D, p1), 1 + r(E,A → B → E)) = 51, and q(B) = min(1 + q(D), 1 + q(E)) = 3. It then selects C and reaches D via p2 = A → C → D. Since r(D, p2) = 4, which is different from r(D, p1) = ∞, it does not regard D via this path as unsolved. Therefore, it reaches B via p2 +B, eventually leading to optimal solution p2 + B + E + F .

Combination with Bounded LDFS Variant

BLDFS with our approach, denoted BLDFSr, controls its threshold by r-values, based on the approach of Bonet and Geffner (2005a) for the ADD model. While RBFAOOr and BLDFSr share the same principles, BLDFSr examines the space with a global threshold controlling scheme.

Let th(n, p) be a threshold for a node n reached via path p, and rt be the root. In each iteration, BLDFSr starts examining the search space with th(rt, rt) = r(rt, rt), and examines n via p as long as r(n, p) ≤ th(n, p). At the start of search, th(rt, rt) = h(rt), since r(rt, rt) = h(rt).

At each internal node, BLDFSr selects a child in the same way as described in Section 2 except that it uses the r-values:

• At an OR node n via path p, for a child Fn,a via path pF = p + a, if c(n, a) + r(Fn,a, pF ) ≤ th(n, p) holds, examine Fn,a with th(Fn,a, pF ) = th(n, p) - c(n, a).
• At an AND node Fn,a via path pF , select any unsolved child s with a new threshold th(s, ps) = th(Fn,a, pF )- r(Fn,a, pF ) + r(s, ps), where ps = pF + s.

Algorithm 6 BLDFS Driver with our approach

Require: Node n

1: if (HasNoChildren(n)) then 2: q = Evaluate(n) //Terminal node/deadend 3: SaveInTT(n, q, q) //Store search results 4: n.r = n.q = q; n.slvd = ⊤ 5: return 6: GenerateChildren(n) 7: if (n is an OR node) then 8: slvd = ⊥; r = q =∞ 9: for (each child chi = Fn,ai ) do 10: (rchi , qchi , fchi ) = FromTT(chi) 11: qchi = c(n, ai) + qchi ; rchi = c(n, ai) + rchi 12: if (n.th < rchi ) then 13: q = min(q, qchi ); r = min(r, rchi ) 14: else if (fchi ) then 15: slvd = ⊤; //Solution within the threshold 16: q = min(q, qchi ); r = rchi 17: //Update the threshold with this upperbound 18: n.th = rchi - 1 19: else 20: chi.th = n.th - c(n, ai) 21: chi.path = n.path + ai 22: BLDFSDriver(chi) 23: q = min(q, c(n, ai) + chi.q); 24: r = min(r, c(n, ai) + chi.r) 25: if (chi.slvd ∧ chi.r ≤ chi.th) then 26: slvd = ⊤; //Solution within the threshold 27: //Update the threshold with this upperbound 28: n.th = c(n, ai) + chi.r - 1 29: n.r = r; n.q = q; n.slvd = slvd ∨n.r =∞ 30: else 31: //n is an AND node 32: for (each child chi) do 33: (r, q) = Sum(n, chi) 34: if (n.th < r) then 35: break 36: if (¬chi.slvd) then 37: chi.th = n.th - (r - chi.r); 38: chi.path = n.path + chi 39: BLDFSDriver(chi) 40: SaveInTT(n, r, q)

The q- and r- values are back-propagated to the root in the same way as RBFAOOr. For theoretical analysis, we modify slightly the original BLDFS. If a solution is found at node n, our BLDFS variant delays to back up the solved flag of ⊤ to n's parent, until the solution cost at n is proven optimal within the threshold. It is when BLDFS marks the solved flag at the root as solved that the optimal solution cost is proven at the root. Theoretical analysis with the original BLDFS under our relaxed assumptions is left as future work.

Algorithms 5-6 show the pseudocode of BLDFSr, which is a combination of BLDFS with our approach. We use notations that are familiar in the heuristic search community. To explain in detail how r-values and q-values are managed, our pseudocode is represented in a more detail than in the work of Bonet and Geffner (2005a; 2005b). The essential differences from original BLDFS are highlighted in bold. Node n includes the threshold th, called the bound in [Bonet and Geffner, 2005a]. In addition, n contains r and q, an r-value and a q-value stored after n is examined, and a path path to n from the root. The Sum method in Algorithm 4 is extended to receive a child si and sets si.slvd, indicating if si is marked as solved in the TT. Sum also updates n.r, n.q and n.slvd.

5 Theoretical Properties

We define the notion of memory requirement linear in the search depth and the branching factor along the path.

Definition 2. Given a search problem and an amount of memory available, we say that the reasonable memory requirement is satisfied if, for any path that could be explored in the search, the memory is sufficient to store all nodes along the current paths, together with all their siblings.

If b is the maximum branching factor, and d is the maximum depth of a path explored in the problem at hand, we need at least O(bd) memory, as discussed in [Korf, 1993].

We prove theoretical properties about our approach combined with RBFAOO and our BLDFS variant that require only reasonable memory, denoted by RBFAOOr and BLDFSr, respectively. Our results ensure that our approach can be enhanced with a TT that has any strategies to replace the TT entries of any nodes previously examined, unless these TT entries are for the nodes/their siblings of the path currently examined. For example, assume that a search path p1 changes to a new one p2. Let n be a node on p1 that is neither on p2 nor any of the siblings of the nodes on p2. Then, the q- and rvalues for n can be safely removed from the TT.

The reasonable memory requirement is close to the theoretically minimum memory requirement to return an optimal solution cost. Note that the size of the solution tree is needed as a memory requirement to return a solution tree.

Let C(n, p) be an optimal solution cost for node n via path p, Tq(n) be q(n) in the TT, and Tr(n, p) be r(n, p) in the TT. If no result is saved, Tq(n) = h(n) where h is an admissible heuristic. So is Tr(n, p), but if p forms a cycle, then Tr(n, p) = ∞. Since Tr(n, p) is increased to Tq(n) as discussed in Section 4, clearly Tq(n) ≤ Tr(n, p) holds.

Lemma 1. Tr(n, p) always has admissible values for any path p leading to node n, i.e., Tr(n, p) ≤ C(n, p).

Theorem 2 (Correctness). The solution cost returned by RBFAOOr/BLDFSr is always optimal.

Lemma 3. Assume that RBFAOOr/BLDFSr marks a node n as always solved, i.e., n via path p is solved and Tq(n) = Tr(n, p) holds. Then, Tq(n) = C(n, n) holds, where C(n, n) is the optimal solution cost of the subtree rooted at n.

Theorem 4 guarantees that an optimal solution cost at n can be transposed from one path to another (see Section 4).

Theorem 4. Assume that node n via path p is solved and Tq(n) = Tr(n, p). Then, marking n as solved via any path does not affect the optimal solution cost.

Proof. Let s0 be the root. We prove the theorem by showing that a node n marked as always solved is not a part of the optimal solution cost at s0, if Tq(n) causes an implicit cycle. In this case, Tq(n) merely prunes away duplicate search rooted at n, even if marked as solved.

Assume that n via p is marked as always solved. Let ST be the (optimal) solution tree rooted at n and Tq(n) = C(n, n).

By Lemma 3 ST has no cyclic path, since the solution cost at each internal OR node m in ST is C(m, m) and c(m, a) > 0.

Let Q(n, p) be the set of OR nodes on the non-cyclic path p from s0 to node n, and P(n, p) = Q(n, p)\{n}. The correctness of the theorem is ensured as follows: (1) If s ̸∈ ST for every s ∈ P(n, p), C(n, p) = C(n, n). No cycle is created from s0 to reach any node in ST . (2) Otherwise, a node s ∈ P (n, p) may be in ST . That is, ST cannot be used to calculate C(n, p), since s creates a cycle. Let m ∈ P(n, p) be the closest node to s0 on p which creates a cycle in ST. Let pm be the prefix of p from s0 to m. Since m is included in ST and c(n, a) > 0 for a ∈ A(n), C(m, m) < Tq(n) = C(n, n) holds. In addition, no node in P(m, pm) creates a cycle in ST. Therefore, C(m, pm) = C(m,m) < Tq(n), indicating that Tq(n) is never a part of the optimal solution at s0.

We prove the admissibility of BLDFSr with more relaxed assumptions than [Bonet and Geffner, 2005b].

Lemma 5. If Algorithm6 (BLDFSDriver) starts with s0.th = b ≪ ∞ at the root s0, then it terminates in finite time with either s0.r > b or s0.slvd = ⊤.

Theorem 6 (Admissibility). BLDFSr finds an optimal solution cost in finite time, if one exists in the finite search space.

Proof sketch. If s0.th ≥ C(s0, s0), BLDFSDriver returns an optimal solution cost C(s0, s0) in finite time, since: (1) Theorems 2 and 4 ensure solution optimality. (2) Each node n in the optimal solution tree is examined, which is easily proven by induction on the number of chains of the recursive calls.

If s.th < C(s0, s0), by Lemma 5, BLDFSDriver strictly increases s0.th in finite time, since BLDFSDriver cannot mark s0 as solved (see line 12 in BLDFSDriver). Since C(s0, s0) ≪ ∞, in a finite number of iterations, BLDFSr sets s0.th = b ≥ C(s0, s0), enabling to optimally solve any solvable instance in finite time.

The results in [Kishimoto and Marinescu, 2014] hold only for finite DAGs (i.e., no cycles involved). On the other hand, RBFAOOr focuses on finite cyclic spaces.

Lemma 7. Assume that RBFAOOr examines a node n via path p with th(n) = b ≪∞. Then, RBFAOOr backtracks to n in finite time with either Tr(n, p) > b and/or n is marked as solved.

Theorem 8 (Admissibility). RBFAOOr finds an optimal solution cost in finite time, if one exists in the finite search space.

Proof sketch. Let s0 be the root and ST be an optimal solution tree rooted at s0. If no path exists which makes RBFAOOr deviate from ST (i.e., ST is the whole search space), since C(s0, s0) ≪ th(s0) = ∞- 1, RBFAOOr finds an optimal solution cost in finite time. This is easily verified by the fact that (1) RBFAOOr requires only reasonable memory and (2) Tr(n, p) ≤ C(n, p) ≪ th(n) = ∞ - k for each n ∈ ST, where k is a small number. This th(n) is large enough to cover all terminal nodes in ST. Otherwise, let n via path p be the first OR node in ST at which RBFAOOr generates two children Fn,a1 and Fn,a2 , where Fn,a1 ∈ ST but Fn,a2 ̸∈ ST. Here, we show only the case with two children, since more general cases are proven in an analogous way. Fn,a2 may or may not lead to another optimal solution, but because of the optimality of ST , C(n, p) = c(n, a1) + C(Fn,a1 , pa1 ) ≤ c(n, a2) + C(Fn,a2 , pa2 ) holds, where pa = p+a . RBFAOOr reaches n with th(n) = ∞-k where k is a small number.

Tr(Fn,a2 ) = ∞ means that RBFAOOr cannot deviate from ST. Hence, we consider the case where Tr(Fn,a2 ) ≪ ∞-k, i.e., c(n, a2)+Tr(Fn,a2 ) ≪∞-k. Since Fn,a1 has an optimal solution, c(n, a1) + Tr(Fn,a1 , pa1 ) ≤ C(n, p) ≪ ∞-k holds (see Lemma 1 as well). Therefore, the threshold t set to examine Fn,a1 and Fn,a2 always satisfies t ≪∞-k.

If RBFAOOr examines Fn,a1 with t < C(n, p) - c(n, a1) = C(Fn,a1 , pa1 ), by Lemmas 7, RBFAOOr backtracks to n in finite time. It holds that Tr(Fn,a1 , pa1 ) is strictly increased, or/and Fn,a1 is solved. If Fn,a1 is solved but v = c(n, a1)+C(Fn,a1 , pa1 ) > c(n, a2)+Tr(Fn,a2 , pa2 ) still holds, Fn,a2 is examined with th(Fn,a2 ) = v - c(n, a2) ≪ ∞. By Lemma 7, this step completes in finite time, proving that a1 leads to an optimal solution cost.

Analogously, if RBFAOOr examines Fn,a2 with t < C(n, p) - c(n, a2), by Lemma 7, RBFAOOr backtracks to n in finite time and Tr(Fn,a2 , pa2 ) is strictly increased, or/and Fn,a2 is solved. If Fn,a2 is solved, Tr(Fn,a2 , pa2 ) = C(Fn,a2 , pa2 ) ≥ C(n, p) - c(n, a2).

Since RBFAOOr requires only reasonable memory, it remembers Tr(Fn,a1 , pa1 ) and Tr(Fn,a2 , pa2 ). By Lemmas 1 and 7, even if Fn,a1 remains unsolved, RBFAOOr strictly increases Tr(Fn,a1 , pa1 ) and Tr(Fn,a2 , pa2 ), eventually leading to c(n, a1) + Tr(Fn,a1 , pa1 ) ≤ C(n, p) ≤ c(n, a2) + Tr(Fn,a2 , pa2 ) = b in finite time. When this happens, RBFAOOr examines Fn,a1 with th(Fn,a1 ) = min(b, th(n)) - c(n, a1). If Tr(Fn,a2 , pa2 ) = ∞ (i.e. Fn,a2 is proven unsolvable), RBFAOOr cannot deviate from ST. If b ≪ ∞, th(Fn,a1 ) = b - c(n, a1), since th(n) = ∞ - k. By Lemma 7, RBFAOOr returns to Fn,a1 in finite time. Since Tr(Fn,a1 , pa1 ) ≤ C(Fn,a1 , pa1 ) ≤ b - c(n, a1), Tr(Fn,a1 , pa1 ) cannot be strictly increased. Therefore, RBFAOOr must mark Fn,a1 as solved, resulting in solving n in finite time. If a2 also leads to another optimal solution, RBFAOOr may choose Fn,a2 rather than Fn,a1 . However, the same discussion holds, resulting in RBFAOOr making Fn,a2 as solved in finite time.

Theorem 2 ensures the solution optimality, once RBFAOOr finds it. Hence, RBFAOOr returns an optimal solution cost for s0 in finite time if a solution exists.

Theorem 8 leads to a new corollary for RBFS [Korf, 1993] with the TT and our approach, denoted by RBFSr. While the admissibility of RBFS assumes that the search space is a tree, RBFSr further reduces duplicate search on cyclic spaces.

Corollary 9. If a solution exists in the finite search space, RBFSr finds an optimal solution in finite time.

RBFAOOr and BLDFSr can prove unsolvability for the graph in Figure 1(right), but have limitations in other cases:

Theorem 10. RBFAOOr and BLDFSr are incomplete when proving unsolvability in the cyclic search space.

Proof sketch. The example shown in Figure 2 cannot be solved. An explicit cycle cannot be detected due to large values of r(B, A → B) and r(C, A → C). This is easily proven in by induction in a similar way to [Akagi et al., 2010].

6 Experimental Results

We use domain-independent nondeterministic planning with unit edge costs and the ADD model to evaluate RBFAOOr and BLDFSr. Baselines RBFAOO and BLDFS unfold repeated states, ensuring solution optimality with the limited TT size or inconsistent heuristics. We modified slightly the original BLDFS [Bonet and Geffner, 2005a] to delay saving a solution cost in the TT until it is proven optimal, as discussed in Section 4. To the best of our knowledge, this change has not empirically impacted the performance, since a first solution our BLDFS returned is optimal in all cases we observed. We coded all algorithms in C++ (64-bit) and ran experiments on an Intel Xeon CPU X5690 processor at 3.47GHz. The TT is limited to 1GB. The time per instance is 30 minutes. When the TT is full, SmallTreeGC [Nagai, 1999] discards R% TT entries with small subtrees. As in [Akagi et al., 2010; Kishimoto and Marinescu, 2014], we set R to 30.

We extended the hmax heuristic [Bonet and Geffner, 2001; Haslum and Geffner, 2000] to nondeterministic planning, which is consistent. In constructing an inconsistent heuristic from hmax , we perform the perturbation as follows: We represent a state as a bit vector of true or false values of grounded predicates. Among the algorithms compared, the same heuristic values are returned when the same states are evaluated. A set of grounded predicates are randomly selected with the same seed among the algorithms, before search is performed. Whether a small value is subtracted or not is determined by whether one of the selected predicates is true or false. We select 5% of the grounded predicates.

Unsolvable Instances and Inconsistent Heuristics. We use instances from the Uncertainty Track in the 6th International Planning Competition in 2008, consisting of BWD (blocksworld, 30 instances), FLTS (faults, 55 instances) and FRES (first-responders, 100 instances). All these instances admit solutions with cycles. They are unsolvable under the cycle-free solution requirement. Table 1(top) shows the number of instances proven unsolvable. Without any search, the inconsistent heuristic proves that 26 instances in BWD, and all 100 instances in FRES are unsolvable. That is, no further improvement can be achieved on these instances even with a better search algorithm. For the remaining four instances in BWD, and all 55 instances in FLTS, the heuristic cannot prove unsolvability at their initial states. In these 59 instances, RBFAOO and BLDFS time out, since all they can do is to unfold repeated states until exceeding their thresholds. On the other hand, both RBFAOOr and BLDFSr successfully prove unsolvability of all instances in BWD and 14 instances in FLTS (i.e., a total of 18 additional instances proven successfully), clearly demonstrating the effectiveness of our approach. The p7 2 instance in FLTS is the most difficult that RBFAOOr and BLDFSr could prove as unsolvable: RBFAOOr expands 288,862,627 nodes (589 seconds), while BLDFSr expands 184,513,049 nodes (351 seconds).

Solvable Instances and Inconsistent Heuristics. Since the instances considered in the previous subsection are unsolvable, we modified them to admit cycle-free solutions, as described in [Fu et al., 2013]. Specifically, in BWD, we make only the pick-up action nondeterministic to ensure that the optimal solution is a tree. In FRES, we additionally allow hospitals to accept victims at status dying. This change allows to have cases where a solution is not always a sequence of actions but a tree. However, 27 instances are proven to be unsolvable, resulting in 73 solvable instances. These three domains have different characteristics. Nondeterministic actions tend to be selected much more frequently in FRES than in BWD. While the search spaces of BWD and FRES contain cycles, the search space of FLTS is a DAG. For DAGs, since r(n, p) = q(n) always holds for any node n and path p, RBFAOOr and BLDFSr have no advantage over RBFAOO and BLDFS but incur extra overhead due to calculating both r-values and q-values. Table 1(bottom) shows the number of instances solved optimally by each algorithm, where the number inside the parentheses is the total search time of the solved instances in seconds. When finding an optimal solution cost, our approach preserves the solving ability of RBFAOO and BLDFS without sacrificing their running time. RBFAOOr and RBFAOO solve the same set of instances, and so do BLDFSr and BLDFS. Search time differences range from 1 to 7%, which is a small overhead, compared to benefits pointed out earlier. For example, in FLTS where the search space is a DAG, RBFAOOr and RBFAOO examine the same portions of the search space, resulting in RBFAOOr running 2% slower than RBFAOO due to the extra computational overhead. We observed a similar phenomenon for BLDFSr and BLDFS.

LimitedTT andConsistent Heuristics. We selected 5 difficult instances (four have optimal solutions and one does not), and ran an experiment using the consistent hmax , a TT limited to 30 MB, and a 2-hour time limit per instance. Table 2 shows the runtimes in seconds. Both RBFAOOr and BLDFSr solve three instances including the one (p 7 2) which has no solution in the cyclic search space. On the other hand, RBFAOO and BLDFS solve only two instances which have optimal solutions due to a lack of the cycle detection scheme. We also see that our approach does not sacrifice the ability to solve solvable instances.

7 RelatedWork

Value Iteration (VI) can optimally solve search problems by solving the Bellman equation using dynamic programming [Bellman, 1957]. However, it is limited to solving problems with relatively small search spaces that fit into memory, and may not be able to prove unsolvability due to cycles.

CFCREV ∗ [Jim´enez and Torras, 2000] is a best-first search like AO* [Nilsson, 1980] that can handle cyclic search spaces to find a cycle-free optimal solution but it needs to keep the examined search space in memory. Liang and Su (2005) presents an algorithm that assumes all terminal nodes are known beforehand and available in memory, which does not hold in domains such as nondeterministic planning.

MAO* [Chakrabarti et al., 1989] is an AO* variant that can operate with limited memory but assumes the search space is a DAG and uses a specific strategy to remove nodes from memory. Our approach makes no specific assumption about the replacement strategies of the TT, and the search space can be cyclic as long as an optimal solution is a tree.

LAO* [Hansen and Zilberstein, 2001] combines AO* with dynamic programming (value or policy iteration) to handle optimal solutions involving cycles. LAO* does not operate with limited memory. In addition, in our setting, cycles need to be regarded as unsolvable, and optimal solutions may not contain cycles if they exist. LDFS(MDP) [Bonet and Geffner, 2006] extends LDFS to solve MDP, allowing for cyclic optimal solutions as LAO* does. Extensions of LAO* and LDFS(MDP) to our scenario remain open.

8 Conclusions

In this paper, we focused on finding optimal acyclic solutions in cyclic AND/OR search spaces. We showed in detail how to integrate our ideas into two state-of-the-art algorithms. Our new theoretical analysis addresses important gaps for cases of insufficient cache memory or inconsistent heuristics. Experiments in domain-independent planning demonstrate a boost in the ability to prove unsolvable difficult instances.

In future work we plan to investigate complete algorithms across unsolvable instances. As previously mentioned, an analysis of the original BLDFS technique in combination with our enhancements is another interesting direction.

Acknowledgments

We would like to thank Masataro Asai for his constructive comments on the paper.