Jul, 2015

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

PDF
TL;DR通过与网络流的等价性和整数线性规划，我们设计了用于解决四个不同目标的新颖和完整算法，从而解决了最佳多机器人路径规划问题。采用基于 ILP 算法模型和启发式算法的组合方法，能够在几秒钟内计算出包含数百个机器人，环境密集的问题的 1.x - 最优解。
multi-robot path planningoptimization objectivesnetwork-flowinteger linear programmingheuristics
发现论文，激发创造
  • 在图上为多个机器人规划最优路径

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

    Apr, 2012

  • 混合整数规划与高效启发式算法的多机器人时间最优覆盖路径规划

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

    Jun, 2023

  • 多智能体路径规划与网络流

    通过将基于图的多智能体路径规划与网络流问题相连接，本文研究表明前者可以归纳为后者，进而实现了组合网络流算法及一般线性规划技术应用于基于图的多智能体路径规划问题。此外，在研究中我们还证明了当目标具有排列不变性的情况下，问题仅有一个可行解路径集，该集合具有不超过 $n+V-1$ 的最大完成时间，并提供了一个完整的算法以在 $O (nVE)$ 时间内找到这样的解决方案。最后，我们研究了可行解的时间和距离优化，表明它们具有成对帕累托优化结构，并提供了优化这两个实际目标的有效算法。

    Apr, 2012

  • 基于图的多机器人路径规划

    对现代算法的评估表明，针对多机器人系统的多智能体路径规划是解决自动仓库实现，火车调度和非完整机器人导航等多个应用领域重要方面的关键技术。

    Jun, 2022

  • DDM：使用多样化路径和最优子问题解数据库启发式算法的快速近似多机器人路径规划

    提出了一种新颖的中央分离式算法，通过利用路径分化和最优子问题解决数据库来解决多机器人路径规划问题，从而实现高效的解决路径冲突，并在大规模、动态环境中取得高水平的解决方案优化。

    Apr, 2019

  • 多机器人系统冲突感知的最优目标分配算法

    通过提出高效的冲突引导方法，避免了计算下一个最佳分配时的瓶颈，以及引入两种算法优化来提高效率和可扩展性，研究表明该算法在实际场景中取得了近一个数量级的加速效果。

    Feb, 2024

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

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

    Dec, 2023

  • 结合启发式和多智体强化学习的多机器人路径规划

    提出了一种结合启发式搜索、经验法则和多智能体强化学习的路径规划方法 MAPPOHR，将启发式搜索用于生成全局路径，用经验法则和奖励函数激励实时规划器，用多智能体强化学习算法实现实时规划，实验证明该方法比传统学习和启发式方法的规划性能更好且学习效率更高。

    Jun, 2023

  • 多机器人路径规划中的子图结构利用

    本文提出两种机器人路径规划算法：抽象化方法和优先级计划算法，证明了前者的完备性和正确性，并演示了将它们组合起来的单一算法的实际效果。

    Oct, 2011

  • 基于超图的多机器人任务和运动规划

    该研究提出一种基于超图的多机器人任务和动作规划方法，将规划空间分解为互相独立的空间子集，使得规划时间相对于已有方法加速了三个数量级，并且展现了该方法在其他多机器人任务和动作规划问题上的有效性。

    Oct, 2022