AAAIDec, 2023

大规模多机器人覆盖路径规划中的局部搜索

PDF
TL;DR我们研究基于图的多机器人覆盖路径规划 (MCPP)，旨在计算多个机器人覆盖给定 2D 网格图 $G$ 的所有顶点的路径。我们提出了一种新的算法框架 LS-MCPP，利用局部搜索直接在图 $D$ 上操作，通过扩展 STC 实现 MCPP 在任何分解图上的完全覆盖，并结合三种新颖的邻域操作符来引导搜索过程。我们的实验结果表明，LS-MCPP 在优化 makespan 方面显著优于现有算法，并且在运行时间方面具有数量级的优势，对于大规模实际覆盖任务具有重要的好处。
multi-robot coverage path planninggraph-based mcppls-mcppextended-stcmakespan optimization
发现论文，激发创造
  • 混合整数规划与高效启发式算法的多机器人时间最优覆盖路径规划

    本研究采用混合整数规划和启发式算法对多机器人覆盖路径规划进行优化，其中包括两种减少规模的启发式算法，通过实验证明，相比现有算法，本研究提出的方法可以显著降低路径覆盖时间。

    Jun, 2023

  • 平面覆盖任务中工作站多机器人系统协同学习

    本文提出了一种基于多机器人系统、强化学习与分布式规划相结合的方法，用于解决多机器人覆盖路径规划问题，并成功减少环境中随机干扰物的影响和避免碰撞，实现了任务完成时间的优化。

    Aug, 2022

  • 多机器人连接费马螺线覆盖

    我们介绍了 Multi-Robot Connected Fermat Spiral（MCFS），这是一个新颖的算法框架，用于多机器人覆盖路径规划（MCPP），它将来自计算机图形学界的 Connected Fermat Spiral（CFS）首次应用于多机器人协调。MCFS 独特地实现了多个机器人编排生成环绕任意形状障碍物的覆盖路径，这是传统方法明显缺乏的功能。我们的框架不仅增强了面积覆盖和任务性能优化，特别是在充满不规则障碍物的工作空间中的完成时间方面，而且通过生成连续平滑的路径而解决了非完整机器人的路径连续性和曲率的挑战，而无需对工作空间进行分解。MCFS 通过构造等值线图并将 MCPP 转换为组合优化问题来解决 MCPP，旨在最小化完成时间同时覆盖所有顶点。我们的贡献包括开发了可扩展且适应性强的 MCPP 统一 CFS 版本，通过优化技术降低成本并保持路径的连续性和平滑性，通过广泛的实验证明 MCFS 在完成时间、路径曲率、覆盖比率和重叠比率方面优于现有的 MCPP 方法。我们的研究在 MCPP 方面迈出了重要的一步，展示了计算机图形学和自动规划原理的融合，以推动多机器人系统在复杂环境中的能力。我们的代码可在此 https URL 找到。

    Mar, 2024

  • 多目标覆盖路径规划：实现复杂实际结构的自动化检测

    使用多目标演化算法，在保证能量使用和覆盖率平衡的同时，规划机器人的路径，实现复杂三维结构的检测。

    Jan, 2019

  • 在线并发多机器人覆盖路径规划

    提出一种非基于时间限制的集中式算法，可以实现并发规划和执行，从而在大规模工作区中完成完整覆盖，无需浪费机器人和计算资源。

    Mar, 2024

  • 基于图形的多机器人最优路径规划：完整算法和有效的启发式算法

    通过与网络流的等价性和整数线性规划，我们设计了用于解决四个不同目标的新颖和完整算法，从而解决了最佳多机器人路径规划问题。采用基于 ILP 算法模型和启发式算法的组合方法，能够在几秒钟内计算出包含数百个机器人，环境密集的问题的 1.x - 最优解。

    Jul, 2015

  • 在连续空间中可扩展的多机器人路径规划的安全间隔 RRT*

    在本文中，我们考虑了连续空间下的多机器人路径规划（Multi-Robot Path Planning，MRPP）问题，以找到无冲突的路径。为此，我们提出了一个两级方法，其中低级是一个基于采样的规划器 Safe Interval RRT*（SI-RRT*），用于找到单个机器人的无碰撞轨迹。高级方法可以使用任何能够解决机器人间冲突的方法，我们采用了两种代表性方法，即优先级规划（SI-CPP）和基于冲突搜索（SI-CCBS）。实验结果表明，SI-RRT * 能够快速找到高质量解，且样本数量较少。SI-CPP 在可扩展性方面表现较好，而 SI-CCBS 相对于现有的连续空间规划器而言，能够产生更高质量的解。与最具可扩展性的现有算法相比，SI-CPP 在保持解质量的同时，成功率提高了多达 94%，并且不会造成显著妥协。SI-CPP 还能够将完成时间缩短 45%。SI-CCBS 相对于竞争对手，将完成时间减少了 9%，尽管成功率降低了 14%。

    Apr, 2024

  • 在图上为多个机器人规划最优路径

    本文研究基于图的多机器人路径规划问题，提出两种多流基于整数线性规划算法，计算最小到达时间和最小总距离的解决方案，其算法性能表现得到评估，并能够适应其他 MPP 问题变体。

    Apr, 2012

  • 多代理路径规划的蒙特卡洛树搜索：初步结果

    研究了多智能体路径规划中如何利用蒙特卡洛树搜索（Monte-Carlo Tree Search）解决问题，提出了一种适用于多智能体路径规划的改进 MCTS 变种，通过计算个体路径和奖励来指导搜索过程，实验证明该方法优于基线规划算法。

    Jul, 2023

  • 利用深度强化学习进行变化功率限制下的无人机覆盖路径规划

    本文提出了一种新方法，利用端到端强化学习通过地图通道提供空间信息并使用 DDQN 平衡有限电力预算和无人机的航程，以控制在一些禁飞区域有随机起飞位置和多个降落选项的环境中的无人机 CNN 航迹规划任务，此方法可以应用于各种环境且很好地协调了复杂的系统约束与目标结构。

    Mar, 2020