h1

TY  - THES
AU  - Meiser, Dominic Sebastian
TI  - Multi‐agent path finding for reversible conveyors
PB  - RWTH Aachen University
VL  - Masterarbeit
CY  - Aachen
M1  - RWTH-2025-10004
SP  - 1 Online-Ressource : Illustrationen
PY  - 2025
N1  - Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
N1  - Masterarbeit, RWTH Aachen University, 2025
AB  - 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.
LB  - PUB:(DE-HGF)19
DO  - DOI:10.18154/RWTH-2025-10004
UR  - https://publications.rwth-aachen.de/record/1022411
ER  -