Hybrid Quantum-Classical Multi-Agent Pathfinding
Authors: Thore Gerlach, Loong Kuan Lee, Frederic Barbaresco, Nico Piatkowski
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 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. |
| Researcher Affiliation | Collaboration | 1University of Bonn 2Fraunhofer IAIS 3Thales Land and Air Systems. Correspondence to: Thore Gerlach <EMAIL>. |
| Pseudocode | Yes | Algorithm 1 QUBOANDPRICEANDCUT Input: Shortest independent paths P and z = 1 Output: Optimal feasible solution 1: C 2: while z is infeasible do Separation 3: Add violated constraints to C 4: while not (5) do Pricing 5: p arg minp cp(λ, C) Shortest path 6: P P {p } 7: λ OPTIMIZELAGRANGIAN(P, C) Solve (8) 8: z OPTIMIZEMASTER(P, C) QUBO (Sec. 4.3) 9: end while 10: end while |
| Open Source Code | No | The paper states: "The code was taken from their respective public repositories1234." but this refers to the baselines used for comparison, not the authors' own implementation of QP and QCP. There is no explicit statement about releasing the code for the methodology described in this paper nor a direct link to a code repository for their work. |
| Open Datasets | Yes | As maps and instances, we use the well-known Moving AI benchmark (Stern et al.). |
| Dataset Splits | Yes | Every scenario on each map (with some exceptions) consists of 1000 start-goal position pairs. To evaluate a solver on a 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. |
| Hardware Specification | Yes | The experiments were conducted on a single core of the type Intel(R) Xeon(R) Silver 4216 CPU @ 2.10GHz. ...for real quantum hardware, we run experiments on a D-Wave Advantage system5.4 (D-Wave Systems Inc., 2021) quantum annealer (QA). |
| Software Dependencies | Yes | D-Wave Systems Inc. D-wave ocean sdk. https: //docs.ocean.dwavesys.com/, 2025. Version 8.1.0. |
| Experiment Setup | Yes | We kept all standard parameters and set a maximum time limit of 180 s for all solvers. We use a maximum limit of 30 pricing steps in total and compute optimal Lagrangian parameters λ with LP in every iteration. As a classical baseline, we use the Simulated Annealing (SA) implementation of D-Wave (D-Wave Systems Inc., 2025) and for real quantum hardware, we run experiments on a D-Wave Advantage system5.4 (D-Wave Systems Inc., 2021) quantum annealer (QA). Since both solvers are probabilistic, we generate 1000 samples each and use 1000 Monte Carlo sweeps for SA and an annealing time of 20 µs for QA. In our experiments, we set these penalties to the values described in Sec. 4.3 for adhering the constraints and leave special tuning for future work. |