多智能体路径规划的启发式编译
多智能体路径规划是解决一组智能体到达目标位置的无碰撞路径问题。先进的经典多智能体路径规划求解器通常采用启发式搜索方法以找到数百个智能体的解决方案,但通常是集中式的,而在短时间内可能难以扩展。机器学习方法学习每个智能体的策略非常吸引人,因为它们可以实现分散式系统,并在保持良好解决方案质量的同时具备良好的扩展性。我们的主要思想是,我们可以通过使用启发式搜索方法来改进机器学习的局部策略,以解决死锁和实现完全水平的规划。我们展示了几种无模型方法来使用带有学习策略的启发式搜索,这些方法显著提高了策略的成功率和可扩展性。据我们所知,我们首次证明了基于机器学习的多智能体路径规划方法在高拥塞场景(例如,20%智能体密度)中的可扩展性。
Mar, 2024
本文介绍了一种基于答案集编程的方法,用于解决涉及多模态转型模式的多智能体路径规划问题(mMAPF),并生成可解释性的解决方案、观察结果、最优路径以及不存在解决方案的查询。
Aug, 2020
该论文旨在通过提供统一的术语来描述常见的 MAPF 假设和目标,并指向两个 MAPF 基准,介绍了一个新的基于网格的 MAPF 基准,并试验性地证明它对当代 MAPF 算法提出了挑战。
Jun, 2019
在这项工作中,我们研究了分布式多智能体路径规划问题的设置,通过集成启发式搜索和强化学习方法,提出了一种解决复杂的问题的方法。我们的方法在广泛的设置中得到了验证,并且在吞吐量和泛化能力上表现优越,同时比现有的基于规则和基于搜索的解决方法快一个数量级。
Oct, 2023
提出了一种基于 Safe interval path planning (SIPP) 和 Conflict-based search (CBS) 算法的多智能体路径规划 (Multi-Agent Pathfinding, MAPF) 方法,不依赖于网格、时间步长和动作的同时,并具有保证最优解的特点。对该算法进行了分析、讨论优劣,并在多项标准基准测试中进行了实验评估。
Jan, 2019
该研究提出了一个基于 Multi-Agent Path Finding (MAPF) 的两层搜索的 MAPF-DP 解决方案,包括规划具有不完美执行计划的有效 MAPF-DP 解决方案,提出了具有鲁棒性的计划执行策略以控制每个代理的行动,展示了能够生成有效 MAPF-DP 计划的两层 MAPF-DP 求解器(称为期望值最小化近似)。
Dec, 2016
多智能体路径规划(Multi-Agent Path Finding)是机器人领域的一个基本问题,该研究提出了一种新方法来解决这个问题,该方法通过引导智能体按照避免拥堵的路径前往目的地,有效提高了解决方案质量,并在整体通量方面取得了显著改进。
Aug, 2023
我们提出了一种基于分布式多智能体蒙特卡罗树搜索方法的多智能体路径规划算法,通过利用智能体的观察结果重新创建内在的马尔科夫决策过程,并结合针对多智能体任务的定制化神经蒙特卡罗树搜索算法进行路径规划,实验证明该方法优于现有的学习型多智能体路径规划器。
Dec, 2023
本文旨在引入一组方法和可视化工具,以帮助 MAPF 社区建立最新 MAPF 性能的清晰指标,并促进 MAPF 求解器之间的大规模比较,以降低新研究人员进入门槛,并进一步推动 MAPF 研究,以便更清楚地了解该领域的进展和主要挑战。
May, 2023