MAPP: 一种具有可行性和完整性保证的可伸缩多智能体路径规划算法
该研究提出了一个基于Multi-Agent Path Finding (MAPF) 的两层搜索的MAPF-DP解决方案,包括规划具有不完美执行计划的有效MAPF-DP解决方案,提出了具有鲁棒性的计划执行策略以控制每个代理的行动,展示了能够生成有效MAPF-DP计划的两层MAPF-DP 求解器(称为期望值最小化近似)。
Dec, 2016
提出了一种基于Safe interval path planning (SIPP)和Conflict-based search (CBS)算法的多智能体路径规划 (Multi-Agent Pathfinding, MAPF) 方法,不依赖于网格、时间步长和动作的同时,并具有保证最优解的特点。对该算法进行了分析、讨论优劣,并在多项标准基准测试中进行了实验评估。
Jan, 2019
该论文旨在通过提供统一的术语来描述常见的MAPF假设和目标,并指向两个MAPF基准,介绍了一个新的基于网格的MAPF基准,并试验性地证明它对当代MAPF算法提出了挑战。
Jun, 2019
本文研究了在大型自动化仓库等场景下,智能体不断需要寻找新的目标点的长期多智能体路径规划问题。我们提出了一种新的解决方案,Rolling-Horizon Collision Resolution框架,通过将问题分解成一系列窗口MAPF实例来解决,其中窗口MAPF解决器仅在有限时间范围内解决智能体路径的冲突,并忽略其外的冲突。我们通过模拟仓库实例,经验性地评估了RHCR,并与各种MAPF解算器进行了比较,在多达1000个智能体的情况下(=地图上38.9%的空单元格),RHCR可以产生高质量的解决方案,显着优于现有工作。
May, 2020
本研究通过对二维网格中时间最优多智能体路径规划的细粒度复杂性分析,揭示了新的可解性界限,并在只有两个方向时,提出了找到最优解的有效算法,从而帮助指导算法设计。
May, 2023
通过改进LaCAM*的算法,本文提出了几种改进技术,以扩展多智能体路径规划算法(MAPF),改进后的算法显著提高了解决方案的质量,进一步推动了MAPF算法的发展。
Aug, 2023
多智能体路径规划(Multi-Agent Path Finding)是机器人领域的一个基本问题,该研究提出了一种新方法来解决这个问题,该方法通过引导智能体按照避免拥堵的路径前往目的地,有效提高了解决方案质量,并在整体通量方面取得了显著改进。
Aug, 2023
在这项工作中,我们研究了分布式多智能体路径规划问题的设置,通过集成启发式搜索和强化学习方法,提出了一种解决复杂的问题的方法。我们的方法在广泛的设置中得到了验证,并且在吞吐量和泛化能力上表现优越,同时比现有的基于规则和基于搜索的解决方法快一个数量级。
Oct, 2023
多智能体路径规划问题涉及为多个智能体在共享环境中规划无碰撞路径。本研究提出了一种名为双向时序计划图(BTPG)的新图形表示,允许在执行过程中切换传递顺序以避免不必要的等待时间,并设计了两种构建BTPG的随时算法:BTPG-naïve 和 BTPG-optimized。实验结果表明,跟随BTPG相对于跟随TPG能更好地节约时间,减少不必要的等待时间8-20%。
Dec, 2023
我们介绍了可扩展的多智能体路径规划的机制设计问题,并提出了三种不可否认策略的机制,其中两种甚至使用了近似的多智能体路径规划算法。我们在实际应用中测试了这些机制,问题规模从几十到数百个智能体。研究结果表明,与简单基准相比,它们可以提高整体效益。
Jan, 2024