Apr, 2012

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

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

    本研究通过对二维网格中时间最优多智能体路径规划的细粒度复杂性分析，揭示了新的可解性界限，并在只有两个方向时，提出了找到最优解的有效算法，从而帮助指导算法设计。

    May, 2023

  • 交通流优化对于终生多智能体路径规划

    多智能体路径规划（Multi-Agent Path Finding）是机器人领域的一个基本问题，该研究提出了一种新方法来解决这个问题，该方法通过引导智能体按照避免拥堵的路径前往目的地，有效提高了解决方案质量，并在整体通量方面取得了显著改进。

    Aug, 2023

  • 带有截止日期的多智能体路径规划

    通过提出两种最优算法，基于减少 MAPF-DL 的流问题和后续抽象的多种商品流网络的紧凑整数线性规划和基于新的组合搜索算法，我们正式规范具有截止日期的多智能体路径规划问题。

    Jun, 2018

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

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

    Jul, 2015

  • 改进的匿名多智能体路径规划算法

    我们考虑投射在图上的匿名多智能体路径规划（AMAPF）问题，给定了一组目标顶点，每个顶点必须被某个智能体到达。本文针对寻找使得最短耗时的目标 - 智能体分配方案和无碰撞路径的问题，通过将其转化为特殊类型的图搜索问题，即在输入图引导下寻找最大流问题来求解。然后，我们提出了一种利用批量搜索状态的特定搜索算法，将搜索空间压缩、存储和扩展为单一状态，从而显著降低了运行时间和内存占用。实验证明，该 AMAPF 求解器在 30 秒内能够解决所有公开可用的来自知名 MovingAI 基准的 MAPF 实例，并表现出卓越的性能优势。

    Dec, 2023

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

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

    Apr, 2012

  • 多智能体路径规划的精确算法和下界：树状拓扑的威力

    在多智能体路径规划问题中，我们通过参数化复杂性框架提出了系统研究，给出了问题的难度结果和固定参数可解性结果。

    Dec, 2023

  • 多智能体路由价值迭代网络

    本文提出了一种多智能体坐标线路图的图神经网络模型，利用学习价值迭代在稀疏相互连接图中执行坐标线路图，并通过通信模块使智能体在线协调并更有效地适应变化，可以应用于自主车辆中实现实时映射和车队管理等。

    Jul, 2020

  • 学习跟随：基于规划和学习的去中心化多智能体路径规划

    在这项工作中，我们研究了分布式多智能体路径规划问题的设置，通过集成启发式搜索和强化学习方法，提出了一种解决复杂的问题的方法。我们的方法在广泛的设置中得到了验证，并且在吞吐量和泛化能力上表现优越，同时比现有的基于规则和基于搜索的解决方法快一个数量级。

    Oct, 2023

  • 容错离线多智能体路径规划

    本文研究了多智能体的新颖图路径规划问题，旨在通过离线规划解决智能体之间的碰撞和死锁问题，使得所有正确的智能体能够到达目的地，从而建立可靠的多机器人系统。

    Nov, 2022