Parallelizing Multi-Objective A* Search (Extended Abstract)

1 Introduction

The Multi-Objective Shortest Path problem (MOSP) aims to find all Pareto-optimal paths between a given pair of nodes in a network where each edge is associated with multiple attributes. MOSP can emerge in various real-world problems. Examples are multi-objective path planing for mobile robots [Ren et al., 2021] and multi-objective route selection problem for unmanned air vehicles [Tezcaner and K¨oksalan, 2011]. Among existing MOSP solution methods, MOA* [Stewart and White III, 1991] is considered state of the art, with recent extensions demonstrating the significant contribution of heuristic search to improving MOA*'s performance in challenging cases [Salzman et al., 2023]. The EMOA* [Ren et al., 2022], TMDA [Maristany de las Casas et al., 2023], LTMOA* [Hern´andez et al., 2023], and NWMOA* [Ahmadi et al., 2024a] are recent approaches that utilize best-first search to solve point-to-point MOSP more efficiently, with NWMOA* demonstrating better performance than other approaches.

In many domains, the performance of planning algorithms can be impacted by slight modifications to the search setting, such as changes in tie-breaking rules or the ordering of operators [Knight, 1993; Howe and Dahlman, 2002; Ahmadi et al., 2024b]. In the case of multi-objective search, while MOA* provides a robust framework for solving MOSP optimally, the ordering of objectives can have a "dramatic effect on the algorithm's running time" [Salzman et al., 2023]. Incorporating multiple objective orderings in a parallel setting can be seen as a potential solution to the above shortcoming. Despite being well studied for single-objective search in various settings [Valenzano et al., 2010; Zhou and Zeng, 2015; Fukunaga et al., 2018], parallelization remains largely underexplored in the multi-objective search literature. While existing approaches mainly focus on parallelizing search procedures [Sanders and Mandow, 2013; Erb et al., 2014; Ulloa et al., 2024], the bi-objective search algorithm BOBA* [Ahmadi et al., 2021] and its weight-constrained adaptation [Ahmadi et al., 2022] provide a parallel framework that executes two concurrent searches with different objective orderings, but they are limited to handling only two objectives.

∗ Short version of [Ahmadi et al., 2025], ICAPS 2025 Best Paper

This research proposes a parallel search framework for MOA*, representing the first attempt to parallelize multiobjective search beyond two objectives. Inspired by the search scheme of BOBA*, the proposed approach runs multiple MOA* searches in parallel, each operating under a different objective ordering. Central to the framework is an innovative upper-bounding technique that not only shrinks the scaled search space but also reduces the problem dimensionality to one under specific conditions. Experimental results demonstrate the effectiveness of the proposed framework in achieving scalable acceleration of MOA*, with speedups proportional to the number of objectives.

2 Notation and ProblemFormulation

We consider a directed graph G = (S, E), where S is a finite set of states and E ⊆ S × S is a set of directed edges. Each edge e ∈ E is associated with a vector-valued cost function cost : E → Rk , where cost(e) = (cost1, cost2, . . . , costk). A path π is defined as a sequence of states ⟨u1, u2, . . . , un⟩ such that (ui, ui+1) ∈ E for all i < n. The cost of a path is obtained by aggregating edge costs componentwise: cost(π) = ∑n-1 i=1 cost(ui, ui+1). The MOSP problem aims to find a set of Pareto-optimal paths between a given pair of (start, goal ) states. A path π∗ is Paretooptimal if there is no other path π′ that simultaneously satisfies costi(π′ ) < costi(π∗ ) and costj(π′ ) ≤ costj(π∗ ) for any i, j ∈ {1, . . . , k}|i ̸= j.

In a search setting, we represent paths using nodes. A node x encodes a path ending in state s(x), where s(·) maps nodes to states. Each node maintains (i) a cost vector g(x) representing the cost from start to s(x), (ii) an estimated total cost vector f(x) from start to goal via x, and (iii) a pointer parent(x) indicating its predecessor in the search tree. All vector operations are defined element-wise, and vector comparisons use standard ordering, where f(x) ⪯ f(y) indicates fi(x) ≤ fi(y) for all i ∈ 1, . . . , k. We additionally define a truncation operator Tr(v) that removes the first component of a vector, with Trλ meaning λ successive truncations. Definition. A vector v is weakly dominated by v′ if v′ ⪯ v. It is strictly dominated if v′ ⪯ v and v′ ̸= v. A node y is weakly dominated by node x if f (x) ⪯ f (y).

3 Multi-Objective A* Search

Multi-objective pathfinding with A* involves a systematic search by expanding nodes in best-first order, where paths with the smallest estimated start-goal costs are given higher priority. These estimates are traditionally established as f (x) = g(x) + h(s(x)) where a consistent heuristic function h : S → Rk estimates lower bounds on the cost of extended paths to goal [Hart et al., 1968].

MOA* maintains a frontier set Open of nodes ordered by f - values, and a solution set Sols containing all non-dominated goal-reaching nodes. For each state u ∈ S, a set GTr (u) stores mutually non-dominated truncated cost vectors corresponding to previously expanded nodes with u. At each iteration, a node x with minimal f -value is extracted from Open. The node is discarded if it is weakly dominated either by a previous expansion with s(x) or by already discovered solutions. These conditions ensure that only promising nodes are expanded. To perform dominance tests more efficiently, MOA* exploits a structural property of the best-first search by removing the first cost component, which is known to be non-decreasing. Dominance checks are then performed in this reduced space: a node x is pruned if Tr(g(x)) (resp. Tr(f(x))) is weakly dominated by any truncated cost vector in GTr (s(x)) (resp. GTr (goal)). If x is not pruned, its truncated vector is inserted into GTr (s(x)), and any dominated entries are removed to maintain a non-dominated set. If s(x) = goal , x is added to Sols; otherwise, it is expanded by generating successors over Succ(s(x)). Successor nodes can be tested for dominance either upon generation or upon extraction from Open, with the latter approach preferred in practice [Hern´andez et al., 2023]. The search terminates when Open is empty, returning Sols as the set of solutions.

4 Parallelized MOA*

The idea behind our parallel framework is straightforward: multiple MOA* searches are executed simultaneously under different objective orderings. Algorithm 1 presents the higher level of the proposed parallel MOA*. Given a k-dimensional MOSP instance, the algorithm uses k CPU threads to run k individual MOA* searches in parallel such that the i-th thread , i ∈ {1, . . . , k}, is provided with a cost and heuristic function that return costi and hi as primary cost and heuristic, respectively (lines 3-5). One such set of orderings can simply

Algorithm 1: Parallel MOA*- Higher Level

Input: A MOSP Problem (G, start , goal , k) Output: A cost-unique Pareto-optimal solution set 1 Sols ← ∅k , f ←∞k 2 for i ∈ {1, . . . , k} do in parallel 3 c ← cost function with cost i as primary cost 4 h←heuristic function corresponding to c 5 Parallelized MOA* on (G, c, h, start, goal , Solsi)

6 return Unique(⋃ki=1 Solsi)

be all cyclic permutations of the costs. The parallel loop can terminate as soon as one thread finishes its search.

Upper-bounding mechanism: Naive parallelization may lead to substantial overlap between the search spaces of different threads, resulting in many duplicate solutions. To mitigate this overhead, we design a novel upper-bounding mechanism that reduces the search effort in each parallelized MOA* instance by establishing an information-sharing pipeline between threads. Let (f1, f2, . . . , fk) be the cost of the solution node x obtained in the first thread guided by cost1. The search in this thread prunes paths with estimated (cost2, . . . , costk) no better than (f2, . . . , fk) due to the first dimension already being non-decreasing. Now, assume that the second thread, guided by cost2, has just extracted a node y with the primary cost of f ′2 . We claim that the dimension in the dominance pruning with x (in the first thread) can be further reduced if we observe f2 ≤ f ′2 , that is, as soon as we see f2 within the explored range of the second thread. In this case, we just need to check the estimated (cost3, . . . , costk) of paths in the first thread against (f3, . . . , fk) with the second dimension also removed. This pruning is correct, as it means extension of paths with estimated costs no smaller than (f3, . . . , fk) - in any dimension - would definitely lead to a start-goal path no better than either x, or one of the solutions obtained in the second thread with cost2 smaller than f ′2 (second thread explores nodes in non-decreasing order of cost2 estimates). The doubly truncated upper bound (f3, . . . , fk) can be further truncated with a similar reasoning: if we observe f3 within the explored range of the third thread (guided by cost3), we can perform one more truncation and use the vector (f4, . . . , fk) as a tighter upper bound instead. It then becomes clear that k - 1 consecutive truncations of (f1, . . . , fk) yields fk as a scalar upper bound on the k-th objective, reducing the dimension to one.

Cost vectors truncated k-1 times can serve as global upper bounds shared across all threads, while also enabling early termination in parallelized MOA*. Let f = (f1, . . . , fk) denote a vector of scalar global upper bounds, initially set to infinity. Under cyclic permutations of objective orderings, each thread is responsible for optimizing a different primary objective and can therefore establish one of the scalar upper bounds in f . These bounds can then be used to prune nodes in any thread whose f-values violate at least one global upper bound. Moreover, the k-th thread (and consequently the entire parallel execution) can terminate early when it extracts a node x with fk(x) > fk, since nodes in that thread are expanded in non-decreasing order of their fk-values.

Algorithm 2: i-th Parallelized MOA* (guided by fi)

Input: Problem (G, cost, h, start , goal ) and a set Sols Output: Sols updated with a subset of optimal solutions 1 Open ← ∅ 2 GTr (u) ← ∅k-1 ∀u ∈ S 3 x ←new node with s(x) = start 4 g(x) ← 0 , f(x) ←h(start) , parent(x) ←null 5 Add x to Open 6 while Open ̸= ∅ do 7 Extract node x fromOpen with the smallest f-value 8 if fi(x) ≰ fi then break 9 if IsDominated(Tr(g(x)), GTr 1 (s(x))) or IsDominatedMD(f(x),GTr (goal)) then 10 continue 11 RemoveDominated(Tr(g(x)), GTr 1 (s(x))) 12 Add Tr(g(x)) to GTr 1 (s(x)) 13 if s(x) = goal then 14 UpdateUpperBound(GTr (goal )) 15 Add x to Sols 16 continue 17 for each t ∈ Succ(s(x)) do 18 y ← new node with s(y) = t 19 g(y) ← g(x) + cost(s(x), t) 20 f (y) ← g(y) + h(t) 21 parent(y) ← x 22 if IsDominated(Tr(g(y)), GTr 1 (t)) or IsDominatedMD(f(y),GTr (goal)) then 23 continue 24 Add y to Open 25 return

Algorithm 3: IsDominatedMD

Input: A vector v and a list of sets V Output: true if v is weakly dominated, false otherwise 1 for j ∈ {1, . . . , k} do 2 if fj(v) ≥ fj then return true 3 for λ ∈ {1, . . . , k -1} do 4 if IsDominated(Trλ (v), Vλ) then return true 5 return false

To apply upper bounding, the framework maintains two shared sets: a solution set Sols = {Sols1, . . . , Solsk} together with a global upper-bound vector f (line 1 of Algorithm 1). Algorithm 2 presents the detailed procedure for the i-th parallelized MOA* search guided by fi. Compared to standard MOA*, the framework introduces three main modifications. First, to support multidimensional truncation, GTr now organizes truncated cost vectors according to their truncation level, i.e., GTr = {GTr 1 , . . . ,GTr k-1 }, where GTr λ stores vectors truncated λ times. Second, dominance checking against previously discovered solutions is generalized through the IsDominatedMD procedure (lines 9, 22). As shown in Algorithm 3, a cost vector v is first evaluated against the shared upper bound f . If it satisfies the bound, the proce-

Algorithm 4: UpdateUpperBound

Input: List of sets V Output: List of sets V updated 1 for λ ∈ {1, . . . , k -2} do 2 j ← index of the primary cost of vectors in Vλ 3 if Solsj = ∅ then continue 4 z ← The most recent solution node in Solsj 5 for v ∈ Vλ do 6 if fj(v) ≤ fj(z) then 7 Remove v from Vλ 8 if IsDominated(Tr(v),Vλ+1) then 9 continue 10 RemoveDominated(Tr(v), Vλ+1) 11 Add Tr(v) to Vλ+1 12 if Vk-1 ̸= ∅ then 13 j ← index of the scalar cost in Vk-1 14 fj ← the scalar cost in Vk-1 15 return

dure performs a sequence of dominance tests over progressively truncated representations of v. At truncation level λ, the resulting vector is compared against the corresponding set GTr λ (goal). Third, whenever a non-dominated solution node is extracted, the framework attempts to tighten the shared upper bounds through the UpdateUpperBound procedure (line 14). This procedure is detailed in Algorithm 4. In each thread, starting from the very first GTr 1 (goal) set, the procedure checks vectors of each set indexed by λ ∈ {1, . . . , k-2} for a further truncation. Let j be the primary (first appearing) cost index of the vector v in GTr λ (goal). The procedure then retrieves the most recent solution of the j-th thread from Solsj (or alternatively, the most recently extracted node in the j-th thread). The vector v can be further truncated if we observe that its fj-value is no larger than the fj-value of the retrieved solution (or the recently extracted) node from the jth thread. The truncation involves: removing the vector from its current set GTr λ , truncating it, and inserting it into the next set GTr λ+1 , while ensuring the vectors of the set remain nondominated after the new vector is added. Thus, the last set GTr k-1 is either empty or contains a single scalar. To keep the vectors of each set non-dominated, we first check the newly truncated vector against the existing candidates in GTr λ+1 . If the new vector is dominated, it does not need to be added to the set (line 8 of Algorithm 4). Otherwise, the newly truncated vector is non-dominated and should be added to the set. To keep our upper-bounding mechanism efficient, we remove from GTr λ+1 all its vectors weakly dominated by the new vector (line 10). The newly truncated vector will be added into GTr λ+1 if it is deemed non-dominated (line 11). In the end, if GTr k-1 is not empty, the procedure utilizes the (single) scalar upper bound obtained through k-1 truncations to update the corresponding global upper bound (lines 12-14).

Merging Solutions. Since nodes are not rigorously checked against all solutions in Sols, threads may still generate duplicate solutions. Therefore, the final step is to merge and return the cost-unique solutions (line 6 of Algorithm 1).

5 Experimental Results

We parallelized two recent MOA* algorithms using our framework: NWMOA*[Ahmadi et al., 2024a] and lazy LTMOA* [Hern´andez et al., 2023], all implemented in C++. All code was compiled using the GCC7.5 compiler with O3 optimization settings, and all experiments were conducted on an Intel Xeon Platinum 8488C processor with four CPU cores (eight threads) running at 2.4 GHz and with 16 GB of RAM with a one-hour timeout. Objective orderings in the parallel algorithms were defined using cyclic permutations of objectives, with one thread assigned to each ordering. For the benchmark map, we used the New York map from the 9th DIMACS Implementation Challenge: Shortest Paths (http:// www.diag.uniroma1.it/∼challenge9/download.shtml) in scenarios with three to five cost components. The edge costs are: (1) distance; (2) time; (3) the positive height difference between the endpoints of the edge; (4) the average (out)degree of the endpoints; and (5) a unit cost (one). We then evaluated all algorithms on 100 random (start , goal ) pairs per scenario.

Performance Impact of Parallelization. Table 1 compares the performance of our parallelized algorithms (main search) against their standard version, which use lexicographical ordering of objectives. We report the number of solved cases (|S| out of 100) and runtime statistics (in seconds). The runtime of unsolved cases is considered to be the timeout. We also report, for mutually solved cases, the average speed up (Sp. Up) obtained over the standard variant, and average memory usage (in GB). We observe that, compared to the standard methods, the parallel variants:

i) consistently solve more instances. In the k = 5 scenario, LTMOA*par and NWMOA*par solve 18 and 17 more instances within the one-hour timeout, respectively;

ii) offer statistically considerable runtime improvement. In the k = 4 scenario, maximum runtime of NWMOA* is reduced from (above) 60 minutes to 26 minutes, and the average runtime from 8 to 3 minutes, approximately;

iii) achieve a speed-up proportional to the problem dimension. Comparing the average speed-up factors across the scenarios, we observe a steady increase as the number of objectives rises, with the average factor growing from 1.3 in the k = 3 scenario to around 4 in the k = 5 scenario;

iv) require more space to accommodate the scaled search space. Memory usage increases proportionally as well. The parallelized LTMOA* consumes 4.4 times more memory in the k = 5 scenario, but only 1.7 times in the k = 3 scenario.

To better illustrate the runtime improvement achieved by parallelization, we present in Figure 1 the runtime distribution of each parallel algorithm against the base variant with k = 4. We observe that, in almost every individual instance, both LTMOA* and NWMOA* have performed faster when parallelized, reducing the computation time by up to an order of magnitude. Further, our detailed results demonstrate that parallel LTMOA* outperforms LTMOA* using the best objective ordering, whereas this improvement is not achieved without the proposed upper-bounding technique, highlighting its crucial role in enabling efficient parallelization of MOA*.

6 Conclusion

This research proposed the first parallel search framework for the multi-objective A* search (MOA*). While being applicable to existing MOA*-based approaches, our framework allows the space of the problem to be searched with different objective orderings simultaneously. The research also builds a unique information-sharing pipeline between concurrent searches that can reduce the dimensionality of the problem to one in certain cases. Two of the leading MOA* algorithms were parallelized based on the proposed approach. The results demonstrate the success of the proposed framework in reducing the computation time of MOA*, achieving an average speed-up proportional to the problem dimension.

Acknowledgments

This research was supported by the Department of Climate Change, Energy, the Environment and Water under the International Clean Innovation Researcher Networks (ICIRN) program grant number ICIRN000077. Saman Ahmadi is supported by Australian Research Council through project IE250100126, and Mahdi Jalili through projects DP240100963, IC240100010, IM240100042 and LP230100439.