Research map / Multi-agent systems and games / Human-AI and goal-conditioned
Hybrid Quantum-Classical Multi-Agent Pathfinding
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes optimal hybrid quantum-classical multi-agent pathfinding algorithms (QP and QCP) that embed QUBO solves of restricted master problems inside branch-and-price(-and-cut), using conflict-graph QUBO formulations evaluated with simulated annealing and a D-Wave Advantage quantum annealer.
Problem
Optimal multi-agent path finding (MAPF) is NP-hard and scales poorly with agent count; existing quantum formulations are edge-based or too large for near-term quantum hardware.
Approach
Embed QUBO solving into a path-based column/row generation (branch-and-price-and-cut) loop: the restricted master problem is solved as a QUBO using conflict-graph formulations that decompose into independent subproblems, with a generalized pricing optimality criterion that allows arbitrary Lagrangian multipliers.
Key results
- QP-ILP achieves the optimal total path cost in almost all cases and beats LNS2 and LaCAM* on most maps with 100 agents (e.g., room-64-64-8: 6107.1 vs LaCAM* 6219.2).
- QP-QUBO with simulated annealing outperforms LNS2 and LaCAM* on several maps (e.g., den312d: 4559.0 vs 5499.4 for LNS2), but is worse on maze-32-32-4.
- Experiments are limited to about 100 agents because the QUBO size grows rapidly; the Half and Conflict formulations are compared on 20-agent problems on D-Wave hardware.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| solve the RMP optimally with ILP rather than use QP-QUBO | QP · MovingAI MAPF benchmark, varying agent counts | total path cost | Helped |
| use QP-ILP instead of the best baseline | QP · room-64-64-8, 100 agents | total path cost | Hurt |
| use QP-QUBO instead of PPP | QP · MovingAI MAPF benchmark, varying agent counts | relative total path cost | Helped |
| use QP-QUBO instead of LNS2 or LaCAM* | QP · MovingAI MAPF benchmark, varying agent counts | relative total path cost | Mixed |
| initialize with PPP rather than a conflict-free solution from LNS2 or LaCAM* | QP · maze-32-32-4, 100 agents | total path cost | Hurt |
| use the Conflict formulation instead of Half for QP (ablation) | QP-QUBO · four MovingAI maps, 20 agents | total path cost | Hurt |
| use Conflict instead of Half for QP (ablation) | QP-QUBO · four MovingAI maps, 20 agents | feasible-solution count | Helped |
| use Slack instead of Half for QCP (ablation) | QCP · four MovingAI maps, 20 agents | optimal-solution quality | No clear effect |
| use Half instead of Slack for QCP (ablation) | QCP-QUBO · four MovingAI maps, 20 agents | feasible-solution count | Helped |
| use Conflict instead of Half (ablation) | QP-QUBO · four MovingAI maps, 20 agents | total path cost | Hurt |
Surprising findings
- QCP-ILP takes far fewer constraints into account but QP-ILP achieves better optimality gaps, so the constraint-generation variant does not dominate on the RMP side.
- Quantum annealer (QA) struggles to find feasible solutions for some maps with all QUBO formulations.
Limitations
- Problem sizes limited to around 100 agents and a few hundred logical qubits due to D-Wave topology and noise.
- QUBO solvers often return suboptimal or infeasible solutions; QP-QUBO performance on maze-type maps is weaker; PPP initialization is weak for large agent counts.
- Penalty parameters were set heuristically and not tuned.
Experimental setup
Datasets: MovingAI benchmark maps and random scenarios
Benchmarks: MovingAI benchmark (empty-32-32, random-32-32-10, room-64-64-8, maze-32-32-4, den312d, ost003d, den520d)
Metrics: total path cost relative optimality gap upper bound number of infeasible QUBO solutions
Baselines: BCP EECBS LaCAM* LNS2 PPP QP-ILP
Builds on: branch-and-cut-and-price (BCP) for MAPF column generation Lagrangian relaxation Yen's k-shortest path algorithm
Closest papers by meaning
- Inapproximability of Optimal Multi-Agent Pathfinding Problems (AAAI 2025 · similarity 0.85)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-Agent Pathfinding (AAAI 2024 · similarity 0.85)
- QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design (NeurIPS 2025 · similarity 0.84)
- Differentiable Quantum Computing for Large-scale Linear Control (NeurIPS 2024 · similarity 0.84)
- Windowed MAPF with Completeness Guarantees (AAAI 2025 · similarity 0.84)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.