Multi‐agent path finding for reversible conveyors

Meiser, Dominic Sebastian; Hermanns, Roy; Noll, Thomas; Katoen, Joost-Pieter

doi:10.18154/RWTH-2025-10004

Multi‐agent path finding for reversible conveyors

Meiser, Dominic Sebastian^RWTH*

2025

Verantwortlichkeitsangabeby Dominic Sebastian Meiser

ImpressumAachen : RWTH Aachen University 2025

Umfang1 Online-Ressource : Illustrationen

Masterarbeit, RWTH Aachen University, 2025

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak09

Hauptberichter/Gutachter
Noll, Thomas (Thesis advisor)^RWTH* ; Katoen, Joost-Pieter (Thesis advisor)^RWTH* ; Hermanns, Roy (Consultant)^RWTH*

Tag der mündlichen Prüfung/Habilitation
2025-11-24

Online
DOI: 10.18154/RWTH-2025-10004
URL: https://publications.rwth-aachen.de/record/1022411/files/1022411.pdf

Einrichtungen

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Quantum computers contain qubits that need to be close to each other for certain operations. The SpinBus architecture is a quantum computer architecture that allows shuttling these qubits around on reversible conveyors. The connectivity, i.e. the number of qubits that can be close to each other, is limited to 2. This means that qubits need to be moved frequently. Also, a conveyor can have more than one qubit on it, which means that qubits cannot move independently. A compiler for this architecture needs to plan moving qubits with the specifics of the architecture in mind. This thesis investigates Q‐MAPF, an extension of Multi‐Agent Path Finding (MAPF) for application in qubit routing. We show poor performance in prior work, in terms of both time and memory usage, and explore ways to improve the performance. First, we approach the problem by exploiting symmetries, which turns out to not improve the performance. Then, we work on a more optimal constraint generation for CBS, an algorithm that can solve MAPF problems, which improves performance: The execution time is improved up to 2.5 times, and we can solve more problems than previously due to lower memory usage. Finally, we extend the problem to Q‐TAPF. Combined Target and Path Finding (TAPF) is an extension of MAPF where the destination of an agent is part of the optimisation problem. This has the potential to improve the quality of the result whilst reducing the runtime. While Q‐TAPF can show improvements of halving the execution time, it does not do so consistently.

OpenAccess:
PDF
(additional files)