Bounded Suboptimal Weight-Constrained Shortest-Path Search via Efficient Representation of Paths

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 17:58:27

Abstract: In the Weight-Constrained Shortest-Path (WCSP) problem, given a graph in which each edge is annotated with a cost and a weight, a start state, and a goal state, the task is to compute a minimum-cost path from the start state to the goal state with weight no larger than a specified weight limit. While most existing works have focused on solving the WCSP problem optimally, many real-world situations admit a trade-off between efficiency and a suboptimality bound for the path cost. In this paper, we propose a novel bounded suboptimal WCSP algorithm called WC-A\*pex that is built on a state-of-the-art approximate bi-objective search algorithm called A\*pex. WC-A\*pex uses an efficient, albeit approximate, representation of paths with similar costs and weights to compute a (1 + ε)-suboptimal path, for a user-specified ε. During search, WC-A\*pex avoids storing all paths explicitly and thereby reduces the search effort while still retaining its (1 + ε)-suboptimality property. On benchmark instances that model road networks, our experimental results show that WC-A*pex with ε = 0.01 (i.e., with 1% suboptimality) achieves an order-of-magnitude speed-up over WC-A\*, a state-of-the-art WCSP algorithm, and its bounded suboptimal variant.

Main paper: 
 introduction and related work: 
 In the Weight-Constrained Shortest-Path (WCSP) problem, given a graph in which each edge is annotated with a cost and a weight, a start state, and a goal state, the task is to compute a minimum-cost path from the start state to the goal state with weight no larger than a specified weight limit. The WCSP problem appears in many real-world applications. In an electric vehicle domain, the graph represents a road network and each edge is annotated with a cost corresponding to driving time and a weight corresponding to battery consumption (Baum et al. 2015) . A desired route minimizes the driving time without depleting the battery. In a bicycling domain, the graph represents a road network and each edge is annotated with a cost corresponding to bicycling time and a weight corresponding to climbing altitude gain (Storandt 2012) . A desired route minimizes the bicycling time with a user-specified limit on total climbing altitude gain.Combinatorially, the WCSP problem also appears as a subproblem in the context of column generation methods used for solving other problems, such as the shift scheduling problem (Cabrera et al. 2020 ) and the virtual network embedding problem (Rost 2019) . Although many path-finding problems are tractable, the WCSP problem is NP-hard to solve optimally, i.e., it is NP-hard to compute the minimumcost path within the weight limit (Handler and Zang 1980; Lorenz and Raz 2001) .The WCSP problem is similar to the Bi-Objective Shortest-Path (BOSP) problem, where each edge is annotated with two costs. Although the task in the BOSP problem (Sec. 3) is different from the task in the WCSP problem, several techniques of BOSP algorithms can be carried over to the WCSP domain by treating the weight as the second cost while being cognizant of the weight limit. In fact, WC-A* (Ahmadi et al. 2022a ) is a state-of-the-art WCSP algorithm that draws inspiration from BOSP algorithms. WC-A* and its bi-directional variant, WC-BA* (Ahmadi et al. 2022b), have been shown to outperform previous state-of-the-art algorithms, Bi-pulse (Cabrera et al. 2020) and RC-BDA* (Thomas, Calogiuri, and Hewitt 2019) , by up to two orders of magnitude on road networks (Ahmadi et al. 2022a,b) .While the algorithms mentioned above focus on solving the WCSP problem optimally, many real-world situations admit-or even encourage-a trade-off between efficiency and a suboptimality bound for the path cost. A bounded suboptimal WCSP algorithm computes a (1 + ε)-suboptimal path, for a user-specified ε. A (1 + ε)-suboptimal path has a cost within (1 + ε) times the minimum path cost and a weight that is no larger than the weight limit.There are only a few existing works on solving the WCSP problem bounded-suboptimally. In the paper of Bipulse (Cabrera et al. 2020) , the authors provided a straightforward method to convert an optimal WCSP algorithm to a bounded suboptimal one, that is, to terminate the search immediately after the cost of the incumbent solution (i.e., the best solution that an algorithm has found thus far) is proven to be within the given suboptimality bound. Other works on bounded suboptimal WCSP algorithms (Lorenz and Raz 2001; Ergun, Sinha, and Zhang 2002) are typically based on fully polynomial-time approximation schemes, whose runtime is polynomial in the size of the graph and 1/ε. Unfortunately, these algorithms are still impractical for large graphs, such as road networks, that often have millions of states.There are many existing works on bounded suboptimal search algorithms for (unconstrained) shortest-path problems. These algorithms include WA* (Pohl 1970) , fo-cal search (Pearl and Kim 1982) , and explicit estimation search (Thayer and Ruml 2011) . While speeding up the search via allowing suboptimality is intuitive, it is unclear how to efficiently do so for the WCSP problem.In this paper, we propose a novel bounded suboptimal WCSP algorithm called WC-A*pex. WC-A*pex takes a WCSP instance and a user-specified ε ≥ 0 as input and computes a (1 + ε)-suboptimal path. WC-A*pex imports techniques from A*pex (Zhang et al. 2022b ), a state-of-theart approximate BOSP algorithm. Unlike other WCSP algorithms, it uses a clever data structure that merges paths with similar costs and weights (instead of storing them explicitly) during the course of its search. Since paths correspond to search nodes, the merged representation of similar paths reduces the number of node expansions and thereby the overall search effort of WC-A*pex. It is noteworthy that WC-A*pex uses a different technique to speed up the search from existing bounded suboptimal search algorithms, most of which rely on node expansion orders to guide the search to quickly find a bounded suboptimal solution.We empirically evaluate WC-A*pex with different suboptimality bounds against competing algorithms on benchmark road networks with 1 to 14 million states and 2 to 34 million edges. The competing algorithms include WC-A* and our adaptation of it to a bounded suboptimal variant using the same method provided by Cabrera et al. (2020) , called WC-A*-ε. WC-A*-ε is similar to WC-A* but terminates the search immediately after the incumbent solution is proven to be (1 + ε)-suboptimal. Our experimental results show that WC-A*pex significantly outperforms WC-A* and WC-A*-ε although WC-A* and WC-A*-ε are also based on BOSP algorithms. This, in turn, demonstrates the power of the merged representation of similar paths used in WC-A*pex. Even with ε = 0.01 (i.e., with 1% suboptimality), WC-A*pex achieves an order-of-magnitude speed-up over WC-A* and WC-A*-ε on the largest road network. In comparison, WC-A*-ε for the same value of ε achieves less than 20% runtime improvement over WC-A*. 
terminology and problem definition: 
 In this section, we formally define the WCSP and the BOSP problems. To set up a notation that serves the description of both problems, we define the cost of an edge as a pair of numbers. In the WCSP context, the first number indicates the cost, and the second number indicates the weight. In the BOSP context, both numbers represent the cost.We use the boldface font to denote pairs and p i , i ∈ {1, 2}, to denote the i-th component of a pair p. The addition of two pairs p and p ′ is defined as p+p ′ = (p 1 +p ′ 1 , p 2 +p ′ 2 ). We say that p (weakly) dominates p ′ , denoted as p ⪯ p ′ , if p 1 ≤ p ′ 1 and p 2 ≤ p ′ 2 . For an approximation factor (or, more precisely, a pair of approximation factors) ε = (ε 1 , ε 2 ), we say that p ε-dominates p ′ , denoted as p ⪯ ε p ′ , ifp 1 ≤ (1 + ε 1 ) • p ′ 1 and p 2 ≤ (1 + ε 2 ) • p ′ 2 . A (bi-objective) graph is a tuple G = ⟨S, E, c⟩,where S is a finite set of states and E ⊆ S × S is a finite set of (directed) edges. succ(s) = {s ′ ∈ S : ⟨s, s ′ ⟩ ∈ E} denotes the successors of state s. The cost function c : E → R ≥0 × R ≥0 maps an edge to its cost, which is a pair of non-negative c 1 c 2 W π*(π) = ℓ-1 j=1 c(⟨s j , s j+1 ⟩). A WCSP (problem) instance is a tuple P = ⟨G, s start , s goal , W ⟩,where G is a graph, s start ∈ S is the start state, s goal ∈ S is the goal state, and W ∈ R >0 is the weight limit. 1 The two components of the cost function c, c 1 and c 2 , correspond to the cost and weight in the context of the WCSP problem, respectively. A path π is a solution of P if it is from s start to s goal and satisfies c 2 (π) ≤ W . We say that P is solvable if it has a solution. An optimal solution of P is a solution with the minimum c 1 -value, denoted as c * 1 , of all solutions. Given a non-negative ε, a solution π is(1 + ε)- suboptimal if c 1 (π) ≤ (1 + ε) • c * 1 .A bounded-suboptimal WCSP algorithm takes a WCSP instance P and a parameter ε ≥ 0 as input and computes a (1 + ε)-suboptimal solution.A path π from s start to s goal is Pareto-optimal if there does not exist another path π ′ from s start to s goal with c(π ′ ) ⪯ c(π) and c(π ′ ) ̸ = c(π). The Pareto front Π * (from s start to s goal ) is the set of all Pareto-optimal paths. For a nonnegative pair ε, a set of paths Π ε from s start to s goal is an ε-approximate Pareto front from s start to s goal if, any path from s start to s goal is ε-dominated by at least one path in Π ε . Note that different ε-approximate Pareto fronts can exist for the same s start , s goal , and ε.A BOSP (problem) instance is a tuple ⟨G, s start , s goal ⟩, where G is a graph, s start ∈ S is the start state, and s goal ∈ S is the goal state. An approximate BOSP algorithm takes a BOSP instance and an approximation factor ε as input and computes an ε-approximate Pareto front from s start to s goal .The following observation shows the connection between a bounded-suboptimal WCSP algorithm and an approximate BOSP algorithm. Observation 1. For a solvable WCSP instance P = ⟨G, s start , s goal , W ⟩ and ε ≥ 0, any (ε, 0)-approximate Pareto front (from s start to s goal ) Π ε contains a (1 + ε)suboptimal solution of P .Proof. Let π * denote an optimal solution of P . By definition, there exists a path π ∈ Π ε with c(π)⪯ (ε,0) c(π * ) (i.e., c 1 (π) ≤ (1 + ε) • c 1 (π * ) and c 2 (π) ≤ c 2 (π * ) ≤ W ). We can see that π is a (1 + ε)-suboptimal solution of P .See Figure 1 for a visualization of an ε-approximate Pareto front and a (1 + ε)-suboptimal solution of a WCSP instance.In this paper, we focus on heuristic-search-based WCSP algorithms. We assume that a heuristic function h : S → R ≥0 × R ≥0 , which provides a lower bound on the cost from any given state s to the goal state, is always available. Additionally, we assume that the heuristic function h is consistent, that is, h(s goal ) = 0 and h(s) ⪯ c(e) + h(s ′ ) for all e = ⟨s, s ′ ⟩ ∈ E. It is a common practice in existing WCSP and BOSP literature (Ahmadi et al. 2021 (Ahmadi et al. , 2022b;; Hernández et al. 2023; Zhang et al. 2022b) to use Dijkstra's algorithm (starting from s goal ) to compute the minimum cost c * i (s) from any state s to s goal for the i-th objective (while ignoring the other objective), i = 1, 2, and h(s) := (c * 1 (s), c * 2 (s)) as the heuristic function. We call these heuristic functions perfect-distance heuristics. 
algorithmic background: 
 In this section, we review existing WCSP and BOSP algorithms, with a focus on BOA* (Hernández et al. 2023), WC-A* (Ahmadi et al. 2022b) , and A*pex (Zhang et al. 2022b) .Many WCSP and BOSP algorithms such as BOA*, WC-A*, and A*pex follow the same best-first bi-objective search framework. In a best-first bi-objective search algorithm, a (search) node n contains a state s(n) and a g-value g(n). The f -value of n is defined asf (n) = g(n) + h(s(n)).The search algorithm maintains a priority queue Open, containing generated but not expanded nodes, and a set of solutions. Open is initialized with a node that contains the start state s start and the g-value 0. In each iteration, the algorithm extracts a node n from Open with an undominated f -value of all nodes in Open. It performs a dominance check to determine whether n or any of its descendants have the potential to be in the solution set. If not, it discards n. Otherwise, when s(n) = s goal , the algorithm adds n to the solution set or, when s(n) ̸ = s goal , expands n by generating a new node for each of the successor in succ(s(n)). The algorithm also performs a dominance check for each generated node and adds the generated node to Open if it passes the dominance check. When Open becomes empty, the algorithm terminates and returns the solution set.Different best-first bi-objective search algorithms mainly differ in which information is contained in the nodes, which node is extracted from Open, and how the dominance checks work. Specifically, BOA*, WC-A*, and A*pex extract the node with the lexicographically smallest f -value (i.e., extract the node with the smallest f 1 -value and break ties in favor of a smaller f 2 -value) in each iteration. The dominance checks in both BOA* and A*pex check if the fvalue of a node is weakly dominated by the f -value of any expanded node with the same state or s goal .BOA* (Hernández et al. 2023) computes a Pareto front for the given start and goal states. In BOA*, each node n corresponds to a path from s start to s(n) with cost g(n). Hernández et al. (2023) show that, due to the consistent heuristic function BOA* uses, the f 1 -values of extracted nodes are monotonically non-decreasing. Thus, BOA* only stores the minimum g 2 -value of all expanded nodes for each state s using a variable named g min 2 (s). Consequently, dominance checks can be done by checking if g 2 (n) < g min 2 (s) and f 2 (n) < g min 2 (s goal ). This dominance check can be performed in constant time (in contrast to previous methods which required time linear in the number of nodes that reached s).WC-A* is built on BOA* and computes an optimal solution for an input WCSP instance. It only maintains at most one incumbent solution in the solution set. In addition to the dominance checks of BOA*, WC-A* also discards nodes whose (1) f 2 -values are larger than the weight limit W or (2) f 1 -values are not smaller than the c 1 -value of the incumbent solution. Since WC-A* extracts nodes with monotonically non-decreasing f 1 -values, it terminates (and returns the incumbent solution) once the minimum f 1 -value in Open is not smaller than the one of the incumbent solution. During the heuristic computation with Dijkstra's algorithm, the minimum-c 1 and minimum-c 2 paths from any state s to s goal can also be obtained. We call these paths the complementary paths of s. When generating a node n, WC-A* tries to update the incumbent solution with better ones by connecting the corresponding path of n with the complementary paths of s(n).WC-A* can be converted to a bounded suboptimal WCSP algorithm by terminating the algorithm when the minimum f 1 -value in Open is not smaller than the f 1 -value of the incumbent solution divided by (1 + ε). We denote this variant of WC-A* as WC-A*-ε and include it in our empirical study.It is noteworthy that Ahmadi et al. (2022b) propose WC-BA*, a bi-directional variant of WC-A* that runs two WC-A* searches (one starting from s start and the other starting from s goal ) concurrently. We omit WC-BA* in this paper because Ahmadi et al. (2022a) later show that WC-BA* does not dominate WC-A* in experimental results and, in fact, has larger average runtime in several scenarios.A*pex computes an ε-approximate Pareto front for the given start and goal states and a user-provided ε-value. In A*pex, a node is a so-called apex-path pair AP = ⟨A, π⟩ that consists of a cost pair A, called the apex, and a path π, called the representative path. We define the g-value of AP as g(AP) := A and s(AP) as the last state of the representative path π. We have f (AP) := g(AP) + h(s(AP)) as the f -value of AP. Conceptually, an apex-path pair corresponds to a set of paths that end at the same state, and its apex is the component-wise minimum value of the cost of these paths. AP is said to be ε-bounded if c(π)+h(s(AP)) ⪯ ε f (AP).Whenever A*pex inserts an apex-path pair to Open or the solution set, A*pex tries to merge apex-path pairs in Open with the same state on condition that the resulting apex-path pair is ε-bounded. The implementation of A*pex by Zhang et al. (2022b) uses a list to maintain the apex-path pairs in Open for each state and hence can iterate these apex-path pairs efficiently. When merging two apex-path pairs, the new apex is the component-wise minimum of the apexes of the two apex-path pairs, and the new representative path is either one of the two representative paths of the two apex-path pairs. See Figure 2 (a) for a visualization of the two possible outcomes. 
wc-a*pex: 
 In this section, we describe WC-A*pex, our bounded suboptimal WCSP algorithm that finds a (1 + ε)-suboptimal solution for a user-provided ε. We first describe the base algorithm of WC-A*pex and then provide its theoretical results and speed-up techniques.Observation 1 shows that a (1 + ε)-suboptimal solution of a WCSP instance can be found in a corresponding (ε, 0)approximate Pareto front. This motivates us to propose WC-A*pex, which can be viewed as a modified A*pex with ε = (ε, 0) and additional prunings. Note that we use boldface ε and regular ε to distinguish between the approximation factor that A*pex would use and the user-provided parameter for the WCSP problem. Similarly to A*pex, a node in WC-A*pex is an apex-path pair AP = ⟨A, π⟩. Since the second component of ε is set to 0, when merging two apexpath pairs ⟨A, π⟩ and ⟨A ′ , π ′ ⟩ with c 2 (π) < c 2 (π ′ ), WC-A*pex cannot choose the π ′ as the new representative path. Otherwise, the resulting apex path pair is not ε-bounded. See Figure 2 (b) for a visualization of merging two apex-path pairs in WC-A*pex. In addition to dominance checks, WC-A*pex also prunes nodes whose f 2 -values are larger than W .Algorithm 1 shows the pseudocode of WC-A*pex. It starts with a single apex-path pair ⟨0, [s start ]⟩ in Open (Line 1). At each iteration, WC-A*pex extracts an apex-path pair from Open with the lexicographically smallest f -value (Line 5). Same as BOA*, WC-A*pex maintains a g min 2 (s) for each state s that contains the smallest g 2 -value of all expanded nodes with state s by updating it on Line 10. Both after extracting (that is, after Line 5) and before generating (that is, before Line 16) an apex-path pair AP with state s, WC-A*pex discards the apex-path pair if (1) g 2 (AP) ≥ g min 2 (s(AP)) or (2) f 2 (AP) > W . Case (1) holds iff there exists an expanded node with state s whose g-value weakly dominated g(AP), which implies that any solution found via AP is also (ε, 0)-dominated by a solution found via expanded node and hence AP can be safely discarded. In Case (2), AP is pruned since the representative path of AP cannot be extended to a solution (whose c 2 -value needs to be not larger than W ).When WC-A*pex expands an apex-path pair AP with state s, it generates a child apex-path pair for each successor s ′ of state s. The apex of the child apex-path pair is the sum of the apex of AP and c(⟨s, s ′ ⟩) (Line 12), and the representative path of the child apex-path pair is the representative path of AP appended with state s ′ (Line 13). Before adding the child apex-path pair AP ′ to Open, WC-A*pex attempts to merge the apex-path pair with an apex-path pair in Open[s(AP ′ )] on condition that the resulting apex-path pair is (ε, 0)-bounded (Lines 19-25), where ε is the input suboptimality factor and Open[s(AP ′ )] denotes the set of apex-path pairs in Open with state s(AP ′ ).g 1 g 2 A π A′ π′ g 1 g 2 A π new A′ π′ A new π new g 1 2 A π A′ A newg 1 g 2 A π A′ π′ merge π new g 1 g 2 A π A′ A new (b) WC-A*pexWC-A*pex terminates when it finds a solution (Line 9) or Open becomes empty (Line 17), in which case, there is no solution for the given WCSP instance.We use an example WCSP instance to demonstrate how WC-A*pex works. Figure 3(a) shows the example graph. The weight limit W and ε are set to 7 and 0.2, respectively. Figure 3 (b) shows the costs of all paths from s start to s goal in this graph. We can see that path [s start , s 1 , s 3 , s 4 , s goal ], whose cost is (7, 7), is the optimal solution for this example. Moreover, since the second best path [s start , s 1 , s 3 , s 4 , s goal ] has a large c 1 -value of 13, [s start , s 1 , s 3 , s 4 , s goal ] is also the only 1.2-suboptimal solution for this example. We use the perfect-distance heuristic. In the text below, slightly abusing the notation, we use subscript i to index an apex-path pair and tuple ⟨s(AP i ), f (AP i ), c(π i )⟩ to denote an apex-path Algorithm 1: WC-A*pex • In Iteration 1, WC-A*pex expands apex-path pair AP 1 = ⟨s start , (5, 5), (0, 0)⟩ and generates two child apex-path pairs AP 2 = ⟨s 1 , (5, 5), (1, 2)⟩ and AP 3 = ⟨s 2 , (6, 6), (3, 2)⟩. • In Iteration 2, WC-A*pex expands apex-path pair AP 2 and generates two child apex-path pairs AP 4 = ⟨s 2 , (5, 7), (2, 3)⟩ and AP 5 = ⟨s 3 , (7, 5), (5, 3)⟩. AP 4 is merged with AP 3 in Open, resulting in apex-path pair AP 6 = ⟨s 2 , (5, 6), (3, 2)⟩. AP 6 is (ε, 0)-bounded because (3, 2) + h(s 2 ) = (6, 6) ⪯ (5, 6). • In Iteration 3, WC-A*pex expands apex-path pair AP 6 and generates child apex-path pair AP 7 = ⟨s 3 , (5, 6), (4, 4)⟩. AP 7 is not merged with AP 5 because, given that the new representative path would have a cost of (5, 3) and the new f -value would be (5, 5), (5, 3) + h(s 3 ) = (7, 5) does not (ε, 0)-dominate (5, 5). • In Iteration 4, WC-A*pex expands apex-path pair AP 7 and generates two child apex-path pairs AP 8 = ⟨s 4 , (5, 8), (5, 6)⟩ and AP 9 = ⟨s 5 , (13, 6), (9, 5)⟩. AP 8 is pruned because f 2 (AP 8 ) > W . • In Iteration 5, WC-A*pex expands apex-path pair AP 5 and generates two child apex-path pairs AP 10 = s start (5,5) ⟨s 4 , (7, 7), (6, 5)⟩ and AP 11 = ⟨s 5 , (15, 5), (10, 4)⟩.Input : P = ⟨G, sstart, sgoal, W ⟩ ε h 1 Open ← {⟨0, [sstart]⟩} 2 for each s ∈ S doA ′ ← A + c(⟨s(AP), s ′ ⟩) 13 π ′ ← π.append(s ′ ) 14 if A ′ 2 ≥ g min 2 (s ′ ) ∨ A ′ 2 + h2(s ′ ) > W thenEQUATIONAP 11 is merged with AP 9 in Open, resulting in apexpath pair AP 12 = ⟨s 5 , (13, 5), (10, 4)⟩. AP 12 is (ε, 0)bounded because (10, 4) + h(s 5 ) = (15, 5) ⪯ (ε,0) (13, 5).• In Iteration 6, WC-A*pex expands apex-path pair AP 10 and generates child apex-path pair AP 13 = ⟨s goal , (7, 7), (7, 7)⟩.• In Iteration 7, WC-A*pex expands apex-path pair AP 13 and returns a solution with cost (7, 7).In this example, WC-A*pex finds the optimal solution. Two merges happen during the entire process, which are in Iteration 2 between AP 3 = ⟨s 2 , (6, 6), (3, 2)⟩ and AP 4 = ⟨s 2 , (5, 7), (2, 3)⟩ and in Iteration 5 between AP 9 = ⟨s 5 , (13, 6), (9, 5)⟩ and AP 11 = ⟨s 5 , (15, 5), (10, 4)⟩, respectively. The representative paths of AP 3 and AP 4 are π 3 = [s start , s 2 ] and π 4 = [s start , s 1 , s 2 ], respectively. Compared to AP 5 , which is expanded in Iteration 5 and eventually extended to the solution, AP 3 and AP 4 have lexicographically smaller f -values and appear to be more promising. However, the two possible extensions of AP 3 and AP 4 to s goal either violate the weight limit (via [s 2 , s 3 , s 4 , s goal ]) or have large c 1 -values (via [s 2 , s 3 , s 5 , s goal ]), as the algorithm finds out in Iterations 3-4. Without merging, other existing WCSP algorithms, like WC-A*, would represent π 3 and π 4 as two different nodes and spend more search effort.In this section, we show that WC-A*pex always returns a (1 + ε)-suboptimal solution, given a solvable WCSP instance. Note that we say a WCSP instance is solvable if there exists a solution for this WCSP instance (Sec. 2).Lemma 1. If we have g 2 (AP) ≥ g min 2 (s(AP)) on Line 6 or 14, there exists an expanded apex-path pair AP ′ with state s(AP ′ ) = s(AP) and f (AP ′ ) ⪯ (ε,0) f (AP).Proof. This lemma is rephrased from Lemma 2 by Zhang et al. (2022b) , and the same proof applies.For the rest of this section, we use π * = [s * 1 , s * 2 . . . s * ℓ ] to denote an optimal solution for the given WCSP instance, assuming that a solution exists. Note that we have s * ℓ = s goal . We use π * j = [s * 1 , s * 2 . . . s * j ], j = 1, 2 . . . ℓ, to denote the subpath of π * that contains the first j states.Lemma 2. We assume that the given WCSP instance is solvable. At the beginning of each iteration, for any expanded apex-path pair AP, if there exists j ∈ {1, 2 . . . ℓ -1} that satisfies s(AP) = s * j and g(AP) ⪯ c(π * j ), there exists an apex-path AP ′ ∈ Open and k > j that satisfy s(AP′ ) = s * k and g(AP ′ ) ⪯ c(π * k ).Proof. We prove this lemma by induction on j, starting from j = ℓ -1 and going backward. Consider an expanded apexpair AP with s(AP) = s * ℓ-1 and g(AP) ⪯ c(π * ℓ-1 ). When it is expanded, WC-A*pex generates a child apex-path pair AP ′ with state s * ℓ = s goal . We have g min 2 (s goal ) = ∞ because, if s(AP) = s goal , the algorithm terminates on Line 9 and cannot reach Line 10 to update g min 2 (s goal ). We haveg(AP ′ ) = g(AP) + c(⟨s * ℓ-1 , s * ℓ ⟩) ⪯ c(π * ).Since the heuristic h is consistent, we have h(s * ℓ ) = 0 and hence f 2 (AP ′ ) ≤ c 2 (π * ) ≤ W . Therefore, AP ′ is not pruned on Line 15 and then inserted into Open. If AP ′ has been extracted from Open, the algorithm should have terminated. We show that AP ′ is still in Open for the current iteration. Now we assume the lemma holds for j = i + 1. Consider an expanded apex-path pair AP with s(AP) = s * i and g(AP) ⪯ c(π * i ). When expanding AP, one of the child apex-path pairs, denoted as AP ′ , is generated with state s * i+1 . We have g(AP ′ ) = g(AP) + c(⟨s * i , s * i+1 ⟩) ⪯ c(π * i ) + c(⟨s * i , s * i+1 ⟩) = c(π * i+1). We distinguish two cases:1. AP ′ is pruned on Line 15. Since f 2 (AP ′ ) = g 2 (AP ′ ) + h 2 (s * i+1 ) ≤ c 2 (π * ) ≤ W , we must have g min 2 (s * i+1 ) ≤ g 2 (AP ′ ).From Lemma 1, there exists an expanded apexpath pair with state s * i+1 and whose g-value weakly dominates g(AP ′ ) and hence c(π * i+1 ). Because the lemma holds for j = i+1, there exists an apex-path pair AP ′′ ∈ Open with s(AP ′′ ) = s * k and g(AP ′′ ) ⪯ c(π * k ) for some k > i + 1. The lemma holds for j = i. 2. AP ′ is not pruned on Line 15 and is then inserted toOpen with or without merging with another apex-path pair. In either case, an apex-path pair with state s * i+1 and whose g-value weakly dominates c(π * i+1 ) is inserted to Open. The lemma holds if this new apex-path pair is still in Open. If this new apex-path pair has been extracted, either it is pruned or expanded, there is an expanded apex-path pair with state s * i+1 and whose g-value weakly dominates c(π * i+1 ). Because the lemma holds for j = i + 1, the lemma also holds for j = i.Therefore, the lemma holds for all j ∈ {1, 2 . . . ℓ -1}.Theorem 1. WC-A*pex returns a (1 + ε)-suboptimal solution, given a solvable WCSP problem instance.Proof. In the first iteration, there is one apex-path pair, denoted as AP init , in Open. Note that we have s(AP init ) = s * 0 and g(AP init ) ⪯ c(π * 0 ). AP init is then expanded in the first iteration, and, from Lemma 2, Open always contains at least one apex-path pair at the beginning of all future iterations. Therefore, WC-A*pex will not reach Line 17 and returns None. Let π sol and AP sol denote the path returned by WC-A*pex and the apex-path pair that contains π sol , respectively. π sol is a solution because it ends at state s goal and its c 2 -value is not larger than W (otherwise AP sol is pruned on Line 7). Because AP sol is (ε, 0)-bounded, we have(1 + ε) • f 1 (AP sol ) ≥ c 1 (π sol ). If π sol is not (1 + ε)- suboptimal, i.e., c 1 (π sol ) > (1 + ε) • c 1 (π * ), we have f 1 (AP sol ) > c 1 (π * ).From Lemma 2, there always exists an apex-path pair AP ∈ Open and j with s(AP) = s * j and g(AP) ⪯ c(π * j ). We have f (AP) = g(AP)+h(s(AP)) ⪯ c(π * j ) + h(s * j ) ⪯ c(π * ). The algorithm must extract AP before extracting AP sol , and hence we find a contradiction. Therefore, π sol must be a (1 + ε)-suboptimal solution.In this section, we describe some speed-up techniques for an efficient implementation of WC-A*pex. Some of these techniques are also used by existing algorithms like WC-A*, and hence we omit the theoretical results for them.Efficient data structures: Same as WC-A*, we use a bucket queue to implement Open for WC-A*pex. Additionally, for each state s, we use a doubly linked list to keep track of all apex-path pairs in Open with state s. Therefore, WC-A*pex can efficiently iterate over Open[s] for any given state s when checking for merging on Lines 19-25 and efficiently update the doubly linked list when an apex-path pair is extracted from or inserted into Open. Our preliminary results showed that these improved data structures speed up the original implementation of A*pex by an order of magnitude.Early solution update: Similar to WC-A*, we can maintain and update an incumbent solution in WC-A*pex using complementary paths. An apex-path pair AP is pruned if (1 + ε) • f 1 (AP) is not smaller than the c 1 -value of the incumbent solution. With early solution update, WC-A*pex terminates when Open becomes empty and returns the incumbent solution.  
experimental results: 
 In this section, we evaluate WC-A*pex with WCSP instances on road networks from the 9th DIMACS Implementation Challenge: Shortest Path. 2 We investigate WC-A*pex with different ε-values and compare the runtime and node expansions of WC-A*, WC-A*-ε, and WC-A*pex. We implemented WC-A*pex in C++ 3 . We used the C++ implementation of WC-A* provided by the original authors 4 and implemented WC-A*-ε based on it. We choose nine road networks FLA (1.1M states and 2.7M edges), NE (1.5M states and 3.9M edges), CAL (1.9M states and 4.7M edges), LKS (2.8M states and 6.9M edges), E (3.6M states and 8.8M edges), W (6.3M states and 15.2M edges), and CTR (14.1M states and 34.3M edges) from the 2 http://www.diag.uniroma1.it/challenge9/download.shtml. 3 Upon acceptance, the code will be made publicly available. 4 https://bitbucket.org/s-ahmadi/biobj/src/master/. DIMACS data set. The c 1 -and c 2 -values for each edge are the travel time and distance, respectively, both available from the DIMACS data set. In other words, each WCSP instance corresponds to computing a path that is boundedsuboptimal in terms of travel time and with travel distance no larger than a specified limit. For each road network, we use the same 100 s start and s goal pairs used by Sedeño-Noda and Colebrook (2019) and Ahmadi et al. (2021) . Following the literature (Cabrera et al. 2020; Ahmadi et al. 2022b ), for each s start and s goal pair, we generate a WCSP instance with the weight limit W = c lb 2 + δ • (c ub 2c lb 2 ) based on a tightness factor δ, where c lb 2 and c ub 2 are the minimum and maximum c 2 -values of Pareto-optimal paths from s start to s goal , respectively. Conceptually, a smaller δ-value corresponds to a tighter weight limit. For each s start and s goal pair, we use three tightness factors 0.25, 0.5, and 0.75. Therefore, we have 300 WCSP instances for each road network.For each WCSP instance, we evaluate WC-A*-ε and WC- A*pex with three ε-values 0.01, 0.05, and 0.1. Table 1 shows the average and maximum runtimes (in seconds) and node expansions (#exp) of WC-A*, WC-A*-ε, and WC-A*pex over all WCSP instances. The results for WC-A* are shown in the rows with ε = 0. With ε = 0.01, i.e., a 1% suboptimality allowed, WC-A*pex solved the WCSP instances on the largest road network (CTR) faster than WC-A* by more than 11× on average. However, the speed-up of WC-A*-ε with ε = 0.01 compared to WC-A* is only less than 20% on average. This is because WC-A*-ε still needs to expand a large number of nodes to prove an incumbent solution is bounded-suboptimal. The runtimes and node expansions of WC-A*pex are always smaller than the ones of WC-A* and WC-A*-ε with the same ε-value on all road networks, which shows that merging apex-path pairs greatly reduce the runtimes and node expansions.Figure 4 shows the individual runtimes (in seconds) of WC-A*pex and WC-A*-ε for all WCSP instances and εvalues. We use different markers for different δ-values that are used to generate the WCSP instances. The diagonal dashed lines and the numbers along them denote different speed-ups (1×, 10×, and the maximum speed-up) of WC-A*pex over WC-A*-ε . For different δ-values, WC-A*pex shows a similar trend regarding the speed-ups over WC-A*-ε. Although WC-A*pex were slower than WC-A*-ε on easy instances (which both algorithm solved mostly within around 0.1 second), in more time-consuming instances (represented by the points on the top-right corners), WC-A*pex achieved significant speed-ups over WC-A*-ε. 
conclusions: 
 In this paper, we proposed a bounded suboptimal WCSP algorithm called WC-A*pex. WC-A*pex is built on A*pex, a state-of-the-art approximate BOSP algorithm. It computes a (1 + ε)-suboptimal path, for a user-specified ε. Its empirical performance on benchmark road networks highlights two important computational aspects of it. First, huge gains in runtime efficiency-up to an order of magnitude-are possible with only a small compromise-within 1% suboptimality-on the cost of the solution. Second, the use of the merged representations of paths with similar costs and weights reduces the number of node expansions and is critical to the success of WC-A*pex over WC-A* and WC-A*-ε.In future work, we intend to generalize WC-A*pex to the case of multiple costs, multiple weights (Skyler et al. 2022) , or both. Another direction is to enhance WC-A*pex with recent algorithmic advancements (Zhang et al. 2022a ) and develop it towards an anytime algorithm. 
 
 Appendix: This W is not to be confused with the W used for the suboptimality bound in certain bounded suboptimal search algorithms. 


Decision: The paper combines two existing algorithms to solve the problems at hand. The reviewers agree that the contribution is interesting and the experimental performance shows the value of the approach, but opinions diverge on whether the contribution is sufficiently novel to warrant publication. All reviewers agree that the novelty of the contribution is limited, with one reviewer arguing that the combination is fairly straightforward, the problem at hand is very similar to the bi-objective case and the experimental evaluation oversells the results by mentioning orders of magnitude of difference while the runtimes are in general very short to begin with (for example 0.07s vs 0.02s). On the other hand, one reviewer pointed out that the combination required a nontrivial strategy on when to merge states and that they understood the order of magnitude claim to rather be relative to optimal algorithms, and one reviewer highlighted the high relevance of the topic for many practical applications.

In my opinion the positive aspects of the paper slightly outweigh the negative aspects and I thus recommend acceptance, but this is a weak recommendation since the limited novely is a noticeable concern and I agree that it is in general hard to glean too much from experiments where the runtime is usually less than a second, but this may also just be an unfortunate limitation of the available benchmarks. In case of rejection I support the suggestions of one of the reviewers that the authors could turn the paper into a short paper which would be a better fit for the size of the contribution.

Regarding poster vs oral presentation, I rather suggest a poster presentation since I could imagine that it is easier to show how the algorithm works on a poster where much information can be displayed at once, but this is also a weak recommendation.

Reviews: review: strength_weakness: strength_weakness: Novelty

If I understood correct, the main contribution is, briefly, an algorithmic idea where the algorithm merges two states if they are "similar enough". This makes sense. However it seems that previous work (A*pex) used the same idea in the bi-objective case. So this leaves me wondering whether the contribution here is truly new, or an adaptation of an existing and very related method.

The authors also claim a novelty on the data structures used. But as above, it seems that very similar data structures have appeared for the bi-objective problem as well.

Experiments

The paper claims orders of magnitude improvements, which sets very high expectations from the reader side. The experiments indicate promising results, but I feel the experiments do not match the expectations.

The numbers in Table 1 seem impressive at face value. But then the runtime of the competing method (WC-A*) can something be very low (subseconds) on some families of problems. Are these reasonable comparisons? For example, if the avg runtime is 0.07 of the competitor, and yours is 0.02, it is technically a three times speed up, but this is such a small runtime that is hard to see the value. Nevertheless there are cases with longer runtimes, and here the method seems to do well, and does so more consistently.

Is average runtime appropriate? This hides the variance, so it is hard to see the advantage. Perhaps a geometric mean could be useful in this case.

The benchmarks are not motivated, the authors only point out that other papers use them. But are these good benchmarks for comparison? The impact of the threshold on the weight plays an important role here, so I also wonder if this can be chosen in some good and principled way.

There are some impressive runtime improvements, but if I am reading Figure 4 correctly, it also seems that there are cases where there are rather significant slowdowns. It is also not easy to fully process Figure 4, the green cloud of points obstruct seeing the other two parameters. Perhaps it would be better to have one smaller picture for each parameter setting (delta).

"Our preliminary results showed that these improved data structures " -> this seems like a natural point to experiment with properly so that we are sure about the benefits over relying on a preliminary study.

Writing

Overall the paper reads well. I am nevertheless struggling to see the big difference between the bi-objective version and this constrained version. The difference is that the second objective is now given as a constraint rather than the objective, correct? If this is the case, then I would think that it would be easier if the paper presents the work in that way, rather than introducing two different problems. This could help lower the mental load required from the readers, and also saves space.

Minor: 

a "different technique" to speed up the search is mentioned in the introduction. It is not clear if this is referring to something new or the previous text. 

"dominated by at least one blue dot" -> there is only one blue dot on the figure. I could see that maybe there are two dots that have a blue circle around, it needs to be clarified if these count as blue dots.
questions: questions: Can you please address my concerns about the novelty, experiments, and writing (see above)?

Furthermore, can you comment on whether you would release the source code?
strength_weakness: strength_weakness: I don't have any major weaknesses. The significance of the new problem/method is not the largest perhaps, but I still think it is enough. 

I did find the way Lemma 1 and Lemma 2 are described and proven somewhat difficult to understand. I am fairly convinced they are correct, but I struggled to understand parts of them. In particular, I felt they could be more explicit about how the proof was working.

Part of the issue with Lemma 2 was the backwards induction was a bit hard to follow. The approach makes sense in hindsight, but I think it could be clarified more upfront. First, I think the Lemma statement would be clearer as

"For any number of expansions n, if at the beginning of the iteration there exists an expanded AP such that s(AP) = s*_j for some j and ..., then there exists a AP' \in Open such that for some k > j ..."

It's an equivalent statement to what is there, but I think it more clearly identifies the assumptions and implication. I don't think that phrasing I gave is perfect either (the first part still feels like it could be improved), but I feel it helps understand better the rest of the proof.

Next, I found the inductive step hard to understand. I think, the proof needs to be clearer that it is considering the iteration right after AP was expanded, and that once it is true after that step, it remains true for the rest of the search. That last point could also be better stated in the base case.

For the Proof of Lemma 1, it would also help if it was clearer that the proof was by contradiction earlier on. The part starting with "Because AP_sol is not (\epsilon, 0) bounded ... " was not obvious until I got to the end of the proof and realized that the proof was by contradiction. Perhaps stating "The proof is by contradiction. Assume \pi_sol is not (\epsilon, 0) bounded" and then proceeding to derive the contradiction would help with readability.

Beyond that, I had no major issues. Perhaps ideally the methods would be tested on a structurally different problem (ie. not road networks), but what is there is sufficient. Similarly, it would be nice to have an extra image like Figure 4 comparing WC-A*pex with some epsilon >= 0.01 (I don't care which), vs WC-A* with epsilon=0, just to clarify if the main benefit of bounded suboptimality is that it makes the biggest improvements on the hardest problems. I would be surprised otherwise though. More importantly, it would be interesting to see if bounded suboptimal WC-A*pex is faster or slower than optimal WC-A* on the easy problems.


Minor Concerns
- I don't understand why in the base case of Lemma 2, g_2^min(s_goal) is infinity. I understand that s(AP) \neq goal as stated on the next line since we already said that s(AP) = s_{\ell - 1}. But s_goal will have been generated tat this point, so it should be non-infinite. I think this is related to the point above that throughout this proof, it is easy to get confused about if we are at the point where AP was just expanded or not.
- I think Table 1 is averaged over all deltas, which seems a bit odd, but is not a major issue. However, if this is the case, it should be mentioned.
questions: questions: 1) Any comments on whether bounded suboptimal WC-A*pex is faster or slower than optimal WC-A* on the easy problems?


Post-Response: Thank you for your response. I think including those clarifications would be useful in future iterations of the work.
strength_weakness: strength_weakness: W1. The proposed methodology is quite incremental and the applied algorithmic and proof concepts are very similar to the ones used for WC-A* and A*pex.

W2. The experimental study only considers two very closely related metrics, namely distance and travel time. Thus, good approximation results are rather unsurprising. In the introduction, examples as electric vehicle and bicycle route planning were mentioned, where energy consumption and height difference play an important role. It would be more interesting and expressive to also consider such metrics in the evaluation. The motivation for minimizing travel time under a distance constraint  is rather weak in my opinion. Note that these two metrics were given in the DIMACS instances not for the purpose of bi-objective path search but to study the performance differences of shortest path planning techniques when using travel time or distance.
questions: questions: Q1. Could you motivate the usage of a doubly linked list to keep track of the elements in open over a data structure with faster access times for individual elements, as e.g. a skip list? For merge operations, the design choice makes a lot of sense but for individual updates, iteration might still be costly.