Tightest Admissible Shortest Path

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 11:55:08

Abstract: The shortest path problem in graphs is fundamental to AI. Nearly all variants of the problem and relevant algorithms that solve them ignore edge-weight computation time and its common relation to weight uncertainty. This implies that taking these factors into consideration can potentially lead to a performance boost in relevant applications. Recently, a generalized framework for weighted directed graphs was suggested, where edge-weight can be computed (estimated) multiple times, at increasing accuracy and run-time expense. We build on this framework to introduce the problem of finding the tightest admissible shortest path (TASP); a path with the tightest suboptimality bound on the optimal cost. This is a generalization of the shortest path problem to bounded uncertainty, where edge-weight uncertainty can be traded for computational cost. We present a complete algorithm for solving TASP, with guarantees on solution quality. Empirical evaluation supports the effectiveness of this approach.

Main paper: 
 introduction: 
 Finding the shortest path in a directed, weighted graph is fundamental to artificial intelligence and its applications. The cost of a path is the sum of the weights of its edges. Informed and uninformed search algorithms for finding shortest (minimal-cost) paths are heavily used in planning, scheduling, machine learning, constraint optimization, etc.Graph edge-weights are commonly assumed to be available in negligible time. However, this does not hold in many applications. When weights are determined by queries to remote sources, or when a massive graph is stored in external memory (e.g., disk) then the order in which edges are visited-accessing external memory-needs to be optimized (Vitter 2001; Hutchinson, Maheshwari, and Zeh 2003; Jabbar 2008; Korf 2008b Korf ,a, 2016;; Sturtevant and Chen 2016) . Similarly, when edge-weights are computed dynamically using learned models, or external procedures, it is beneficial to delay weight evaluation until necessary (Dellin and Srinivasa 2016; Narayanan and Likhachev 2017; Mandalika, Salzman, and Srinivasa 2018; Mandalika et al. 2019) .Instead of delaying and re-ordering expensive edgeweight evaluations, a recent formalization focuses instead on using multiple weight estimators (Weiss and Kaminka 2023b; Weiss, Felner, and Kaminka 2023) . Edge-weights are replaced with an ordered set of estimators, each providing lower and upper bounds on the true weight. Incrementally, subsequent estimators can tighten the bounds, but at increasing computation time. A search algorithm may quickly compute loose bounds on the edge-weight, and invest more computation on a tighter estimator later in the process.For example, consider finding the fastest route between two cities, where edges and their weights represent roads and travel times, resp. First rough bounds on travel time can be estimated from fixed distances and speed limits (say, from a local database). For more accuracy, Google Maps, which considers additional road factors and traffic data, can be queried online. Even more accuracy can be achievedat increased run-time-by further considering vehicle attributes together with road characteristics, which can be highly relevant for large and heavy vehicles such as trucks and buses (PTV-Group 2023).Having multiple weight estimators for edges is a proper generalization of standard edge-weights, and raises several shortest path problem variants. The classic singular edgeweight is a special case, of an estimator whose lower-and upper-bounds are identical. However, since the true weight may not be known (even applying the most expensive estimator), other variants of the shortest path problems involve finding paths that have the best bounds on the optimal cost.In this paper, we introduce the tightest admissible shortest path (TASP) problem, which is an important shortest-path problem variant in graphs with multiple-estimated edgeweights. Its solution provides an answer to the question: what is the tightest suboptimality factor w.r.t. the optimal cost that can be achieved given that edge-weights have uncertainty bounds? We show that solving TASP can be reduced to solving two simpler problems: The shortest path tightest lower bound (SLB), that was introduced and solved optimally by the BEAUTY algorithm in (Weiss, Felner, and Kaminka 2023) ; and the shortest path tightest upper bound (SUB) problem, which we define and solve in this paper.To solve SUB, we present BEAST, an uninformed search algorithm based on uniform-cost search (UCS, a variant of Dijksra's algorithm) (Dijkstra 1959; Felner 2011) , that takes advantage of prior information about the solution of SUB. We then use it to construct BEAUTY&BEAST, an algorithm that solves TASP problems by exploiting coupling between the problems of SLB and SUB. Experiments demonstrate the effectiveness of BEAUTY&BEAST compared to the base-line that solves SLB and SUB separately.Our main contributions in this paper are threefold: (1) The introduction of TASP as a natural extension of the familiar shortest path problem to settings with bounded edgeweight uncertainty, and its solution by solving the related problems SLB&SUB. (2) The BEAST algorithm that finds optimal solutions for SUB. (3) The idea that information obtained from solving either SLB or SUB can be used to enhance the solution of the other (which is demonstrated by BEAUTY&BEAST). 
background and related work: 
 This paper belongs to a line of works that consider the run-time of edge-evaluation to be non-negligible, within the context of graph search. It is thus useful to consider the overall edge-evaluation time T e and its decomposition as T e = τ e × n e , where τ e is the average edge-evaluation time and n e is the total number of edge-weight computations conducted over all edges throughout the search. In contrast to standard search algorithms that assume that τ e is negligible and thus focus on pure search time, algorithms in the setting discussed in this paper utilize various techniques in order to reduce T e , sometimes at the expanse of increased search effort (e.g., more node expansions), with the aim to minimize overall run-time.In the domain of robotics it is common to have shortest path problems in robot configuration spaces, where τ e is typically high, as in these applications edge existence and cost are determined by expensive computations for validating geometric and kinematic constraints. A well known technique in these cases is to reduce n e by explicitly delaying weight computations (Dellin and Srinivasa 2016; Narayanan and Likhachev 2017; Mandalika, Salzman, and Srinivasa 2018; Mandalika et al. 2019 ), even at the cost of increasing search effort. Related challenges arise in planning, where action costs can be computed by external (potentially expensive-tocompute) procedures (Dornhege et al. 2012; Gregory et al. 2012; Frances et al. 2017) , or when multiple heuristics have different run-times (Karpas et al. 2018) .There are also approaches that aim to reduce τ e , instead of n e . When the graph is too large to fit in random-access memory, it is stored externally (i.e., disk). External-memory graph search algorithms optimize the memory access patterns for edges and nodes, to make better use of faster memory (caching) (Vitter 2001; Hutchinson, Maheshwari, and Zeh 2003; Jabbar 2008; Korf 2008b Korf ,a, 2016;; Sturtevant and Chen 2016) . This reduces τ e by amortizing the computation costs, but still assumes a single computation per edge.The approach we take in this paper follows a recent line of work-that is complementary to those described abovewhich focuses on using multiple edge estimators (Weiss and Kaminka 2023b; Weiss, Felner, and Kaminka 2023) , specifically for estimating edge-weights. In this framework the weight of each edge can be estimated multiple times, successively, at increasing expense for greater accuracy. The idea is that in some cases cheaper weight estimates can be used instead of the best and most expensive estimates, thus decreasing τ e , and although n e might increase, the overall edge-evaluation time T e might still decrease.Lastly, there are also works that consider weight uncertainty in graphs, regardless of edge-computation time. These include, e.g., the case where weights are assumed to be drawn from probability distributions (Frank 1969) , and the usage of fuzzy weights (Okada and Gen 1994 ) that allow quantification of uncertainty by grouping approximate weight ranges to several representative sets. All these lines of work ignore the weight computation time, in contrast to the work reported here.3 Shortest Path with Estimated Weights Graph Definitions. A weighted digraph is a tuple (V, E, c), where V is a set of nodes, E is a set of edges, s.t. e = (v i , v j ) ∈ E iff there exists an edge from v i to v j , and c : E → R + is a cost (weight) function mapping each edge to a non-negative number. Let v i and v j be two nodes inV . A path π = ⟨e 1 , . . . , e n ⟩ from v i to v j is a sequence of edges e k = (v q k , v q k+1 ) s.t. k ∈ [1, n], v i = v q1, and v j = v qn+1 . The cost of a path π is then defined to be c(π) := n k=1 c(e k ). The Goal-Directed Single-Source Shortest Path (GDS 3 P ) problem involves finding a solution, which is a path π from the source node to a goal node, with minimal c(π), denoted as C * . A solution π for a GDS 3 P problem is said to be a B-admissible shortest path if c(π) is bounded by a suboptimality factor B, i.e.,c(π) ≤ C * × B.(1)If B = 1, then π is a shortest path.We recall several definitions that were introduced in (Weiss, Felner, and Kaminka 2023) . Definition 1. A cost estimators function Θ, for a set of edges E and with a cost function c : E → R + , maps every edge e ∈ E to a finite and non-empty sequence of weight estimation procedures, Θ(e) := (θ 1 e , . . . , θ k(e) e), k(e) ∈ N,where estimator θ i e , if applied, returns lower-and upperbounds (l i e , u i e ) on c(e), such that 0 ≤ l i e ≤ c(e) ≤ u i e < ∞). Θ(e) is ordered by the increasing running time of θ i e , and the bounds monotonically tighten, i.e., [l j e , u j e ] ⊆ [l i e , u i e ] for all i < j. Definition 2. An estimated weighted digraph (EWDG) is a tuple G = (V, E, c, Θ), where V, E are sets of nodes and edges, resp., c is an un-observable cost function for the edges in E, and Θ is a cost estimators function for E. . For a path π, the tightest path lower bound and tightest path upper bound w.r.t. Θ follow, respectively, from the tightest edge bounds defined above.EQUATIONIntuitively, l Θ(π) and u Θ(π) are the best estimations that are provided by Θ for the true cost of the path π, and they satisfy l Θ(π) ≤ c(π) ≤ u Θ(π) .Shortest Path Problems. Regular weighted digraphs are a special case of EWDGs where for every edge e, there is a single estimation procedure θ 1 e = (c(e), c(e)) with lower and upper bounds that are identical to the weight c(e). In this special case, a shortest tightly-bounded path π in the graph is an optimal solution for a GDS 3 P problem. However, in the general case of EWDGs, multiple estimators exist per edge, and we are not guaranteed that every weight can be estimated precisely, even if all estimators for it are used, as the best estimator available for an edge can still deviate from the exact true cost provided by c. Thus, several variants of the shortest path problem exist, which correspond to different tightest bounds for the shortest path.In this paper we focus on the problem of finding the smallest possible suboptimality factor on the optimal cost C * as well as finding a path π that achieves it, in a given EWDG. In order to properly define this problem, we first have to extend the notion of B-admissibility to EWDGs. Indeed, Inequality (1), which characterizes the suboptimality factor, requires knowing exact edge costs to obtain c(π) and C * , but the cost function c is un-observable in EWDGs. Instead, we introduce an extension (Def. 4) that uses edge cost estimates that are provided by Θ. The extension relies on L * , which is the best lower bound that can be derived for C * , that was introduced in (Weiss, Felner, and Kaminka 2023) :L * := min π ′ {l Θ(π ′ ) | π ′ is a path from v s to v ∈ V g }. (4) Definition 4. Let P = (G, v s , V g ), where G is an EWDG with cost estimators function Θ, v s ∈ V is the source node and V g ⊂ V is a set of goal nodes. A solution π is said to be a B-admissible shortest path w.r.t. Θ if the following holds u Θ(π) ≤ L * × B.(5)Note that u Θ(π) is the tightest upper bound for c(π) w.r.t. Θ (Eq. ( 3)), so c(π) ≤ u Θ(π) holds. Similarly, L * is the tightest lower bound for C * w.r.t. Θ (Eq. ( 4)), so L * ≤ C * holds. Thus, if Inequality (5) holds, thenEQUATIONis necessarily satisfied. Namely, standard B-admissibility is assured by B-admissibility w.r.t. Θ.Next, we define the main problem addressed in this paper. Problem 1 (TASP, finding B * ).Let P = (G, v s , V g ), where G is an EWDG with cost estimators function Θ, v s ∈ V is the source node and V g ⊂ V is a set of goal nodes. Let B * be the tightest B-admissibility factor w.r.t. Θ, i.e., B * := min π ′ {B | u Θ(π ′ ) ≤ L * × B, π ′ is a solution}. (7)The Tightest Admissible Shortest Path (TASP) problem is to find B * as well as a solution π that its B-admissibility factor is B * . If B-admissibility cannot be obtained for any finite value of B, or no solution exists, then B * = ∞ should be returned.Next, we describe two problems that are related to Prob. 1. The first problem among the two deals with finding a shortest path w.r.t. lower bounds. It was introduced in (Weiss, Felner, and Kaminka 2023) , and we review its definition here.Problem 2 (SLB, finding L * ). Let P = (G, v s , V g ), where G is an EWDG with cost estimators function Θ, v s ∈ V is the source node and V g ⊂ V is a set of goal nodes. The Shortest path tightest Lower Bound (SLB) problem is to find a solution π, such that π has the lowest tightest path lower bound of any path from v s to v ∈ V g , w.r.t. Θ, i.e., l(π) = L * .The second problem, which we define here for the first time, is complementary to Prob. 2 and deals with finding a shortest path w.r.t. upper bounds. Problem 3 (SUB, finding U * ). Let P = (G, v s , V g ), where G is an EWDG with cost estimators function Θ, v s ∈ V is the source node and V g ⊂ V is a set of goal nodes. The Shortest path tightest Upper Bound (SUB) problem is to find a solution π, such that π has the lowest tightest path upper bound of any path from v s to v ∈ V g , w.r.t. Θ, i.e., u(π) = U * , withU * := min π ′ {u Θ(π ′ ) | π ′ is a path from v s to v ∈ V g }. (8)We next show that Problems 1-3 are all generalizations of standard GDS 3 P (see Thm. 1 below). In addition, they are also related to each other, in that their solutions are linked. Indeed, Thm. 2 below shows that the best lower bound for C * (Prob. 2) and the best upper bound for C * (Prob. 3) can be used to calculate the best suboptimality factor B * (Prob. 1). Thm. 2 also shows that an optimal solution path for Prob. 3 is also an optimal solution path for Prob. 1. The proof of Thm. 2 also implies that if U * > L * = 0 it is impossible to prove B-admissibility at all. Theorem 1 (Generality). Problems 1, 2 and 3 are generalizations of a GDS 3 P problem.Proof. Any GDS 3 P problem can be formulated as Problem 1, or 2, or 3, by considering the special case where each edge has one estimator (namely, k(e) = 1 for every e), that returns the exact cost (i.e., l 1 e = c(e) = u 1 e ). In this special case it holds that L * = C * = U * and B * = 1 (in the case of L * = U * we set B * = 1 even if C * = 0 as there is no uncertainty at all). Therefore, the cost of the solutions of these problems are all equal to the minimum cost C * , hence are by definition shortest paths.Theorem 2 (B * = U * /L * ). Let P = (G, v s , V g ), where G is an EWDG with cost estimators function Θ, v s ∈ V is the source node and V g ⊂ V is a set of goal nodes. If L * > 0 for P , then a solution path π for P is a tightest admissible shortest path iff it is a shortest path tightest upper bound (i.e. a solution that achieves U * ). Furthermore, B * = U * /L * .Proof. Assume L * > 0 for P . By definition (of TASP and of B * ) a solution π is a tightest admissible shortest path iff it achieves the lowest B-admissibility factor, i.e., iff it satisfiesEQUATION)Since L * does not change with different choices of π ′ in the argmin expression of Eq. ( 9), it follows that By definition of U * (Eq. ( 8)), a solution π satisfying Eq. ( 10) achieves u Θ(π) = U * . On the other hand, a solution satisfying Eq. ( 8), also achieves B * , as implied by Eq. ( 9). Thus, π is a tightest admissible shortest path iff it is a shortest path tightest upper bound (SUB). Furthermore, it holds thatEQUATIONB * = U * /L * .Corollary 1. Thm. 2 shows how to obtain an optimal solution for Prob. 1 from optimal solutions for Problems 2 and 3. Thus, any algorithmic improvement to solving either Prob. 2 or Prob. 3 directly affects the efficiency of solving Prob. 1.Next, we use an example taken from (Weiss, Felner, and Kaminka 2023) with slight modification and supplement it to illustrate the meaning of the solutions for Problems 1-3. Example 1. Consider the estimated weighted digraph G = (V, E, c, Θ) provided in Fig. 1 . Given the graph above, we may define the problem P = (G, v s , V g ) with v s = v 0 and V g = {v 3 , v 4 }, i.e., searching for paths from v 0 to either v 3 , or v 4 . Then, the unknown optimal cost is C * = c(π * ) = c 01 + c 14 = 9 with π * = ⟨e 01 , e 14 ⟩; the tightest lower bound for C * is L * = l Θ(π1) = l 2 02 + l 1 24 = 7 with π 1 = ⟨e 02 , e 24 ⟩ (the SLB solution); the tightest upper bound for C * is U * = u Θ(π1) = u 1 01 + u 2 14 = 10 with π 2 = π * (the SUB solution); and tightest admissibility factor is B * = U * /L * = 10/7 with π 3 = π 2 (the TASP solution). 
algorithms: 
 As indicated in Corollary 1, we can obtain optimal solutions for TASP problems by optimally solving the corresponding SLB and SUB problems. SLB was studied in (Weiss, Felner, and Kaminka 2023) , which introduced BEAUTY, a complete algorithm that finds optimal solutions for it. Hence, this section focuses on solving SUB, particularly towards solving TASP in a manner that takes advantage of information already obtained during the solution of SLB.In Subsection 4.1 we present BEAST (Branch&bound Estimation Applied to Searching for Top, Alg. 1), a complete algorithm that finds optimal solutions for SUB problems. BEAST extends UCS to dynamically apply cost estimators during a best-first search w.r.t. upper bounds of edge costs, and it aims to reduce the number of expensive estimators used, by utilizing both cheaper estimates and prior information on U * . BEAST is thus particularly suitable to be used whenever prior information on U * is available.We note that BEAST has several analogies to BEAUTY, but also several fundamental differences which are due to the fact that upper bounds tighten towards lower values whereas lower bounds tighten towards higher values. Thus, cheaper (and looser) estimates cannot be used analogously to guide the search in minimization of tight upper bounds (SUB) compared to minimization of tight lower bounds (SLB). Specifically, BEAUTY first uses a looser lower bound to guarantee that a more expensive lower bound estimate is required. This can be done since if a path π 1 to a node n and its tightest path lower bound l Θ(π1) are known, and a new path π 2 to n is considered, then if a loose lower bound of c(π 2 ) is already greater than l Θ(π1) , then necessarily l Θ(π2) > l Θ(π1) (i.e., π 1 is better). Hence, more expensive estimates for π 2 can be avoided. In contrary, this cannot be done analogously with looser upper bounds. Indeed, knowing that a loose upper bound of c(π 2 ) is already greater than u Θ(π1) does not imply that u Θ(π2) > u Θ(π1) . Hence, more expensive estimates for π 2 cannot be avoided in the same way. For this reason, BEAST makes use of a combination of upper and lower bounds to try to avoid expensive estimates (see full description in Subsection 4.1).In Subsection 4.2 we introduce BEAUTY&BEAST (Alg. 2), a complete algorithm that finds optimal solutions for TASP problems, that first uses BEAUTY to optimally solve SLB, and then uses BEAST, together with prior information already obtained on U * , to optimally solve SUB.Algorithm 1 receives an SUB problem instance and one hyper-parameter u prune . For simplicity we will first describe a base case where u prune is set to ∞, and therefore has no effect and can be ignored. The relevant instructions using u prune are colored in blue (Lines 12, 15) and should be ignored for now. We will come back to this parameter later.Base Setting. BEAST is structurally similar to UCS. It activates a best-first search process using the standard OPEN and CLOSED lists. Nodes n in OPEN are prioritized by g u (n) which is always equal to the optimal upper bound to node n along the best known path (similar to using g(n) for ordering nodes in UCS in regular graphs, which is done according to optimal cost). The best such node n is chosen for expansion in Line 4, and its successors are added in the loop of Lines 8-19. When a goal node n is found in Line 5, the solution path π ending in n and its tight upper bound g u (n) = U * are returned (Thm. 3).The main difference of BEAST over UCS is in the duplicate detection mechanism performed when evaluating the cost of a new edge e that connects n to its successor s. In UCS, the exact edge cost c(e) is immediately obtained and used to update the path cost that ends in s. In BEAST, we iterate over the different estimators θ i e for edge e (Lines 12-13). In each iteration g u (n) + l(e) serves as a lower bound for the tightest path upper bound of the path to s given the current estimator (Line 13). Namely, the tight upper bound is used up to node n and a lower bound is used for the edge e from n to s. Now such a path can be already pruned earlier if its current lower bound for the tight upper bound (using the current estimator) will not improve the best known path to s (g u (s)). In that case we will not need to further activate more expensive estimators. Thus, if g u (n) + l(e) ≥ g u (s), Insert s into OPEN with key g u (s) and parent n 20: return ∅, ∞ the while statement (Line 12) ends. Then, ordinary duplicate detection is performed in Lines 14-19.Algorithm 1: BEAST Input: Problem P = (G, v s , V g ),We emphasize that in case the while loop (Line 12) terminates due to g u (n) + l(e) ≥ g u (s) being satisfied, then necessarily gu = g u (n) + u(e) ≥ g u (s) will be satisfied as well and the path will be (justifiably) pruned. On the other hand, notice that u(e) cannot be used in place of l(e) for early pruning, since upper bound estimates tighten towards lower values. See Example 2 for a demonstration of using BEAST in its base setting.Example 2. Consider calling BEAST with u prune = ∞ (i.e., base setting) on P from Example 1. Tracing its run, at the first iteration of the outer while loop v 0 is removed from OPEN, θ 1 e01 , θ 1 e02 and θ 2 e02 are invoked, and v 1 , v 2 are inserted to OPEN with keys 4, 5. At the second iteration v 1 is removed from OPEN, θ 1 e14 , θ 2 e14 are invoked, and v 4 is inserted to OPEN with key 10. At the third iteration v 2 is removed from OPEN, θ 1 e23 , θ 2 e23 and θ 1 e24 are invoked, and v 3 is inserted to OPEN with key 13. At the forth iteration v 4 is removed from OPEN and BEAST returns ⟨e 01 , e 14 ⟩, 10.Remark 1. In its base setting BEAST eventually uses the best estimates for edges leading to new nodes, thus it can be modified to directly jump to the best estimates in these cases. This was left out for simplicity of the pseudo-code.Enhanced Setting. We now consider the enhanced setting where u prune is set to some constant value (not ∞). In this setting u prune serves as an upper threshold that limits the search, similarly to bounded cost search (Stern et al. 2014) . This manifests in two aspects. First, u prune is used as an upper threshold to exit the while loop (Line 12) and avoid activating more expensive estimators in case the tight upper bound to s is determined to be greater than u prune . This is done in Line 12 where the condition g u (n) + l(e) ≤ u prune is tested, and if not fulfilled it breaks the loop. As explained in the base setting, g u (n) + l(e) serves as a lower bound to the tight upper bound to s and can thus facilitate early stopping. Second, u prune is used as an upper threshold to prune (and not add to OPEN) any node with upper bound > u prune . This is done in Line 15.The primary purpose of using u prune with U * ≤ u prune < ∞ is to avoid applications of redundant (and potentially expensive-to-compute) estimators. Additionally, it can decrease the size of OPEN, which implies less insertion operations and cheaper insert/delete operations. Since U * is unknown, setting this hyper-parameter to a meaningful value requires prior information. Practically, such information can be achieved by obtaining a suboptimal solution with u sub ≥ U * , and using it to set u prune = u sub .Finally, in case U * ≤ u prune < ∞ is satisfied then a solution path π will be found (if a solution exists) and it will be returned together with its tight upper bound g u (n) = U * (Thm. 3). On the other hand, in case u prune < U * is satisfied then ∅, ∞ are returned (Thm. 4). See Example 3 for a demonstration of using BEAST in its enhanced setting.Example 3. Consider calling BEAST with u prune = 4 (i.e., enhanced setting, u prune < U * = 10) on P from Example 1. Tracing its run, at the first iteration of the outer while loop v 0 is removed from OPEN, θ 1 e01 , θ 1 e02 and θ 2 e02 are invoked, and v 1 is inserted to OPEN with key 4. At the second iteration v 1 is removed from OPEN, θ 1 e14 is invoked. At the third iteration OPEN is empty and BEAST returns ∅, ∞.Now consider calling BEAST with u prune = 11 (i.e., enhanced setting, u prune ≥ U * = 10) on P from Example 1. Its run is identical to the run from Example. 2, with the same output, except that at the third iteration θ 2 e23 is not invoked. Next, we provide the theoretical guarantees for BEAST.Theorem 3 (Conditional Completeness and Optimality, Prob. 3). BEAST, with u prune ≥ U * , returns a shortest path tightest upper bound π and U * , if a solution exists for P . In case no solution exists, BEAST returns ∅, ∞.Proof. First, it is straightforward to see that every node encountered by BEAST after the initial node is a successor of another node encountered during the search, as new nodes are only introduced in Line 8. Additionally, every node inserted into OPEN (except the initial node) is saved with a pointer to its parent node. Hence, whenever a goal node is found (at Line 5), it can necessarily be traced back to the initial node via a series of connected nodes, i.e., a valid solution path is returned at Line 6.Second, BEAST inspects nodes that are removed from OPEN by best-first order w.r.t. upper bound of path cost. Since finding a goal node at Line 5 terminates the search, it is assured that the path leading to the first goal node found will be returned. Hence, the solution returned necessarily has the best (lowest) upper bound of path cost out of all the paths inspected by BEAST.It remains to be shown that the search is systematic, namely that every path with tight upper bound up to u prune is inspected by BEAST; and that every edge encountered during the search is either tightly (fully) estimated, or it is at least estimated in a manner that enables BEAST to determine that it is not part of the solution path.Consider any successor s of a node n that is popped from OPEN. If the node s is encountered for the first time, then at first g u (s) ← ∞ is set at Line 10, so the condition g u (n) + l(e) < g u (s) at Line 12 is never satisfied. This means that the edge e leading to s will either be tightly (fully) estimated in case the current path to s has tight upper bound smaller or equal to u prune , or otherwise the tight upper bound to s is greater than u prune . Since u prune ≥ U * is assumed, this means that this path is not relevant and can be safely ignored. Indeed, in this case it is rightfully pruned in Line 15. If the node s was already encountered earlier in the search, then the same mechanism described above applies, but additionally we have to consider the condition g u (n) + l(e) < g u (s) at Line 12. In case it is not satisfied then this means that a better path was already found to s so it can be safely ignored, and indeed it is pruned in Line 15.Lastly, since we have shown that the search up to tight upper bound u prune is systematic, and considering that each edge has a finite number of estimators where each of them has finite run-time, BEAST necessarily terminates in finite time either when an optimal solution is found and returned (Line 6) with U * , or when the search is exhausted up to tight upper bound u prune and BEAST reports that no solution exists (Line 20). Note that in the latter case the assumption u prune ≥ U * implies that u prune must have been set to ∞, so no solution at all exists. Hence, if u prune ≥ U * holds, BEAST is complete and returns an optimal solution.Theorem 4 (Soundness, Prob. 3). For any value of u prune , if ∅, ∞ are returned by BEAST then no solution exists for P with tight upper bound that is smaller or equal to u prune . Conversely, if BEAST returns a solution then it is correct.Proof. Following the proof of Thm. 3, since the search is systematic up to tight upper bound u prune , it follows that if u prune < U * holds then all paths with tight upper bound greater than u prune will be pruned, and since every solution has at least tight upper bound U * , the search will necessarily terminate with ∅, ∞. The other direction, i.e., u prune ≥ U * , is assured by Thm. 3.Algorithm 2 receives a TASP problem instance, and returns an optimal solution for it (Thm. 5). It works by first calling BEAUTY on P (Line 1). If no solution is found then by the completeness of BEAUTY no solution at all exists, and ∅, ∞ are returned (Lines 2-3). Otherwise, the tightest upper bound of the solution found by BEAUTY, u(π SLB ), is obtained (Line 4). In case L * = u(π SLB ) then necessarily L * = C * = U * and then π SLB and B * = 1 are returned (Line 5-6). Otherwise, BEAST is called on P (Line 7) with u prune = u(π SLB ), which is necessarily greater or equal to U * , and thus by Thm. 3 a shortest path tightest upper bound Algorithm 2: BEAUTY&BEAST Input: Problem P = (G, v s , V g ), where G is an estimated weighted digraph with cost estimators function Θ Output: Path π * , bound B * 1: π SLB , L * ← Solve SLB for P using BEAUTY2: if π SLB = ∅ then 3: return ∅, ∞ 4: u(π SLB ) ← u Θ(π SLB ) // Get the upper bound of π SLB 5: if L * = u(π SLB ) then 6:return π SLB , 1 7: π * , U * ← Solve SUB for P using BEAST, u(π SLB ) 8: if L * = 0 and U * > 0 then 9: return π * , ∞ 10: return π * , U * /L * is returned. If U * > L * = 0 then the shortest path tightest upper bound that was found, π * , is returned together with ∞ (Line 8-9). Otherwise π * and B * = U * /L * are returned. Remark 2. Note that in Alg. 2 BEAUTY can be replaced by any algorithm that solves SLB optimally. Moreover, it can be replaced by an anytime algorithm, and then each time the lower bound or upper bound are improved (tightened) they can be translated to a tightened B.Theorem 5 (Completeness and Optimality Prob. 1). BEAUTY&BEAST is complete. Furthermore, if a solution exists for P then a tightest admissible shortest path π andB * are returned (if U * > L * = 0 holds, then B * = ∞).The proof follows directly from the completeness and optimality of BEAUTY and BEAST, and from Thm. 2. 
empirical evaluation: 
 The theoretical guarantees of BEAST (base setting) and BEAUTY&BEAST (enhanced setting) assure optimality and completeness, but do not provide information about their runtime performance. We therefore empirically evaluate the algorithms in diverse settings, based on AI planning benchmark problems that were modified to have multiple action-cost estimators, so that these induce TASP problems.The set of problems was taken from a collection of IPC (International Planning Competition) benchmark instances 1 . Starting from the full collection, we selected all domains that use action costs, were part of an optimal track in IPC, and without duplication (e.g., only one version of the Elevators domain). Then, we created additional problems by using different configurations of costs. Lastly, for all domains and problems, we synthesized three estimators, using six parameters f 1 , ..., f 6 , according to the scheme described below.The with f 3 ≥ f 2 ≥ f 1 ≥ 1, so that l i e is the i th lower bound (l 1 e is the loosest and l 3 e is the tightest). Upper bounds were analogously defined byu 1 e := c old × f 6 , u 2 e := c old × f 5 , u 3 e := c old × f 4 , (13) with f 6 ≥ f 5 ≥ f 4 ≥ f 3 , so that u ie is the i th upper bound (u 1 e is the loosest and u 3 e is the tightest). To diversify the estimator sets for different edges, the parameters for lower bounds f 1 , f 2 , f 3 were taken from the setsEQUATIONSimilarly the parameters for upper bounds f 4 , f 5 , f 6 were taken from the setsEQUATIONThis induced a very wide range of relations between the different estimators and a wide variety of uncertainty levels (reflected by B * ). The choice of configuration was taken according to the result of a simple hash function, that depends on c old (e) and a user-input seed, described as follows:Hash = (c old (e) + seed) mod 27,so that every value of Hash corresponded to one estimator configuration for the lower and upper bounds. Each problem was run once per seed, where all seeds from the set [0, 26] were taken (namely, 27 seeds per problem). The full list of domains, problems and configurations that were used in the experiments is detailed in (link redacted for anonymity). We note that the estimator configurations that were chosen according to the hash function of Eq. ( 16) guarantee that the same ground action, in different states, will have the same cost estimates.BEAST and BEAUTY&BEAST were implemented as search algorithms in PlanDEM (Planning with Dynamically Estimated Action Models (Weiss and Kaminka 2023a) , an open source C++ planner that extends Fast Downward (FD) (Helmert 2006) (v20.06) . All experiments were run on an Intel i7-1165G7 CPU (2.8GHz), with 32GB of RAM, in Linux. We also implemented Estimation-time Indifferent UCS (EI-UCS), a UCS algorithm that uses the most accurate estimate on each edge it encounters, to serve as a baseline for solving SUB.We measured the performance of solving SUB via EI-UCS, BEAST (base setting) and BEAUTY&BEAST (enhanced setting with information obtained from solving first SLB). We report the results (summarized in Table 1 , extended in Fig. 2 ) from problem instances which all algorithms solved successfully, i.e., found optimal solutions, within 5 minutes. Overall, we report on a cumulative set of 891 problem instances, spanning 7 unique domains.Base Setting vs. EI-UCS In its base setting BEAST expands the same nodes as EI-UCS, but with potentially fewer expensive estimates (replaced by less expensive ones). Thus, we are interested in the relative savings that it achieves in practice. We denote the number of the most expensive estimators invoked during the search of an algorithm ALG by θ max (ALG). Column 3 in Table 1 provides the relevant data: it shows 1 -(θ max (BEAST (∞))/θ max (EI-UCS)) in percentages, per domain (Rows 2-8), cumulatively by average±standard deviation (Row 9), and by range minimum-maximum (Row 10).Roughly 40% of the expensive estimators are saved on average, with large differences across domains and problems. Over all, the range is from 14% to almost 80%. The top left plot in Fig. 2 shows the full empirical distribution (histogram), illustrating the high variability in the results. We suspect that different distributions of edge costs explain some of the variability, a topic left for future research.Enhanced Setting vs. Base Setting We can test the performance boost that can be achieved in practice from using BEAST in its enhanced setting with u prune = u(π SLB ), by running BEAUTY&BEAST. Column 4 in Table 1 provides this data: the format is similar to that of Column 3, but instead it shows 1 -(θ max (BEAST (u(π SLB )))/θ max (BEAST (∞))). It can be seen that roughly 35% of the expensive estimators are saved on average w.r.t. to the base setting of BEAST, again with very large differences across domains and problems, where over all problem instances the range is from 0% to around 98%. The top right plot in Fig. 2 shows the full empirical distribution, revealing that in the most common case the savings are rather low, but on the other hand in quite a few cases the savings achieved are very substantial.Column 5 in Table 1 presents pruned nodes (out of generated nodes) for BEAST (u(π SLB )), and it shows that roughly 15% of the generated nodes are pruned on average. Column 6 shows B * (which is a property of the problem instance), where we can see that approximately it was on average 1.5 (the values in this column are not in percentages).For both of these measures, we see high variability in the results: The range of pruned nodes (Column 5) is from 0% to 60%. The range of B * over all problems was from 1 to 2.5. However, examining the distributions for both columns (Fig. 2 ; bottom left plot for pruned nodes, bottom right for B * ), we see that the distributions are qualitatively very different. We will investigate this in future research.We conclude that BEAST seems to offer significant empirical gains over EI-UCS, and that using the information obtained from solving SLB can, though not always, provide an additional significant performance boost. 
conclusions: 
 This paper introduces-and offers a solution to-the tightest admissible shortest path (TASP) problem. It determines how close can one get to cost-optimality, given bounded edgeweight uncertainty. The formalization relies on a recently suggested generalized framework for estimated weighted directed graphs, where the cost of each edge can be estimated by multiple estimators, where every estimator has its own run-time, and returns lower and upper bounds on the edge weight. We show how to generally solve TASP problems by reducing it to the solution of two more basic problems-SLB and SUB. We then present a complete algorithm that obtains optimal solutions for TASP problems, which uses a coupling between SLB and SUB to reduce overall run-time compared to separately solving SLB and SUB. Experiments support the efficacy of the approach.There are many directions for future research. Algorithmic extensions to informed search seem highly relevant, as well as exploring additional trade-offs between search and estimation time to reduce overall run-time. Extending the framework to utilize priors on estimation times to choose estimators across edges also appear promising. 
 
 Appendix:  


Decision: A consensus to (weak) accept this paper was reached after reviewer PZXt increased their evaluation based on the authors' rebuttal.

We ask the authors to follow the reviewers' recommendations and include the needed clarifications in the final version of their paper.

Reviews: review: strength_weakness: strength_weakness: I found only two "weaknesses", which are more like "what I wish had been extended a bit further".

The first is the motivation for the new domain. The example of Google Maps is okay, but I wonder if there is a better motivating example, or just additional examples. It's not immediately obvious to me where this may arise in practice. Fleshing this out would definitely strengthen the paper in my opinion.

The paper is so well written that when I got to the results section, I felt a little blindsided by a lot of synthetic complexity to create these new kinds of problems based on the IPC domains. Perhaps this is a restatement of the first thing I mentioned, but I did not get an intuitive idea of the utility of multiple edge cost estimators based on the chosen benchmark set.

The results being presented, seem like a useful improvement over the baselines in terms of reduction of calls to the most expensive edge cost evaluator. It's not super clear how impactful that is though. Whereas in robotics domains where edge cost/feasibility is expensive collision checking, that can have a practical reportable improvement in terms of calls to the collision checker and runtime. I wish this kind of analysis had been done to really sell the win here.
questions: questions: Just a few questions:

1) You cite that the seeding of the cost estimators yielded the same cost estimates for the same ground action in different states. I could easily see this not being the case (especially in something like robotics where state geometry may play a large role), is that a property that is strictly necessary to maintain the results of your proofs?

2) Why did you choose to normalize the BEAUTY&BEAST estimator against just BEAST and not EI-UCS like in the previous section? It seems like a missed continuity opportunity?

3) Admittedly, it's difficult to come up with a set of monotonically constraining cost estimators for a set of synthetic domains, and I have no issue with your choice there. However, could anything be said about how these synthetic cost functions performed against each other? It's "unlikely" but it could be the case that f1=f2=f3 and f4=f5=f6? Is the possible lack of variation in the final functions giving an unfair advantage to BEAST and BEAUTY&BEAST?
strength_weakness: strength_weakness: W1. There is no running time analysis.

W2. The experiments do not consider a real application (although one is explained in the introduction), but instead artificial cost estimates are used. Therefore, there are also no cost differences for the estimators that can be taken into account. This somewhat defeats the purpose of the whole approach, where the total running time includes this aspect. It is only measured how many expensive estimator costs are saved. But this is not the full story, as asking several cheaper estimation queries could still accumulate a higher running time in total than going directly for a more precise estimate. The total number of oracle calls for each precision level are not presented, and running times are not provided at all.

W3. Minor comment: The interpretability of the histograms might be increased by going with percentages instead of absolute counts.
questions: questions: Q1. What are the theoretical worst-case running times of the BEAST and the combined algorithm? Are there scenarios where computing the best cost estimate for all edges directly and then proceeding with classical search algorithms is more efficient?

Q2. What are the running times? How do they compare to the baseline? What would the oracle cost difference need to be to get a significant running time reduction with the new approach?
strength_weakness: strength_weakness: My concerns primarily stem from novelty and impact.
The paper studies a variant of a problem that appears in an existing literature (Weiss, et al., ECAI2023). Most of its components are derived from this with minor modifications, including definitions, theorems, and the SLB algorithm. 
However, it could be more significant if this following work can explore in directions like:

1. Application: Despite a paragraph explaining the motivation behind studying this problem (TASP on EWDG), a concrete real-world
   example of its application is absent; 

2. Theoretical insight on estimators: The impact is questionable due to the strong assumptions made about estimators, 
i.e., their behaviour must be predictable (more time yields tighter bound), which seems odd when we're dealing with a
problem that involves uncertainty. Also note that the difficulty of obtaining lower and upper bounds may differ; e.g., for an edge in a road network, the lower bound could simply be the Euclidean distance, but determining the upper bound may require simulation;

3. Better search framework for TASP, rather than trivially call SLB then SUB in algorithm 2.
It could be more interesting to elaborate on 'remark 2', e.g., using cheap estimators as a heuristic, or interleaving SLB and SUB.

As a result, I regard it as an incremental work with limited novelty and small impact.

I believe it is crucial to provide a concrete example of TASP on EWDG to substantiate the significance of this problem. It is also important to incorporate a domain in the 
experiment, with real estimators (such as those from the concrete example) to demonstrate actual performance in terms of elapsed time.

I am open to revising my opinion based on the response.
---
Revision:
The information provided by the authors has convinced me of the impact of this work. Thus, I have adjusted my decision to 'weak accept', even though I remain not fully satisfied with its novelty.
questions: questions: Could you provide a concrete example of an EWDG in a planning problem and illustrate how TASP can effectively solve it, while highlighting why other existing methods are not suitable?