A Quantum Computing Approach for Multi-robot Coverage Path Planning

本文研究了多车覆盖路径规划（CPP）问题，该问题对于搜索和救援或环境监测等应用至关重要。由于其NP-hard的性质，随着问题规模的增大，寻找最优解变得不可行。这促使我们开发启发式方法，即使在效率方面略微提高也能提高效率。我们提出了一种新的方法，用于在2D网格中探索路径，专门设计用于与量子交替算子Ansatz（QAOA）轻松集成的。我们的贡献包括：1）针对使用QAOA解决多车CPP的目标函数。2）理论证明保证所提出方法的有效性。3）有效构建QAOA算子以进行实际实现。4）资源估计以评估执行QAOA的可行性。5）与已建立的算法（如深度优先搜索）进行性能比较。这项工作为利用量子计算优化多车路径规划铺平了道路，有可能在各种应用中带来现实世界的进展。

本文旨在解决多车辆覆盖路径规划问题，这在搜索和救援或环境监测等应用中非常重要。由于其NP-hard的性质，对于更大的问题规模，找到最优解变得不可行。这促使开发启发式方法，即使在效率上稍微提高也是有意义的。

本文提出了一种新的方法，用于在二维网格中探索路径，特别是为了与量子交替算子Ansatz（QAOA）轻松集成而设计。我们的贡献包括：1）针对使用QAOA解决多车辆CPP的目标函数。2）理论证明保证了所提出方法的有效性。3）有效构建QAOA算子以进行实际实现。4）资源评估以评估QAOA执行的可行性。5）与已建立的算法（如深度优先搜索）进行性能比较。

本文为利用量子计算优化多车辆路径规划铺平了道路，潜在地导致各种应用领域的现实进展。实验设计了一个目标函数，理论证明了方法的有效性，实现了QAOA算子的有效构建，评估了QAOA执行的资源需求，并与现有算法进行了性能比较。

最近在这个领域中，还有一些相关的研究，如《A Survey of Coverage Path Planning》、《Multi-robot coverage path planning: A survey》等。