Nov, 2022

多目标冲突搜索的成本分担

PDF
TL;DR本文提出了两种新的拆分策略 (cost splitting 和 disjoint cost splitting)，用于解决 Multi-Objective Conflict-Based Search (MO-CBS) 算法中的重复搜索问题，并证明了这些拆分策略与 MO-CBS 既完整又最优。实验结果表明，disjoint cost splitting 是最佳的拆分策略，可将 MO-CBS 加速两个数量级并在各种情景下显著提高其成功率。
multi-objective multi-agent path findingmo-mapfmulti-objective conflict-based searchsplitting strategiesoptimality guarantees
发现论文，激发创造
  • 基于冲突的可解释多智能体路径规划搜索

    本文利用冲突基础搜索算法处理可解释多智能体路径规划问题，并探讨了计划时间与可解释性之间的权衡。

    Feb, 2022

  • k - 强韧多智能体路径规划中的对称性破缺

    本文介绍了多机器人路径规划问题中考虑异常情况的 k-Robust Conflict-Based Search 算法，以及引入对 k-robust 规划特定的对称性约束可以有效地找到冲突代理的兼容和最优路径，在多个领域中的应用效果较好，包括传统的 MAPF 基准测试，自动化仓库领域和最近推出 Flatland 挑战的铁路领域。

    Feb, 2021

  • 优化先决约束计划任务的多智能体路径规划

    本文提出了一种 Precedence Constrained Conflict Based Search (PC-CBS) 算法，用于解决 Precedence Constrained Multi-Agent Path Finding (PC-MAPF) 问题，算法在仓库装配和多智能体取送货问题中表现优异。

    Feb, 2022

  • 连续时间冲突基于搜索的团分析与绕行

    研究对连续时间多智能体路径规划问题的对称性打破增强方法以及连续时间冲突基于搜索的求解器，并且通过实证研究证明这些增强方法在密集图中比以往的最新技术在相同时间内解决多达 10% 或 20% 更多智能体问题上有统计显著性的性能提升。

    Dec, 2023

  • 子优化 CBS 中加权代价函数和冲突启发式的有效融合

    本文研究了多智能体路径规划中的 Conflict-Based Search 算法，证明了权重 cost-to-go 和冲突启发式算法可以被用于低级规划器，旨在提高算法效率和解决冲突问题。此外，该文章进一步表明算法性能与高低级之间的权衡有关，对现有算法进行了优化。

    May, 2022

  • 最优和有界次优的任意角度多智能体路径规划

    多智能体路径规划中的任意角路径规划问题，利用连续冲突搜索算法和安全区间路径规划算法的最优算法及其可行解空间分割和多约束技术，能解决比传统组合更多的问题。

    Apr, 2024

  • MGCBS: 解决多目标多智能体路径规划问题的最优高效算法

    我们提出了基于目标安全区间访问顺序搜索和单智能体路径规划的多目标冲突搜索（MGCBS）方法，并介绍了时间 - 间隔 - 空间森林（TIS Forest）来增强 MGCBS 的效率。实验证明，我们的方法始终能够获得最优结果，并在评估中执行速度比最新的方法快 7 倍。

    Apr, 2024

  • 改进连续时间的冲突搜索算法

    本文提出了在连续时间领域使用 prioritizing conflicts（PC）、disjoint splitting（DS）、high-level heuristics 等算法来扩展 CSB 算法，以在无需离散化时间的情况下保证最优解。作者通过实验证明，这些改进显著优于原始 CCBS 算法，解决了更多智能体问题，并推动了在连续时间领域中的多智能体路径规划的极限。

    Jan, 2021

  • 基于冲突搜索 (CBS) 和焦点搜索 (FS) 组合的任意时间 MAPF 解算器分析

    本研究针对 CBS 算法的优化问题，设计并测试了多种不同的改进方式；研究结果表明，在多种情形下使用基于 Focal Search 的 anytime variant 算法优于传统的 CBS 算法。

    Sep, 2022

  • 分布式蒙特卡洛树搜索用于部分可观察多智体路径规划

    我们提出了一种基于分布式多智能体蒙特卡罗树搜索方法的多智能体路径规划算法，通过利用智能体的观察结果重新创建内在的马尔科夫决策过程，并结合针对多智能体任务的定制化神经蒙特卡罗树搜索算法进行路径规划，实验证明该方法优于现有的学习型多智能体路径规划器。

    Dec, 2023