提升 LaCAM 以实现可扩展的最终最优多智能体路径规划
通过改进 LaCAM * 的算法,本文提出了几种改进技术,以扩展多智能体路径规划算法 (MAPF),改进后的算法显著提高了解决方案的质量,进一步推动了 MAPF 算法的发展。
Aug, 2023
我们提出了一种新颖的完整算法用于多智能体路径规划 (LaCAM),LaCAM 使用两级搜索快速找到解决方案,即使有数百个代理也是如此,我们的全面实验表明,LaCAM 在各种情况下可与或优于最先进的 MAPF 子最优算法,涉及成功率,计划时间和成本总和解决方案的质量。
Nov, 2022
多智能体路径规划是将多个智能体从起点移动到目标点而无碰撞的问题,终身智能体路径规划通过不断为智能体分配新目标进一步扩展了多智能体路径规划。本文概述了三个主要的研究挑战,包括寻找在有限的规划时间内(例如,每步 1 秒)为大量智能体(例如,10,000 个)或极高智能体密度(例如,97.7%)搜索高质量的终身智能体路径规划(LMAPF)解决方案的挑战,缓解拥堵和短视行为在 LMAPF 算法中的影响的挑战,以及弥合文献中使用的 LMAPF 模型和实际应用之间的差距的挑战。
Apr, 2024
本文介绍了一种名为 Caching-Augmented Lifelong MAPF(CAL-MAPF)的新机制,用于改善 Lifelong MAPF 的性能,并通过实验证明了在某些任务分布、地图和代理配置下,CAL-MAPF 具备提升性能的潜力。
Mar, 2024
多智能体路径规划(Multi-Agent Path Finding)是机器人领域的一个基本问题,该研究提出了一种新方法来解决这个问题,该方法通过引导智能体按照避免拥堵的路径前往目的地,有效提高了解决方案质量,并在整体通量方面取得了显著改进。
Aug, 2023
在这项工作中,我们研究了分布式多智能体路径规划问题的设置,通过集成启发式搜索和强化学习方法,提出了一种解决复杂的问题的方法。我们的方法在广泛的设置中得到了验证,并且在吞吐量和泛化能力上表现优越,同时比现有的基于规则和基于搜索的解决方法快一个数量级。
Oct, 2023
该研究提出了一个基于 Multi-Agent Path Finding (MAPF) 的两层搜索的 MAPF-DP 解决方案,包括规划具有不完美执行计划的有效 MAPF-DP 解决方案,提出了具有鲁棒性的计划执行策略以控制每个代理的行动,展示了能够生成有效 MAPF-DP 计划的两层 MAPF-DP 求解器(称为期望值最小化近似)。
Dec, 2016
我们考虑投射在图上的匿名多智能体路径规划(AMAPF)问题,给定了一组目标顶点,每个顶点必须被某个智能体到达。本文针对寻找使得最短耗时的目标 - 智能体分配方案和无碰撞路径的问题,通过将其转化为特殊类型的图搜索问题,即在输入图引导下寻找最大流问题来求解。然后,我们提出了一种利用批量搜索状态的特定搜索算法,将搜索空间压缩、存储和扩展为单一状态,从而显著降低了运行时间和内存占用。实验证明,该 AMAPF 求解器在 30 秒内能够解决所有公开可用的来自知名 MovingAI 基准的 MAPF 实例,并表现出卓越的性能优势。
Dec, 2023
多智能体路径规划是解决一组智能体到达目标位置的无碰撞路径问题。先进的经典多智能体路径规划求解器通常采用启发式搜索方法以找到数百个智能体的解决方案,但通常是集中式的,而在短时间内可能难以扩展。机器学习方法学习每个智能体的策略非常吸引人,因为它们可以实现分散式系统,并在保持良好解决方案质量的同时具备良好的扩展性。我们的主要思想是,我们可以通过使用启发式搜索方法来改进机器学习的局部策略,以解决死锁和实现完全水平的规划。我们展示了几种无模型方法来使用带有学习策略的启发式搜索,这些方法显著提高了策略的成功率和可扩展性。据我们所知,我们首次证明了基于机器学习的多智能体路径规划方法在高拥塞场景(例如,20%智能体密度)中的可扩展性。
Mar, 2024
本文介绍了一种名为 HiMAP 的新型可扩展方法,应用了带启发式指导的模仿学习,并在分散化方式下进行训练,展示了在仅限于模仿学习的大规模多智能体路径规划领域能够取得竞争性的成功率和可扩展性结果,显示了模仿学习在路径规划领域的潜力。
Feb, 2024