Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction

doi:10.1109/TRO.2025.3567476

2025-01-01

PRE

Jingtao Tang

Z. Morley Mao

Hang Ma

DOI：10.1109/TRO.2025.3567476

原文链接

原文求助

摘要

En 中文

本文研究了四邻接二维网格上的多机器人覆盖路径规划（MCPP），其目的是为多个机器人计算覆盖网格中所有单元格的路径。传统方法因其首先在象限粗化网格上计算覆盖树，然后采用生成树覆盖（STC）范式在上生成路径，因此无法应用于包含部分阻塞块的网格。为解决此限制，我们直接在上重新表述问题，革新了基于网格的MCPP求解并建立了新的NP困难性结果。我们引入了扩展STC（ESTC），一种将STC扩展以确保在包含部分阻塞块时仍能实现完全覆盖且具有有界次优性的新范式。此外，我们提出了LS-MCPP，一种将ESTC与局部搜索策略中的三种新型邻域算子相结合的新型算法框架，以直接在上优化覆盖路径。与以往的基于网格的MCPP工作不同，我们的方法还整合了一种通用的后处理程序，首次将多智能体路径查找（MAPF）技术应用于MCPP，实现了这两个多机器人协调领域的重要融合。该程序通过求解MAPF变体有效解决机器人间的冲突并考虑转向成本，使我们的MCPP解决方案更适合实际应用。大量实验表明，我们的方法显著提高了解的质量和效率，可在几分钟内管理多达100个机器人在大小的网格上的运行。物理机器人的验证确认了在实际条件下我们解决方案的可行性。

Keyword:

Automated planning

heuristic search

multirobot system