Exact Multi-objective Path Finding with Negative Weights and Negative  Cycles

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-05 23:50:17

Abstract: The point-to-point Multi-objective Shortest Path (MOSP) problem is a classic yet challenging task that involves finding all Pareto-optimal paths between two points in a graph with multiple edge costs. Recent studies have shown that employing A* search can lead to state-of-the-art performance in solving point-to-point MOSP instances with non-negative costs. In this paper, we propose a novel A*-based multi-objective search framework that not only handles graphs with negative costs and even negative cycles but also incorporates multiple speed-up techniques to enhance the efficiency of exhaustive search with A*. Through extensive experiments on large realistic test cases, our algorithm demonstrates remarkable success in solving difficult MOSP instances, outperforming the state of the art by up to an order of magnitude.

Main paper: 
 introduction: 
 The point-to-point Multi-objective Shortest Path Problem (MOSP) is a classic network optimisation problem that involves finding all Pareto-optimal paths between a pair of (Origin, Destination) locations in graphs with multiple link attributes. The problem has a wide range of real-world ap-20 plications in diverse areas such as transportation planning, telecommunication networks, and robotics. MOSP can be modelled to plan paths that are optimal in terms of fuel consumption, distance, and arrival time in maritime transportation (Wang, Mao, and Eriksson 2019) , to select emergency routes for major chemical accidents (Xu, mei Gai, and Salhi 2021) , or to simultaneously minimise difficulty, risk, and elevation of planned paths for mobile robots in harsh situations (Jeddisaravi, Alitappeh, and Guimarães 2016) .MOSP and its bi-objective variant BOSP (Bi-objective Shortest Path) are well-studied topics in both network optimisation and AI literature, and have attracted growing interest in recent years. Salzman et al. present an overview of some of the existing MOSP algorithms and their key features, highlighting the significance of heuristic-guided search, in particular A* (Hart, Nilsson, and Raphael 1968) , in reducing overall computation time of MOSP. BOSP can be considered as the most basic variant of MOSP. Currently, there are several specialised algorithms designed to tackle BOSP on a large scale, such as Bi-objective search with A* (Ulloa et al. 2020; Ahmadi et al. 2021a ). Among the recent attempts at optimally solving MOSP for more than two ob-jectives, three novel exact solutions, namely EMOA* (Ren et al. 2022) , TMDA (Maristany de las Casas et al. 2023) , and LTMOA* (Hernández et al. 2023) , have been successful in efficiently utilising best-first search to address the problem. EMOA* follows the search strategy of NAMOA* dr of Pulido, Mandow, and Pérez-de-la-Cruz (2015a) but employs balanced binary search trees to store non-dominated partial paths expanded during the search. The recent TMDA algorithm adapts one-to-all MDA of de las Casas, Sedeño-Noda, and Borndörfer (2021) to a point-to-point MOSP solution using heuristic-guided search. Despite NAMOA* dr where the search priority queue contains all unexplored paths, the multi-objective search of TMDA follows a Dijkstralike queueing approach (Dijkstra 1959 ) and stores at most one (best) path per graph node into the priority queue. LT-MOA* is another A*-based algorithm that performs lineartime dominance check prior to expanding partial paths. The dominance check is necessary to insures the (partial) path is not dominated by any previously expanded path in all objectives, thus reducing the search effort by avoiding unnecessary expansions. Based on the results, it is evident that all EMOA*, TMDA, and LTMOA* outperform NAMOA* dr , with LTMOA* demonstrating superior performance compared to EMOA*. However, a direct comparison between LTMOA* and TMDA is currently unavailable.MOSP with negative weights and negative cycles: Many real-world applications of MOSP need to be modelled with graphs containing negative edge weights. Energy requirement, for example, can be observed in both positive (consumption) and negative (generation) forms. Unfortunately, none of the aforementioned point-to-point MOSP solutions are capable of handling such graphs. While there are a few existing solutions to MOSP with negative weights, it has remained a relatively underexplored topic. The oneto-all MDA algorithm of de las Casas, Sedeño-Noda, and Borndörfer (2021) , build on the basis of Martin's Principle of Optimality (Martins 1984) , can solve MOSP with negative weights. MDA can only solve bounded MOSP instances. Thus, the graph must be free of negative cycles (Sastry, Janakiraman, and Mohideen 2003) . Note that one-toall MOSP exhibits a larger search space than the point-topoint variant, demanding far larger computation time. The path-ranking method of Sastry, Janakiraman, and Mohideen (2005) and the label setting approach of Kurbanov, Cuchý, and Vokrínek (2022) are two other MOSP approaches that can deal with negative weights. These solutions are not exact as they do not compute all Pareto-optimal solutions. This paper introduces NWMOA*, a point-to-point Multi- if i) cost i (π) < 0; ii) u i ̸ = u j for any i, j ∈ {1 . . . n -1, i ̸ = j}; iii) u 1 = u n .The point-to-point MOSP aims to find a set of cost-unique Pareto-optimal paths between a given pair of start ∈ S and goal ∈ S, a set in which every individual solution offers a path that minimises the multi-criteria problem in all dimensions.Following the conventional notation in the heuristic search literature, we define our search objects to be nodes (equivalent to partial paths). A node x is a tuple that contains the main information of the partial path to s(x), where s(x) is a function returning the state associated with x. Node x traditionally stores a cost vector g(x) which measures the cost of a concrete path from the start state to state s(x). In addition, node x is associated with the cost vector f(x), which estimates the cost of a complete path 125 from start to goal via s(x); and also a reference parent(x) which indicates the parent node of x. Further, the operator Tr(v) truncates the cost 1 of the cost vector v. For example, (g 2 (x), . . . , g k (x)) is the truncated vector of g(x).We consider all operations of the cost vectors to be 130 done element-wise. For example, we define g(x) + g(y) as (g 1 (x) + g 1 (y), . . . , g k (x) + g k (y)). We use ⪯ or ≤ lex symbols in direct comparisons of cost vectors, e.g. g(x) ⪯ g(y) denotes g i (x) ≤ g i (y) for all i ∈ {1, . . . , k} and g(x) ≤ lex g(y) means the cost vector g(x) is lexicographically smaller than or equal to g(y). Analogously, we use ⊀ or ≰ lex symbols if the relations cannot be satisfied. Definition For the node pair (x, y), we say y is (weakly) dominated by x if we have g(x) ⪯ g(y) or f (x) ⪯ f (y).The main search in A*-based solution methods is guided by start-goal cost estimates or f-values, which are traditionally established based on a consistent and admissible heuristic function h : S → R k (Hart, Nilsson, and Raphael 1968) . In other words, for every search node x, we have f (x) = g(x) + h(s(x)) where h(s(x)) estimates lower bounds on the cost of paths from state s(x) to the goal state. One common method of computing a well-informed h i function is solving a one-to-all single-objective shortest path problem on cost i from the goal state on the graph G with all links reversed, building a perfect heuristic function.A perfect heuristic is consistent and admissible.Definitionh i : S → R is admissible iff h i (u) ≤ cost i (π * )for every u ∈ S where π * is the optimal path on cost p from state u to the goal state. It is also consistent if we haveh i (u) ≤ cost i (u, v) + h i (v) for every edge (u, v) ∈ E.The multi-objective search with A* involves in general two types of strategies: expand and prune. It performs a systematic search by expanding nodes in best-first order. That is, the search is led by a partial path that shows the lowest cost estimate or f -value. Each iteration involves three main steps: i) Extraction: remove one (lexicographically) least-cost node from a priority queue, known as Open list.ii) Dominance check: ensure the extracted node is not dominated by some previous expansions;iii) Expansion: generate new (non-dominated) descendant nodes and store them in Open for further expansion.To commence the search, we initialise Open with a node associated with start, g = 0 and f = h. Open always contains generated (but not expanded) nodes. For the purpose of further expansion, Open reorders its nodes according to their f -value such that the lexicographically least-cost node is always at the front of the list. More accurately, given the cost vector (f 1 , f 2 , . . . , f k ), Open first orders nodes based on their f 1 -value, and then the truncated vector (f 2 , . . . , f k ) if it finds two (or more) of the nodes showing the same f 1 -value. The latter operation is called tie-breaking. Once a least-cost node is extracted from Open, it undergoes a rigorous dominance test to ensure the expansion of the node can lead to a promising solution. This dominance rule usually involves checking the cost of the extracted node against that of the previously expanded nodes of the state, as well nodes expanded with the goal state (established solutions). The same strategy can be applied once a new descendant node is generated (during expansion). It is always safe to prune dominated nodes, essentially because their expansion will never lead to an optimal solution. Nodes associated with the goal state represent solution paths and can be stored in a solution set. Since solution paths must be acyclic, A* does not need to expand such solution nodes. Finally, multi-objective A* terminates once there is no node in Open to explore. With this introduction, we now describe our NWMOA*.Many real-world MOSP problems deal with attributes that are negative in nature, or attributes that may exhibit negative values in specific circumstances, such as energy recuperation in electric vehicles. There might also be cases where the graph contains negative cycles on (one or even all) cost com-ponents. Our NWMOA* performs multi-objective search on the basis of A* and can deal with negative weights and negative cycles. We start with discussing the latter case.Negative cycles: Although it is widely accepted in the MOSP literature that the existence of negative cycles makes MOSP inevitably unbounded, we now elaborate this is not always the case in the point-to-point variant. Consider the sample graph of Figure 1 with three attributes shown on the edges. The graph contains negative weights, as well as negative cycle (through the third cost component of the links u 4 ⇝ u 5 ⇝ u 6 ⇝ u 4 shown in red). We aim to find optimal paths from u s to u g . This MOSP instance is bounded, as there are three optimal paths, none of them visiting the vertices of the negative cycle. Given this important observation, we can conclude that negative cycles are not problematic for a point-to-point MOSP instance as long as they do not appear on any start-goal path. Thus, we distinguish two cases:1. There is negative cycle on any arbitrary path from start to goal : The problem becomes unbounded, as there will be at least one dimension on which we can take the negative cycle to further reduce cost of the path indefinitely.2. No path can be found from start to goal via a negative cycle: The problem is bounded, as this essentially implies that there is either no negative cycle present, or if there is one, it cannot be reached from start or reach goal .As described above, to determine whether the problem is bounded or not, we need to perform a simple (polynomialtime) reachibility test: Let S ′ be the set of states that are reachable from start and can reach goal . The problem is unbounded if we can find a negative cycle onG ′ = (S ′ , E ′ ) with E ′ ⊆ S ′ × S ′ .In the sample graph of Figure 1 , the three states consisting the only negative cycle of the graph can reach u g (the goal state), but are not reachable from u s (the start state). Hence, we can assure that no negative cycle can appear on any optimal path, and thus the multi-objective search can be conducted safely. To accommodate this crucial preliminary test, we describe our NWMOA* in two levels.Algorithm 1 provides a high-level description of NWMOA*, presenting it as a merged procedure for establishing heuristic functions and detecting negative cycles. It first initialises h-value of all states with a vector of k large values, followed by eliminating all states not reachable from start (e.g., using breath-first search) to form a reduced graph. The algorithm then conducts for each i ∈ {1, . . . , k} a backward one-to-all single-objective search to compute cost i -optimal path from goal . This can be as simple as k runs of the Bellman-Ford algorithm (Bellman 1958; Ford Jr 1956) , or the Dijkstra's algorithm with re-expansions allowed (Johnson 1973 ). There will be negative cycle on a start-goal path if the length (number of edges) of the cost i -optimal path to any state of the reduced graph grows to be larger than or equal to |S|.The condition h i (u) = -∞ at line 6 of Algorithm 1 denotes the situation where we can identify unbounded MOSP instances through the growing length of optimal paths. Otherwise, the problem is bounded and we can safely proceed with the NWMOA*'s lower-level search (via line 8).Algorithm 1: NWMOA* High LevelInput: A MOSP Problem (G, start, goal , k) Output: A cost-unique Pareto-optimal solution set 1 h(u) ← ∞ ∀u ∈ S 2 S ← Remove from S states not reachable form start 3 for i ∈ {1 . . . k} do 4 foreach u ∈ S do 5 hi(u) ← costi-optimal path from u to goal 6 if hi(u) = -∞ then 7 return ∅ 8 Sols ← Multi-objective Search on (G, h, start, goal ) 9 return SolsOur new search framework differs from existing methods in three key aspects: i) Nodes in NWMOA* are processed in order of their f 1 -260 value, rather than any lexicographical ordering. This will reduce the cost of priority queue operations, and enable the use of simpler yet efficient queueing data structures.ii) The search is equipped with a novel constant-time dominance check. This will help reduce the overall dominance 265 check attempts, and nodes generated during the search. iii) Unlike LTMOA*, where truncated vectors are stored in no specific order, NWMOA* stores truncated vectors in lexicographical order, reducing dominance checks per iteration.Algorithm 2 shows the pseudo-code of the multi-objective 270 search of NWMOA*, with the new features highlighted in blue. The algorithm starts with initialising the priority queue Open, and the solution set Sols. It then sets up for every state u ∈ S a list G Tr cl (u), responsible for storing the (nondominated) truncated cost-vector of previous (closed) ex-275 pansions with state u. To reduce the number of costly dominance checks, NWMOA* keeps track of the most recent expansion of u via a cost vector called g Tr last (u). This cost vector is initialised with large cost values (line 3) to allow for capturing the first expansion. NWMOA* then initialises a 280 node with the start state and insert it into the priority queue.Each iteration of the algorithm starts at line 7. Let Open be a non-empty queue. NWMOA* extracts in each iteration of the algorithm a node x with the smallest f 1 -value (line 8).Quick dominance check: Most recent expansions are 285 generally more informed and can be seen as strong candidates for dominance check. Node x is quickly checked for dominance against the last expanded node of two states: goal and the state associated with x, i.e., s(x) (line 9). As we will show in the next section, NWMOA* processes nodes in 290 non-decreasing order of their f 1 -value. Because the first dimension is expanded in sorted f 1 order, later expansions are already dominated by previous f 1 -values. So, the dominance test can be done by just comparing the truncated cost vector of x, i.e., Tr(f (x)), with that of the two candidates.Dominance check with IsDominated: If the extracted node cannot be quickly dominated, NWMOA* takes Tr(g(x)) and Tr(f (x)) to conduct a rigorous dominance check by comparing x against (potentially all) truncated vec- tors of previous expansions with both s(x) and goal . Algo-300 rithm 3 shows the details of this procedure. G Tr cl (s(x)) stores in a lexicographical order all non-dominated truncated cost vectors derived from previous expansions with s(x). Thus, the dominance test of Algorithm 3 does not need to traverse the entire G Tr cl (s(x)) list, and can terminate early when it discovers a candidate with a truncated cost vector not lexicographically smaller than that of x (line 3 of Algorithm 3).Algorithm 2: Multi-objective Search of NWMOA* Input: A MOSP Problem (G, h, start, goal ) Output: A cost-unique Pareto-optimal solution set 1 Open ← ∅ , Sols ← ∅ 2 G Tr cl (u) ← ∅ ∀u ∈ S 3 g Tr last (u) ← ∞ ∀u ∈ S 4 x ← new node with s(x) = start 5 g(x) ← 0 , f (x) ← h(start) , parent(x)Lexicographical ordering with Consolidate: Let x be a non-dominated node. Thus, its truncated cost vector, i.e., Tr(g(x)), must be stored in G Tr cl (s(x)) for the purpose of future dominance checks with s(x). However, it is possible that Tr(g(x)) dominates some vectors of G for i ∈ {1 . . . |V|} do 2 v ′ ← Cost vector at index i of V 3 if v ′ ≰ lex v then 4 return false 5 if v ′ ⪯ v thenOutput: V updated 1 i ← |V| 2 while i ≥ 1 do 3 v ′ ← Cost vector at index i of V 4 if v ≰ lex v ′ then 5 break 6 if v ⪯ v ′ then 7 Remove v ′ from V 8 i ← (i -1) 9 Insert v to index (i + 1) of V 10 returntains its lexicographical order. A similar strategy is used in TMDA (Maristany de las Casas et al. 2023) . Once Tr(g(x)) is captured, NWMOA* stores a copy of it into g Tr last (s(x)) as the most recent expansion (line 13 of Algorithm 2).Capturing solution paths: Let x represent a tentative solution path, i.e., we have s(x) = goal (line 14 of Algorithm 2). If Sols is empty, we simply capture x as a tentative solution and add it to the solution set (line 21). Otherwise, since NWMOA* does not explore nodes in a lexicographical order, it is possible for x to dominate some previous solution nodes in Sols. NWMOA* takes care of such situation via lines 15-20. To remove any dominated solutions from the list, NWMOA* (linearly) iterates backward through Sols and checks the new solution x against those tied with x, i.e., those showing the same f 1 -value. Solution nodes with f 1value smaller than f 1 (x) cannot be dominated by x. Thus, a full traversal of Sols may not be necessary (line 18).Expansion: Let x be a non-dominated node other than a solution node. Expansion of x involves generating new descendant nodes through s(x)'s successors. Consistent with lazy dominance checks in recent MOSP solutions, NWMOA* delays the (full) dominance check of descendant nodes until they are extracted from Open. Nonetheless, the quick dominance check against the most recent expansion of each successor state can still be applied (see line 28). Such quick pruning during expansion can reduce the queue size and consequently improve the search performance.Finally, the algorithm returns Sols, as a cost-unique Pareto-optimal solution set to a bounded MOSP instance.Example: We further elaborate on the key steps of us (-2,0,2) NWMOA* by solving a sample MOSP instance with three cost components, depicted in Figure 1 . u s and u g denote start and goal , respectively. Although the graph contains negative cycle, the problem is bounded because the cycle is not on any start-goal path. For the states reachable from start, the triple inside the state denotes h-value, calculated in the higher level of NWMOA*. We briefly explain all iterations (It.) of NWMOA* for the given instance, with the trace of generated nodes and sets illustrated in Table 1 . Since none of the nodes in this simple instance is quickly dominated, we do not display the changes on g Tr last of states.u1 (2,2,2) u5 (3,3,-) u2 (1,1,1) u4 (1,1,-) u3 (2,1,1) ug (0,0,0) u6 (2,2,-) (-4,1,3) (1,-1,1) ( 1 , 1 , 1 ) ( 1 , 1 , 1 ) (2,1,1) ( 1 , 1 , 1 ) ( 1 , 1 , 1 ) ( 1 , 1 , 1 ) (1,1,-3) ( 1 , 1 , 1 ) ( 1 , 1 , 1 ) ( 1 , 1 , 1 )It.1-4: The first four iterations of the algorithm expand all states on the cost 1 -optimal path, namely u s , u 1 , u 2 and u g . At the end of the fourth iteration, we have one truncated cost vector stored in the G Tr cl list of each of the expanded states, as shown in third column of Table 1 . x 5 is our first solution.It.5: x 2 , the second descendant node of x 0 , is extracted. x 2 's truncated cost Tr(g(x 2 )) = (1,1) dominates the only vector available in G Tr cl (u 2 ). Thus, (1,1) replaces (2,4) in G Tr cl (u 2 ). x 2 is non-dominated and should be expanded. The new node x 6 is added to Open upon expansion of x 2 . It.6: x 6 is extracted from Open. This node appears nondominated, and is a tentative solution. G Tr cl (u g ) is then updated with the new truncated cost (2,2). The existing vector (3,5) is dominated and removed. x 6 is added to Sols. It.7: NWMOA* undergoes the first expansion with state u 3 via x 3 . Two new nodes, x 7 and x 8 , are added to the queue. It.8: Both x 7 and x 8 exhibit the same f 1 -value. In the absence of tie-breaking, we may extract x 7 first. x 7 appears non-dominated. Thus, we can add its truncated cost (0,2) to G Tr cl (u 2 ). Its expansion leads to u g via the new node x 9 .It.9: Both x 8 and x 9 exhibit the same f 1 -value. Assume x 9 is extracted first. x 9 is a non-dominated solution node, so we can update both G Tr cl (u g ) and Sols with the new node. This solution does not dominate any previous solutions. It.10: x 8 is the only node in the queue. x 8 is a non-dominated solution node, and its truncated cost (0,2) dominates all vectors in G Tr cl (u g ). x 8 should be added to Sols. However, the new solution x 8 dominates the previous solution x 9 (both showing the same f 1 -value). Thus, x 9 is removed from Sols. It.11: Open is empty, and all optimal solutions are in Sols.The example above shows how NWMOA* processes nodes in the order of their f 1 -value. As we observed in It.9, 2, 2, 2), (1, 1, 1), u2]  x3=[(3, 0, 2), (1, 1), 3, 5), 3, 5 2, 2, 2), (1, 1, 1), u2]  x3=[(3, 0, 2), (1, 1), u3 ] NWMOA* may perform extra expansions due to not breaking ties between nodes before extractions. More accurately, x 7 would not be expanded if we processed nodes lexico-395 graphically. However, we observed in It.10 how NWMOA* refines the optimal solution set in such circumstances.It. Open : [f (x), g(x), s(x)] G Tr cl Sols 1 * x0=[(-2,0,2), (0,0,0), us] G Tr cl (us)=[(0,0)] 2 * x1=[(-2,3,5), (-4,1,3), u1] G Tr cl (u1)=[(1,3)] x2=[(2,2,2), (1,1,1), u2] x3=[(3,0,2), (1,-1,1), u3] 3 * x4=[(-2,3,5), (-3,2,4), u2] G Tr cl (u2)=[(2,4)] x2=[(), ug] G Tr cl (ug)=[(3,5)] x5 x2=[(5 * x2=[(2,2,2), (1,1,1), u2] G Tr cl (u2)=[(1,1)] x5 x3=[(3,0,2), (1,-1,1), u3] 6 * x6=[(2,2,2), (2,2,2), ug] G Tr cl (ug)=[(2,2)] x5,6 x3=[(3,0,2), (1,-1,1), u3] 7 * x3=[(3,0,2), (1,-1,1), u3] G Tr cl (u3)=[(-1,-1)] x5,6 8 * x7=[(3,1,3), (2,0,2), u2] G Tr cl (u2)=[(0,2),(1,1)] x5,6 x8=[(3,0,2), (3,0,2), ug] 9 * x9=[(3,1,3), (3,1,3), ug] G Tr cl (ug)=[(1,3),(2,2)] x5,6,9 x8=[(3,0,2), (3,0,2), ug] 10 * x8=[(3,0,2), (3,0,2), ug] G Tr cl (ug)=[(0,2)] x5,Always Logarithmic Dominance Check with k = 3In case of three objectives, truncated cost vectors consist of two cost components only. Since G Tr cl lists store non-400 dominated truncated vectors in lexicographical order, we can achieve logarithmic-time dominance check via binary search. Let v = (g 2 , g 3 ) be the truncated cost vector of x, and v ′ = (g ′ 2 , g ′ 3 ) be the predecessor of v in G Tr cl (s(x)), obtained by binary search. Since v ′ ≤ lex v, we should have: 405 1. g ′ 2 = g 2 and g ′ 3 = g 3 : thus v ′ weakly dominates v 2. or g ′ 2 = g 2 and g ′ 3 < g 3 : thus v ′ dominates v 3. or g ′ 2 < g 2 : there are two cases, either g ′ 3 ≤ g 3 or g ′ 3 > g 3 . The former denotes v ′ dominates v. The latter, however, confirms v is non-dominated, because all other 410 lexicographically smaller candidates in G Tr cl (s(x)), i.e., vectors before the predecessor v ′ , do not exhibit smaller cost 3 than g ′ 3 and thus cannot dominate v.This section provides a formal proof for the correctness of 415 multi-objective search of NWMOA*, providing theoretical results on why NWMOA* can solve bounded MOSP instances with negative weights. That is, we assume negative cycles have already been handled via Algorithm 1. Lemma 1 Suppose NWMOA*'s search is led by smallest (possibly negative) f 1 -values. Let x i and x i+1 be nodes extracted from Open in two consecutive iterations of NWMOA*. We havef 1 (x i ) ≤ f 1 (x i+1 ) if h 1 is consistent.Proof Sketch We distinguish two cases: i) if x i+1 was available in Open at the time x i was extracted, the lemma is trivially true. ii) otherwise, x i+1 is the descendant node of x i . For the edge linking state s(x i ) to its successor s(x i+1 ), the consistency requirement of h 1 ensures h 1 (s(x i )) ≤ h 1 (s(x i+1 ))+cost 1 (s(x i ), s(x i+1 )). Adding the cost g 1 (x i ) to both sides of the inequality yieldsf 1 (x i ) ≤ f 1 (x i+1 ). □Corollary 1 Let (x 1 , x 2 , ..., x t ) be the sequence of nodes extracted from Open. The (perfect) heuristic function h is consistent and admissible. Then, under the premises of Lemma 1, i ≤ j implies f 1 (x i ) ≤ f 1 (x j ), meaning f 1 -value of extracted nodes are monotonically non-decreasing.Lemma 2 Suppose x j is extracted after x i and s(x i ) = s(x j ). x i (weakly) dominates x j if Tr(g(x i )) ⪯ Tr(g(x j )).Proof Sketch x j is extracted after x i , so we havef 1 (x i ) ≤ f 1 (x j ) according to Corollary 1. Given h 1 (s(x i )) = h 1 (s(x j )), we obtain g 1 (x i ) ≤ g 1 (x j ). The other condition Tr(g(x i )) ⪯ Tr(g(x j )) means g 2 (x i ) ≤ g 2 (x j ), . . . , g k (x i ) ≤ g k (x j ). Thus, g(x j) is no smaller than g(x i ) in all dimensions. □ Lemma 3 Suppose x j is extracted after x i with s(x i ) = goal . Extending x j towards the goal state will not lead to a non-dominated solution node if Tr(g(x i )) ⪯ Tr(f (x j )). Proof Sketch Node x j is extracted after x i , so we have f 1 (x i ) ≤ f 1 (x j ), or equivalently g 1 (x i ) ≤ f 1 (x j ). Expanding the condition Tr(g(x i )) ⪯ Tr(f (x j )), we have g 2 (x i ) ≤ f 2 (x j ), . . . , g k (x i ) ≤ f k (x j ). Thus, f (x j ) is no smaller than g(x i ) in all dimensions. Since h is admissible, we can guarantee that all subsequent expansions of x j towards goal will exhibit the same condition. Thus, x j and all its descendant nodes will be (weakly) dominated by x i . □ Lemma 4 Dominated nodes cannot lead to any cost-optimal start-goal solution path. Proof Sketch We prove this lemma by assuming the contrary, namely by claiming that dominated nodes can lead to a cost-optimal start-goal solution paths. Let x and y be two nodes associated with the same state where y is dominated by x. Suppose that π * is a cost-optimal start-goal solution path via the dominated node y. Since x dominates y, one can replace the subpath represented by y with that of x on π * to further reduce the cost of the start-goal optimum path for at least one attribute. However, being able to reduce the cost of the established optimal solution path would contradict our assumption on the optimality of the solution path π * . Therefore, we conclude that dominated nodes cannot form any cost-optimal start-goal solution path. □ Lemma 5 Let y be a node weakly dominated by node x and s(x) = s(y). If y's expansion leads to a cost-optimal solution path, x's expansion will also lead to an optimal solution. Proof Sketch We prove this lemma by assuming the contrary, namely that x cannot lead to any cost-optimal solution path. Since y is weakly dominated by x, we have g 1 (x) ≤ g 1 (y), . . . , g k (x) ≤ g k (y), meaning that x offers a better cost at least in one dimension, or cost equal to the cost of y. In such condition, one can replace the partial path represented by y with that of x, and nominate a path lexicographically smaller than or equal to the optimal solution path 480 via y. The existence of a better solution path in the former case would contradict our assumption on the optimality of the solution path via node y. The later case means both paths are equal in terms of cost and thus should be non-optimal, contradicting our assumption. Therefore, node x will defi-485 nitely lead to a cost-optimal solution path if node y leads to an optimal solution. □ Theorem 1 NWMOA* computes a cost-unique Paretooptimal solution set for any bounded MOSP instance. Proof Sketch NWMOA* enumerates all partial paths from 490 the start state towards the goal state in best-first order, in search of all optimal solutions. The dominance rules utilised by NWMOA* (Lemmas 2 and 3) ensure that removal of (weakly) dominated nodes is safe, as they will not lead to cost-unique optimal solution paths (Lemmas 4 and 5). 495 Thus, we just need to show that Sols does not contain a (weakly) dominated solution when NWMOA* terminates. NWMOA* captures all nodes reaching the goal state. However, since it does not process nodes lexicography, some tentative solutions may later appear dominated. Let x be a new 500 non-dominated solution extracted after solution z. We have f 1 (z) ≤ f 1 (x). There are two cases: i) if f 1 (z) < f 1 (x), the tentative solution x confirms the optimality of z because the older solution z cannot be dominated by x and all future solutions. ii) if f 1 (z) = f 1 (x), a dominance check is per-505 formed to ensure the optimality of z, or remove z from Sols if it is deemed to be (weakly) dominated by x, as scripted in lines 15-20 of Algorithm 2. Therefore, we conclude that NWMOA* terminates with returning a set of cost-unique Pareto-optimal solution set, even with negative weights. □ 510This section compares the performance of NWMOA* against the recent MOSP algorithms: LTMOA* (Hernández et al. 2023) , TMDA (Maristany de las Casas et al. 2023), EMOA* (Ren et al. 2022 ) and also the lazy variant of 515 NAMOA* dr (Pulido, Mandow, and Pérez-de-la-Cruz 2015b) studied in Maristany de las Casas et al. (2023) .Implementation: We implemented our NWMOA* algorithm in C++ and used the publicly available version of the other algorithms, all implemented in C++. The implementa-520 tion of TMDA and Lazy-NAMOA* dr utilises linked lists to store truncated vectors. However, we found both algorithms performing faster when vectors are handled via dynamic arrays (nearly 30%). Hence, we used the faster array-based implementation. For the LTMOA* algorithm, we were unable 525 to obtain the original implementation and instances. We, therefore, implemented the fast performing variant of the algorithm (Lazy-LTMOA*-A) in C++ based on the descriptions provided in the original paper. All algorithms utilise dynamic arrays to store truncated vectors. We ran all experi-530 ments on a single core of an Intel Xeon Gold 5220R processor running at 2.2 GHz and with 32 GB of RAM, under the CentOs Linux 7 environment and with a two-hour timeout. All C++ code was compiled using the GCC7.5 compiler.The Open list: Since NWMOA* processes nodes based on their f 1 -value only, we can utilise simpler yet efficient data structures to implement the priority queue, such as bucket-based queues (Denardo and Fox 1979; Cherkassky, Goldberg, and Radzik 1996) . It can be shown that the difference between the largest and smallest f 1 -values available in Open in any arbitrary iteration of NWMOA* is bounded by max{h1 (v) -h 1 (u) + cost 1 (u, v)|(u, v) ∈ E, h 1 (v) ̸ = ∞}.Thus, we implemented Open using a cyclic fixed-size bucket-based queue, with bucket width of one. Linked lists were used to handle queue operations via the Last-In, First-Out (LIFO) strategy.Benchmark instances: We used the New York map from the 9th DIMACS Implementation Challenge: Shortest Paths 1 to generate MOSP instances. The map contains two cost components only: distance and time. To extend the dimensions, following Storandt (2012) , we enriched the map with Shuttle Radar Topography Mission 2 height information and set the third dimension to be the positive height difference of the endpoints of each link, i.e., we setcost 3 (u, v) = |height(v) -height(u)| for each (u, v) ∈ E.For the fourth edge attribute, following Ren et al. (2022) , we calculate the average (out)degree of the link, i.e., number of adjacent vertices of each end point, namely cost 4 = ⌊(deg(u) + deg(v))/2⌋ for each (u, v) ∈ E. Finally, as in Maristany de las Casas et al. (2023) , we set the fifth cost of each edge to 1, with cost 5 of paths denoting the number of edges traversed. We then generated 100 random (start, goal ) pairs, and evaluated all algorithms on the same set of instances but with 3-5 cost components. Our code and benchmark instances will be made publicly available. Since all algorithms use the same approach to compute heuristic functions, we report the runtime of the main search only. Table 2 presents the runtime statistics for all of the studied algorithms with 3-5 cost components, as well as for the variant of NWMOA* with logarithmic-time dominance check for k = 3, denoted by NWMOA* log . We report both arithmetic and geometric mean, and the runtime of unsolved cases is considered to be the timeout. ϕ in the last column represents the average slow-down factor (of runtime) over the mutually solved instances when compared to the virtual best oracle. The virtual oracle is given the best runtime of all algorithms for every mutually solved instance. ϕ = 1 means the algorithm is as good as the virtual best oracle.Comparing the performance of the algorithms with k = 3, we find that NWMOA* log is best performer, dominating other algorithms in all individual instances with ϕ = 1. This variant performs on average 20% faster than the standard NWMOA*, 4.2 times faster than Lazy-LTMOA*, and above one order of magnitude faster than others. Our detailed results show that the number of dominance checks is reduced by 71% on average when binary search is used for dominance check in NWMOA* with k = 3. Comparing the results for instances with four and five cost compo- Ablation study: To gain a deeper understanding of how the key features of NWMOA* impact search performance, 600 we performed detailed performance analyses on three variants of NWMOA*, namely: NWMOA* without quick dominance check and/or NWMOA* without lexicographical ordering of node in G Tr cl . We also compare how Lazy-LTMOA* performs against these variants. The detailed results are pre-605 sented in Table 3 for mutually solved instances for k = 4, where ϕ denotes average percentage increase in runtime when compared to standard NWMOA*. |per | also denotes the average number of percolations (total swaps performed) in the binary heap of Lazy-LTMOA*, and the total number 610 of buckets traversed in the priority queue of NWMOA*.Comparing the results, we see all variants expanding the same number of nodes on average (slightly larger than Lazy-LTMOA*), and consuming nearly the same amount of memory. Interestingly, the quick dominance check of NWMOA* 615 effectively prunes two third of dominated nodes, reducing the number of generated nodes by 20% on average. We see 18.8% increase in runtime when no quick dominance check is in place. The impact is more severe when non-dominated truncated costs are not stored lexicographically, where we 620 observe a runtime increase of over 100%. In this situation, the number of dominance checks is raised drastically, requiring a linear traversal of the entire G Tr cl list. The performance decline is less pronounced if quick dominance checks are not performed alongside the latter case (the second last variant of Table 3 ). Even with both features removed, this downgraded variant still preforms better than Lazy-LTMOA* due to its simpler node queueing strategy and far lower |per |.Negative weights and priority queues: For the last experiment of this study, we analyse the performance of 630 NWMOA* using different data structures for Open. Further, to evaluate our algorithm on large graphs with both negative and non-correlated edge attributes, we changed the edge cost vector of the NY map with four new attributes as follows: cost 1 is the energy consumption along the link. We use the energy model of Ahmadi et al. (2021b) to produce realistic, potentially negative, energy estimates for an electric vehicle with three passengers on board. We did not bound the battery capacity, thus the plain NWMOA* can be used to find energy efficient paths. The second cost is now a penalised height function. We set cost 2 of link (u, v) ∈ E to be height(v) -height(u) if height(v) ≤ height(u) (downhill links), and 2 × (height(v) -height(u)) otherwise (uphill links). For the third and fourth costs, we choose random integers in the [1,100] range. The resulting graph is free of 645 negative cycles, thus all MOSP instances would be bounded.We report in Table 4 the performance results for three types of priority queues in two variations: Bucket (with LIFO or First-In, First-Out strategy), Hybrid and Heap queues (with or without tie-breaking). Our Hybrid queue is a two-level bucket-based queue, with a bucket list and heap used for the higher and lower levels, respectively (Denardo and Fox 1979) . Nodes may be inserted to either of the data structures (depending on f 1 -value), but are always extracted from the lower level. We set the bucket width to one in both Bucket and Hybrid queues. Hybrid queue can handle both integer and non-integer costs. We use the same timeout and (start, goal ) pairs as in the previous experiment, and report the average number of expansions, memory consumed, and queue percolation for all mutually solved instances.As we expected, the minimum number of expansions is achieved when tie-breaking is in place for Heap and Hybrid queues. However, this seems costly in terms of space, with the memory consumption nearly doubled when compared with the variant without tie-breaking. Although we see slight improvement in the runtime of heap queue with tiebreaking, the effort is not paid off in the Hybrid queue and NWMOA* performs around 20% faster when not breaking ties. NWMOA* performs best with Bucket queue using the LIFO strategy. It undergoes minimal queue effort and memory use, while expanding only 1% extra nodes. The Bucket queue with FIFO strategy, however, shows the largest number of expansions, and is outperformed by Hybrid queue without tie-breaking. This observation highlights the significance of prioritising most recent (better informed) expansions in multi-objective search with A*.We have introduced NWMOA*, an exact MOSP algorithm that determines within polynomial time whether a point-topoint MOSP problem instance is bounded. If the instance is found to be bounded, NWMOA* can then compute a costunique Pareto-optimal solution set, even in the presence of negative weights. NWMOA* challenges the convention in multi-criteria search by not processing paths in lexicographical order of their costs, while utilising novel strategies to expedite the exhaustive search of A*. The results of our extensive experiments over a new large set of realistic instances show the success of NWMOA* in efficiently solving difficult MOSPP instances in limited time, outperforming all state-of-the-art algorithms by up to an order of magnitude. 
 
 Appendix:  


Decision: This paper introduces NWMOA*, an algorithm designed to address the point-to-point Multi-objective Shortest Path (MOSP) Problem in scenarios where the graph permits negative weights and cycles.  A key contribution lies in presenting an algorithm for detecting negative cycles (Algorithm 1). Subsequently, the paper rigorously establishes the correctness of NWMOA* (Theorem 1, after several lemmas obtained), asserting that the algorithm computes a cost-unique Pareto-optimal solution set for any bounded MOSP instance, considering the detection and handling of negative cycles having already been done. Furthermore, the paper incorporates various techniques within the A* search process to expedite the algorithm. Extensive experiments are conducted, yielding promising results.  Additionally, the paper describes several speed-up techniques for multi-objective search, including a quick dominance check approach and a bucket-based heap.

Strengths
- The paper presents a novel algorithm that outperforms state-of-the-art algorithms.
- The new algorithm can solve problems with negative weights and cycles.
- The paper is well-written and well-organized in most parts.
- The experiments section is convincing.
- The paper offers a detailed exposition of the proposed algorithm and several enhancements aimed at improving efficiency. 
- The algorithm is accompanied by a theoretical proof, bolstering confidence in its correctness. 


Weaknesses
- Some of the proposed techniques have appeared in existing works. Although some of these papers are already cited, we think the authors should discuss them in more detail.
- Using bucket queue and ordering nodes according to only f1 value has appeared in [1]. Although [1] focuses on a different problem, the Weight Constraint Shortest Path (WCSP) problem, it is not surprising that the technique is transferable given the close relation between WCSP and MOSP, as discussed in [1]. 
- EMOA*[2] also employed a log time dominance checks mechanism for problems with 3 objectives and skips checking those truncated cost vectors if their first components are larger than that of the vector being checked. Although EMOA* uses a different data structure to implement this idea, we think it should be mentioned in this paper.
[1] Ahmadi, Saman, et al. "Enhanced Methods for the Weight Constrained Shortest Path Problem: Constrained Path Finding Meets Bi-objective Search." arXiv preprint arXiv:2207.14744 (2022).
[2] Ren, Zhongqiang, et al. "Enhanced multi-objective A* using balanced binary search trees." Proceedings of the international symposium on combinatorial search. Vol. 15. No. 1. 2022.
- It was not initially clear to us why consistent heuristics are always available for bounded problem instances, and we think the paper would benefit from adding such a discussion to the theoretical results.
- In the abstract and the conclusion, the improvement of performance seems to be over-claimed. For example, the abstract claims that NWMOA "outperforming the state of the art by up to an order of magnitude." If we look at the results, LTMOA seems to be the state-of-the art and is outperformed by at most 4 times.

Suggestions to improve the final submission:
- We suggest adding a short discussion on why adjusting existing MOSP algorithms to solve MOSP with negative costs is not straightforward.
- Add a discussion regarding the existing techniques that share some similarities with the ones proposed in this paper, for instance [1] and [2] above.
- The authors stated in the rebuttal "NWMOA* performs an order of magnitude faster than TMDA and up to 4 times better than LTMOA*, two state-of-the-art MOSP algorithms. We will make the performance improvement clearer in both abstract and conclusion."
- The authors state in the rebuttal, "our initial set of experiments focused on instances with non-negative weights only". We would make this clearer so as not to confuse the reader. It would also be good to have a set of experiments that include negative weights.

The paper does not need an ethical statement to accompany it.

Reviews: review: strength_weakness: strength_weakness: Main comments -
- There is some information missing, which makes some parts hard to understand (all mentioned below).
- As I mentioned above, I find the motivation of the paper a bit confusing. While the paper suggests a method that can handle negative weights, most of the experimental study evaluates this method on graphs with no negative weights. Moreover, I couldn't understand whether all state-of-the-art MOSP algorithms are also capable of solving MOSP (with only minor modifications, where no negative cycles exist).

Other comments and suggestions -
- Introduction - bounded MOSP is mentioned but the reader cannot understand what it is.
- Introduction - "both Negative Weights and negative cycles" -> "both negative weights and negative cycles".
- Introduction - "realistic instances show the" - "realistic instances shows the".
- Introduction - "a pair of (Origin, Destination)" - in the rest of the paper, they are called start and goal.
- Notation and Problem Formulation - "which every individual solution offers a path that minimises the multi-criteria problem in all dimensions" - this should be explained. I couldn't understand what happens with negative cycles. I only understood it while reading the suggested algorithm itself.
- Notation and Problem Formulation - The operator Tr(v) is very hard to understand. It should be better defined.
- Notation and Problem Formulation - Definition hi - "cost_p" -> "cost_i". Also, the notation of cost_i() is overloaded. How does it give the cost from some state u to goal without receiving it?
- NWMOA*’s High-Level Description - This is basically a way to calculate the perfect heuristic and, during this calculation, it also finds negative cycles. The name "high-level" is misleading.
- Multi-objective Search of NWMOA* - "state and insert it into the priority" - "state and inserts it into the priority".
- Algorithm 2 - line 3 - g^Tr_last is a vector and, therefore, a value cannot be assigned to it.
questions: questions: 1) Does it matter which cost the algorithm chooses to be f_1? Is it better to choose a cost for f_1 that has many different values in the graph or one that has only a few different values? Did you try different policies for choosing this cost?
2) Assume we modify the given graph and add a large value to all edges, making them non-negative. In this case, will all state-of-the-art MOPS algorithms also be able to return all the Pareto Frontier solutions (assuming no negative cycles/the high-level is executed before)? In general, it seems that all state-of-the-art algorithms can be adjusted to solve multi-objective path finding with negative weights. What makes these algorithms (as they are) unable to find all solutions in this setting? Can you provide an example of where these algorithms don't return the same solution as MWMOA*?

--- Post-rebuttel ---
Thank you for answering my questions. I suggest adding a short discussion to the paper on the fact that adjusting existing MOSP algorithms to solve MOSP with negative cost is not straightforward.
strength_weakness: strength_weakness: A "potential" weakness is identified, acknowledging first that it might stem from a lack of detailed scrutiny or the reviewer's non-specialization in the field. Specifically, the significance of Algorithm 1, particularly the part detecting negative cycles, is questioned. It appears to be rather straightforward, or not? 

Additionally, the reviewer expresses curiosity about the perceived importance of negative weights and suggests a potential solution involving the addition of a base value to all edges to eliminate negative costs without altering solution optimality. It is most-likely a naive question?  

I understand that the actual challenge of negative weights might not be such a trivial matter. If it indeed presents a challenge, how is it possible that NWMOA* is compared with all the other existing algorithms (such as EMOA*, TMDA, and LTMOA*), while these algorithms are unable to handle negative weights at all?
questions: questions: 1) The title of the paper highlights the importance and novelty of "negative cycles," but based on Algorithm 1, isn't it *almost* trivial to detect them?

2) If "negative weight" has not been considered before, how is it possible that the current algorithm is compared with other existing algorithms that, by nature, do not take negative weights into account?
strength_weakness: strength_weakness: 1. Although the paper is presented as a new MO search algorithm NWMOA that can handle negative weights, it seems more like a paper that describes several independent techniques. For example, the high level of NWMOA* can be combined with existing MO search algorithms like EMOA* and LTMOA* as well. The speed-up techniques also seem applicable to other MO search algorithms and are not related to the presence of negative weights.

2 Some of the proposed techniques have appeared in existing works. Although some of these papers are already cited, I think the authors should discuss them in more detail.
2.i) Using bucket queue and ordering nodes according to only f1 value has appeared in [1]. Although [1] focuses on a different problem, the Weight Constraint Shortest Path (WCSP) problem, it is not surprising that the technique is transferable given the close relation between WCSP and MOSP, as discussed in [1]. 
2.ii) EMOA*[2] also employed a log time dominance checks mechanism for problems with 3 objectives and skips checking those truncated cost vectors if their first components are larger than that of the vector being checked. Although EMOA* uses a different data structure to implement this idea, I think it should be mentioned in this paper.

3. It was not initially clear to me why consistent heuristics are always available for bounded problem instances, and I think the paper would benefit from adding such a discussion to the theoretical results. 

4. Part of the pseudo-code is inconsistent with the text and seems inefficient. 
4.i) On Lines 4-7 of algorithm 1, iterating over the entire S and computing a cost-i-optimal path seems extremely inefficient. However, what is described in the text (k runs of Bellman-Ford or Dijkstra’s) seems more reasonable. 
4.ii) The remove and insert operations on Lines 7 and 9 of algorithm 4 seem to take O(N) time, given that dynamic arrays are used to implement V. Is NWMOA really implemented this way?

In the abstract and the conclusion, the improvement of performance seems to be over-claimed. For example, the abstract claims that NWMOA "outperforming the state of the art by up to an order of magnitude." If we look at the results, LTMOA seems to be the state-of-the art and is outperformed by at most 4 times.

[1] Ahmadi, Saman, et al. "Enhanced Methods for the Weight Constrained Shortest Path Problem: Constrained Path Finding Meets Bi-objective Search." arXiv preprint arXiv:2207.14744 (2022).
[2] Ren, Zhongqiang, et al. "Enhanced multi-objective A* using balanced binary search trees." Proceedings of the international symposium on combinatorial search. Vol. 15. No. 1. 2022.
questions: questions: Please address my point 4 in the weakness section. How are algorithms 1 and 4 actually implemented in the code?