本研究通过对二维网格中时间最优多智能体路径规划的细粒度复杂性分析,揭示了新的可解性界限,并在只有两个方向时,提出了找到最优解的有效算法,从而帮助指导算法设计。
May, 2023
在多智能体路径规划问题中,我们通过参数化复杂性框架提出了系统研究,给出了问题的难度结果和固定参数可解性结果。
Dec, 2023
该研究提出了一个基于 Multi-Agent Path Finding (MAPF) 的两层搜索的 MAPF-DP 解决方案,包括规划具有不完美执行计划的有效 MAPF-DP 解决方案,提出了具有鲁棒性的计划执行策略以控制每个代理的行动,展示了能够生成有效 MAPF-DP 计划的两层 MAPF-DP 求解器(称为期望值最小化近似)。
Dec, 2016
通过提出两种最优算法,基于减少 MAPF-DL 的流问题和后续抽象的多种商品流网络的紧凑整数线性规划和基于新的组合搜索算法,我们正式规范具有截止日期的多智能体路径规划问题。
Jun, 2018
我们考虑投射在图上的匿名多智能体路径规划(AMAPF)问题,给定了一组目标顶点,每个顶点必须被某个智能体到达。本文针对寻找使得最短耗时的目标 - 智能体分配方案和无碰撞路径的问题,通过将其转化为特殊类型的图搜索问题,即在输入图引导下寻找最大流问题来求解。然后,我们提出了一种利用批量搜索状态的特定搜索算法,将搜索空间压缩、存储和扩展为单一状态,从而显著降低了运行时间和内存占用。实验证明,该 AMAPF 求解器在 30 秒内能够解决所有公开可用的来自知名 MovingAI 基准的 MAPF 实例,并表现出卓越的性能优势。
多智能体路径规划是将多个智能体从起点移动到目标点而无碰撞的问题,终身智能体路径规划通过不断为智能体分配新目标进一步扩展了多智能体路径规划。本文概述了三个主要的研究挑战,包括寻找在有限的规划时间内(例如,每步 1 秒)为大量智能体(例如,10,000 个)或极高智能体密度(例如,97.7%)搜索高质量的终身智能体路径规划(LMAPF)解决方案的挑战,缓解拥堵和短视行为在 LMAPF 算法中的影响的挑战,以及弥合文献中使用的 LMAPF 模型和实际应用之间的差距的挑战。
Apr, 2024
讨论多智能体路径规划在现实世界场景中通用的问题和四个 解决方向,并强调解决这些问题的重要性,反对仅仅开 发更快的标准 MAPF 问题求解方法。
Feb, 2017
本文提出了一种名为 SocialMAPF 的路径规划算法,该算法适用于考虑代理人个体私人的激励因素的约束环境。我们使用机制设计提高了个体的私人效用和全局系统目标,从而使得机器人能够在考虑到自身私人激励情况下达到更高的整体效用。实验表明,这种算法比传统方法更加高效,而且机制设计算法还能应用于静态环境中,具有很高的研究价值。
Oct, 2022
我们介绍了可扩展的多智能体路径规划的机制设计问题,并提出了三种不可否认策略的机制,其中两种甚至使用了近似的多智能体路径规划算法。我们在实际应用中测试了这些机制,问题规模从几十到数百个智能体。研究结果表明,与简单基准相比,它们可以提高整体效益。
Jan, 2024
多智能体路径规划(Multi-Agent Path Finding)是机器人领域的一个基本问题,该研究提出了一种新方法来解决这个问题,该方法通过引导智能体按照避免拥堵的路径前往目的地,有效提高了解决方案质量,并在整体通量方面取得了显著改进。
Aug, 2023