该研究通过利用强化学习中用户定义的奖励函数来实现冲突搜索算法(CBS)和任务分配与路径规划,解决了具有优先和时间约束的任务分配与路径规划问题(TAPF-PTC)。通过实验证明,相对于 MARL 和适应性目标分配与路径规划(TAPF)方法,我们的算法 CBS-TA-PTC 有效地解决了具有优先和时间约束的高难度拆弹任务。
Feb, 2024
研究了已知地形中团队智能体的 TAPF(组合目标分配和路径查找)问题,提出了 CBM(基于冲突的最小成本流)算法,结合匿名和非匿名多智能体路径查找算法的思想,可用于处理各种规模的 TAPF 实例,并可适用于模拟仓库系统。
Dec, 2016
对现代算法的评估表明,针对多机器人系统的多智能体路径规划是解决自动仓库实现,火车调度和非完整机器人导航等多个应用领域重要方面的关键技术。
Jun, 2022
本文研究了多智能体取送问题的一个生命周期版本,提出了两种算法 Token Passing 与 Token Passing with Task Swaps,其中 TP 算法对于拥有数百个智能体和任务的 MAPD 实例仍然有效,可全面推广为全分布式 MAPD 算法,TPTS 需要少量智能体之间的通信,TP 算法适用于需要实时计算的情况,TPTS 算法则在 TP 算法与集中式 MAPD 算法之间做出了平衡。
May, 2017
通过提出高效的冲突引导方法,避免了计算下一个最佳分配时的瓶颈,以及引入两种算法优化来提高效率和可扩展性,研究表明该算法在实际场景中取得了近一个数量级的加速效果。
该论文旨在通过提供统一的术语来描述常见的 MAPF 假设和目标,并指向两个 MAPF 基准,介绍了一个新的基于网格的 MAPF 基准,并试验性地证明它对当代 MAPF 算法提出了挑战。
Jun, 2019
本文介绍了一种基于答案集编程的方法,用于解决涉及多模态转型模式的多智能体路径规划问题(mMAPF),并生成可解释性的解决方案、观察结果、最优路径以及不存在解决方案的查询。
Aug, 2020
本研究提出了一种名为 ITA-CBS 的增量目标指派 CBS 方法,该方法不需要计算 K 个最佳任务分配,只在搜索过程中增量计算新的最佳分配,有效避免了多个搜索树中的冲突,保证了最优解和计算效率。
Jul, 2023
本文介绍了一种新的 MAPF 扩展,称为 Terraforming MAPF(tMAPF),其中一些代理负责移动障碍以为其他代理清除道路。我们介绍了两种先进算法 CBS 和 PBS 的扩展来解决 tMAPF 问题,并表明它们无论在哪种静态障碍条件下都可以持续超过最佳解决方案。
Mar, 2022
我们考虑投射在图上的匿名多智能体路径规划(AMAPF)问题,给定了一组目标顶点,每个顶点必须被某个智能体到达。本文针对寻找使得最短耗时的目标 - 智能体分配方案和无碰撞路径的问题,通过将其转化为特殊类型的图搜索问题,即在输入图引导下寻找最大流问题来求解。然后,我们提出了一种利用批量搜索状态的特定搜索算法,将搜索空间压缩、存储和扩展为单一状态,从而显著降低了运行时间和内存占用。实验证明,该 AMAPF 求解器在 30 秒内能够解决所有公开可用的来自知名 MovingAI 基准的 MAPF 实例,并表现出卓越的性能优势。
Dec, 2023