Hybrid Quantum-Classical Multi-Agent Pathfinding
Authors: Thore Gerlach
Loong Kuan Lee
Frederic BARBARESCO
Nico Piatkowski
Venue: ICML 2025 poster (2025)
Keywords: QUBO
MAPF
Column Generation
Optimal
Quantum Computing
ILP
Operations Research
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: First optimal quantum algorithms for Multi-Agent Pathfinding based on generating new paths until an optimality criterium is met.

Abstract: Multi-Agent Path Finding (MAPF) focuses on determining conflict-free paths for multiple agents navigating through a shared space to reach specified goal locations.  This problem becomes computationally challenging, particularly when handling large numbers of agents, as frequently encountered in practical applications like coordinating autonomous vehicles. Quantum Computing (QC) is a promising candidate in overcoming such limits. However, current quantum hardware is still in its infancy and thus limited in terms of computing power and error robustness. In this work, we present the first optimal hybrid quantum-classical MAPF algorithms which are based on branch-and-cut-and-prize. QC is integrated by iteratively solving QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our approach dominates previous QUBO formulations and state-of-the-art MAPF solvers.

Hybrid Quantum-Classies Multi-Agent Pathfinding
Thore Gerlach 12
Loong Kuan Lee? Frederic Barbaresco Nico Piatkowski?
Abstract
The scalability of optimal state-of-the-art MAPF solvers is limited, since finding optimal solutions is NP-hard (Sharon et al.). Thus one often falls back to suboptimal or anytime methods (Li et al., a;;; Huang et al.; Okumura, 2023b;a; Li et al., 2021). Even though such methods are compu- tationally efficient in finding a feasible solution, the solu- tion quality can be insufficient which implies the urge for optimal solution methods. By reformulating MAPF as a multi-commodity flow problem, it can be solved optimally via Integer Linear Programming (ILP). However, the re- duction uses an inefficient representation of the problem setting in terms of space complexity and is only effective on small instances. More popular techniques for optimal MAPF include Conflict-busedd Search (CBS) (Sharon et al.) and Branch-and Cut-and-Price (BCP) (Lam al., b). CBS is two-level procedure, with splitting search tree based detected confficts between agents and subsequent replan- ning. This tree is explored with best-first search until a collision-free node is found. BCP takes a different approach of considering a (possibly infeasible) solution which is then refined iteratively by successively adding paths and con- straints. Similarly CBS, BCP is a two-level algorithm: on the low level solves a series of single-agent pathfinding problems, while the high level uses ILP to assign feasible paths to agents. While low level single agent pathfinding can be performed efficiently, the high level problems of both CBS and BCP remain NP-hard.
Multi-Agent Path Finding (MAPF) focuses on de- termining conflict-free paths for multiple agents navigating through shared space reach speci- fied goal locations. This problem becomes compu- tationally challenging, particularly when handling large numbers of agents, as frequently encoun- tered in practical applications like coordinating autonomous vehicles. Quantum Computing (QC) is a promising candidate in overcoming such lim- its. However, current quantum hardware is still in its infancy and thus limited in terms of comput- ing power and error robustness. In this work, we present the first optimal hybrid quantum-classier MAPF algorithms which are based on branch sanechh-nddd -ndd cut-and-price QC is integrated by iteratively solv- ing QUBO problems, based on conflict graphs. Experiments on actual quantum hardware and results on benchmark data suggest that our ap- proach dominates previous QUBO formulations and state-of-the-art MAPF solvers.
1. Introduction
Emerging domains of large-scale resource allocation prob- lems, such as assigning road capacity to vehicles, ware- house management or 3D airspace to Unmanned Aerial Vehicles (UAVs), often require Multi-Agent Pathfind- ing (MAPF) (Stern al.; Choudhury et al.; Li et al., c) to determine feasible allocations. MAPF involves calculating non-colliding paths for large number of agents simulta- neously, presenting significant computational challenges in realistically sized scenarios. These challenges are becoming increasingly relevant in case of large-scale real-world ap- plications. E.g., future UAV traffic in urban environments, driven by parcel delivery demands, is expected to involve managing thousands of flight paths (Doole et al., 2020).
Quantum Computing (QC) is considered promising for tackling certain NP-hard Combinatorial Optimization (CO) problems. This is due its potential to leverage quantum phenomena to solve certain types of problems faster than classical methods. The quantum mechanical effect of su- perposition enables exploration of a vast solution space in parallel, which is particularly advantageous for finding the best solution from a large set of possibilities. During this exploration quamtum entanglement allows the encoding of high-order relationships among problem variables, leading to an effective exploration of the solution space. In par- ticular, QC is suited for solving Quadratic Unconstrained Binary Optimization (QUBO) problems (Punnen, 2022)
University of Bonn FFrunnhofer IAIS TThales Land and Air Systems. Correspondence to: Thore Gerlach <gerlach @ uni- bonn.de>.
min z ZTQ=. *E(0,13
(1)
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
where Q is an n X n real matrix and n is the number of qubits. Despite this simple problem structure, it is NP.

---

Hybrid Shantum-Classieen Multi-Agent Pathfinding
Separation
Pricing
(a) Initialize paths.
(b) Identify conflicts.
(c) Generate paths.
(d) Solve QUBO.
(e) Final solution.
Figure 1: Schematic visualization of our quantum MAPF algorithm. (a) First, initial paths are generated for every agent with possible conflicts. (b) We enter the outer loop (separation), where identify conflicts between paths and add them the problem. (c) In the pricing step, we generate new paths for every agent and (d) find best set of paths by solving QUBO problem. This inner loop repeated until adding a new path cannot improve the solution quality, while the outer loop is terminated when our set of chosen paths has no conflicts. (e) By construction, a conflict-fre free optimal set of paths is returned.
hard and hence encompasses a wide range of real-world problems, such as chip design (Gerlach al., 2024), flight gate assignment (Stollenwerk et al., a) and trajectory plan- ning (Stollenwerk et al., b).
rent quantum hardware is still limited, our framework is modular and designed to be compatible with future devices.
Our contributions can be summarized follows:
One prominent QC method is Adiabatic Quantum Comput- ing (AQC), which is grounded in the adiabatic theorem (Al- bash & Lidar, 2018). This theorem states that a quantum system will remain in its ground state its Hamiltonian changes slowly enough and there is sufficient energy gap from excited states. The problem is encoded into the final Hamiltonian, and the system is evolved gradually from initial Hamiltonian. If done adiabatically, the system ends in the ground state of the problem Hamiltonian, which cor- responds to the optimal solution. Approximations for AQC can be obtained by either using digital QC hardware, such as the Quantum Approximate Optimization Algorithm (Farhi et al., 2014), or by purposefully built analog devices, such as Quantum Annealers (Johnson et al., 2011). Despite QC's promise, we find ourselves in the Noisy Intermediate-ser Quantum (NISQ) (Preskill, 2018) era. QC devices face challenges including eтror rates, limited computing power and restricted hardware topology, which lead to suboptimal solutions obtained with currently available hardware.
Two novel optimal hybrid quantum-classica MAPF algorithms (QP and QCP), which iteratively solve re- stricted IL.P problems by using QUBO,
An optimality criterion with proof, generalizing the pricing problem of classical column generation.
Hardware-aware QUBO formulations for the restricted ILP problems with using the concept of conflict graphs, leading to parallel solvable independent subproblems,
Extensive experiments benchmark datasets which show the superiority of method over previous QUBO approaches on real quantum hardware and state- of-the-art MAPF solvers.
2. Related Work
Our algorithms based BCP (Lam et al., b). Despite their optimality, such algorithms require sophisticated branching strategy and are not guaranteed to find good solution in reasonable time. An anytime adaption of MAPF BCP has been investigated (Lam et al., a), but further in- vestigation of optimal anytime algorithms of great in- terest (Okumura, 2023a). Heuristics are used for avoiding exponentially many branching steps, leading efficient suboptimal algorithms (Sadykov et al.). However, such rounding heuristics can lead to unsatisfying results, making the investigation of QC for this task intriguing.
In this paper, investigate the use of hardware- QC for MAPF by constructing two optimal hybrid quantum- classical algorithms based on QUBO subproblems. To the best of our knowledge, these are the first quantum algo- rithms for MAPF. We call our algorithms QUBO-and- www.aand--------PPPA Price (QCP) which are based on the idea BCP. We iteratively add paths (and constraints) the problem and solve QUBO, which leads to the applicability of QC. This gives on the best possible solution and stopping condition tells us when our set of paths contains the optimal solution. An overview of QCP can be found in Fig. 1. Even though cur-
Price (QP) and
upper bound
QC is a promising candidate for large-scale planning prob- lems (Stollenwerk et al., a; Li et al., 2024). In the area of multi-agent problems, flow-problem formulations have
2

---

Hybrid Chaatum-CClassice Multi-Agent Pathfinding
been investigated (Ali et al., 2024; Zhang al., 2021; Tar- quini et al., 2024; Davies & Kalidindi). These methods are edge-based, that is each edge in the spatio-temporal graph is represented by qubit. Even though certain constraints can be integrated into the quantum state in this framework, the problem size is way beyond current QC hardware capa- bilities and also infeasible for near-term devices.
such as possible obstacles, while E captures motion con- straints of the agents, e.g., velocity and maximum turning rates of UAVs. The goal of MAPF is now to find optimal paths from the origin to the destination for each agent, s.t. they avoid pairwise conflicts. For rating optimality, we use the objective of the sum of all weighted path lengths. We here consider classical collision conflicts, that is the vertex conflict and the (swapping) edge conflict. A vertex conflict between two agents exists if they move to the same node the same time, while an edge conflict prohibits two agents to use the same edge at the same time. Introducing the time component, we allow the agents to start at different points in time, while also giving them the opportunity to wait at a certain location.
Instead of representing all edges in the given graph, a dif- ferent approach is taken in (Martín & Martin) by consider- ing which path to choose as decision variables. This leads to introducing a QUBO formulation for the Unsplittalee Multi- CutiiiCoommodity Flow problem by directly integrating the inequality constraints. Similar to BCP, they iteratively add paths to their problem. However, they present no theoret- ically sound criterion on when stop, but have rely on suboptimal heuristics. Furthermore, the large amount of constraints have to be incorporated into the QUBO for- mulation which either leads to huge number of auxiliary variables or the need for an iterative optimization scheme to adapt Lagrangian parameters (Mücke & Gerlach, 2023). The authors of (Stollenwerk et al., b; Huang et al., 2022) circumvent this problem by using conflict graphs for rep- resenting possible constraints. However, their methods are not directly applicable to the MAPF setting, since only the starting times of preplanned trajectories are optimized.
For finding a solution the MAPF problem, a spatio- temporal directed graph formulation is typically used. That is, we define GT = (Vr, ET) as the graph, with nodes v = (s) E V x {1...., .T and edges e (v, = (5', (..(+1)) 1)) E VT x VT with weights w. = "(s,a"> where ss,s') E E and T E N is a maximum allowed time horizon. We define the reverse edge of e = (s, (5', & + 1) as é :- (s', (s,t+11 for representing edge conflicts. Gr is an acyelic weighted directed graph with |V7] T and ET O (ST [V], where S is the average number of possible state transitions. For example, if we consider the classical two-dimensional grid environment, an agent has five possible state transitions, i.c., wait, go north, go cast, go south and go west.
We combine the ideas of an iteratively expanding path-based approach with the concept of conflict graphs. A pricing criterion tells us when all variables are included which are part of an optimal solution. The proof is based on (Rönnberg & Larsson), which however assumes negativity on reduced costs. We loosen this assumption and adapt it for general applicability to MAPF.
Every agent a e A is obliged to find path in GT from origin (oa, Vr destination (da, la + Ta) E Vr for starting time ta E [T] and To S T ta- A path is sequence of edges = (e1....,, CT, s.t. Et- la + ((x, ta ( 1)), e++1 = 4, +1), + 1+2)),e1= = ((0,, ta), (s, tu +1) and er. = ((s, tu +Ta 1), (da,, + T.)). The cost/length 6p of a path p is defined as the sum of all its edge weights, i.c.. Cp = Eeso We. Specifically, we go over to the mathematical description of the MAPF objective.
3. Backkrrund
For notational convenience, we onforth denote matrices as bold capital letters (e.g. A), vectors as bold lowercase letters (a) and define B- = {0, 1}. Furthermore, let 1 de- note the vector consisting only of ones, with the dimension following from context. Lastly, let < denote entry-wise inequality between vectors, i.e., a =' b + a; & b, Vi. The following sections will formalize MAPF (Sec. 3.1) and give a mathematical formulation of how to solve it (Sec. 3.2).
3.2. Path-Based Formulation
We encode each possible path p E P for every agent by Ep E IB. An ILP formulation is given by:
3.1. Multi-Agent Pathfinding
MP: min SEBN
Σ
Σ Cpăp
(2a)
A PEP
The input to the MAPF problem is a set of agents A, a weighted undirected graph G = (V, F)) and an origin- destination pair for each agent. The graph G captures the underlying environment, where all possible agent states (e.g. location) are represented by V and E can be regarded as valid transitions from one state to another, with an under- lying cost. V already captures environmental constraints,
s.t.
Σ
2p = 1, Va E A
(2b)
PEP,
Σ
Σ PP:p $,, Vie
(2c)
AEA
ΣΣ (ve + v.) 1, Ve E Er, (2d)
aEAPEP.
3

---

Hybrid Sraantu--Classial Multi-Agent Pathfinding
where oe ve B indicate whether path p visits vertex E VT /e/ed// edge E For, Pa indicates the set of all possible paths for agent and N = [P], P Une A (Pal. Note that zy D are constant and we just optimize over 2p. The constraint in (2b) ensures that exactly one path is chosen for every agent, while (2c) and (2d) avoid conflicts. We denote (2) as the Master Problem (MP).
Algorithm QUBOANDPRICEANDCUT
Input: Shortest independent paths P and # = 1
Output: Optimal feasible solution
C-6
2:
while z infeasible do Add violated constraints to C while not (5) do
Separation
3:
4:
Pricing Shortest path
5:
D" arg min, Cx(A,
6:
P - pu
We have VT constraints for avoiding vertex conflicts and EEl constraints for avoiding swapping conflicts. The num- ber of our decision variables representing possible solutions now corresponds to the number of all possible paths for all agents, which is exponential in the maximum time horizon, A large maximum time T or number of agents |A| can make the problem size increase very quickly, making it infeasible to solve it with current NISQ devices.
7:
À + OPTIMIZELAGRANGIAN C)
Solle (8)
8:
OPTIMIZEMASTER(P... b QUBO (Sec. 4.3)
9:
end while
10: end while
N = =O[|A|S"
This method was developed for Linear Program- ming (LP) (Dantzig) without the restriction of integrality of the variables-in our case we do not optimize over the continuous domain [o, 1] but over the binary values {0, 1]. To cope with these kind of ILP problems, branching meth- ods, such as BCP (Desrosiers & Lübbecke), are used. In the worst case, exponentially many branching steps are needed, We circumvent this problem by considering solutions to the ILP MP, instead of the relaxed LP version. Ideally, we want n < N, while an optimum of RMP is also an optimum of MP. The next section governs how to add new paths to our problem and check whether a solution is equivalent.
4. Methodology
Not only the huge number of decision variables poses a chal- lenge for current quantum computers, but also the number of constraints strongly impacts the solvability of the resulting QUBO formulation. We overcome this issue by considering the Restricted Master Problem (RMP) which optimizes over subset of decision variables
RMP: : min cT2 z =E2 s.t.
(3a)
(3b)
4.1. Pricing
Instead of using a relaxed LP formulation for the PP, we use Lagrangian Relaxation (LR) (Wolsey, 2020), which can be used for ILP problems of the form in (3). The partial Lagrangian is given by L(z, A) == c x + X (Dz 1), X E Th and the LR of the RMP is defined as
with Z = f2 E PEP. 3p =1, Va A), C Pa.
&p
n = IP| P = UneA A Pa and E T the vector consisting
of the corresponding path lengths. The constraint matrix D captures inequality constraints from (2):
if VT, Drp + if FiEEr.
LR: C(A) = min C(z, A) = min 2 11, (4) 26
26%
To get equivalence between (3) and (2), we use a two-loop iterative optimization scheme: the outer loop decides which constraints are not fulfilled and should be added to our prob- lem and the inner loop optimizes over subsets of all possible paths for every agent, increasing the number of paths in every step (see Fig. and Algorithm 1). This procedure builds with the hope that we already find a (nearly) optimal solution with not exploring the whole search space, both in terms of decision variables n and number of constraints m. The mathematical framework describing this technique is called Column/Row Generation (Lübbecke). The columns are identified with the decision variables and the rows with the constraints. It alternatingly solves high-level (RMP) and low-level Pricing and Separation problems (PP and SP), which decide which variables/constraints to add to the MP. If solving the PP/SP tells us to not add any more variables, the solution to the MP is optimal by construction.
where c A is the Lagrangian reduced cost vector. Note that (()) S ((RM)), where v(.) indicates the optimal value of the optimization problem.
Theorem 4.1. Let be the objective value of a feasible solution to RMP (Dz 3 1, E 7 and i = c. and X E R. UfMP) + v(MP) then
3a E A: min CA(A) min (,(A) < -(A)). (5)
PEPa/Pa
pEP,
Proof. We give a proof by showing that u (RMP) = (MP)) holds if (5) does not hold. The path variables not in RMP are implicitly assumed to take the value O. Assume now, that one variable not included in the RMP takes value 1 for
4

---

Hybrid Quantum-Classice Multi-Agent Pathfinding
agent a E i.e.e EpEPo Paa 3p 2 1. It follows that
with an optimal dual solution of the LP relaxation of the RMP (Lam et al., b). In our case, we solve the Lagrangian dual (LD)
(MP) = min =EZ
coip: D2 11.
Σ 3p 2 21 (6a)
PEP
PEPu
LD: : max L(A)
max min C(2, AERT SEZ
(8)
AERT
2 min #E2
[ A): : Σ 2p 21
(6b)
Due to standard IL. theory (Geoffrion, 2009), the optimum of LD and the LP relaxation of RMP coincides, since Z is convex. Also, the dual parameters of this LP relaxation exactly correspond to the optimal X Instead of relying on optimal Lagrange parameters, our theorem allows any choice of X E RT.
PePa
min ZE2
(A)zp) Σ
2p 2 1
- -Cx (6c)
PEP
PEPa
min
(x) up
min 8p (A) Cx (6d)
xE2
PEP.
PEP(Pp
4.2. Separation
= Σ
min Ep (A) + min (A) - Cx
(6e)
In addition to adding new paths to our RMP, we can take a similar approach with handling the constraints. Starting off with no inequality constraints ((2c) and (2d)), we can iteratively add them to the RMP, reducing computational (6f)
PEP
PEPa
(a)
= min Cp (A)
min Eo (A) + (()) PEP,
PEP.
20 2 (RMP).
(6g)
overhead. Given a feasible solution & to the RMP, we check whether it is also feasible for the MP. That is, we add the row/constraint & S 1 to the RMP D > 1, Vi E V ET. However, to ensure that our algorithm is optimal, we need to find an optimal solution w.r.t. the current constraints. If this cannot be guaranteed, Algorithm I can diverge to a suboptimal solution. The performance of this procedure is evaluated in Sec. 5.
with Pa = Pa Pa. Cx 1 and 2 = f= E BN EpEr, 2p = 1, Va E A). (6g) holds since we assume that (5) does not hold. We follow that no feasible solution to MP with EPEr. \p. Zp 2 1 can be better than an optimal solution to RMP for each a E A. As all paths not included in the RMP are in the set USEA Pa') \ Pa and ((M)) I ((MP)) is always true, we conclude vMM)) = (RMP). Hence, if (MP) + e(RM)) then (5) holds.
4.3. Solving RMP with QUBO
This theorem leads to an optimality criterion, telling when the variables in the RMP contain the ones for optimal solution to the MP. The pricing problem (PP) aims to find a path not included in the RMP with optimal reduced costs
It remains to clarify how to obtain a solution of (3). In fact, solving the RMP (Algorithm 1, Line 8) is the main computa- tional bottleneck of our developed algorithm, since finding shortest paths (Algorithm 1, Line 5) and solving LP prob- lem (Algorithm 1, Line 7) can be done efficiently. Since we want the solutions to be solvable with QC, we reformu- late the constrained problems into QUBO formulations. We have a look at three different approaches, which all rely on using penalty factors to integrate constraints. The one-hot constraint given in Z (2b) can be integrated by using
PP: min (A), Va E A. PEPoYP.
Even though Pa \\ Pa can be exponentially large, (7) can be solved efficiently. It boils down to a k shortest path problem (k $ (Pa)) on the graph GT with updated edge weights Ae is added to the cost of w. and wa for confficted edges and X is added to all incoming edges to conflicted vertices in the current solution ž. This can be done efficiently, e.g. using Yen's 's algorithm (Yen), which dynamically updates the new shortest path using the already computed paths, obtained with A
min e TTz +> min cTz+ #E2
|| 1||
w
=EB"
for large enough wi > 0, which leads to a QUBO formu- lation (1). Setting w > maxpeP, Cp always guarantees the equivalence. It remains to incorporate the inequality constraints.
Interestingly, (5) generalizes the stopping criterion in clas- sical column generation. The RHS is an upper bound on the optimality gap between the RMP and LD, i.e., (RMP) - v(LD) < 0 C()). If that gap is O, we ex- actly recover the criterion given in (Lam et al., b) given by C,-- a < 0, where a, = minpep. (A) is the dual variable corresponding to the convexity constraint of agent (2b). In typical column generation, the pricing is solved
Slack Variables The first approach inserts slack variables for every inequality constraint, similar to (Davies & Ka- lidindi). This is often pursued in practice but can lead to large number of variables, especially when the number of constraints is large. The linear inequality constraint in (3) can be reformulated with using an auxiliary vector s E B
5

---

Hybrid Caantum-Classicaa Multi-Agent Pathfinding
Since the structure of the CG depends on the underlying problem, it may contain several connected components. Thus, the graph of the QUBO matrix can have multiple connected components, dependent on C. These connected components can be seen as smaller instances, giving us the ability to solve them independently. This can lead to large reduction of the considered problem sizes, which is very vital for current QCs, due to the limited number of available qubits. Furthermore, lower density and well-behaved prob- lem structure can have huge effect on current quantum hardware, as we will see in Sec. 5.
(a) Conflicted paths of exam- plary MAPF problem.
(b) Corresponding discon- nected conflict graph.
Schematic visualization of a conflict graph, which has two connected components. This leads the decomposition into independent subproblems with reduced problem size.
Figure 2:
This leads to two different hybrid quantum-classical MAPF algorithms. QUBO-and and--ricee (QP) describes generating new paths and stopping when (5) is violated (inner loop in Fig. 1). Even though the QUBO solver might not be optimal, this procedure leads to generating all sufficient paths for obtaining an optimal solution. We denote the extension of iteratively adding constraints to our problem as OUBO-and-Cut-andd to generate an optimal path set if the QUBO is solved to optimality in every step. However, we also investigate its suboptimal performance in the next section.
with binary entries, since D= 3 < - 0. This leads to the slightly different but equivalent problem mingez cT 2, s.t. Dz - + 8 = 0. This constrained prob- lem can then be reformulated to an equivalent unconstrained problem by introducing penalty parameter w. 0
(QCP). It is only guaranteed
min
c 2 c, Dz 1+ s|
(9)
Using this formulation, however, comes with the overhead of introducing m additional binary variables. One variable is needed for every inequality constraint, leading to total QUBO dimension of n + m. As we are still in the NISQ era, it is better to resort to QUBO formulation that uses fewer qubits. However, we have a look at the performance of real quantum hardware for this QUBO formulation in Sec. 5.
5. Experimental Evaluation
We compare our algorithms QP and QCP with four state- of-the-art MAPF solvers: BCP (Lam et al., b), EECBS (Li et al., 2021). LaCAM* (Okumura, 2023a) and LNS2 (Li et al., b). BCP is an optimal algorithm but has also been adapted to anytime, while EECBS is suboptimal. LaCAM* and LNS2 are anytime algorithms, which can quickly obtain good feasible solution. For more details on these methods, we refer to the original papers. The code was taken from their respective public repositories 2234, We kept all standard parameters and set a maximum time limit of 180 a for all solvers. The experiments were conducted on a single core of the type Intel(R) Xcon(R) Silver 4216 CPU @ 2.10GHz.
Without Slack Variables Since D E B we can avoid using slack variables by using the equivalence
1 = 2
D2 - 1 + a|| + min 2E2.
min
Dz
(10)
sEZ
since (ni = minnen(n- - +.4 Thus, we do not optimize over any slack variables and reduce the corresponding QUBO size.
For QP and QCP we generate the initial paths with Priori- tized Puth Planning (PPP) (Ma et al.). That is, every agent is planned successively, with removing edges and nodes of previously planned paths. No clever priorization heuristic is followed, we randomly sample which agent to be chosen next. We use maximum limit of 30 pricing steps in total and compute optimal Lagrangian parameters X with LP in every iteration. We compare the optimal solution of the RMP obtained by an IIP wrrch-and-Boung method with the solutions obtained by two different QUBO solvers. As a classical baseline, we use the Simulated Annealing (SA)
Conffict Graph As a third concept, we have a look into Conflict Graphs (CG). The vertices of such a graph corre- spond to all paths considered in the problem and the edges indicate whether there is least one conflict between a pair of paths. An examplary schematic visualization of a conflict graph is given in Fig. 2. We denote the adjacency matrix of CG graph as C. The RMP in (3) is equivalent to
min cT x + wax T CC ZEZ
(11)
'nttps//github.com/ee http://hhhbbbcooomccllamm/mmpppp mapf
"hugs://gihabb.ccm/iiaaaaggggggu
where We E R. penalizes potential conflicts. Note that it is square and the dimension is only dependent on the number of considered paths and not on the number of constraints.
6

---

Hybrid Ciaatum--Classiee Multi-Agent Pathfinding
PPP
QCP-ILP
QP-ILP
QCP-QUBO
QP-QUBO
mandom-32-32-41
r00m-64-64-8
den520d
ost003d
Rel. gap bound
1.0
0.5
0.0
1.0
BCP
Rel. cost
EECBS
0.5
0.0
1.0
LNS2 LaCAM
Rel. cost
0.5
0.0
20
40
60
80
10020
40
60
40 Number of agents
80
10020
60
80
10020
40
60
80
100
Relative performance comparison of methods QP-ILP, QP-QUBO, QCP-ILP and QCP-QUBO the baselines PPP, BCP, EECBS, LNS2 and LaCAM* on four different maps varying number agents. The relative upper bound the optimality gap (top) is shown along with the relative total path costs (middle and bottom) averaged over all 25 scenarios. The lower the better, i.e., a value of 0 corresponds to the best performance, while 1 corresponds to the worst performing algorithm.
Figure 3:
implementation of D- Dawe (D-Wave Systems Inc., 2025)
exceptions) consists of 1000 start-goal position pairs. To evaluate solver on given scenario, we run it on the first 20, 40, 60, 80 and 100 start-goal pairs for all 25 scenarios and indicate the average performance.
and for real quantum hardware, we run experiments D- Wave Advantage system5.4 (D-Wave Systems Inc., 2021) quantum annealer (QA). Since both solvers probabilis- tic, we generate 1000 samples each and use 1000 Monte Carlo sweeps for SA and an annealing time of 20 jss for QA. The remaining remaining unspecified parameters are set to their default values. We compare the three differ- ent QUBO formulations from Sec. 4.3 and denote them by SLACK (9), HALF (10) and CONFLICT (11). These QUBO formulations are dependent penalty parameters, and un- derstanding their impact is crucial for NISQ devices. Large penalty weights can increase the dynamic range of QUBO coefficients (Mücke et al.; Gerlach & Piatkowski, 2024) and decrease the spectral gap (Stollenwerk et al., a;b), reducing solution quality and requiring longer annealing times. In our experiments, set these penalties to the values descrihed in Sec. 4.3 for adhering the constraints and leave special tuning for future work.
Quantum Hardware Limitations We did not scale up our experiments further in terms of the number of agents (e.g. |A| 1000) because the QUBO size grows rapidly with the number of paths and constraints, making the prob- lem increasingly difficult to solve on current NISQ hard- ware. Even with conflict graph decomposition, the resulting QUBOs from larger environments often exceed the qubit capacity and connectivity limitations of existing quantum hardware.
While the D-Wave Advantage System features impressive 5, 670 physical qubits', its limited qubit connectivity poses significant constraints. To embed arbitrary graphical struc- tures, D- Wave relies on chaining multiple physical qubits into logical super-qubits, a process necessitated by the un- derlying hardware topology. The current Pegasus topology
As maps and instances, we use the well-known MovingAl benchmark (Stern et al.). This benchmark includes 33 maps and 25 random scenarios, some of which were utilized our experiments. Every scenario each map (with some

---

Hybrid Quantum-Classen Multi-Agent Pathfinding
Table 1: Total path costs for different maps using 100 agents averaged over 25 scenarios. show the mean and the standard deviation and indicate the best performing method in bold an the second best by underlining the result.
Environment
LNS2
LaCAM
QP-QUBO
QP-ILP
empty-32-32
2164.2 + 88.0
2164.2 + 87.6
2166.5 : 88.9
2163.4 + 88.6
rundom-32-32-10
2239.0 = 113.1
2236.8 + 112.2
2231.3 112.2
2225.4 + 111.5
ro0m-64-64-8
6301.2 + 307.2
6219.2 + 285.4
6323.4 + 342.4
6107.1 + 303.7
maze-32-32-4
4725.4 334.6
4534.3 + 219.8
6332.5 1272.6
5715.9 + 1020.6
d2n312d
5499.4 = 232.6
5492.3 + 224.9
4559.0 + 195.2
4558.9 + 195.2
ost003d
15164.8 + 782.8
15164.2 + 782.2
15166.2 + 783.0
14901.8 + 1452.7
den520d
17391.3 + 970.8
17391.0 + 970.8
17389.5 + 973.5
17378.9 + 3541.7
supports embeddings of up to 182 densely connected logi- cal qubits, while the upcoming Zephyr' topology extends this to 232. Combined with inherent noise limitations, this means that only fraction of the full qubit count can be effectively utilized, restricting practical problem sizes few hundred logical qubits at most. Since path variables added in every iteration of our algorithm, considering problems with more than 100 agents would thus lead to un- reasonable results to the aforementioned limitations. As the quantum hardware matures, more large-scale experiments will be conducted in future work.
more efficient. This is also beneficial for the QUBO solvers, since they can easier generate good solutions for a more well-behaved problem (less constraints).
The mean relative total path cost for the single MAPF in- stances are depicted in the middle and bottom plot row. We compare the baselines PPP, BCP, EECBS, LNS2 and La- CAM* with QP solving the RMP optimally (QP-ILP) and with QUBO (QP-QUBO) If a method does not return any solution in the given time window, we set its performance to the worst other performing method, allowing for a naive anytime comparison. It is evident that QP-ILP is always optimal, while QP-ILP almost always outperforms the best performing baselines LNS2 and LaCAM*, which are better for 100 agents on room-64-64-8, The (sub)optimal algo- rithms BCP and EECBS are always outperformed by our methods due to their bad anytime performance. It is interest- ing that for no map they are able to find all optimal solutions in the given time frame. Since QP-QUBO able to out- perform LNS2 and LaCAM in many cases, our method is applicable without the need of exactly solving the RMP.
Algorithm Performance In Fig. 3, we depict the per- formance of our two algorithms QP and QCP for four different maps of the MovingAl benchmark and varying the number of agents. All performances are shown rela- tive to the best and worst performing configuration, i.c., Pse = (u Pbest) (Nworst - Vbea)) and averaged over all scenarios. This maps all obtained values the range [0, 1], where indicates the best and the worst performance, respectively. For QC-QUBO and QCP-QUBO we use the CONFLICT formulation and the SA solver.
In Table 1, we depict the mean and standard deviation of the total path costs averaged over 25 scenarios for different maps using 100 agents. It is evident, that our method with solving the RMP exactly (QP-ILP) is almost always optimal, except for maze-32-32-4. We use PPP for initializing the set of paths which can lead to bad initial results for large number of eecents-sppecallll for small corridors appearing in the maze-like maps. Adapting the initialization method for obtaining a valid set of conflict-free paths (e.g. using LNS2 or LaCAM instead) can mitigate this effect. Further, finding valid solutions to the RMP with our proposed QUBO formulation (QP-QUBO) is often also outperforming state- of-the-art art heuristics (LNS2 and LaCAM*). However, an increasing agent count makes harder to solve the result- ing -ighnsiienii QUBO problem, sometimes leading to unsatisfactory solver performance. With quantum hard- ware becoming more mature in the future, we expect the
The top plot row shows the mean relative upper bound Gee - Vee (LD) on the optimality gap for a different num- ber of agents. It not only a measure of solution quality, but it also quantifies the problem size. The higher this gap is, the more new paths are added our problem during pricing, since it corresponds to the RHS in our optimality criterion (5). We can see that optimally solving the RMP (QCP-ILP and QP-II.) often has a smaller gap than gen- erating a possibly suboptimal solution by a QUBO solver. However, the QUBO methods largely improve upon the base PPP method. Even though QP clearly outperforms QCP for optimal solving (ILP) of RMP, QCP takes way less constraints into account and is thus computationally
hhtpp::/www.wwwar www.ddwwwwesss.s/miiiiiiee a zephyr topology of d-wave quantum processors.pdf
8

---

Hybrid Chantum-CCasssiee Multi-Agent Pathfinding
Half
Conflict
ILP
Half
Slack
ILP
1.0
1.0
Cost
Cost
0.5
0.5
20
#Infeasible
20
#infcasible
10
10
SA
QA
SA
QA
Figure Performance comparison of different QUBO formulations four different maps with 20-agent problems along optimal solution, where we run QP (Sec. 5) and QCP (Sec. 5) 30 pricing steps. compare SA and QA by indicating the total path cost of the hest sample (top) and the number of infeasible solutions (bottom), i.e. (2c) and (2d) are violated. The cost is scaled by 10
performance of QP-QUBO approach the one of QP-ILP.
is depicted in the bottom row. While SA always finds feasi- ble solutions for HALF, is easier for QA to obtain feasibil- ity with CONFLICT. This is due to the sparsity advantage of CONFLICT over HALF and the corresponding decompo- sition into independent subproblems. Since the hardware topology current quantum computers is strongly limited, such properties have large effect on the solution quality obtained. For QCP, we find that QA finds slightly more feasible solutions with HALF than SL.AKK. However, note that only few separation steps happened and thus only small number of constraints have been generated. Using more pricing steps or scaling the problem size would lead to way more included constraints, making the SLACK QUBO infeasible to solve.
The most time consuming step in algorithm is to solve the QUBO problem. However, a wall-clock time compari- son is difficult for quantum devices nowadays, since there is a large communication overhead when using real quantum hardware over cloud services. Nevertheless, assuming per- feet communication with the QA, we can generate solutions QUBO with annealing time of around 50 jus. Due to its probabilistic nature, we have to generate only few thousand samples. In the near future, this could also lead to very good wall-clock time performance.
QUBO Comparison The effect of using different QUBO formulations for solving the RMP is depicted in Fig. 4. We consider four different maps (maze-32-32244 empty-32-32, uundom-32-32-10 room-32-32-4) and compare the results of QP (Sec. 5) and QCP (Sec. 5) for 20 agents. This leads to varying QUBO sizes between 20 and 400, depending on the underlying map and scenario. We use SA and QA for solving HALFF and CONFLICT for QP and HALF and SLACK for QCP.
6. Conclusion
In this paper, we presented two novel optimal hybrid quantum-classical MAPF algorithms. Extending the classi- cal approach exponentially many branching steps. Paths and constraints are iteratively added to our problem which then solved by utilizing different QUBO formulations, making our algo- rithms suited for quantum computing. On an ideal adiabatic quantum processor, the QUBO subproblems global optimality. We proof generalization of the clas- sically known criterion telling us that our currently avail- able path set is optimal. Experiments indicate good perfor- mance of our algorithm compared to state-of-the-ie MAPF algorithms. Evaluating different QUBO formulations in- dicates the superiority of our approaches over previously presented methods. With these insights, conclude that the hardware-awan design of the QUBO problems can al- ready lead to an advantage on near-term quantum devices.
we circumvent
In the top row, we show the cost of the best sample obtained by SA and QA over all 25 scenarios, along with the op- timal solution (ILP). Only feasible samples are indicated here, that only those who adhere the constraints. For QP, we can see that finding feasible solution with the HALF QUBO is nearly almost optimal while the solution quality of CONFLICT slightly deteriorates. Comparing HALF and SLACK for QCP, we find that both solvers are able to find op- timal solutions. However, QA has problems finding feasible solutions for the first map for all QUBO formulations.
solved to
The number of infeasible solutions returned by SA and QA

---

Hybrid Chantum-CClassicee Multi-Agent Pathfinding
Acknowledgments
Geoffrion, A. M. Lagrangean relaxation for integer pro- gramming. In Approaches to integer programming, pp. 82-114. Springer, 2009.
This research has been funded by the Federal Ministry of Education and Research of Germany and the state of North- Rhine Westphalia as part of the Lamarr Institute for Machine Learning and Artificial Intelligence.
Gerlach, T. and Piatkowski, N. Dynamic range reduction via branch-and anduh--nd--oudd. arXiv preprint wrXiv:2499.1086. 2024.
Impact Statement
Gerlach, T., Knipp, S., Biesner, D., Emmanouilidis,, S., Hauber, K., and Piatkowski, N. Fpga-placement via quan- tum annealing. In Proceedings of the 32nd ACM/SIGDA International Symposium on Field Programmable Gate Arrays (ISFPGA), pp. 43. ACM, 2024.
This paper presents work whose goal is to advance the fields of Optimization and Artificial Intelligence. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Huang, T., Li, J., Koenig, S., and Dilkina, B. Anytime multi-agent path finding via machine learning-guided guided large neighborhood search. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI).
References
Albash, T. and Lidar, D. A. Adiabatic quantum computation. Reviews of Modern Physics. 90(1):015002, 2018.
Ali, M., Ahmed, H., Malik, M. H., and Khalique, A. Multi- commodity information flow through quantum annealer. Quantum Information Processing, 23(9):313, 2024.
Huang, Z., Li, Q. Zhao, J., and Song, M. Variational quantum algorithm applied to collision avoidance of un- manned aerial vehicles. Entropy, 24(11):1685, 2022.
Choudhury, S.. Solovey, K., Kochenderfer, M., and Pavone, M. Coordinated multi-agent pathfinding for drones and trucks over road networks. In Proceedings of the 21th In- ternational Conference on Autonomous Agents and Mul- fiagent Systems (AAMAS).
Johnson, M., Amin, M., Gildert, S., Lanting, T., Hamze, F. Dickson, N., Harris, R., Berkley, A., Johansson, J., Bunyk, P., Chapple, E., Enderud, C., Hilton, J., Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Perminov, I. Rich, C., Thom, M., Tolkacheva, E., Truncík, C., Uchaikin, S., Wang, J., Wilson, B., and Rose, G. Quan- annealing with manufactured spins. Nature, 473 (7346), 2011.
Wave Systems Inc.
Advantage system per- Technical Report 14-
formance update.
1054A-A, D-Wave Systems Inc., 2021. URL
https: //t::///wwww http:://wwwwwwwwee www.:udwwweeuuntu.... cww/media/////cc//mmmccc.c.ccacm
Lam, E., Harabor, D. D., Stuckey, P. J., and Li, J. Exact anytime multi-agent path finding using branch-and-cut- and-price and large neighborhood search. In Proceedings of the 33rd International Conference on Automated Plan- ning and Scheduling (ICAPS), a.
kjtlcemb/1441054er a_adiaaaaae_aaaaaaaaaaaaaaaaaa system__ derforraacc__updateeeee Technical Report.
Wave Systems Inc.
D-wave ocean sdk. https:
//docs. wecean.dwwaee.... com/, 2025. Version 8.1.0.
Lam, E., Le Bodic, P., Harabor, D. D., and Stuckey, P. J. wwwaannndt-ad---iiiee for multi-agent pathfinding. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), b.
Dantzig, G. B. Linear programming. Operations research, 50(1).
Davies, E. and Kalidindi, P. Quantum algorithms for drone mission planning. In Proceedings of Quantum Technolo- giesfor Defence and Security.
Li, J., Chen, Z., Harabor, D., Stuckey, P. J., and Koenig, Anytime multi multi-agent agent path finding via large neighborhood search. In Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI), a.
Desrosiers, J. and Lübbecke, M. E. Branch-price-and-cne algorithms. Encyclopedia of Operations Research and Management Science.
Li, J., Chen, Z., Harabor, D., Stuckey, P. J., and Koenig, Mapf-Ins2: Fast repairing for multi-agent path finding via large neighborhood search. In Proceedings of the 36th AAAI Conference Artificial Intelligence (AAAI), b.
Doole, M., Ellerbroek, J., and Hoekstra, J. Estimation of traffic density from drone-based delivery in very low level urban airspace. Journal of Air Transport Management, 88: 18:881 2020.
Li, J., Tinka, A., Kiesel, S., Durham, J. W., Kumnr,, T. S., and Koenig, S. Lifelong multi-agent path finding in large- scale warehouses. Proceedings of the 35th AAAI Con- ference on Artificial Intelligence (AAAI),
Farhi, E., Goldstone, J., and Gutmann, A quantum approximate optimization algorithm. arXiv preprint 1rXiv:14/1.402.. 2014.
10

---

Hybrid Caantum-Classicii Multi-Agent Pathfinding
Li, J., Ruml, W., and Koenig, S. Becbs: A bounded- suboptimal search for multi-agent path finding. In Pro- ceedings of the 35th AAAI Conference on Artificial Intel- ligence (AAAI), pp. 12353. AAAI Press, 2021.
Sharon, G., Stern, R., Felner, A., and Sturtevant, N. Conflict- based search for optimal multi-agent path finding. In Proceedings of the 26th AAAI Conference Artificial Intelligence (AAAI).
Li, Q., Huang, Z., Jiang, W., Tang, Z., and Song, M. Quan- tum algorithms using infeasible solution constraints for collision-avoidaacee route planning. IEEE Transactions on Consumer Electronics, 2024.
Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T., Li, J., Atzmon, D., Cohen, I.., Kumar, T. et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proceedings of the 12th International Symposium on Combinatorial Search (SoCS).
Lübbecke, M. E. Column generation. Encyclopedia of Operations Research and Management Science, 17.
Stollenwerk, T., Lobe, E., and Jung, M. Flight gate assign- ment with quantum annealer. In International Workshop on Quantum Technology and Optimization Problems,
Ma, H., Harabor, D., Stuckey, P. J., Li, J., and Koenig, S. Searching with consistent prioritization for multi-agent path finding. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI).
Stollenwerk, T., O' O'Gorman, B., Venturelli, D., Mandra, S., Rodionova, O., Ng, H., Sridhar, B., Rieffel, E. G., and Biswas, R. Quantum annealing applied de-conflicting optimal trajectories for air traffic management. IEEE Transactions on Intelligent Transportation Systems, 21 (1), b.
Martín, M. P. and Martin, S. Unsplittable multi-commodity flow problem via quantum computing. Proceedings of the 9th International Conference on Control, Decision and Information Technologies (CoDIT).
Tarquini, S., Dragoni, D., Vandelli, M., and Tudisco, F. Test- ing quantum and simulated annealers on the drone deliv- ery packing problem. arXiv preprint 2xXv:2406.004300 2024.
Mücke, S. and Gerlach, T. Efficient light source placement using quantum computing. In Proceedings of the Con- ference "Lernen, Wissen, Daten, Analysen" (LWDA). CEUR-WS.org. 2023.
Wolsey, L. A. Integer programming. John Wiley & Sons, 2020.
Mücke, S., Gerlach, T., and Piatkowski, N. Optimum- preserving qubo parameter compression. Quantum Ma- chine Intelligence, 7(1).
Yen, Finding the k shortest loopless paths in network. Management Science, 17(11).
Zhang, Y., Zhang, R., and Potter, A. C. Qed driven qaoa for network- -foow optimization. Quantum, 5:510, 2021.
Okumura, K. Improving lacam for scalable eventually opti- mal multi-agent pathfinding. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 243, 2023a.
Okumura, K. Lacam: Search-based algorithm for quick multi-agent pathfinding. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), pp. 11655. AAAI Press, 2023b.
Preskill, J. Quantum computing in the nisq era and beyond. Quantum, 2:79, 2018.
Punnen, A. P. The quadratic unconstrained binary optimiza- tion problem. Springer, 2022.
Rönnberg, E. and Larsson, T. An integer optimality condi- tion for column generation on zero-one linear programs. Discrete Optimization, 31.
Sadykov, R., Vanderbeck, F., Pessoa, A., Tahiri, L, and Uchoa, E. Primal heuristics for branch and price: The as- sets diving methods. INFORMS Journal on Computing, (2)..


Reviews:
[{"review_id": "jhpPj4HoQO", "reviewer": "Reviewer_Hq32", "summary": "This paper approaches large scale multi-agent path finding as a hybrid quantum computing problem by combining branch-and-cut-and-prize (BCP) with quadratic unconstrained binary optimization (QUBO) formulations for resolving path conflicts. The resulting hybrid algorithms are evaluated on several common large-scale multi-agent path finding tasks, where favorable performance over baseline algorithms is demonstrated.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thorough and insightful evaluation of our paper. We are encouraged by the positive assessment regarding our motivation, theoretical contributions, experimental validation, and presentation. We address the reviewer’s specific comments and questions below. Everything not addressed in this answer will be integrated into the camera ready version.\n\n### Scalability to Larger MAPF Instances (e.g., den520d, lak503d):\nWe appreciate the suggestion to evaluate on larger-scale maps. The main limitation in scaling to domains such as den520d and lak503d is twofold:\n#### QUBO dimensionality\nThe number of binary variables grows rapidly with the number of paths and constraints, which directly impacts the QUBO size and solvability on current NISQ hardware.\n#### Hardware constraints\nEven with conflict graph decomposition, QUBOs derived from larger environments often exceed current quantum annealers' qubit capacities and connectivity constraints.\n\nOur contributions consist of the presentation of the first quantum-compatible optimal algorithm that leverages QUBO \nformulations. Our approach is grounded in a theoretically proven optimality guarantee, which generalizes classical \ncolumn generation theory to the binary domain. We introduce a hardware-aware QUBO design, enabling scalable and \nparallel sub-problem decomposition—crucial for current and near-term quantum devices. By successfully integrating \nthese concepts and demonstrating favorable performance on standard MAPF benchmarks, our work paves the way for exploiting future generations of quantum hardware in complex combinatorial planning tasks.\n\nThat said, our method is modular and scales well with improvements in hardware or more aggressive decomposition techniques. We plan to explore den520d and lak503d in future work using circuit-based quantum methods or batched hybrid strategies. We will add a discussion on this to the paper.\n\n### Clarification on QP-QUBO vs. LNS2 Scaling Trends (Maze and Room Domains):\nWe agree that the observed trend—LNS2 improving with more agents, while QP-QUBO degrades—is interesting. \nThis can be attributed to the heuristic flexibility of LNS2, which benefits from local repair in denser agent settings. \nIn contrast, QP-QUBO solves a more rigidly structured optimization problem where QUBO hardness increases with more \nconflicts. Since QUBO is solved heuristically via SA/QA, solution quality can deteriorate with size unless additional \npaths or constraints are added, which also increases problem size. \nFurthemore, we use Prioritized Path Planning for initializing the set of paths which can lead to suboptimal initial \nresults for a large number of agents. Adapting the initial heuristic for obtaining a valid set of conflict-free paths (e.g. using LNS2 instead) can \nmitigate this effect. We will clarify these phenomena in the revised version.\n\n### Benchmark Variability Across Map Sizes:\nThank you for highlighting this. Due to space constraints, we selected representative maps from each structural class. However, we agree that presenting performance across different sizes within the same map type (e.g., room-32-32 vs. room-64-64) would enrich the analysis. We will consider adding this to the appendix or releasing extended experiments online.", "claims_and_evidence": "The claims of the paper are well-motivated and the resulting algorithms are tested on several example scenarios with favorable performance compared to selected baselines. Additional ablations provide further insights into performance differences among e.g. different underlying QUBO formulations.", "methods_and_evaluation_criteria": "The proposed methods and evaluations make sense, validating performance on established tasks against capable baselines. Scaling to even larger scale examples, as considered by one of the baselines, could further improve the paper (or alternatively further discussion of why this is currently not possible).", "theoretical_claims": "I did not see issues with the theoretical claims.", "experimental_designs_or_analyses": "The overall evaluation is good, comparing against key baselines on established benchmarking tasks. Extension to larger scale domains provided in the MAPF benchmark or discussion of why this is currently infeasible would further strengthen the paper.", "relation_to_broader_scientific_literature": "The paper gives a good overview of related work and where the current approach is situated relative to prior works.", "essential_references_not_discussed": "Consider citing a D-Wave technical report.", "other_strengths_and_weaknesses": "- The paper is well-written, leverages well-crafted illustrations, and is therefore mostly easy to follow\n- The maps considered for benchmarking include small to intermediate size scenarios from the MAPF benchmarks by MovingAI. What is restricting extension to the larger maps? Are you hardware limited? It would be interesting to discuss further details here.\n- Similarly, the original BCP paper evaluated on the larger den520d and lak503d domains - how would QP-QUBO fare on these tasks?\n- The used MAPF benchmark provides different sizes per map type, it would be interesting how performance comparisons behave across map sizes.\n- In Figure 3, consider adding environment names to each column in addition to the map\n- It could be interesting to see e.g. performance standard deviation around the average in Figure 3, potentially as an extra figure in the appendix to maintain visual clarity.", "other_comments_or_suggestions": "- Line 023: also add CBS abbreviation after “Conflict-based Search”\n- Line 131: wait (at) a certain location\n- Line 194: NISQ abbreviation used before introduction in Line 306\n- The abbreviations QP and QCP might be a bit overloaded for some readers thinking of Quadratic(ally Constrained) Programs - QuP and QuCP could be options?", "questions_for_authors": "- Could you clarify why LNS2 seemingly improves with increasing agent count on the maze and room domains, while QP-QUBO shows the opposite trend?\n- Could you clarify scalability (issues) when considering larger environments from the MAPF benchmark?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ELGg83414P", "reviewer": "Reviewer_uUqH", "summary": "The paper presents a quantum-classical hybrid approach to multi-agent path finding based on solving the restricted master problem via a QUBO translation.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed and structured feedback. We address your concerns below and will incorporate unresolved items into the final version.\nAny other points not mentioned in this answer will be fixed in the camera ready version.\n\n### On the Strength of Our Claims and Baseline Selection:\nWhile we appreciate that the reviewer finds our claims supported, we respectfully disagree that they are weak. Our contributions go beyond empirical comparisons:\n- We present the first quantum-compatible optimal MAPF algorithm, introducing a novel integration of QUBO formulations into a branch-and-cut-and-price framework.\n- We provide a theoretical optimality guarantee, generalizing known results to the integer domain.\n- Our hardware-aware QUBO design, incorporating conflict graphs, enables practical decomposition and paves the way for future scalability with emerging quantum hardware.\n- Through our quite general and extensive experimental setup, we show advantages over popular MAPF baselines\n\n### On Baseline Selection:\nWhile our experiments compare against selected strong baselines (BCP and LNS2), we agree that more extensive comparisons could further strengthen the work. We are currently running additional experiments with EECBS [1] and LaCAM [2,3], and will incorporate their results or a discussion in the updated version.\n\n### On Classical Baselines and Fully Classical Solvers:\nThe reviewer correctly points out the importance of a fair baseline. In addition to heuristic methods (e.g., LNS2), we note that our ILP-based solver is itself a fully classical method, using branch-and-bound for exact optimization. We will clarify this point in the manuscript and expand the discussion of classical methods in the related work section, including suboptimal but high-performance solvers like EECBS and LaCAM.\n\n### On Experimental Design and Quantum Annealing Setup:\nWe agree that more details on the quantum annealing setup can enhance clarity. We used D-Wave’s default parameters and will include explicit settings such as annealing time (e.g., 50µs) and the number of samples. If the reviewer has specific choices they would like us to elaborate on (e.g., QUBO encoding, annealer scheduling, embedding strategies), we are happy to address those explicitly.\n\n### On the Usefulness of Quantum Annealing Today:\nWe fully agree that quantum annealing is not yet outperforming classical methods in most practical MAPF scenarios. Our paper does not claim otherwise. Instead, our goal is to present a hardware-aware, theoretically grounded framework that integrates quantum optimization in a meaningful way—even if its benefits will become more tangible as hardware improves. We will clarify this positioning and explicitly reference hardware roadmaps such as IBM’s quantum roadmap (https://www.ibm.com/roadmaps/quantum/) to illustrate the forward-looking relevance of this work.\n\n[1] Li, Jiaoyang et al. \"EECBS: Bounded-Suboptimal Search for Multi-Agent Path Finding.\" In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.\n\n[2] Okumura, Keisuke. \"LaCAM: Search-based Algorithm for Quick Multi-Agent Pathfinding.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 10. 2023.\n\n[3] Okumura, Keisuke. \"Engineering LaCAM*: Towards Real-time, Large-scale, and Near-optimal Multi-agent Pathfinding.\" In Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2024.", "claims_and_evidence": "Claims are supported, but the claims are rather weak anyway, involving only certain baseline solvers in a specific setup.", "methods_and_evaluation_criteria": "The classical baseline approach appears too simple and competitive classical state of the art is not sufficiently discussed.", "theoretical_claims": "One theorem is introduced, although not really needed for the empirical approach of this study.", "experimental_designs_or_analyses": "The comparison study is lacking better baselines as well as a fully classical optimization-based approach. Various choices are insufficiently discussed and the quantum computer setup is not sufficiently explained.", "relation_to_broader_scientific_literature": "appears fine", "essential_references_not_discussed": "none come to mind", "other_strengths_and_weaknesses": "Aside from what I described above, it is also unclear where any possible advantage up to the point of \"dominat[ing] [...] baseline MAPF solvers\" should even come from. Quantum annealing is notoriously inefficient at the moment.", "other_comments_or_suggestions": "typos: \"prize\" (l. 024), \"j--th\"(use \"$j$th\", l. 090), \"however\" (meant \"but\", l. 109), wrong citation style (l. 139, e.g.), \"implicitely\" (l. 227), \"c.f.\" (l. 234), \"the in the ...\" (l. 359)", "questions_for_authors": "none", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "orSKt048EX", "reviewer": "Reviewer_f7fA", "summary": "The paper proposes novel hybrid quantum-classical algorithms leveraging quantum annealers for the problem of multi-agent path finding (MAPF). It proposes two iterative variant algorithms, QUBO-and-Price (QP) and QUBO-and-Cut-and-Prince (QCP) based on the idea of branch-and-cut-and-price (BCP) to find conflict-free paths for multiple agents navigating through shared space, which are among the first of its kind in the literature. Alongside theoretical proof guarantee, the experiments show that these algorithms have achieved competitive performance comparatively. This work provides an interesting method for solving this problem.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and constructive feedback. Below, we address each of the raised concerns and clarify several technical points. We will incorporate any remaining clarifications and adjustments into the final version.\n\n### Relevance to ICML and the Machine Learning Community:\nWe acknowledge the reviewer's concern regarding scope. While MAPF is a combinatorial optimization problem, our submission aligns with ICML’s growing interest in quantum computation, optimization theory, and AI planning. Recent ICML papers have explored quantum optimization, hardware-aware algorithm design, and combinatorial planning—topics closely related to our work. Furthermore, MAPF is widely studied in multi-agent reinforcement learning and planning under constraints, often intersecting with machine learning methodologies.\n\n### Clarification on the Adiabatic Theorem (Lines 84–88):\nWe agree that the current phrasing may overstate the practical applicability of the adiabatic theorem to real-world quantum annealers. We will revise this section to clearly distinguish idealized adiabatic quantum computation from practical implementations such as D-Wave’s quantum annealer, which is subject to thermal noise and device-specific imperfections. Our discussion will be reframed under the broader umbrella of quantum optimization, and not restricted to quantum annealing.\n\n### Use of the Term “NISQ” (Line 194):\nWe appreciate the clarification. While “NISQ” is typically used to describe gate-based devices, it is also used in broader literature to refer to pre-fault-tolerant quantum systems, including annealers. We will clarify this distinction and highlight that quantum annealers suffer from different noise models (e.g., Integrated Control Errors, ), as documented in D-Wave’s technical materials (https://docs.dwavequantum.com/en/latest/quantum_research/errors.html). Regardless, we will revise this terminology for clarity and consistency.\n\n### Use of QUBO for ILP and Comparison to Classical Solvers:\nWe acknowledge the need to clarify this point. The original optimization objective is indeed an Integer Linear Program (ILP), which is NP-hard. We explicitly compare our QUBO-based approach with a classical exact ILP solver (via branch-and-bound), and will emphasize this more clearly in the experimental section. The benefit of QUBO is not in replacing linear programming for trivial cases, but in enabling structured quantum-compatible formulations with hardware-aware decomposition, which can become more relevant as hardware capabilities improve.\n\n### Ablation Studies and Penalty Effects in QUBO:\nWe agree that understanding the effect of penalty parameters and hardware constraints is critical. Large penalty weights may increase the dynamic range of the QUBO coefficients, potentially leading to:\n- Weaker embedding quality and increased chain breaks\n- Reduced solution quality due to spectral gap constraints\n- Increased annealing time requirements\n\nThese trade-offs are well-known in the quantum annealing literature. While our current contribution focuses on algorithmic structure and theoretical guarantees, we recognize the importance of such ablation studies and plan to pursue them in future work, especially as hardware matures.\n\nWe fully agree that quantum annealing is not yet outperforming classical methods in most practical MAPF scenarios. Our paper does not claim otherwise. Instead, our goal is to present a hardware-aware, theoretically grounded framework that integrates quantum optimization in a meaningful way—even if its benefits will become more tangible as hardware improves. We will clarify this positioning and explicitly reference hardware roadmaps such as IBM’s quantum roadmap (https://www.ibm.com/roadmaps/quantum/) to illustrate the forward-looking relevance of this work.\n\n### Clarification from Eq. (9) to (10):\nThank you for pointing this out. The equivalence from (9) to (10) stems from the fact that the slack variables in (9) only serve to linearize the inequality constraint Dz ≤ 1. In (10), we exploit the binary nature of D and z, and reformulate the constraint violation as a quadratic penalty without introducing additional variables. We will elaborate on this derivation in the revised version for clarity.\n\nWe thank the reviewer again for their helpful suggestions, which we believe will substantially improve the clarity and impact of our paper.", "claims_and_evidence": "below expectations", "methods_and_evaluation_criteria": "n/a", "theoretical_claims": "inaccurate", "experimental_designs_or_analyses": "below expectations", "relation_to_broader_scientific_literature": "n/a", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "Strength: \n1) The first quantum-classical solver for MAPF; \n2) Detailed math formulation of the MAPF problem as a QUBO which can run on annealers; \n3) Extensive experimental evaluations of the protocol which showed great performance compared to other solvers adopted for benchmark. \n\nWeaknesses: \n1) The proper tries to address the problem of coordinating paths for multiple agents. My question is then how is this related to machine learning as ICML is a conference for machine learning? I think it could be better presented at a conference like IROS; \n2) The writing is not easy and logical enough to follow and requires special attention; \n3) Some statements on the background of quantum computing are inaccurate. For example, in L84 - 88, the adiabatic theorem only guarantees the ground state if there are no thermo-perturbations which does not exist for D-Wave annealers. This statement could be misleading; \n4) in L194, the \"NISQ\" device normally refers to gate-based methods, but not for annealers. Specifically, annealers do not suffer from the noise that is commonly referred to in gate-based models; \n5) Some details require further explanation. For example, from (9) to (10), why does (10) hold if slack variables are not used? I have to think and guess it makes sense, but it can benefit from a more thorough explanation; \n6) In the formulation of the QUBO problem, the quadratic nature comes from the way that the constraint is incorporated, not the original objective function. So there raises a question: How justifiable is it to use the annealer in this case. In other words, if the constraint is not enforced via a soft constraint but through some other form, the objective is just a linear programming problem, in which there exist many more specific solvers. A more detailed comparison with these solvers is lacking in the experiment; \n7) Some ablation studies are missing. How does the penalty impact the problem accuracy and the hardware-specific sparsity? Probably also the chain broke during the embedding.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "n/a", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MmHqvFz80B", "reviewer": "Reviewer_32og", "summary": "This paper studies the problem of multi-agent pathfinding. The authors proposed a framework that can formulate the problem to a two-level optimization problem and then be able to use a quantum computing method to efficiently solve the problem (QUBO). The authors proved that the algorithm is able to find the optimal solution in the end. The authors provided a detailed comparison between the performance of the proposed methods and several benchmark planners' anytime performances and conclude that the proposed planner can efficiently solve MAPF problem optimally in many different cases.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and thoughtful observations. Below, we address each of the main concerns and suggestions raised.\n\n### Clarification of Contributions and Novelty:\nWe appreciate the reviewer’s request for a clearer articulation of our contributions. Our key novelty lies in proposing the first quantum-compatible algorithm for MAPF that is theoretically grounded and hardware-aware. While QUBO as a general optimization framework is not new, our contribution lies in:\n- Structuring the MAPF problem via a two-level optimization framework suitable for QUBO translation.\n- Proving a formal optimality guarantee in this setting, extending classical results to the integer domain.\n- Introducing a hardware-aware QUBO design, using conflict graphs to enable decomposition into independent subproblems for practical execution on current quantum devices.\n\nQuantum annealing is not yet outperforming classical methods in most practical MAPF scenarios. Our paper does not claim otherwise. Instead, our goal is to present a hardware-aware, theoretically grounded framework that integrates quantum optimization in a meaningful way—even if its benefits will become more tangible as hardware improves. We will clarify this positioning and explicitly reference hardware roadmaps such as IBM’s quantum roadmap (https://www.ibm.com/roadmaps/quantum/) to illustrate the forward-looking relevance of this work.\n\nWe will revise the introduction and contribution sections to make these points more explicit.\n\n### Comparison with SOTA MAPF Algorithms (LaCAM and EECBS):\nWe thank the reviewer for pointing out important recent advancements. We are currently running experiments with LaCAM* and EECBS to compare against our proposed methods and will include the results or a detailed discussion in the updated version. Additionally, we will expand the related work section to cover the LaCAM series (including PIBT) and EECBS to provide better contextualization within the MAPF literature.\n\n### Scaling Beyond 100 Agents (e.g., to 1000 Agents):\nWe agree that scaling is a crucial topic. While our current experiments evaluate up to 100 agents, scaling to thousands of agents on today’s quantum hardware remains infeasible due to hardware limitations in terms of qubit count, connectivity, and precision. Nonetheless, our framework is modular and designed to be compatible with future quantum devices. We identify large-scale testing (e.g., 1000 agents) as an important direction for future work, especially as quantum hardware evolves.\n\nWe appreciate the reviewer’s positive comments on the novelty and applicability of our approach, as well as the clarity and illustrations in the paper. We believe that with these improvements, the paper will provide even greater value to both the MAPF and quantum optimization communities.", "claims_and_evidence": "As discussed below, there are other SOTA algorithms in the field, and it would be better if the authors can take them into consideration and compare the performance. Besides that, the claims are supported well and look good to me. Besides, the contribution of this work is not explicit to me. It seems that the core weapon of the framework - QUBO solving strategy is not the novelty here, and this work applies this method in the MAPF problem. The flow-problem formulations and integer programming related methods and formulations are studied before as well. It would be nice if the authors can explicitly discuss the contribution of this work more clearly.", "methods_and_evaluation_criteria": "In this paper, the authors compared the performance of the proposed planner with LNS2 and BCP. However, the current SOTA algorithm of MAPF problem should be LaCAM series algorithm. Specifically, LaCAM* is also an anytime MAPF algorithm which is able to converge to the optimal solution. Given this, it would be good if the authors can include LaCAM into the benchmarks and compare the performance with it (them). Besides, some variant algorithms of CBS are bounded suboptimal, such as EECBS (AAAI 2021), although it's not anytime, since BCP is taken into account, it would be nice if such bounded suboptimal algorithms can also be compared.", "theoretical_claims": "The proof looks good to me.", "experimental_designs_or_analyses": "The authors used many experiments and illustrated the advantages of the proposed algorithms against BCP and LNS in different cases. The experiments look good in general, but in the performance comparison experiments, it would be interesting to see the results in experiments with more agents. As the authors mentioned on page 4, the efficiency of the quantum algorithm is closely related to the number of decision variables. Currently the maximum scale of the problem is 100 agents, and it would be nice if the authors can provide the results for experiments with more agents (1000, let's say) and compare the performance.", "relation_to_broader_scientific_literature": "In this paper, the authors proposed an interesting and applicable approach to solve MAPF problems using quantum computation, which is pretty novel in the community. On the other hand, the result in the paper paves the way for using quantum computing in more robotics scenarios, which is interesting and promising.", "essential_references_not_discussed": "As mentioned in the above Methods And Evaluation Criteria part, LaCAM series algorithms should be included and discussed. The papers are published in AAAI and IJCAI 2023, with the prior work PIBT published in IJCAI 2019.", "other_strengths_and_weaknesses": "The paper is written and organized clearly and the illustrations are useful for understanding the algorithm.", "other_comments_or_suggestions": "The term NISQ is used in page 4 without explanation. The explanation is on page 6. It's better to put the explanation before using it.", "questions_for_authors": "All discussed in the above parts", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper presents a hybrid quantum-classical algorithm for solving multiagent path-finding problems. The experiments on quantum hardware show the promise of this approach. 

The reviewers acknowledge the work's merits. Their criticisms mostly stem from the paper's originally insufficient explanation of the quantum aspects of this work's background, but the rebuttals have addressed this, and on the whole the reviewers would like to see this paper accepted. The metareviewer encourages the authors to incorporate the explanations they provided during the rebuttal phase into the camera-ready version of the manuscript.
Decision: Accept (poster)