连续时间冲突基于搜索的团分析与绕行
本文提出了在连续时间领域使用 prioritizing conflicts(PC)、disjoint splitting(DS)、high-level heuristics 等算法来扩展 CSB 算法,以在无需离散化时间的情况下保证最优解。作者通过实验证明,这些改进显著优于原始 CCBS 算法,解决了更多智能体问题,并推动了在连续时间领域中的多智能体路径规划的极限。
Jan, 2021
本文介绍了多机器人路径规划问题中考虑异常情况的 k-Robust Conflict-Based Search 算法,以及引入对 k-robust 规划特定的对称性约束可以有效地找到冲突代理的兼容和最优路径,在多个领域中的应用效果较好,包括传统的 MAPF 基准测试,自动化仓库领域和最近推出 Flatland 挑战的铁路领域。
Feb, 2021
多智能体路径规划中的任意角路径规划问题,利用连续冲突搜索算法和安全区间路径规划算法的最优算法及其可行解空间分割和多约束技术,能解决比传统组合更多的问题。
Apr, 2024
本文提出了两种新的拆分策略 (cost splitting 和 disjoint cost splitting),用于解决 Multi-Objective Conflict-Based Search (MO-CBS) 算法中的重复搜索问题,并证明了这些拆分策略与 MO-CBS 既完整又最优。实验结果表明,disjoint cost splitting 是最佳的拆分策略,可将 MO-CBS 加速两个数量级并在各种情景下显著提高其成功率。
Nov, 2022
本研究针对 CBS 算法的优化问题,设计并测试了多种不同的改进方式;研究结果表明,在多种情形下使用基于 Focal Search 的 anytime variant 算法优于传统的 CBS 算法。
Sep, 2022
本文针对多智能体路径规划中的对称性问题,提出了一种通过推理技术解决对称性问题的方法,并将其应用于 CBS 算法,实现了在性能和效率方面的显著提升。
Mar, 2021
提出了一种基于 Safe interval path planning (SIPP) 和 Conflict-based search (CBS) 算法的多智能体路径规划 (Multi-Agent Pathfinding, MAPF) 方法,不依赖于网格、时间步长和动作的同时,并具有保证最优解的特点。对该算法进行了分析、讨论优劣,并在多项标准基准测试中进行了实验评估。
Jan, 2019
我们提出了基于目标安全区间访问顺序搜索和单智能体路径规划的多目标冲突搜索(MGCBS)方法,并介绍了时间 - 间隔 - 空间森林(TIS Forest)来增强 MGCBS 的效率。实验证明,我们的方法始终能够获得最优结果,并在评估中执行速度比最新的方法快 7 倍。
Apr, 2024
通过基于在线学习的 inadmissible 估计和 EES 算法,在研究现有的 bounded-suboptimal MAPF 算法的基础上,提出一种新的 bounded-suboptimal 算法 EECBS,相较于 ECBS,BCP-7 和 eMDD-SAT 等先进算法,在运行时间上表现更快,希望其可推广到更多 bounded-suboptimal MAPF 算法的应用中。
Oct, 2020