Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

Hybrid Quantum-Classical Multi-Agent Pathfinding

Created by
  • Haebom

Author

Thore Gerlach, Loong Kuan Lee, Fred Eric Barbaresco, Nico Piatkowski

Outline

In this paper, we present the first optimal hybrid quantum-classical algorithm for the many-agent pathfinding (MAPF) problem. MAPF is a problem of determining collision-free paths for multiple agents to reach a goal location in a shared space, which becomes computationally difficult especially when dealing with a large number of agents. In this paper, we present a hybrid algorithm based on branch-and-cut-and-price and integrate quantum computing (QC) into the iterative solution of the QUBO problem based on a conflict graph. We demonstrate that it outperforms the existing QUBO formulation and the state-of-the-art MAPF solver through experiments on real quantum hardware and benchmark data.

Takeaways, Limitations

Takeaways:
We present the first optimal hybrid quantum-classical algorithm for the multi-agent pathfinding problem.
Demonstrated superior performance over conventional QUBO formulations and state-of-the-art MAPF solvers.
Presentation of experimental results on real quantum hardware.
Limitations:
Consideration should be given to the limited computational power and error tolerance of current quantum hardware.
Further research is needed on the scalability of the algorithm and its applicability to various MAPF problem types.
👍