团队 Agent 的最优目标分配和路径规划
本研究从理论和算法两个角度对多目标任务分配和路径规划问题(MG-TAPF)进行了建模和研究,并提出了算法建立在多智能体路径规划问题上,在各种基准领域上对算法进行了实验比较。
Aug, 2022
本研究提出了一种名为 ITA-CBS 的增量目标指派 CBS 方法,该方法不需要计算 K 个最佳任务分配,只在搜索过程中增量计算新的最佳分配,有效避免了多个搜索树中的冲突,保证了最优解和计算效率。
Jul, 2023
该研究通过利用强化学习中用户定义的奖励函数来实现冲突搜索算法(CBS)和任务分配与路径规划,解决了具有优先和时间约束的任务分配与路径规划问题(TAPF-PTC)。通过实验证明,相对于 MARL 和适应性目标分配与路径规划(TAPF)方法,我们的算法 CBS-TA-PTC 有效地解决了具有优先和时间约束的高难度拆弹任务。
Feb, 2024
我们考虑投射在图上的匿名多智能体路径规划(AMAPF)问题,给定了一组目标顶点,每个顶点必须被某个智能体到达。本文针对寻找使得最短耗时的目标 - 智能体分配方案和无碰撞路径的问题,通过将其转化为特殊类型的图搜索问题,即在输入图引导下寻找最大流问题来求解。然后,我们提出了一种利用批量搜索状态的特定搜索算法,将搜索空间压缩、存储和扩展为单一状态,从而显著降低了运行时间和内存占用。实验证明,该 AMAPF 求解器在 30 秒内能够解决所有公开可用的来自知名 MovingAI 基准的 MAPF 实例,并表现出卓越的性能优势。
Dec, 2023
多智能体路径规划 (MAPF) 的一个变种是综合目标分配和路径规划 (TAPF) 问题,本文引入了 ITA-ECBS 作为 ITA-CBS 的边界次优变体,并采用聚焦搜索和基于新的下界矩阵确定目标分配,经测试在 54,033 个案例中表现出优于基线方法 ECBS-TA 的结果占据了 87.42%。
Apr, 2024
本文介绍了一种新的 MAPF 扩展,称为 Terraforming MAPF(tMAPF),其中一些代理负责移动障碍以为其他代理清除道路。我们介绍了两种先进算法 CBS 和 PBS 的扩展来解决 tMAPF 问题,并表明它们无论在哪种静态障碍条件下都可以持续超过最佳解决方案。
Mar, 2022
提出了一种基于 Safe interval path planning (SIPP) 和 Conflict-based search (CBS) 算法的多智能体路径规划 (Multi-Agent Pathfinding, MAPF) 方法,不依赖于网格、时间步长和动作的同时,并具有保证最优解的特点。对该算法进行了分析、讨论优劣,并在多项标准基准测试中进行了实验评估。
Jan, 2019
多智能体路径规划(Multi-Agent Path Finding)是机器人领域的一个基本问题,该研究提出了一种新方法来解决这个问题,该方法通过引导智能体按照避免拥堵的路径前往目的地,有效提高了解决方案质量,并在整体通量方面取得了显著改进。
Aug, 2023
本文提出了一种 Precedence Constrained Conflict Based Search (PC-CBS) 算法,用于解决 Precedence Constrained Multi-Agent Path Finding (PC-MAPF) 问题,算法在仓库装配和多智能体取送货问题中表现优异。
Feb, 2022