Heuristic-Search Approaches for the Multi-Objective Shortest-Path Problem: Progress and Research Opportunities

1 Introduction

Many optimization problems involve multiple objectives that should be optimized. For example, when planning a driving route, one may wish to minimize both driving distance as well as tolls. Alternatively, when planning power line routes one may wish to consider both economic and ecological impacts Such problems have been used in numerous applications where decisions need to be taken when it is not possible to simultaneously optimize the different objectives [Miettinen, 2012; Roijers and Whiteson, 2017; Hwang and Masud, 2012; Emmerich and Deutz, 2018]. Multiobjective optimization typically consists of an optimization phase in which a set of possible solutions is computed and a decision-making phase in which a decision maker chooses a solution computed in the optimization phase [Roijers and Whiteson, 2017].

In this paper we restrict ourselves to the optimization phase that occurs in a very specific instance of multiobjectiveoptimization problems termed the multi-objective shortestpath problem, a generalization of the well-studied shortestpath problem. This family of problems is not new with results dating back to the 1970's [Vincke, 1976] and several surveys on the topic appeared [Cl´ımaco and Pascoal, 2012;

Current and Marsh, 1993; Skriver, 2000; Tarapata, 2007; Ulungu and Teghem, 1991].

Nevertheless, the field of heuristic search has made significant progress which resulted in a new and growing interest in the sub-field of multi-objective search. To this end, we present an overview of the field with an emphasis on results obtained in recent years using heuristic-search techniques. Importantly, other approaches which are out of the scope of this paper have been used. These include evolutionary algorithms (see, e.g., [Pangilinan and Janssens, 2007; Li et al., 2015]), integer programing (see, e.g., [Halffmann et al., 2022]), as well as reinforcement-learning algorithms (see, e.g., [Tozer et al., 2017; Hayes and others, 2022]).

Perhaps the most closely-related books and reviews are on the topic of multi-objective optimization in sequential decision problems, commonly modeled as Markov decision processes, which can be seen as a generalization of our problem [Roijers et al., 2013; Roijers and Whiteson, 2017]. However, restricting the problem to multi-objective shortest-path computation opens the door for highly-efficient algorithms as well as new algorithmic challenges. Advances in our setting can then be used to advance the field of multi-objective optimization in sequential decision problems.

Outline We begin in Sec. 2 by introducing notation and our problem definition and continue in Sec. 3 to describe general algorithmic building blocks common to many state-of-the-art algorithms. Subsequently, we start with a general overview of relevant work in Sec. 4 followed by a deep-dive into recent work in Sec. 5 with an emphasis on new challenges. We then move on (Sec. 6) to describe commonly-used benchmarks and conclude (Sec. 7) with a discussion and summary.

2 Notation and Setting

In this section, we introduce relevant notation (Sec. 2.1) and the multi-objective shortest-path problem (Sec. 2.2).

2.1 Notation

As we will see, paths in our setting will have a cost value for each objective. Thus, a common practice is to associate cost vectors with paths. Here we introduce the relevant notation.

Boldface font indicates vectors, lower-case and upper-case symbols indicate elements and sets, respectively. The notation pi will be used to denote the i'th component of p. The addition of two d-dimensional vectors p and q and the multiplication of a real-valued scalar k and a d-dimensional vector p are defined in the natural way, namely as p + q = (p1+q1, . . . , pd+qd) and kp = (kp1, . . . , kpd), respectively.

Let p and q be d-dimensional vectors. We say that p weakly dominates q and denote this as p ⪯ q if ∀i, pi ≤ qi. We say that p dominates q and denote this as p ≺ q if p weakly dominates q and ∃j, pj < qj. Similarly, when p doesn't dominate (resp. doesn't weakly dominate) q, we will write p ⊀ q (resp. p ⪯̸ q). For p ̸= q, if p ⪯̸ q and q ⪯̸ p we say that p and q are mutually undominated. Finally, we say that p is lexicographically smaller than q and denote this as p ≺lex q if pk < qk for the first index k s.t. pk ̸= qk.

Let X be a set of d-dimensional vectors. We say that X is a mutually undominated set if all pairs of vectors in X are mutually undominated (namely, no vector in X weakly dominates any other vector in X). Now, given a (notnecessarily mutually undominated) set X, MU(X) is a costunique subset of X that is a mutually undominated set. 1 Note that MU(X) ⊆ X and that MU(X) may not be unique.

Finally, let p and q be two d-dimensional vectors and let ε be another d-dimensional vector such that ∀i εi ≥ 0. We say that p approximately dominates q with an approximation factor ε and denote this as p ⪯ε q if ∀i, pi ≤ (1 + εi) · qi.

Example 1. Consider the following two-dimensional vectors p = (2, 4), q = (2, 4), r = (3, 6) and w = (3, 2) Here, p ⪯ q (i.e., p weakly dominates q), p ≺ r (i.e., p dominates r) and both p ⊀ w and w ⊀ p (i.e., p and w are mutually undominated). Similarly, for ε = (1, 2) we have that r ⪯ε p (i.e., r approximately dominates p). Finally, we have that p ≺lex w ≺lex r and if we set X = {p, q, r,w}, then MU(X) can be either {p, w} or {q, w}.

2.2 Setting

A multi-objective search graph is a tuple (S, E, c), where S is the finite set of states, E ⊆ S ×S is the finite set of edges, and c : E → Rd≥0 is a cost function that associates a ddimensional vector of non-negative real costs with each edge. A path π from s1 to sn is a sequence of states s1, s2, . . . , sn such that (si, si+1) ∈ E for all i ∈ {1, . . . , n - 1}.

We define the cost of a path π = s1, . . . , sn as c(π) = ∑n-1 i=1 c(si, si+1). Given paths π and π′ , we extend all the above definitions to paths. E.g., we say that π dominates (resp. weakly dominates) π′ and denote this as π ≺ π′ (resp. π ⪯ π′ ) if c(π) ≺ c(π′ ) (resp. c(π) ⪯ c(π′ )).

1 A set X is said to be cost unique if ∀p, q ∈ X ∃k s.t. pk ̸= qk.

Let (S, E, c) be a multi-objective search graph and sstart ∈ S a start state. The complete Pareto-optimal frontier of s, denoted as ˜Πs, is the set of all paths from sstart to s that are not weakly dominated by any other path from sstart to s. As ˜Πs may contain multiple paths with the same cost, we are often interested in a subset of ˜Πs which contains only mutuallyundominated paths. We call such a set the cost unique pareto optimal frontier or just Pareto-optimal frontier for short.

Typically, we are also given a goal state sgoal ∈ S and we call a path from sstart to sgoal a solution and its Paretooptimal frontier, which we denote Π∗ , as the Pareto-optimal solution set. See Fig. 1. Intuitively, Π∗ contains all "interesting" paths-those that are not dominated by any other solution and may be candidate solutions that the decision maker will choose from. However, computing Π∗ is NPhard [Serafini, 1987] as its cardinality may be exponential in |S| [Hansen, 1980; Ehrgott, 2005; Breugem et al., 2017]. Even determining whether a path belongs to Π∗ is NP-hard [Papadimitriou and Yannakakis, 2000].

In real-world settings we are often not interested in the entire Pareto front-it's too large to present to decision makers. Thus, we are often interested in computing a bounded approximation of Π∗ . To this end, given an approximation factor ε, an ε-approximate Pareto-optimal solution set Π∗ε is a set of solutions such that every path in Π∗ is ε-dominated by a path in Π∗ε . Note that (i) the ε-approximate Pareto-optimal solution set is not necessarily unique and that (ii) Some variants of this definition require that Π∗ε ⊆ Π∗ while others don't. Namely, they allowΠ∗ε to contain solutions that do not belong to Π∗ (but still approximately dominating solutions in Π∗ ).

Example 2. Consider the graph presented in Fig. 2 that contains the following solutions πp = ⟨sstart, s1, s3, sgoal⟩ with c(πp) = (2, 4), πq = ⟨sstart, s3, sgoal⟩ with c(πq) = (2, 4), πr = ⟨sstart, sgoal⟩ with c(πr) = (3, 6) and πw = ⟨sstart, s2, s3, sgoal⟩ with c(πw) = (3, 2). Note that solution costs correspond to the vectors used in Example 1. Here, the complete Pareto-optimal frontier ˜Πs3 to s3 contains all three paths to s3 while a Pareto-optimal frontier to s3 contains the paths that traverse s1 and s2. Finally, a Pareto-optimal solution set Π∗ is {πp, πw}, and for an approximation factor of ε = (1, 2) an ε-approximate Pareto-optimal solution set Π∗ε can be {πp}, or {πr},

3 Algorithmic Problems and Building Blocks

In this section, we describe the fundamental problems that multi-objective search algorithms typically need to solve (Sec. 3.1) as well as key algorithmic building blocks used by many state-of-the-art algorithms (Sec. 3.2 and 3.3).

3.1 Dominance Checks

Recall that in the single-objective shortest-path problem we are only required to maintain one path to each state (as one path weakly dominates all other paths found so far). In contrast, in the multi-objective case we often need to store a mutually undominated set of paths. When an algorithm considers a new path, we need to check if it is dominated by any of the paths found so far. If this is not the case, we need to update the mutually undominated set of paths maintained, possibly deleting an existing path if it is dominated by the new path. These operations, which are key in many algorithms, are formalized in the following two problems, which pinpoint the additional complexity inherent in multi-objective search.

Problem 1 (Dominance Check (DC)). Given a mutually undominated set X of d-dimensional vectors (with d ≥ 2) and a new d-dimensional vector p, the DC problem calls to verify whether there exists a vector q ∈ X such that q ⪯ p.

Problem 2 (Mutually Undominated Set Update (MUSU)). Given a mutually undominated set X of d-dimensional vectors (with d ≥ 2) and a new d-dimensional vector p that is not dominated by any vector in X, the MUSU problem computes MU (X ⋃{p}).

Naive solutions to the DC and MUSU problem may require O(|X|) vector comparisons in the worst case. However, datastructures such as ND-Trees [Jaszkiewicz and Lust, 2018] have been specifically tailored to improve the efficiency of these problems (see, e.g. [Fieldsend, 2020; Altwaijry and Menai, 2012]). Interestingly, these data structures are typically employed by evolutionary algorithms and not heuristicsearch algorithms.

Example 3. Consider the following two-dimensional vectors used in Example. 1 p = (2, 4), q = (2, 4), r = (3, 6) and w = (3, 2) and set X = {p, r}. Solving the DC problem for both q and w on X yields that p ∈ X dominates w and that there is no element in X that dominates w. Now, if we solve the MUSU problem for w on X we can conclude that MU(X ⋃{w}) = {p, w}.

3.2 Dimensionality Reduction

The following approach, first presented by Pulido et al. [2015] and termed dimensionality reduction, is a general technique that helps to solve the DC problem (Prob. 1). However, to describe it, we need to introduce some additional notation. For a d-dimensional vector p = (p1, . . . , pd), its truncated vector TR(p) is a (d-1)-dimensional vector without p's first component, i.e., TR(p) := (p2, . . . , pd). Similarly, given a set of vectors X, its associated set of truncated vectors is TR(X) := {TR(p)|p ∈ X}

Let X be a set of vectors and p be a vector lexicographically larger than all elements in X. Namely, ∀q ∈ X, q ≺lex p. Then, p is weakly dominated by a vector in X iff ∃q ∈ MU(TR(X)) for which TR(q) ⪯ TR(p).

We can complete the DC test in O(|MU(TR(X))|) time instead of O(|X|) time. As the cardinality of MU(TR(X)) is often much smaller than that of X, the procedure just described often requires far less comparison operations than naive solutions to Prob. 1. Moreover, for the specific setting where we have two objectives, |MU(TR(X))| = 1 (as it is the minimum of the second component of all elements in X), regardless of |X| and the test takes O(1) time.

Example 4 (adapted from [Pulido et al., 2015]). Consider the set X = {p, q, r} with p = (6, 2, 4), q = (4, 4, 5) and r = (2, 3, 6) and note that X = MU(X) and MU (TR(X)) = {TR(p)}. To test if w = (7, 2, 4) is dominated by a vector in X (not using dimensionality reduction) may require up to three vector comparisons but because |MU (TR(X)) | = 1 and TR(p) ⪯ TR(w), we only need one vector comparison to conclude that w /∈ MU (X ⋃{w}).

3.3 Heuristics

Similar to single-objective search algorithms, multi-objective search algorithms often use a heuristic function to guide the search. A single-valued heuristic h : S → Rd≥0 estimates the cost to sgoal from every state s. 2 We say that h is admissible iff ∀s ∈ S, h(s) ⪯ c(π) for any path π from s to sgoal. Similarly, h is consistent iff h(sgoal) = (0, . . . , 0) and h(s) ≤ c(s, s′ ) + h(s′ ) for all (s, s′ ) ∈ E.

For any path πs from sstart to some state s, if h is admissible and if there exists a path πgoal ∈ Π∗ such that c(πgoal) ⪯ c(πs)+h(s), then any path extending πs to sgoal will be dominated by πgoal. If such a setting is identified by a search algorithm, it can discard πs. We call this goal pruning (other pruning techniques exist that do not use heuristics).

Unless stated otherwise (see Sec. 5.1), existing algorithms use the so-called "ideal point heuristic" hideal which combines a set of d single-objective heuristics h1, . . . , hd. Here, hi : S → R≥0 corresponds to the shortest path from each state according to the i'th objective and ∀s ∈ S hideal(s) := (h1(s), . . . , hd(s)). The ideal point heuristic, which is admissible, is easily computed by running d (single-objective) instances of Dijkstra's algorithm starting from sgoal (i.e., one instance for each objective).

Example 5. The ideal point heuristic hideal for state sstart in the graph depicted in Fig. 2 is (2, 2).

4 Existing Algorithms-Overview

In this section we start by reviewing algorithms to compute Π∗ (Sec. 4.1), and subsets of Π∗ (Sec. 4.2). We conclude (Sec. 4.3) by describing algorithms for variants of the multi-objective shortest-path problem.

4.1 Efficient Computation of Π∗

To efficiently compute Π∗ , both generalizations of the labelcorrecting paradigm to the multi-objective setting were suggested [Guerriero and Musmanno, 2001] as well as adaptations of the celebrated A* algorithm [Hart et al., 1968]. Here, we focus on the latter approach.

2 The reason we call this a single-valued heuristic and not simply a heuristic will be evident in Sec. 5.1.

Stewart et al. (1991) introduced Multi-Objective A* (MOA∗ ) which is a multi-objective generalization of A∗ . Similar to A∗ , MOA∗ maintain a priority queue OPEN, which contains the generated but not yet expanded nodes. MOA∗ also stores a set of solution nodes (A∗ does not do this because it halts once the first solution is found). Each node n contains a state s(n), a g-value g(n) which is the cost to reach s(n) from sstart along a path π(n), an h-value h(n), and an fvalue f (n) = g(n) +h(n). At each iteration, MOA∗ extracts a node n that is not dominated by any other node in OPEN (similar to using the minimal f -value in A∗ ). It then solves the DC problem to determine if g(n) is weakly dominated by the g-value of some other node n′ with s(n) = s(n′ ) or if f (n) is weakly dominated by the f -value of a solution node. If so, the node is pruned. If n is extracted and not pruned, MOA∗ expands it by either generating its child nodes if s(n) ̸= sgoal or adding it to the solution set by solving the MUSU problem. When OPEN becomes empty, MOA∗ terminates and returns the solution set.

MOA∗ served as the foundation to multiple extensions (see, e.g., [Mandow and De La Cruz, 2005; Mandow and De La Cruz, 2010]) which differ in which information is contained in the nodes, how nodes are ordered in OPEN, and how dominance checks are implemented and at what stages they are performed (upon generation or upon expansion). Unfortunately, as we discuss in Sec. 6, different benchmarks are used and it is not always clear if one algorithm always outperforms other state-of-the-art methods.

A key insight that was used to dramatically improve the performance of these algorithms was to order nodes in OPEN in increasing lexicographic order and apply the notion of dimensionality reduction introduced by Pulido et al. [2015] and described in Sec. 3. This was used to suggest a multiobjective search algorithm named NAMOA-dr 3 . Hern´andez et al. [2023a] adapted and simplified NAMOA-dr for the biobjective setting to suggest the Bi-Objective A* algorithm (BOA*) which allows to perform dominance checks in O(1) time when a consistent heuristic is used.

Ahmadi et al. [2021] extended BOA* by simultaneously running two BOA*-like searches from sstart-one where the lexicographical order is done according to (c1, c2) and the second where the lexicographical order is done according to (c2, c1). Ren et al. [2022c] presented Enhanced MultiObjective A* (EMOA∗ ) which efficiently maintains Paretooptimal frontiers for multiple (i.e., more than two) objectives by incrementally constructing balanced binary search trees within the MOA∗ search framework

Sede˜no-Noda and Colebrook [2019] introduced an adaption of Dijkstra's algorithm to the bi-objective setting named Bi-objective Dijkstra or BDA. Key to the efficiency of BDA is that one candidate node is stored for each state at any given point of time. This dramatically simplifies the complexity of the DC and MUSU problems solved within BDA. Consequently, the theoretical running time of BDA is |Π∗ | multiplied by Dijkstra's running time.

3 Here, 'dr' stands for dimensionality reduction.

BDA was recently extended to the multi-objective setting. Specifically, de las Casas et al. [2021b] used both a heuristic and an upper-bound on the cost to reach the target in order to improve running times. While de las Casas et al. [2021c] suggested a memory-efficient multi-objective shortest-path algorithm generalizing BDA. Here, the size of the priority queue used in the algorithm is bounded by |S|. This yields an output-sensitive running time bound for the new algorithm that is roughly the running time of Dijkstra's algorithm.

4.2 Efficient Computation of Subsets of Π∗

Following the aforementioned hardness results, and as we are often only interested in one or a few solutions that lie on, or close to Π∗ , an active line of work has been concerned with computing only a subset of Π∗ or computing Π∗ε .

Bounded Approximations of Π∗

Early approaches towards approximating Π∗ focused on Fully Polynomial Time Approximation Schemes 4 (FPTAS) [Vazirani, 2001]. Warburton [1987] used scaling and rounding techniques while Perny and Spanjaard [2008] presented another FPTAS assuming that a finite upper bound L on the numbers of arcs of all solutions in Π∗ is known. This assumption was later relaxed [Tsaggouris and Zaroliagis, 2009; Breugem et al., 2017] by partitioning the space of solution into a grid of cells whose dimensions are a function of the approximation factor and, roughly speaking, take only one solution in each grid cell. Recently de las Casas et al. [2021a] suggest an FPTAS for the dynamic multi-objective shortestpath problem in which edges undergo cost changes. Unfortunately, the complexity of FPTASs is typically bounded by a polynomial of high degree, and hence they are often slower in practice than approaches to compute Π∗ even when applied to relatively-small instances. Consequentally, running these approaches on moderately-sized graphs (i.e., with roughly 10, 000 states) is often impractical [Breugem et al., 2017].

An alternative approach to compute Π∗ε (though not necessarily in polynomial time) was suggested by Perny and Spanjaard [2008]. They suggest a simple variation of MOA∗ , termed MOA∗ε that reduces computation times by punning intermediate paths that are approximately dominated by already-computed solutions. Subsequently, Goldin and Salzman [2021] suggested PPA∗ , an extension of BOA* that outperforms MOA∗ε by introducing new pruning techniques. This was later generalized by Zhang et al. [2022b] to allow approximation of Π∗ for any number of objectives. Noteworthy is that while they all return solutions that approximate Π∗ , MOA∗ε returns solutions that belong to Π∗ while PPA∗ may return solutions not on Π∗ .

General Subsets of Π∗

A different approach to compute a subset of Π∗ is to compute the set of extreme solutions, also known as the set of supported solutions [Sede˜no-Noda and Raith, 2015]. Formally, the set of extreme solutions Π∗extreme is defined as the set of solutions whose cost lie on the convex hull of Π∗ . For a visualization, see Fig. 1.

4 An FPTAS is an approximation scheme whose time complexity

is polynomial in the input size and also polynomial in 1/ε where ε

is the approximation factor.

Interestingly, any extreme solution corresponds to finding a solution that minimizes a linear combination of the different objectives [Roijers et al., 2013]. Thus, computing the set of extreme solutions is useful when we know that the desired solution is a linear combination of the different objectives but we don't know a-priori which weights will be used and want to have all options available. Approaches to compute Π∗extreme for the bi-objective setting include a Dijkstralike method [Sede˜no-Noda and Raith, 2015] as well as a branch-and-bound-based approach that only executes a series of (single-objective) shortest-path searches [Zhang et al., 2016]. Noteworthy is that |Π∗extreme | may be orders of magnitude smaller than |Π∗ |. E.g., when comparing the two on road maps from the 9'th DIMACS Implementation Challenge: Shortest Path (see Sec. 6), |Π∗ | is larger (on average) than |Π∗extreme | by 17× on the small NY instance and by 168× on the large LKS instance.

Taking a different approach to approximate Π∗ , Legriel et al. (2010) suggest a method based on satisfiability/constraint solvers. Alternatively, Rivera et al. [2022] consider the bi-objective setting and suggest to transform the original bi-objective search problem P into another bi-objective problem P ′ such that the number of solutions of P ′ is smaller (potentially orders of magnitude smaller, depending on values of the algorithm's hyperparameters) than the number of solutions of P. Importantly, each solution to P ′ is a solution to P (though not vice-versa).

4.3 Variants of Multi-Objective Shortest-Path

Skyler et al. [2022] consider the setting where we want a solution which belongs to Π∗ whose costs are below given upper bounds on each objective. This is a variant of the constrained shortest-path problem (CSP) [Storandt, 2012]. Zhang et al. [2022a] suggest an anytime algorithm for the bi-objective setting such that whenever the algorithm is terminated, it outputs an approximate Pareto-optimal solution set.

Ren et al. [2022b] consider the problem of finding collision-free Pareto-optimal solutions for agents moving amid obstacles that follow known trajectories while simultaneously optimizing multiple objectives. Ren et al. [2022a] propose an approach based on D* Lite [Koenig and Likhachev, 2002] that allows interleaving planning and execution in the multi-objective case while Ren et al. [2021] propose to extend the multi-agent path finding problem (MAPF) [Stern et al., 2019; Salzman and Stern, 2020] to the multi-objective case.

5 Recent Advances and Open Challenges

In this section, we perform a deeper-dive into several topics in multi-objective search with an emphasis on new emerging challenges in the field.

5.1 Single-Valued vs. Multi-Valued Heuristics

Following Mandow and De La Cruz [2010] and in contrast to the single-objective setting, in the general case of multiobjective search, the heuristic value of a state s is not a single number, but a set of cost vectors. Formally, a multi-valued heuristic is defined as a mapping H : S → 2Rd≥0 . The notions of admissibility and consistence introduced for single-valued heuristics are naturally extended to multi-valued heuristics as well as the notion of goal pruning which we now detail.

A multi-valued heuristic H is admissible iff for every state s and every path πs from s to sgoal, H contains a cost vector that weakly dominates c(πs).

Example 6. Consider the graph presented in Fig. 2 and the single-valued heuristics h1 and h2 s.t. h1(sstart) = (2, 4), h2(sstart) = (3, 2), h1(s1) = h2(s1) = (2, 3), h1(s2) = h2(s2) = (2, 2) and h1(s3) = h2(s3) = (1, 1). If we set H = {h1, h2}, then it is easy to verify that H is admissible

Goal Pruning Using Multi-Valued Heuristics

Let n be a node in a search algorithm corresponding to some path π(n) leading to a state s(n). Furthermore, assume that we are using an admissible multi-valued heuristic H and that Πgoal is the current mutually-undominated set of solutions found by the algorithm. The node n can be pruned if for every single-values heuristic h ∈ H there exists a solution πgoal ∈ Πgoal that weakly dominates n's f-value when computed according to h. Namely, n can be pruned if

Testing for goal pruning can be easily implemented in O(d · |H| · |Πgoal|) time. However, for the case where a singlevalued heuristic is used (i.e., when |H| = 1) recent results suggest how to do this more efficiently: As mentioned in Sec. 4.1, Hern´andez et al. [2023a] describe a method to test for goal pruning in constant time when considering only two objectives and Ren et al. [2022c] show that testing for goal pruning can be done in O(log (|Πgoal|)) time when considering three objectives and in O((d-1) · |Πgoal|) for an arbitrary number of objectives d. However, it is not clear how to extend these results when using multi-valued heuristics.

Heuristics Used in Empirical Evaluations

Typical empirical evaluation (see e.g., [Stewart and White III, 1991; Hern´andez et al., 2023a] and Sec. 6 below) only make use of the "ideal point heuristic" hideal. The only work that empirically considers the implication of using a multi-valued heuristic is the recent paper by Geißer et al. [2022] in which they study the question of how to construct informative multivalued admissible heuristics. Specifically, they generalized several classes of well-known admissible planning heuristics to the multi-objective case . Namely abstraction-based (see, e.g., [Sievers and Helmert, 2021]), critical path-based (see, e.g., [Haslum and Geffner, 2000]), and LP/IP-based heuristics (see, e.g., [Pommerening et al., 2014].Interestingly, on the benchmarks tested, these heuristics are often more informed than hideal. 5 Having said that, on other benchmarks test, either this is not true or the overhead of computing these heuristics is large and the total runtime is larger than when using hideal.

5 Roughly speaking, Geißer et al. [2022] define a multi-valued heuristic H1 to be more informed than another heuristic H2 if using H1 results in less node expansions than when using H2.

To summarize, using multi-valued heuristics in the context of multi-objective shortest-path problems offers the potential to dramatically speed up multi-objective search algorithms. However, it also raises two key challenges:

• C1 How to efficiently compute informative multivalue heuristics?
• C2 How to effectively use multi-value heuristics to prune nodes in heuristic search algorithms?

5.2 Correlated Objectives

In many multi-objective settings there is some correlation between the different objectives which may be positive or negative. For example, in road networks, one may consider distance and time as two positively-correlated objectives (shorter routes are typically fast to traverse). Alternatively, one may consider distance and how beautiful a route is as two negatively-correlated objectives (scenic routes are typically longer to traverse).

Clearly, the correlation between the objectives may have a dramatic effect on the size and structure of Π∗ . In the extreme case, where all objectives are identical (and hence perfectly correlated), the multi-objective problem essentially collapses to a single-objective problem. When the correlation is high, |Π∗ | may be extremely large but |Π∗ε | may be quite small, even for small approximation factors. However, it is not clear how correlation is defined in our setting: is this correlation along edges? along paths? Moreover, it is not clear how correlation can be used to design efficient algorithms.

Interestingly, these types of questions received little attention from the research community and, to the extent of our knowledge, these were primarily focused on the bi-objective setting. Mote et al. [1991] evaluated random graphs and grid graphs with a positive correlation between the two objectives associated with each edge. They showed that |Π∗ | decreases when the correlation increases and that in such cases |Π∗ | is relatively small. Similar results were shown by BrumbaughSmith and Shier [1989] when evaluating graphs where the two objectives associated with each edge are randomly generated from a bi-variate normal distribution.

The only work that introduces a formal model related to correlated objectives is the work of M¨uller-Hannemann and Weihe [2006]. Specifically, their model can be used to describe (to some extent) the structure of road networks, communication networks and train graphs. 6 Roughly speaking, this model assumes that edges can be classified into a small number of classes (e.g., in road networks, edges can be classified into highways, national roads, local roads etc.). Consequently, solutions on Π∗ often have the structure that edge class increase and then decrease (such paths are termed bitonic). For example, it is quite atypical that solutions in a road network that belong to Π∗ will include a local road connecting two highways or that in a train network paths belonging to Π∗ include a local train between two high-speed trains. While in the worst-case graphs that fall under this model may include an exponentially large Pareto-optimal solution set, the empirical evaluation of M¨uller-Hannemann and Weihe suggest that the size of Π∗ for each visited state can be regarded as constant for all practical purposes.

6 For a precise definition of train graphs, see [Schulz et al., 2000].

A deeper understanding of how objectives are correlated can, and should, be used in practical applications. To this end, we suggest to explore the following research challenges:

• C3 How to define the correlation between different objectives?
• C4 Assuming we know that the objectives are correlated, how can this be used to speed up heuristic search algorithms?

5.3 Ordering Objectives

Recall that in multi-objective search problem it is common practice to order nodes in lexicographical order. This implies that there is some intrinsic ordering between the different objectives. Interestingly, this order may have a dramatic effect on the algorithm's running times. For example, we evaluated (Tbl. 1) the running time of LazyLTMOA* [Hernandez et al., 2023b], a variant of EMOA∗ , on four tri-objective instances of the New York (NY) map from the 9'th DIMACS Implementation Challenge: Shortest Path. Here, the first, second and third objectives are the travel time T, the travel distance D and the economic cost M (see [Pulido et al., 2015] for a precise definition of the economic cost).

As expected, the runtime increases when |Π∗ | grows. However, we observed that order M-T-D can be several times faster (two orders of magnitude faster in instance three) than order D-T-M. A similar phenomena was observed for two objectives [Hern´andez et al., 2023a; Ahmadi et al., 2021].

Thus, we suggest to explore the following challenge:

C5 How to choose the best lexicographic order when ordering nodes to expand?

5.4 ParalelizingMulti-Objective Algorithms

In early work, Guerriero and Musmanno [2001] state that "parallel computing [. . . ] represents the main goal for future developments". However, there is surprisingly little work on parallel multi-objective shortest-path algorithms.

More than a decade later, Sanders and Mandow [2013] present a parallel variant of one of the first algorithms for the bi-objective setting [Martins, 1984].Their approach, focused on the bi-objective setting with an emphasis on the theoretical asymptotic running time, targets the heap operations used to order OPEN as the main source of parallelism. However, no experiments are provided and the authors state that their algorithm "might be too complicated to be practical". Soon after, Erb et al. [2014] present a parallel biobjective shortest-path algorithm that uses weight-balanced B-trees with bulk updates. Their work, which was empirically evaluated and demonstrated dramatic speedups builds on the the work by Sanders and Mandow [2013] that on first glance looks impractical. Finally, Medrano and Church [2015] present another parallel approach for computing the set of extreme solutions for the bi-objective setting. Their results indicate the applicability of their method both on small-scale personal machines as well as large-scale shared memory supercomputers.

Additional work is a modification of BOA*, suggested by Ahmadi et al. [2021], in which one search runs from the source and another from the target. These searches may be executed in parallel with limited information reuse but no big empirical improvement was reported when paralelization was used. de las Casas et al. later adopts the similar modification for their bi-objective [de las Casas et al., 2021b] and multiobjective [de las Casas et al., 2021c] search algorithms.

To summarize, parallelizing multi-objective search is extremely under-explored and a challenge, already identified over twenty years ago, largely left unnoticed is

C6 How to efficiently and effectively parallelize search algorithms in the multi-objective setting?

5.5 Memory Footprint

Multi-Objective search algorithms often suffer from a large memory footprint, especially when the number of solutions in Π∗ and the number of states S are large. This is because we typically store multiple paths for each state that need to be allocated in memory. For example, Ahmadi et al. [2021] reports the use of 96GB of memory (allocating 1B search states). While runtime is key in multi-objective search performance, typically improving memory usage implies increasing runtime [Coego et al., 2009; Kothare et al., 2022].

To cope with high memory usage, Kothare et al. [2022] proposed PE-EMOA* which applies the notion of partial expansion (see, e.g., [Yoshizumi et al., 2000]) to the multiobjective setting. PE-EMOA* uses a user-defined hyperparameter to balance runtime and memory footprint and was shown to be effective in grid maps with a large branching factor [Rivera et al., 2020]. However in road maps, the improvement in memory usage is negligible.

Another recent technique to save memory was presented by Ahmadi et al. [2021]. Considering that BOA* only expands nodes once, they propose to recycle the memory used to store already-processed nodes, while storing their backtracking information in other compact data structures. They report a decrease of 5× in memory used on average on road maps while also slightly improving the runtime. Other techniques to save memory include extensions of linear-memory algorithms for single objective search to the multi-objective setting [Coego et al., 2009; Coego et al., 2013].

C7 How to efficiently cope with the memory footprint in heuristic-search algorithms without compromising on runtime?

6 Benchmarks

Key to the advancement of a research field that contains the empirical evaluation of algorithms is a standard set of benchmarks that spans multiple domains, each with its own characteristics. For example, the standardization of such a set of benchmarks in the MAPF domain presented by Stern et al. [2019] played a critical role in the advancement of the field. Similarly, the International Planning Competition (IPC) (see, e.g. [Vallati and others, 2015]) has been an important driver for research in the field of classical planning. In particular, they have resulted in a language for describing planning domains and problems (PDDL), a body of benchmark domains and problems in that language, and the ability to directly compare different generative planning techniques. Unfortunately, the multi-objective community is lacking such a set of benchmarks with different papers using different benchmarks to evaluate their algorithms. In this section, we review different benchmarks used in the hope that this will spark a discussion by the community which, in turn, will lead to a standard set of benchmarks.

Many papers (see, e.g., [Hern´andez et al., 2023a; Pulido et al., 2015]) use the 9'th DIMACS Implementation Challenge: Shortest Path 7 which is a set of road networks with two cost functions available. A third cost function was suggested by Enriqueand and Lawrence [2011] and used in subsequent studies. A recent paper by Weise and Mostaghim [2022] proposes five objective functions commonly-available on road networks representing distance, traveling time, delays caused by accidents, curvature and elevation. These can be applied to any real-world data such as OpenStreetMap. 8

Another set of benchmarks used (see, e.g., [de las Casas et al., 2021c; de las Casas et al., 2021b]) is NetMaker 9 which allows one to generate synthetic graphs with a moderate number of nodes. Alternative studies (see, e.g., [Pulido et al., 2015; Ren et al., 2022c]) suggested to use four-connected grids, where each component of the cost vector of an edge is a randomly generated integer from a given range.

Recently, Geißer et al. [2022] show that some well-known planning domains can be seen as multi-objective. For example, in the Sokoban puzzle, the number of moves and the number of pushes are two different objectives.

C8 How to generate a publicly-available, diverse, comprehensive set of benchmarks that will be used by the entire community?

7 http://www.diag.uniroma1.it//∼challenge9/.

8 https://www.openstreetmap.org/.

9 https://www.netmaker.org/

7 Summary and Discussion

Multi-objective search is an important research topic with applications ranging from route planning for power lines considering economic and ecological impacts [Bachmann et al., 2018], transporting hazardous materials considering travel distance and risk [Bronfman et al., 2015], and inspecting a region of interest using cameras placed on-board robotic platforms [Fu et al., 2019; Fu et al., 2021].

While being an active area of research for several decades, there is ample room to improve the state-of-the-art by addressing the key challenges that we described in this paper. A catalyst that will allow the field to further progress is a unified suite of benchmarks agreed upon by the community. To this end, we lay the groundwork by reviewing different domains used in different papers. However, the work is not complete: a comprehensive set of benchmarks should be diverse and analyzed according to how much the objectives are correlated and what the structure of the Pareto-optimal solution set for each benchmark is (see Sec. 5).

Acknowledgements

This research was supported by the United States-Israel Binational Science Foundation (BSF) grants no. 2019703 and 2021643 and by the Israeli Ministry of Science & Technology grants No. 3-16079 and 3-17385. The research at the University of Southern California was supported by the National Science Foundation (NSF) under grant number 2121028. The research at Universidad San Sebasti´an was supported by the National Center for Artificial Intelligence CENIA FB210017, Basal ANID, and the Centro Ciencia & Vida, FB210008, Financiamiento Basal ANID.