面向终身多智能体路径规划的公路研究
多智能体路径规划(Multi-Agent Path Finding)是机器人领域的一个基本问题,该研究提出了一种新方法来解决这个问题,该方法通过引导智能体按照避免拥堵的路径前往目的地,有效提高了解决方案质量,并在整体通量方面取得了显著改进。
Aug, 2023
本文研究了在大型自动化仓库等场景下,智能体不断需要寻找新的目标点的长期多智能体路径规划问题。我们提出了一种新的解决方案,Rolling-Horizon Collision Resolution 框架,通过将问题分解成一系列窗口 MAPF 实例来解决,其中窗口 MAPF 解决器仅在有限时间范围内解决智能体路径的冲突,并忽略其外的冲突。我们通过模拟仓库实例,经验性地评估了 RHCR,并与各种 MAPF 解算器进行了比较,在多达 1000 个智能体的情况下(= 地图上 38.9%的空单元格),RHCR 可以产生高质量的解决方案,显着优于现有工作。
May, 2020
多智能体路径规划是将多个智能体从起点移动到目标点而无碰撞的问题,终身智能体路径规划通过不断为智能体分配新目标进一步扩展了多智能体路径规划。本文概述了三个主要的研究挑战,包括寻找在有限的规划时间内(例如,每步 1 秒)为大量智能体(例如,10,000 个)或极高智能体密度(例如,97.7%)搜索高质量的终身智能体路径规划(LMAPF)解决方案的挑战,缓解拥堵和短视行为在 LMAPF 算法中的影响的挑战,以及弥合文献中使用的 LMAPF 模型和实际应用之间的差距的挑战。
Apr, 2024
本文介绍了一种名为 Caching-Augmented Lifelong MAPF(CAL-MAPF)的新机制,用于改善 Lifelong MAPF 的性能,并通过实验证明了在某些任务分布、地图和代理配置下,CAL-MAPF 具备提升性能的潜力。
Mar, 2024
在这项工作中,我们研究了分布式多智能体路径规划问题的设置,通过集成启发式搜索和强化学习方法,提出了一种解决复杂的问题的方法。我们的方法在广泛的设置中得到了验证,并且在吞吐量和泛化能力上表现优越,同时比现有的基于规则和基于搜索的解决方法快一个数量级。
Oct, 2023
本文介绍了一种多机器人路径规划算法的新方法 exRHCR,该算法利用先前任务的解决方案来加速新的任务的解决,实验表明,exRHCR 相对于 RHCR 的解决速度提高了 39%,可以在给定时间预算内处理更多的机器人,从而提高了系统的吞吐量。
Feb, 2022
该论文旨在通过提供统一的术语来描述常见的 MAPF 假设和目标,并指向两个 MAPF 基准,介绍了一个新的基于网格的 MAPF 基准,并试验性地证明它对当代 MAPF 算法提出了挑战。
Jun, 2019
本文研究了多智能体取送问题的一个生命周期版本,提出了两种算法 Token Passing 与 Token Passing with Task Swaps,其中 TP 算法对于拥有数百个智能体和任务的 MAPD 实例仍然有效,可全面推广为全分布式 MAPD 算法,TPTS 需要少量智能体之间的通信,TP 算法适用于需要实时计算的情况,TPTS 算法则在 TP 算法与集中式 MAPD 算法之间做出了平衡。
May, 2017
多智能体路径规划是解决一组智能体到达目标位置的无碰撞路径问题。先进的经典多智能体路径规划求解器通常采用启发式搜索方法以找到数百个智能体的解决方案,但通常是集中式的,而在短时间内可能难以扩展。机器学习方法学习每个智能体的策略非常吸引人,因为它们可以实现分散式系统,并在保持良好解决方案质量的同时具备良好的扩展性。我们的主要思想是,我们可以通过使用启发式搜索方法来改进机器学习的局部策略,以解决死锁和实现完全水平的规划。我们展示了几种无模型方法来使用带有学习策略的启发式搜索,这些方法显著提高了策略的成功率和可扩展性。据我们所知,我们首次证明了基于机器学习的多智能体路径规划方法在高拥塞场景(例如,20%智能体密度)中的可扩展性。
Mar, 2024
提出了一种基于 Safe interval path planning (SIPP) 和 Conflict-based search (CBS) 算法的多智能体路径规划 (Multi-Agent Pathfinding, MAPF) 方法,不依赖于网格、时间步长和动作的同时,并具有保证最优解的特点。对该算法进行了分析、讨论优劣,并在多项标准基准测试中进行了实验评估。
Jan, 2019