Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search

1 Introduction

If the cost of finding the optimal solution is too expensive, an alternate is to relax the solution quality in order to reduce the time required to find a solution. Such techniques are widely used in applications that are sensitive to response time such as embedded systems [Benton et al., 2007] or video games [Bulitko et al., 2011]. Research has focused on bounded suboptimal search (BSS), which guarantees that the solution found has cost no greater than w×C ∗ , where w is the bound on the solution quality and C ∗ is the optimal solution cost.

BSS algorithms have been relatively well-studied in the literature. A classic example is weighted A* (WA*) [Pohl, 1970], which weights the heuristic in order to focus on states that have lower heuristic values. WA* uses a single priority function f (n) = g(n) +w · h(n), where w is the suboptimality bound. Later versions of the algorithm [Pohl, 1973] used a dynamic weight to try to improve performance.

In BSS there are two tasks that any algorithm must balance, (1) finding a solution and (2) proving that the solution is within the suboptimality bound. A* does both of these with a simple priority function, but more advanced algorithms split these two tasks and work on them somewhat independently.

Algorithms in this category include A*ϵ [Pearl and Kim, 1982], Optimistic Search [Thayer and Ruml, 2008], EES [Thayer and Ruml, 2011], and DPS [Gilon et al., 2016]. These algorithms can outperform WA* in some domains,

[Gilon et al., 2016], which maintains a single priority queue, but must frequently re-sort the queue.

In generic best-first search, what makes an algorithm unique is the definition of best. A priority function is typically used to define the best state to expand over all states. A* uses a priority function of f(n) = g(n) + h(n) while WA* uses f(n) = g(n)+w·h(n). This paper analyzes the class of priority functions in the form of f(n) = Φ(h(n), g(n)) that can avoid re-expansions during search.

2.1 Assumptions and Notation

A heuristic search problem is defined by a n-tuple {G, start, goal, h, B}. The state space, G, is a finite directed graph whose vertices are states and whose edges are pairs of states. Each edge (u, v) ∈ G has a cost c(u, v) ≥ 0 and we assume there is at most one edge between each pair of states. A path in G is a finite sequence U = (U0, . . . , Un) of states in G where (Ui, Ui+1) is an edge in G for 0 ≤ i < n. A path U contains edge (u, v) iff for some i Ui = u and Ui+1 = v.

In BSS the currently explored path to a state does not necessarily correspond to the shortest path. Thus, the g-cost of a state is the cost of the current path from the start to that state.

Let d(u, v) be the shortest distance from state u to state v in G, i.e., the cost of the cheapest path from u to v. If there is no path from u to v then d(u, v) = ∞. We let g∗ (u) = d(start, u). We use end(U) to refer to the state at the end of a path. Given two states start and goal in G, a solution path is a path U with u0 = start and end(U) = goal. The shortest path has solution cost C ∗ = d(start, goal).

Provided with a problem is the heuristic function h(n), which estimates the distance between n and the goal. This paper assumes that the heuristic is both admissible (h(n) ≤ d(n, goal)) and consistent (h(n) ≤ c(n, m)+h(m)). A problem also includes a bounding function B(x) [Valenzano et al., 2013] which provides the bound on the solution quality for a given problem. For a problem instance with solution cost C ∗ , the algorithm must return a solution C ≤ B(C ∗ ). For WA*, B(n) = w · n. This paper only studies w-suboptimal bounding functions, as other bounding functions introduce complications that are beyond the scope of this paper.

A node re-opening occurs when a shorter path is found to a state on closed and the state is removed from closed and placed back on open. A re-expansion occurs when the state is later removed and expanded from open a second time. WA* does not need to re-open or re-expand states to maintain its bound [Likhachev et al., 2004].

3 Motivation

Reopenings have a significant impact in BSS [Sepetnitsky et al., 2016]. This is illustrated in Table 1 which shows the cost of re-opening nodes with WA* in several domains. Recent work has shown that WA* with re-expansions may perform O(N 2 ) expansions in a graph with N states [Chen et al., 2019]. Performing or not performing re-openings also has impact on solution quality [Valenzano et al., 2014].

The main contribution of this paper is to develop a set of conditions on the priority function used by a best-first search that ensures that the best-first search will find a bounded suboptimal solution without re-expanding states. This paper will fully develop two specific priority functions from a larger class that have this property. But, first, we will motivate why alternate priority functions are potentially interesting.

First, consider the priority function used in A* or WA*. This is a function R2 → R, so a priority function is described by a two-dimensional surface over the x-y plane, where the height of the surface is the priority of a state. Sets of points along this surface which have the same priority fall on isolines of the surface. Consider plotting every state on the open list as a point according to its g-cost and h-cost. States on the same isoline will have the same priority, and a best-first search will expand the state with lowest priority first. This is illustrated in Figure 1, where part (a) represents A* and part (b) represents WA* with a weight of 3. A* expands states according to g(n) +h(n), so in part (a) all states with the same g(n) + h(n) are on the same line. Because it is on a lower isoline, the state represented by the solid circle, with priority

5, will be expanded before the hollow states, which have priority 7.5. With WA* the steeper slope of the isolines allows suboptimal solutions.

Because the isolines are straight lines, WA* allows the same suboptimality along each portion of the path being explored. But, there are other possibilities. In Figure 2(a), we show three different isolines for different priority functions. Each of these priority functions will return w-suboptimal solutions, but they place different requirements on the path that is found. Figure 2(b) shows part of the curve in more detail. The straight black line in the middle is WA* with w = 2. Because the WA* isoline is straight, at any point in the search WA* can expand a state that increases the g-cost by 2 and decreases the h-cost by 1 while maintaining the same priority.

The blue line isoline on the bottom, however, is curved. The slope when g is close to 0 is almost -1. Thus, if the isolines of the priority function follow this shape, then best-first search with this priority function will allow very little suboptimality at the beginning of any path that is explored. As the g-cost increases, however, larger amounts of suboptimality will be allowed. The red line on the top has the opposite impact. Early in the search a larger suboptimality is allowed, but the closer the search gets to the goal the less suboptimality is allowed.

The practical use of such priority functions is illustrated in Figure 3. Suppose that WA* is searching from s to g with w = 2. We can reason from the h-cost of the start that the top path from s to n to g is within the 2x path cost bound. But, WA* requires that the portion of the path from n to g be at most 2x suboptimal, so all nodes on the bottom path from n to g will always have lower priority than the goal will along the top path. However, the priority function with the blue isoline in Figure 2 allows less suboptimality on the first half of the path and more suboptimality on the second half, so it would be able to find the solution length 340 in this example. Whether this is useful in practice will depend on the properties of a domain and a heuristic.

4 Conditions for Avoiding Re-expansions

This section develops the conditions on any function Φ(x, y) that can be used as a priority function for best-first search and does not require node re-expansions to find a bounded cost solution. First, let Φ(x, y) be a function R2 → R. Given a state u in open reached by a path U, f(u) = Φ(h(u), g(u)). Φ describes a surface, but we are interested in the sets of states on that surface which have the same priority. Such states fall on isolines of the surface. For WA* we use Φ(x, y) = x+ 1w · y.

It is worth noting that in a finite state space, a best-first search with any function Φ is complete even if it does not re-open states.

Lemma 1. In a finite state space, a best-first search with any priority function Φ is complete (finds a solution if one exists) even if it does not re-open states.

Proof. Assume that the optimal path from start to goal is p0, p1, p2, ...pn, where p0 = start, pn = goal. If goal is not expanded, then prior to each expansion there always exist at least one pi such that 0 ≤ i ≤ n and pi is on Open while none of pi+1, ...pn is closed. This implies that the search always makes progress on exploring the optimal path (even if the costs used to explore the path are not optimal), and thus will eventually expand the goal and complete. We prove this by induction.

Base case: At the very beginning, p0, which is start is on open, meeting the requirement for this lemma.

Inductive step: Assume at some point there exists some pi which meets this condition. If the next state that is chosen for expansion is not from pi, pi+1, ...pn, then pi is still valid after the next expansion. Otherwise, suppose we choose to expand pk which is one of pi, pi+1, ...pn. Then pk+1 will be placed on open and meet the condition.

4.1 Properties of Φ that Avoid Re-expansions

The following properties are the sufficient conditions for Φ to avoid re-expansions. We provide a brief intuition of how these properties related to search, and we will provide the proofs for sufficiency in next subsection.

This property means we assume that for two states with same h-cost, we will alway prefer the one with lower g-cost; similarly, for two states with same g-cost, we will alway prefer the one with lower h-cost.

This property requires that Φ grows faster when the h-cost is increased than when the g-cost is increased by the same amount. Namely, there is more weight on the h-cost term than the g-cost term. In terms of isolines, this property is equivalent to saying that the slope of any iosoline at any point is no greater than -1. A slope greater than -1 corresponds to WA* with a weight less than one, which is never beneficial with a consistent heuristic. Practically speaking it means that the hollow diamond state in Figure 1(a) can be expanded no later than the hollow circle, because the hollow diamond state has lower h-cost.

A state with h-cost of v and g-cost of 0 should have equivalent priority to a state with g-cost of w · v, because both of these can lead to a w-suboptimal path. The actual priority (value of Φ) at these points can be scaled by a constant, but for simplicity we assume the priority (value of Φ of these states is also t.

This last property is related to the rate of change of the isolines; this needs to be bounded (the value of 2 arises from the constant t used in Property 3) in our construction.

4.2 Proofs that ΦAvoid Re-expansions

The proof is done in a top-down manner. We begin by showing a condition that is sufficient for a best-first search algorithm to avoid re-expansions, and then work out the practical properties required to meet this condition. We call the primary condition the Φ-inequality; it relies on property 3.

The Φ-inequality is illustrated in Figure 4(a). The black dot is the point (h(p), g(p)) and the blue dot is the point (h(p), g∗ (p)). The blue dot represents where p would be plotted if we found the optimal path to p instead of the current path with cost g(p). The minimum path cost through p to the goal is h(p) + g∗ (p), and if the solution is wsuboptimal, the longest w-optimal solution will have cost w(h(p)+g∗ (p)). The Φ-inequality says that (h(p), g(p)) will not be above the isoline that passes through (h(p)+g∗ (p), 0) and (0, w(h(p) + g∗ (p))).

For WA*, the Φ-inequality says that when p is expanded the portion of the path found so far is at most w-suboptimal. More generally, it is saying that the path so far is within the local bound allowed by the priority function.

Theorem 2. Assume a best-first search is using a priority function Φ with a suboptimality bound of w that meets property 1. If, for every state p that is expanded the first time, the Φ-inequality holds, then it is not necessary to re-open (and thus re-expand) states during search to return a w-suboptimal solution.

Proof. Lemma 1 shows that any best-first search algorithm that does not perform re-openings is complete. Thus, we know we will expand the goal state at some cost g(goal). If for any p expanded it holds that Φ(h(p), g(p)) ≤ Φ(0, w(h(p)+g∗ (p))), then it also holds for the path discovered to the goal. In this case Φ(0, g(goal)) ≤ Φ(0,wC ∗ ). Because Φ is monotonically increasing with y due to Property 1, this means that g(goal) ≤ wC ∗ and the solution is w-suboptimal.

Thus, it is sufficient to show that the Φ-inequality holds for every state expanded with a given priority function. The highlevel approach to proving this is illustrated in Figure 4(b). Suppose we plan to expand a state q where p is the last state expanded on the optimal path to q. As before, the point in blue below p represents the optimal path to p and the curved line at (a) is the isoline for that point. We know by the Φinequality that p is under the isoline that begins at point (a).

Thus, if the search moves optimally from p to q it should still hold that q (and all states on the optimal path from p to q) is under the h(q) + g∗ (q) isoline at point (b) on the h-axis because the optimal path does not accumulate any additional suboptimality. If this holds, then there will always be at least one path (the remaining portion of the optimal path) where it is possible to reach the goal under the optimality bound without re-expanding a previously expanded state. While the search may expand a less optimal path in practice, the explored path will still be guaranteed to be within the bound allowed by Φ.

To show this holds, we can compare the change in Φ from p to q to the change in Φ between (a) and (b). As long as the change in Φ between p and q is less than the change in Φ between (a) and (b) then the Φ inequality will hold when q is expanded. To do this, we want to measure the rate of change of Φ in a direction (a, b).

Lemma 3. Suppose that state q is a descendant of state p. The coordinates of p on h-g plane are (h(p), g(p)) and the coordinates of q are (h(q), g(p) + d(p, q)). For any state p1 on the optimal path from p to q, p1 must be in the rectangle formed with opposite corners on p and q. (Two lower edges of this rectangle are shown in red in Figure 4(b).)

Proof. This is a direct result of a consistent heuristic.

Given that the path from p to q stays inside a rectangle around p and q, we need to know which point on the rectangle has maximum priority.

Definition 2. We define r as the right most corner of the rectangle described in Lemma 3. It can be computed that xr = h(p) + d(p,q)+h(q)-h(p) 2 , yr = g(p) + d(p,q)+h(q)-h(p) 2 .

We now present a general condition that will allow us to show that no state on the path between p and q has higher priority than r.

Lemma 4. φ(x+at, y+bt) ≤ φ(x, y)+ct for any fixed point (x, y) if φ is a function R2 → R satisfying a · ∂φ ∂x +b· ∂φ ∂y ≤ c.

Although we omit the proof of this property, note that this is a general condition related to whether φ is Lipschitz.

Proof. - ∂Φ ∂x + ∂Φ ∂y ≤ 0 by property 2. Thus, Φ satisfies the requirement of Lemma 4 for a = -1, b = 1, c = 0 and so Φ(x - t, y + t) ≤ Φ(x, y).

This tells us that in Figure 4(b), Φ(xr, yr) ≥ Φ(h(q), g(q)).

Lemma 6. For all states s on all optimal paths between p and q, Φ(h(s), g(p) + d(p, s)) ≤ Φ(xr, yr) where r is defined in Definition 2.

Proof. First of all, we know s must be in the rectangle described in Lemma 3. Then, by Property 1, the maximum value of Φ on this rectangle must be a point on the segment qr. By Corollary 5, as we move from q to r, the Φ-value is monotonically non-decreasing. Therefore, Φ(xr, yr) has maximum value in the rectangle defined by p and q.

Proof. ∂Φ ∂x + ∂Φ ∂y ≤ 2 by property 4. Thus, Φ satisfies the requirement of Lemma 4 for a = 1, b = 1, c = 2 and so Φ(x + t, y + t) ≤ Φ(x, y) + 2t.

This bounds the change in Φ between p and r.

Given these results, we can now show that the Φ-inequality holds as long as Φ meets properties 1 - 4.

Theorem 8. Assume a best-first search is using a priority function Φ which meets properties 1 - 4. Then, the Φ-inequality holds for all expansions: Φ(h(n), g(n)) ≤ Φ(h(n) + g∗ (n), 0)

Proof. Proof by induction.

Base case: Initially start is chosen for expansion, so Φ(h(start), g(start)) = Φ(h(start), 0) = Φ(h(start) + g∗ (start), 0), and the claim holds.

Inductive step: Assume the inequality holds for all expanded paths. And a state q is the next state from Open is chosen for expansion. We need to prove that Φ(h(q), g(q)) ≤ Φ(h(q) + g∗ (q), 0)).

Let the last node that is closed on optimal path from start to q be p. The hypothesis guarantees that:

Since p is closed, there must exist a direct successor of p, px on open, which is on the optimal path from p to q. Examining the rectangle formed around p and q, the absolute distance along each axis from p to the corner state r with maximum priority is:

So, according to Lemma 6, we get:

According to Corollary 7,

By combining inequalities (1), (3) and (4) we can get

In practice, we chose to expand q instead of px, so the priority of q will be no more than that of px. Thus:

This proves that the Φ-inequality holds for each expansion.

Theorem 9. If there is a path from start to goal, then a BFS using any Φ that meets properties 1 - 4, is guaranteed to find a solution within the given bound without re-opening states.

Proof. This is a direct result of Theorem 2 and 8.

5 Function Selection

Given now that we understand the properties required for Φ we can develop several different functions that meet these properties.

5.1 Linear Function

The first function we develop is a linear function, which is equivalent to WA*. In this case Φ(x, y) = 1w · y + x. While WA* typically puts a weight of w on the heuristic, it is equivalent to put a weight of 1/w on the g-cost.

We can, for instance, verify that property 4 holds for w ≥ 1:

In a similar manner, it can be shown that properties 1 - 3 also hold. Thus, as was known, WA* maintains a w-optimal solution without re-expanding states.

5.2 Non-linear Priority Functions

We can now derive new priority functions that meet properties Properties 1 - 4.

Convex Downward Parabola

Our first priority function that has isolines similar to the bottom parabola shown in blue in Figure 2. A parabola is a function is of the form y = ax2 + bx + c, where a, b, c are to be determined. Assume that parabola goes through the points (0, wU) and (U, 0) and has slope -1 at (U, 0). The slope of

-1 at (U, 0) means that paths with low g-cost must be nearoptimal. This results in the following equation set:

Solving for a, b and c, the equation of the parabola is

We can rewrite equation (7) as an equation of U:

The Φ function we are looking for, is proportion to the larger root of equation (8):

A check of properties 1 - 4 shows that they all hold for this priority function. We call this priority function the convex downward parabola (XDP) priority function .

Convex Upward Parabola

Our second function corresponds to the top parabola shown in red in Figure 2. This parabola goes through points (0, wU) and (U, 0), has slope -1 at point (0, wU). Because the slope is -1 near (0, wU) it means that near the goal the path found must be near-optimal.

Following the same steps as before we get the priority function:

This function is a convex upward parabola (XUP) and also meets properties 1 - 4.

6 Experimental Results

This paper characterizes priority functions that return wsuboptimal solutions without requiring node re-openings during search. The experimental results compare priority functions within this class to see if the new priority functions outperformWA*. Several standard domains are used for testing.

6.1 Experimental Settings

On grid maps we tested on 15,928 problem instances from the Dragon Age: Origins (DAO) map set, 6,444 problem instances from the StarCraft 1 (SC1) map set, and on 35,360 problem instances on maps with 40% random obstacles [Sturtevant, 2012]. The instances for these maps contain 10

problems for each length; we randomly select 10% of each of these problems for testing.

We also tested on the 15-puzzle with the unit edge cost setting and the heavy tile setting, where the cost of moving tile X is X. Manhattan Distance (MD) is used as heuristic for regular tiles, and the modified MD [Thayer and Ruml, 2011] is used for heavy tiles. The instance are the standard 100 Korf instance [Korf, 1985].

Finally, we followed the heavy variant of pancake puzzle created by Gilon et al. [2016], where the cost of flipping a prefix (V [1] · · · V [i + 1]) is the max(V [1]; V [i + 1]). The heuristic we used is their HGAP heuristic. The problem set is 50 randomly generated 12-pancake instances.

We experiment with the various weights for WA*, and best-first search with the convex downward parabola (ΦXDP ) and the convex upward parabola (ΦXUP ). As a general trend, the difference in performance on grid maps was noticeable but not notable. The most interesting trend is the phase transition between ΦXUP , WA*, and ΦXDP in Table 2 as the weights increase. This same trend is seen in all experimental results. There is less than 5% difference in path quality between the different priority functions, with fewer node expansions leading to lower solution quality.

On the other exponential domains in Table 4 we can see a significant improvement with the right priority function. With low weights on the 15-puzzle, Heavy 15-puzzle and Heavy Pancake Puzzle, ΦXDP significantly outperforms WA* both in node expansions and time with the same weight. With a weight of 10, ΦXUP has better performance in the Heavy 15puzzle. See Chen et al. [2019] for further experiments.

If we examine focal list algorithms, they run an A* search near the start to prove that the solution is within the bound, while greedily searching for the goal. ΦXDP able to accomplish both of these in a single search, balancing a tight bound around the start with a looser bound around the goal.

7 Conclusions and FutureWork

This work generalized WA* to a family of algorithms that can find w-suboptimal solutions while avoiding node reexpansions. We also provide two new priority functions, ΦXDP and ΦXUP . ΦXDP only requires a minor change to a best-first search implementation, but offers a significant improvement over WA* in the exponential domains we tested.

This work just handles curves for w-suboptimal paths, however there are other classes of suboptimality which are not addressed, such as additive bounds [Valenzano et al., 2013]. We have also developed w-suboptimal piece-wise continuous curves which are not presented here. Future research will continue develop this broader classes of bounds.