Efficient Approximate Search for Multi-Objective Multi-Agent Path Finding

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 07:11:52

Abstract: The Multi-Objective Multi-Agent Path Finding (MO-MAPF) problem is the problem of computing collision-free paths for a team of agents while considering multiple cost metrics. Most existing MO-MAPF algorithms aim to compute the Pareto frontier of the solutions. However, a Pareto frontier can be time-consuming to compute and contain solutions with similar costs. Our first main contribution is BB-MO-CBS-pex, an approximate MO-MAPF algorithm that computes an approximate frontier for the user-specific approximation factor. BB-MO-CBS-pex builds upon BB-MO-CBS, a state-of-the-art MO-MAPF algorithm, and leverages A*pex, a state-of-the-art single-agent multi-objective search algorithm, to speed up different parts of BB-MO-CBS. We also provide two speed-up techniques for BB-MO-CBS-pex. Our second main contribution is BB-MO-CBS-k, which builds upon BB-MO-CBS-pex and computes up to k solutions for a user-provided k-value. BB-MO-CBS-k is useful when it is unclear how to determine an appropriate approximation factor. Our experimental results show that both BB-MO-CBS-pex and BB-MO-CBS-k solved significantly more instances than BB-MO-CBS for different approximation factors and k-values, respectively. Additionally, we compare BB-MO-CBS-pex with an approximate baseline algorithm derived from BB-MO-CBS and show that BB-MO-CBS-pex achieved speed-ups up to two orders of magnitude.

Main paper: 
 introduction: 
 The Multi-Agent Path Finding (MAPF) problem is the problem of finding a set of collision-free paths for a team of agents. It is related to many real-world applications (Wurman, D'Andrea, and Mountz 2008; Morris et al. 2016) . A solution is a set of collision-free paths for all agents. Computing a minimum-cost solution for the MAPF problem is known to be NP-hard (Yu and LaValle 2013; Ma et al. 2016) . In this paper, we study a variant of the MAPF problem called the Multi-Objective MAPF (MO-MAPF) problem (Ren, Rathinam, and Choset 2022) , which considers multiple cost metrics. Many real-world applications of MAPF can be viewed as multi-objective problems. For example, in multi-robot systems, some interesting cost metrics are travel distance, energy consumption, and risk.Most existing MO-MAPF algorithms, such as MO-M* (Ren, Rathinam, and Choset 2021) , MO-CBS (Ren, Rathinam, and Choset 2022) , and BB-MO-CBS (Ren et al. 2023), aim to compute the Pareto frontier of the solutions, that is, a set of all solutions that are not dominated by any other solutions, where a solution P dominates another solution P ′ if the cost of P is no larger than the cost of P ′ for every cost metric and the cost for at least one cost metric is smaller. Unfortunately, even in the single-agent case, the size of the Pareto frontier can be exponential in the size of the graph being searched (Ehrgott 2005; Breugem, Dollevoet, and van den Heuvel 2017) . Therefore, computing Pareto frontiers for MO-MAPF can be time-consuming. Existing works on multi-objective single-agent search have been proposed to compute an approximate frontier (Perny and Spanjaard 2008; Goldin and Salzman 2021; Zhang et al. 2022) instead, which significantly speeds up the search. However, this has yet to be investigated for MO-MAPF.Our first main contribution is BB-MO-CBS-pex, an approximate MO-MAPF algorithm that computes an approximate frontier for the user-specific approximation factor. BB-MO-CBS-pex builds upon BB-MO-CBS, a state-of-the-art MO-MAPF algorithm that consists of a low-level search to plan paths for each agent and a high-level search to resolve collisions. BB-MO-CBS-pex leverages A*pex (Zhang et al. 2022) , a state-of-the-art single-agent multi-objective approximate search algorithm, as the low-level search algorithm and also applies the algorithmic idea behind A*pex to to speed up the high-level search. In addition, we provide two techniques to further speed up BB-MO-CBS-pex.In practice, a too large approximation factor can cause BB-MO-CBS-pex to return only one solution, which offers no trade-off to users, while a too small one provides no chance for BB-MO-CBS-pex to speed up. Therefore, one might prefer to specify the desired number of solutions instead. Our second main contribution is BB-MO-CBSk, which builds upon BB-MO-CBS-pex and computes a set of up to k solutions for a user-provided k-value.In our experimental study, we compare BB-MO-CBS-pex and BB-MO-CBS-k with BB-MO-CBS. Our results show that BB-MO-CBS-pex and BB-MO-CBS-k solved significantly more problem instances than BB-MO-CBS within the given runtime limit of 120 seconds for different approximation factors and k-values, respectively. Additionally, we compare BB-MO-CBS-pex with BB-MO-CBS-ε, an approximate baseline algorithm derived from BB-MO-CBS. Our results show that BB-MO-CBS-pex solved significantly more instances and achieved up to two orders of magnitude speed-up compared to BB-MO-CBS-ε.We use boldface font to denote vectors or vector functions and v i to denote the i-th component of vector or vector function v. We define the addition of two M -dimensional vectors u and v as u+v = [u 1 +v 1 , u 2 +v 2 , . . . , u M +v M ]. We define the vector minimum of u and v as vector min(u, v) = [min(u 1 , v 1 ), min(u 2 , v 2 ), . . . , min(u M , v M )]. u ⪯ v de- notes that u i ≤ v i , i = 1, 2, . . . , M .In this case, we say that u weakly dominates v. u ≺ v denotes that u ⪯ v and ∃i ∈ {1, 2, . . . , M }, u i < v i . In this case, we say that u dominates v. u ⪯ ε v for an approximation factor (or, more precisely, vector of approximation factors) ε = [ε 1 , ε 2 , . . . , ε M ] denotes that u i ≤ (1 + ε i )v i , i = 1, 2, .. . , M . In this case, we say that u ε-dominates v.In the MO-MAPF problem, we are given a shared workspace, represented by a finite directed graph G = ⟨V, E⟩ and, a set of N agents {a 1 , a 2 , . . . , a N }. V denotes the set of vertices, and each vertex v ∈ V corresponds to a possible location for agents. E ⊆ V × V denotes the set of edges, and each edge e = ⟨u, v⟩ ∈ E corresponds to a move action from u to v. Note that an edge from a vertex to itself can also be included in E, which means that agents can wait at the vertex. The cost of an edge e is a positive M -dimensional vector denoted as c(e) ∈ R M >0 , where M is the number of objectives. The agents are indexed by I = {1, 2 . . . N }. In the rest of the paper, we use |I| instead of N to denote the number of agents. We use superscript i∈I to indicate that a variable is related to agent a i . Each agenta i has a start vertex v i start ∈ V and a goal vertex v i goal ∈ V . A path π i = (v i 1 , v i 2 , . . . , v i ℓ ) for agent a i is a sequence of vertices with v i 1 = v i start , v i ℓ = v i goal , and ⟨v i j , v i j+1 ⟩ ∈ E, j = 1, 2 . . . ℓ -1. The cost of path π i is defined as c(π i ) = ℓ-1 j=1 c(⟨v i j , v i j+1 ⟩).A path also corresponds to a sequence of move and wait actions. We assume that agents stay at their goal vertices forever after they execute their last actions.For a set of agent indices I ′ , a joint path P = {π i : i ∈ I ′ } is a set of paths, one for each agent whose index is in I ′ . Throughout this paper, we assume that I = I ′ , unless mentioned otherwise. The cost of joint path P is defined as c(P ) = i∈I ′ c(π i ). We consider two types of conflicts: A vertex conflict happens when two agents stay at the same vertex simultaneously, and an edge conflict happens when two agents switch their vertices simultaneously. A solution is a conflict-free joint path.In this paper, we use symbol P to denote a joint path, which is a set of paths for different agents, and symbol Π to denote a set of paths for the same agent. Additionally, we use symbol P to denote a set of joint paths.We say that a path π weakly dominates another path π ′ (resp. π ε-dominates π ′ ) if c(π) ⪯ c(π ′ ) (resp. c(π) ⪯ ε c(π ′ )). A set of paths Π is undominated if its paths do not weakly dominate each other. A Pareto frontier of Π is defined as an undominated subset of Π such that each path in Π is weakly dominated by at least one path in the Pareto frontier. An ε-approximate frontier for Π is defined as an undominated subset of Π such that each path in Π is εdominated by at least one path in the ε-approximate frontier.For joint paths, we define weakly dominance, εdominance, undominated sets, Pareto frontiers, and εapproximate frontiers in the same way that we do for paths. Unless mentioned otherwise, we use a Pareto frontier (resp. an ε-approximate frontier) to refer to a Pareto frontier (resp. an ε-approximate frontier) of all solutions for the MO-MAPF problem instance we consider.This section reviews CBS (Sharon et al. 2015) , BB-MO-CBS (Ren et al. 2023) , and A*pex (Zhang et al. 2022) .CBS (Sharon et al. 2015 ) is a complete and optimal singleobjective MAPF algorithm. We omit the pseudocode for CBS due to the space limit. CBS consists of two levels. On the high level, CBS performs a best-first search on a Constraint Tree (CT). Each CT node contains (1) a set of constraints and (2) a minimum-cost joint path that satisfies all these constraints. A constraint has the form ⟨i, v, t⟩ or ⟨i, e, t⟩, where i ∈ I, v ∈ V, e ∈ E, t ∈ N >0 . For the first case, any path π i = (v i 1 , v i 2 , . . . , v i l ) for a i is prohibited from v i t = v; for the second case, any pathπ i = (v i 1 , v i 2 , . . . , v i l ) for a i is prohibited from ⟨v i t , v i t+1 ⟩ = e.The g-value of a CT node is defined as the cost of its joint path. CBS maintains an Open list for all generated but not yet expanded nodes and initializes Open with the root CT node, which has an empty set of constraints and a path for each agent that has the minimum path cost when ignoring conflicts. In each iteration, CBS extracts a CT node with the minimum g-value from Open and returns its joint path as the solution if the joint path is conflict-free. Otherwise, CBS picks a conflict of the joint path to resolve, splits the CT node into two child CT nodes, and adds a constraint to each child CT node to prohibit either one or the other of the two conflicting agents from using the conflicting vertex or edge at the conflicting timestep. CBS then calls its low level to replan the path of the newly constrained agent in each child CT node. The low level planner finds a path with the minimum path cost while satisfying all constraints of the child CT node but ignoring conflicts.BB-MO-CBS (Ren et al. 2023) generalizes CBS from single-objective MAPF to MO-MAPF. Given an MO-MAPF problem instance, BB-MO-CBS computes a Pareto frontier of its solutions.Algorithm 1 shows the pseudocode for BB-MO-CBS. BB-MO-CBS maintains an Open list for all generated but not yet expanded nodes and a solution set S for the solutions it has found. Similar to CBS, BB-MO-CBS also consists of two levels. On the high level, BB-MO-CBS maintains a CT. A major difference between CBS and BB-MO-CBS is that, while a CT node of CBS corresponds to one joint path, a CT node of BB-MO-CBS corresponds to a set of joint-paths that are different combinations of Pareto-optimal path for each agent. This design allows BB-MO-CBS to resolve the same conflict in different joint paths simultaneously. More specifically, in BB-MO-CBS, we redefine a CT node as a tuple n = ⟨Ω, {Π i | i ∈ I}, P⟩, which contains (1) a set of constraints Ω, where a constraint has the same form with the constraints in CBS, (2) a Pareto frontier of paths Π i for each agent a i that satisfy constraints in Ω, and (3) a set of joint pathsP ⊆ P F (Π 1 × Π 2 × • • • × Π |I| ), where P F (Π 1 × Π 2 × . . . × Π |I| )denotes a Pareto frontier of all joint paths that consist of a path from Π i for each agent a i . As we will show later, BB-MO-CBS repeatedly updates P to the subset ofP F (Π 1 × Π 2 × • • • × Π |I| )that are not weakly dominated by any solution in S. We use P.lexF irst to denote the joint path with the lexicographically smallest cost in P and call it the current joint path of node n. The g-value of node n is defined as c(P.lexF irst).During the initialization, BB-MO-CBS first computes a Pareto frontier of paths Π i o , ignoring other agents, for each agent a i , and a Pareto frontier of joint pathsP o = P F (Π 1 o × Π 2 o × • • • × Π |I| o ) (Lines 1-4). It then initializes Open with the root CT node n o = ⟨∅, {Π i o | i ∈ I}, P o ⟩ (Line 5). In each iteration, BB-MO-CBS extracts a CT node n = ⟨Ω, {Π i | i ∈ I}, P⟩ with the lexicographically smallest g-value (Line 7). The current joint path of n, that is, P.lexF irst, must have the lexicographically smallest cost among (and hence is not dominated by) the joint paths of all CT nodes in Open. BB-MO-CBS first computes P ′ by removing the joint paths weakly dominated by any solution in S from P. If P ′ is empty, BB-MO-CBS discards node n and ends the iteration (Line 9). If the current joint path changes, (that is, P ′ .lexF irst ̸ = P.lexF irst), BB-MO-CBS reinserts a CT node with the updated joint path set P ′ to Open and ends this iteration (Lines 10-12). If the current joint path does not change and is conflict-free, BB-MO-CBS adds it to S. Different from CBS, BB-MO-CBS does not terminate in this case. It removes the new solution P ′ .lexF irst from P ′ and reinserts a CT node with the updated joint path set P ′ to Open if P ′ is still not empty (Lines 14-19). BB-MO-CBS does this because the remaining joint paths in P ′ still have the potential to lead to new solutions. If the current joint path is not conflict-free, similar to CBS, BB-MO-CBS for all i ′ ∈ {i, j} do 22:Algorithm 1 BB-MO-CBS 1: S ← ∅; Open ← ∅ 2: for all i ∈ I do 3: Π i o ← LowLevelSearch(i, ∅) 4: Po ← P F (Π 1 o × Π 2 o × • • • × Π N o ) 5: add no = ⟨∅, {Π i o |i ∈ I},{Π i new |i ∈ I} ← {Π i |i ∈ I} 23: Ωnew ← Ω ∪ {ω i ′ } 24: Π i ′ new ← LowLevelSearch(i ′ , Ωnew) 25: Pnew ← P F (Π 1 new × Π 2 new × • • • × Π N new ) 26:add ⟨Ωnew, {Π i new |i ∈ I}, Pnew⟩ to Open 27: return S picks a conflict of the joint path to resolve, splits the CT node into two child CT nodes, and adds a constraint to each child CT node. BB-MO-CBS then calls its low level to replan a Pareto frontier of paths for the newly constrained agent in each child CT node that satisfy all constraints of the child CT node. The low level planner of BB-MO-CBS can be implemented with any single-agent multi-objective search algorithm that computes a Pareto frontier, such as BOA* (Ulloa et al. 2020) and EMOA* (Ren et al. 2022) .BB-MO-CBS terminates and returns S when Open is empty. Ren et al. (2023) showed that S is a Pareto frontier for the given MO-MAPF problem instance.A straightforward approach to introduce approximation to BB-MO-CBS is to prune joint paths that are ε-dominated by any found solution. We propose BB-MO-CBS-ε, an approximate variant of BB-MO-CBS that we will use as a baseline. Given an MO-MAPF problem instance and an ε-value, BB-MO-CBS-ε computes an ε-approximate frontier of the solutions. BB-MO-CBS-ε only changes one line of BB-MO-CBS, that is, when computing the updated joint path set P ′ (Line 8), it removes all the joint paths in P that are εdominated by any solution in S.A*pex (Zhang et al. 2022 ) is a multi-objective (single-agent) search algorithm that computes an ε-approximate frontier of paths from a given start state v start to a given goal state v goal for a user-provided ε-value. In A*pex, a node n corresponds to a set of paths Π from v start to some vertex v. Instead of explicitly storing Π, A*pex stores only one path π ∈ Π, called the representative path of n, and a cost vector A(n), called the apex of n. Cost vector A(n) is the vector minimum value of the costs of all paths in Π. We say that node n isε-bounded if c(π) + h(v) ⪯ ε A(n) + h(v), where h is a consistent heuristic function where each component of h(v) provides a lower bound on the cost of any path from v to the goal vertex v goal for each objective.By merging nodes whose representative paths end at the same vertex on condition that the resulting node is εbounded, A*pex reduces the search effort and can quickly compute an ε-approximate frontier. When merging two nodes n and n ′ , the new apex is the vector minimum of the A(n) and A(n ′ ), and the new representative path is either one of the two representative paths of n and n ′ . Zhang et al. (2022) proposed several approaches for choosing the new representative path. When expanding a node n that reaches v goal , A*pex adds the representative path of n, denoted as π, to the solution set it maintains. Slightly abusing the notation, we use A(π) to denote A(n) and call it the apex of π. A*pex terminates and returns a set of solutions, denoted as Π ε , when its open list becomes empty. In the rest of this paper, we assume that A*pex also outputs the apexes of solutions in Π ε . Let Π * denote a Pareto frontier from v start to v goal . The apexes of paths inΠ ε collectively "lower-bound" Π * , that is, ∀π * ∈ Π * ∃π ∈ Π ε A(π) ⪯ c(π * ).In this section, we first describe BB-MO-CBS-pex, a variant of BB-MO-CBS that computes an ε-approximate frontier for a given MO-MAPF problem instance and a userprovided ε-value. BB-MO-CBS-pex builds upon BB-MO-CBS-ε with the two major improvements: 1. BB-MO-CBS-pex leverages A*pex to speed up the lowlevel search. 2. BB-MO-CBS-pex generalizes the merging idea of A*pex to reduce the sizes of joint paths for CT nodes (and hence speed up the high-level search).In BB-MO-CBS-pex, each joint path P represents a set of joint paths that are ε-dominated by P . BB-MO-CBSpex maintains an apex for each joint path P to keep track of the set of joint paths that were discarded due to being ε-dominated by P . Similar to an apex in A*pex, A(P ) is the vector minimum of the costs of these joint paths. We say that P is ε-bounded if c(P ) ⪯ ε A(P ). When merging two joint paths P and P ′ , the resulting joint path is either P or P ′ , and the new apex is the vector minimum of the A(P ) and A(P ′ ). BB-MO-CBS-pex merges two joint paths only when the resulting joint path is ε-bounded. Similar to BB-MO-CBS, a CT node in BB-MO-CBS-pex is a tuple n = ⟨Ω, {Π i |i ∈ I}, P⟩, with two differences: (1) Π i for each agent a i is an ε-approximate frontier of paths that satisfy constraints in Ω, and (2) P is a set of joint paths computed by merging joint paths in PF (Π 1 × Π 2 × • • • × Π |I| ).We use P.lexF irst to denote the joint path with the lexicographically smallest apex in P and call it the current joint path of node n. The g-value of node n is defined as A(P.lexF irst).Algorithm 2 shows the pseudocode for BB-MO-CBS-pex. We highlight the changes of BB-MO-CBS-pex over BB-MO-CBS using the blue text color. These changes are:1. Lines 3 and 24. When initializing the root CT node n 0 and replanning paths for agents, BB-MO-CBS-pex uses A*pex to compute an ε-approximate frontier, instead of a Pareto frontier, of paths for each agent in each CT node. 2. Lines 4 and 25. When computing the set of joint paths for a CT node, BB-MO-CBS-pex calls M ergeJointP ath, which we will explain later, to compute an ε-approximate frontier of joint paths. This reduces the search effort of BB-MO-CBS-pex because fewer joint paths are considered for each CT node. 3. Line 8. When computing P ′ for an extracted CT node, BB-MO-CBS-pex calls P runeApproxDom to remove a joint path P if A(P ) is ε-dominated by the cost of some solution P sol in S . Additionally, BB-MO-CBSpex updates A(P sol ) to the vector minimum of A(P ) and A(P sol ) (Line 32). This update guarantees that, if BB-MO-CBS-pex merges P sol with other solutions later on Line 15, the cost of the resulting solution still εdominates A(P ). 4. Line 15. When adding a solution P to S, BB-MO-CBSpex attempts to merge P with another solution in S on condition that the result solution is still ε-bounded. We show the merge function on Lines 40-43.Algorithm 3 shows the pseudocode for function M ergeJointP ath. In M ergeJointP ath, BB-MO-CBSpex iteratively computes P i , i = 1, 2, . . . , |I|, where P i is a set of joint paths for agent indices a 1 , a 2 , . . . , a i and P 1 is initialized with Π 1 (Line 1). To compute P i , i = 2, 3, . . . , |I|, BB-MO-CBS-pex iterates over all combinations in P i-1 × Π i , where each combination corresponds to a joint path P for agents {a 1 , a 2 , . . . , a i }. BB-MO-CBSpex first checks if P i contains a joint path P ′ that satisfies M erge(P, P ′ ) is ε-bounded and, if so, replaces P ′ (in P i ) with M erge(P, P ′ )(Line 8). Otherwise, P is added to P i (Line 9). Eventually, function M ergeJointP ath returns P |I| .We propose two additional improvement techniques:Choosing representative paths or joint paths based on conflicts: While Zhang et al. ( 2022) proposed to choose representative paths based on the costs of paths for A*pex, we propose to chose representative paths (in the low-level search) or joint paths (in M ergeJointP ath) based on conflicts. In the low-level search, we use Conflict Avoidance Tables (CATs) (Sharon et al. 2015) to store the number of other agents passing via a given vertex or a given edge at a given timestep in the current joint path (P.lexF irst). Therefore, for each path, we can compute its number of conflicts with other paths using the CAT. When merging two paths, the low-level search chooses the less conflicting path as the representative path on condition that the resulting node is ε-bounded and otherwise chooses the other path.In M ergeJointP ath, we also compute the number of conflicts for each joint path and prefer the less-conflicting joint path as the representative path when merging.Algorithm 2 BB-MO-CBS-pex 1: S ← ∅; Open ← ∅ 2: for all i ∈ I do 3: for all i ′ ∈ {i, j} do 22:Π i o ← ApproxLowLevelSearch(i, ∅, ε) 4: Po ← M ergeJointP aths({Π i o |i ∈ I}, ε) 5: add no = ⟨Po, ∅, {Π i o |i ∈ I}⟩{Π i new |i ∈ I} ← {Π i |i ∈ I} 23: Ωnew ← Ω ∪ {ω i ′ } 24: Π i ′ new ← ApproxLowLevelSearch(i ′ , Ωnew, ε) 25: Pnew ← M ergeJointP aths({Π i new |i ∈ I}, ε) 26:add ⟨Pnew, Ωnew, {Π i new |i ∈ I}⟩ to Open 27: return S 28: procedure P runeApproxDom(P) 29:P ′ ← a copy of P 30:for all P ∈ P ′ do 31:if ∃P sol ∈ S c(P sol ) ⪯ε A(P ) then 32:A(P sol ) ← vector min(A(P ), A(P sol )) 33:remove P from P ′ 34:return P ′ 35: procedure AddSolution(P ) 36:if ∃P sol ∈ S M erge(P, P sol ) is ε-bounded then 37:replace P sol in S with M erge(P, P sol ) 38:else 39: add P to S 40: procedure M erge(P, P ′ ) 41:Pnew ← choose from P and P ′ 42:A(Pnew) ←vector min(A(P ), A(P ′ )) 43:return PnewEager solution update: BB-MO-CBS and BB-MO-CBSpex can be considered as updating solutions "lazily", that is, they try to update S only when extracting a node n from Open and the current joint path of n is conflict-free.We propose a eager solution-update scheme, which can be applied to both BB-MO-CBS(-ε) and BB-MO-CBS-pex: In BB-MO-CBS-ε with eager solution update, after Line 8 of Algorithm 1, we remove all conflict-free joint paths from P new , add these joint paths to S, and remove dominated solution from S. In BB-MO-CBS-pex with eager solution update, after Line 8 of Algorithm 2, we remove all conflict-free joint paths from P new and call AddSolution to add these joint paths to S.Input: {Π i | ∀i ∈ I}, ε 1: P1 ← Π 1 2: for all i = 2, 3, . . . , |I| do 3: Pi ← ∅ 4: for all ⟨Pi-1 = {π 1 , π 2 , . . . , π i-1 }, π i ⟩ ∈ Pi-1 × Π i do 5: P ← {π 1 , π 2 , . . . , π i } 6: A(P ) ← A(Pi-1) + A(π i ) 7:if ∃P ′ ∈ Pi M erge(P, P ′ ) is ε-bounded then 8:replace P ′ with M erge(P, P ′ ) in Pi 9:else add P to Pi 10: return P |I| Algorithm 4 M ergeJointP aths, AddSolutions and M ergeU ntil for BB-MO-CBS-k1: procedure M ergeJointP aths({Π i : ∀i ∈ I}, ε) 2: P1 ← {{π 1 } | π 1 ∈ Π 1 } 3: M ergeU ntil(P1, k) 4:for all i = 2, 3, . . . , |I| do 5:Pi ← ∅ 6:for all ⟨Pi-1 = {π 1 , π 2 , . . . , π i-1 }, π i ⟩ ∈ Pi-1 × Π i do 7: P ← {π 1 , π 2 , . . . , π i } 8: A(P ) ← A(Pi-1) + A(π i ) 9:add P to Pi 10:M ergeU ntil(Pi, k) 11:return P |I| 12: procedure AddSolution(P ) 13: add P to S 14:M ergeU ntil(S, k) 15:ε ← max{BF (P ) | P ∈ S} 16: procedure M ergeU ntil(P, k) 17:while |P| > k do 18:choose two joint paths P and P ′ from P such that BF (M erge(P, P ′ )) is minimized 19:remove P and P ′ from P 20:add M erge(P, P ′ ) to PIn practice, it is unclear how to choose an appropriate εvalue for a given MO-MAPF problem instance. If ε is set too large, BB-MO-CBS-ε or BB-MO-CBS-pex might return only one solution, which provides no trade-off to users. If ε is set too small, BB-MO-CBS-ε or BB-MO-CBS-pex might not benefit from approximation at all. Instead of specifying an approximation factor, one might prefer to specify a desirable number of solutions k. Therefore, we propose BB-MO-CBS-k, a variant of BB-MO-CBS-pex that computes a set of up to k solutions for any user-specified k-value. In BB-MO-CBS-k, all components of ε are equal, i.e., ε = [ε, ε, . . . , ε], and we will denote ε simply as ε in the rest of this section. BB-MO-CBS-k builds upon BB-MO-CBS-pex with the following changes:1. The approximation factor ε is initialized to zero and dynamically updated during the search. 2. Every time after low-level search for an agent a i , BB-MO-CBS-k calls M ergeU til to merge the set of paths Π i until the size of Π i is no larger than k. M ergeU ntil is explained later. 3. BB-MO-CBS-k uses a modified M ergeJointP aths function, which always outputs a set of at most k joint paths, and a modified AddSolutiuon function, which always keeps the size of S no larger than k. The modified M ergeJointP aths and AddSolution are also explained later.For a joint path P , we define its boundedness factor asBF (P ) := max 0, max i=1,2,...,M c i (P ) A i (P ) -1 .It is easy to verify that BF (P ) is the smallest ε-value that satisfies joint path P is ε-bounded (i.e., c i (P ) ≤ (1 + ε)A i (P )).Algorithm 4 shows the pseudocode for M ergeU ntil function, and modified M ergeJointP aths and AddSolution functions. For a given set of joint paths (or a set of paths) P, the M ergeU ntil function iteratively chooses two joint paths P and P ′ from the input joint path set P such that BF (M erge(P, P ′ )) is minimized and replaces P and P ′ with M erge(P, P ′ ) in P until the size of P is no larger than k. The modified M ergeJointP aths function for BB-MO-CBS-k calls M ergeU ntil to keep the sizes of P i , i = 1, 2, . . . , |I|, no larger than k (Lines 3 and 10). The AddSolution function for BB-MO-CBS-k also uses M ergeU ntil to keep the size of S no larger than k. Additionally, it updates the approximation factor ε to the largest bounded factor of S. When BB-MO-CBS-k terminates, it returns S, which contains no more than k solutions. Additionally, S is guaranteed to be an ε-approximate frontier for the eventual value of ε.Due to the space limit, we put some of our proof in the appendix. Upon acceptance, we will purchase extra pages to include the complete proof or make our appendix available online.Definition (CVN set) Given a set of joint paths P and a node n with constraints Ω, let CV N (n, P) be the set of all joint paths that (i) satisfy all constraints in Ω, (ii) are conflict-free, and (iii) whose costs are not weakly dominated by the apex of any joint path in P.We say a node n permits a joint path P with respect to P if P ∈ CV N (n, P). Lemma 1. For agent a i and constraints Ω, let Π i := ApproxLowLevelSearch(i, Ω, ε). We have (1) for each path π ′ of agent a i that satisfies Ω, there exists a path π ∈ Π i with A(π) ⪯ c(π ′ ), and (2) all paths in Π i are ε-bounded.Proof. The lemma is shown by Theorem 1 in the paper of A*pex (Zhang et al. 2022) .Lemma 2. Let n new denote node ⟨P new , Ω new , {Π i new |i ∈ I}⟩ that Algorithm 2 inserts to Open on Line 26. We have (1) for any solution P ′ that satisfies Ω new , there exists a joint path P ∈ P new with A(P ) ⪯ c(P ′ ) and (2) all joint paths in P new are ε-bounded.BB-MO-CBS-pex uses M ergeJointP aths to compute P new . Therefore, to prove Lemma 2, we inductively show that, in Algorithm 3, for i = 1, 2, . . . , |I|, P i satisfy that for any conflict-free joint path P ′ for agents a1 , a 2 , . . . , a i that satisfies Ω new , there exists a joint path P ∈ P i with A(P ) ⪯ c(P ′ ) and, all joint paths in P i are ε-bounded. The complete proof is in the appendix.Lemma 3. When Algorithm 2 reaches Line 13, for any joint path P ∈ CV N (n, S), there exists a joint path P ′ ∈ P ′ with A(P ′ ) ⪯ c(P ).Proof. Before Algorithm 2 reaches Line 13, n might have been previously extracted from and reinserted to Open with different sets of joint paths. Let P gen denote the set of joint paths computed by M ergeJointP aths when node n was generated on Line 26. From Lemma 2, for any solution P that satisfies Ω, there exists a joint path P ′ ∈ P gen with A(P ′ ) ⪯ c(P ). Assume that P ′ is in P gen but not in P ′ , which happens only if P ′ has been removed on Lines 16 or 33. If P ′ was removed on Lines 16, Algorithm 2 then added it to S on Line 15. If P ′ was removed on Lines 33, the apex of some solution was updated to weakly dominate A(P ′ ) (Line 32). In both cases, there existed a solution in S whose apex weakly dominates A(P ′ ). Algorithm 2 might later merge this solution several (more) times with other solutions on Line 37 or update its apex on Line 32, but the apex of this solution will still weakly dominate A(P ′ ). We hence find a contradiction because, by the definition of CVN sets, the cost of P is not weakly dominated by the apex of any solution in S.Lemma 4. At the beginning of each iteration of BB-MO-CBS-pex (i.e., before executing Line 7), for any solution P , if there does not exist a solution P sol ∈ S with A(P sol ) ⪯ c(P ), there exists a node n ∈ Open, which permits P with respect to S.Theorem 1. Given an MO-MAPF instance that has at least one solution, when BB-MO-CBS-pex terminates, S is an εapproximate frontier.Theorem 2. Given an MO-MAPF instance that has at least one solution, BB-MO-CBS-pex terminates in finite time.In our experimental results, we evaluated (1) BB-MO-CBS, (2) BB-MO-CBS-ε, (3) BB-MO-CBS-pex, (4) BB-MO-CBS-pex-E (BB-MO-CBS-pex with eager-solution update), ( 5) BB-MO-CBS-pex-E-CB (BB-MO-CBS-pex-E with conflict-based merging), and (6) BB-MO-CBS-k. All algorithms are implemented in C++ 1 and share a common base as much as possible. We conducted all experiments on a Ubuntu 20.04.5 laptop with an Intel Core i7-10510U 1.80GHz CPU and 16GB RAM.The low level of BB-MO-CBS and BB-MO-CBS-ε is implemented with BOA* for bi-objective domains and randomly sampling each cost component from 1 to 5. The MAPF benchmark contains 25 random scenarios for each map, and each scenario provides a list of start-goal pairs. For each scenario, we vary the number of agents N from 4 to 28 and generate problem instances with the first N start-goal pairs. We run experiments with two and three objectives and a runtime limit of 120 seconds for each problem instance.We compare BB-MO-CBS, BB-MO-CBS-ε, and different variants of BB-MO-CBS-pex on empty-48-48, random-32-32-20, and room-32-32-4 with approximation factors of 0.03, 0.05, and 0.1. Figures 2 and 3 show the experimental results for different algorithms on instances with two and three objectives, respectively. The solid lines show the success rate (i.e., the percentage of instances solved by an algorithm within the runtime limit) for each algorithm. BB-MO-CBS-ε has higher success rates than BB-MO-CBS. BB-MO-CBS-E has higher success rates than BB-MO-CBS-ε, while, in turn, BB-MO-CBS-E-CB has significantly higher success rates than BB-MO-CBS-pex-E, which shows the usefulness of the eager-solution update and conflict-based merging techniques. The improvements in success rates of these techniques are more significant for ε-values of 0.05 and 0.10. For example, in random-32-32-30 with two objectives and 20 agents, the addition of conflict-based merging doubles the success rate. The dashed lines in Figures 2 and 3 show the average numbers of solutions of BB-MO-CBS and BB-MO-CBS-pex-M-CB. We can see that introducing approximation to the MO-MAPF problem reduces the sizes of solution sets by up to two orders of magnitude.Figure 4 shows the individual runtime of BB-MO-CBSε and BB-MO-CBS-E-CB for each problem instance. BB-MO-CBS-pex-M-CB takes significantly less time than BB-MO-CBS-ε in general. When ε becomes larger, and on instances with three objectives, BB-MO-CBS-pex-M-CB becomes significantly more efficient than BB-MO-CBS-ε.We compare BB-MO-CBS and BB-MO-CBS-k on random-32-32-20 with two and three objectives. For BB-MO-CBSk, we use two k-values, 5 and 10. The experimental results are shown in Figure 5 . The solid lines show the success rate for each algorithm, and we can see that BB-MO-CBS-k has significantly higher success rates than BB-MO-CBS. The dashed lines show the average approximation factor output by BB-MO-CBS-k, and we can see that, with k = 5 and k = 10, BB-MO-CBS-k still computes solution sets with approximation factors smaller than 0.1.In this paper, we proposed BB-MO-CBS-pex, which leverages A*pex to compute approximate frontiers for MO-MAPF problems for user-specified approximation factors. Based on BB-MO-CBS-pex, we proposed BB-MO-CBSk, which computes up to k solutions for a user-provided k-value. Our experimental results show that both BB-MO-CBS-pex and BB-MO-CBS-k solved significantly more instances than BB-MO-CBS for different approximation factors and k-values, respectively. We also show that BB-MO-CBS-pex achieved speed-ups up to two orders of magnitude compared to BB-MO-CBS-ε, our baseline approximation variant of BB-MO-CBS.Upon acceptance, the code and the data will be made publicly available. 
 
 Appendix:  


Decision: This paper lead to a lot of discussion. The scores were at first in general positive (+1/+1/+2) and the reviews deemed it an advancement of the state of the art. On the other hand, the rebuttal was not received well due to a lack of detail and the authors seemingly not intending to improve the paper based on the reviews. For example, two reviewers were dissatisfied with the lack of comparison between the $\epsilon$-approximate algorithm and the $k$-approximate algorithm, which the authors agreed would be interesting but deferred to future work. This resulted in two reviews lowering their score (2 -> 1 and 1 -> -1). Another concern was that a proof lacked important details, but this was resolved by the authors promising to move the more detailed proof from the supplementary material to the main paper by buying additional pages.

While the scores overall are positive, it is noteworthy that the only negative score comes from the reviewer with the highest confidence. Nevertheless I weakly recommend to accept the paper due to the following:
1) The reviews were at first positive.
2) The paper is both theoretically sound and performs well empirically.
3) If I were the author it would not have been clear to me from the initial reviews that the positive score is depending on revising and extending parts of the paper.

Reviews: review: strength_weakness: strength_weakness: I find the proof somewhat difficult to follow. This may be because I still need more time or a complete proof is not given due to space limitation. The authors promise to purchases extra pages to put the complete proof upon acceptance.

Post rebuttal: Thank you for providing the rebuttals. I did lower my score a bit due to the fact that it appears that a better experimental evaluation would be needed to highlight the salient features of the proposed algorithms.
questions: questions: Page 5: "In BB-MO-CBS-ε with eager solution update, after Line 8 of Algorithm 1, we remove all conflict-free joint paths from P_{new}" -> Do you mean P'?
Alg 1 Line 7: "n = (...)" -> "n = <...>"?
Alg 1 Line 8: Remove the "∧" to keep the writting style consistent?
Alg 2, Lemma 2: Shouldn't the notion of a CT node be written as <Omega, {...}, P> as defined in the introduction of BB-MO-CBS-pex?
Page 5: "MergeUtil" -> "MergeUntil".
Figs 2, 3: "solution numbers" -> "number of solutions"?
Alg 4: "AddSolutions" -> "AddSolution".
Page 5: "propose a eager" -> "propose an eager".
Page 6: "AddSolutiuon" -> "AddSolution".
Fig 4: "BB-MO-CBS-pex-M-E-CB" -> "BB-MO-CBS-pex-E-CB"?
Page 8: Three instances of "MO-CBS-pex-M-CB" -> "MO-CBS-pex-E-CB"?
strength_weakness: strength_weakness: I did not identified any major weakness in the paper. However some minor details could be improved.

Eager solution update : in Line 8 of Alg.1 (resp Alg. 2) refers to P’ not P_new.

I suggest to the authors to add some information on the experimental section. For instance, which are the cost components used in experiments. 

Additionally, y-axis labels and legend of figures 4.a, 4.b and 4.c and the text in paragraph explaining Fig. 4 results should be also corrected (e.g. BB-MO-CBS-pex-M-E-CB →  BB-MO-CBS-pex-E-CB). And, in last lines in paragraph « Figures 2 a 3 [...] »,  BB-MO-CBS-E-CB should be corrected to BB-MO-CBS-pex-E-CB.

Significantly higher success rates : authors argue that the success rate obtained with  BB-MO-CBS-pex-E-CB is significantly higher then  BB-MO-CBS-pex-E, but these results are not supported by statistical analysis. So, the term « significantly » should not be used in my opinion.
questions: questions: - Could authors comment more on the benefits on BB-MO-CBS-pex(-E)-CB in terms of number of conflicts. Are the paths proposed by this variant "less conflicting" when compared with the others ? 
- If I well understood, BB-MO-CBS-k is based on BB-MO-CBS-pex and not on BB-MO-CBS-pex-E-CB (the more effective approach), why ?
- Why the authors did not compared  BB-MO-CBS-pex(-E-CB) with  BB-MO-CBS-k ?
strength_weakness: strength_weakness: The paper amalgamates two concepts or algorithms: A*pex and BB-MO-CBS, the latter being an adaptation of CBS (a MAPF solver) to the MOSP setting. While the combination does not pose significant challenges, two ideas stand out beyond mere amalgamation:
(*) I really liked the idea of choosing representative paths or joint paths based on conflicts since this is intimately related to the MAPF part of the problem.
(*) The concept of k-solutions, although seemingly detached from the MAPF aspect, holds independent interest within the (single-agent) MOSP community. However, it remains unclear whether these k solutions offer any approximation of the PF. Additionally, the evaluation benchmarks used for these solutions were notably simplistic. A more fitting baseline approach could involve running BB-MO-CBS-pex with decreasing epsilon values until reaching k.

The authors motivate their work by stating that "Many real-world applications of MAPF can be viewed as multi-objective problems. For example, in multi-robot systems, some interesting cost metrics are travel distance, energy consumption, and risk." The same sentence could have been written for the single-agent setting. In the MAPF literature, researchers typically consider two cost functions - the Sum of Costs (SOC) and the Makespan which are related but may differ. There is no clear case when each should be used and so combining the two in the context of MOS is the most natural step if MOS is considered. This is not trivial since Makespan is not additive over edges but I am sure that this is a technicality that can be addressed. It is unfortunate that these interesting and more relevant questions were overlooked.

Finally, small issues
(*) Bottom of page 5 
	- "after low-level search" => "after \insert{the} low-level search"
	- MergeUtil => MergeU\insert{n}til
(*) References:
	- 	Ren, Z.; Rathinam, S.; and Choset, H. 2022. 
		A Conflict-Based Search Framework for Multi-Objective Multi-Agent Path Finding. 
		https://arxiv.org/abs/2108.00745.
		
		Replace with journal paper:
		
		Zhongqiang Ren, Sivakumar Rathinam, Howie Choset: 
		A Conflict-Based Search Framework for Multiobjective Multiagent Path Finding. 
		IEEE Trans Autom. Sci. Eng. 20(2): 1262-1274 (2023)
		
	- 	Ulloa, C. H.; Yeoh, W.; Baier, J. A.; Zhang, H.; Suazo, L.; and Koenig, S. 2020. 
		A Simple and Fast Bi-Objective Search Algorithm. 
		In Proceedings of the International Conference on Automated Planning and Scheduling, volume 30, 143–151.

		Replace with journal paper:

		Carlos Hernández, William Yeoh, Jorge A. Baier, Han Zhang, Luis Suazo, Sven Koenig, Oren Salzman:
		Simple and efficient bi-objective search algorithms via fast dominance checks. 
		Artif. Intell. 314: 103807 (2023)
questions: questions: What can you say about howwell can the k-solution approximatethe PF? Can this be appliedto the single-agent setting?