Feb, 2024

利用基于冲突的搜索、优先级和时间约束进行最优任务分配和路径规划

PDF
TL;DR该研究通过利用强化学习中用户定义的奖励函数来实现冲突搜索算法（CBS）和任务分配与路径规划，解决了具有优先和时间约束的任务分配与路径规划问题（TAPF-PTC）。通过实验证明，相对于 MARL 和适应性目标分配与路径规划（TAPF）方法，我们的算法 CBS-TA-PTC 有效地解决了具有优先和时间约束的高难度拆弹任务。
multi-agent path findingtask assignmentpath findingprecedence constraintstemporal constraints
发现论文，激发创造
  • 优化先决约束计划任务的多智能体路径规划

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

    Feb, 2022

  • 多目标任务分配和路径规划的最优和有界次优方案

    本研究从理论和算法两个角度对多目标任务分配和路径规划问题（MG-TAPF）进行了建模和研究，并提出了算法建立在多智能体路径规划问题上，在各种基准领域上对算法进行了实验比较。

    Aug, 2022

  • 使用单一约束树解决多智体目标分配和路径规划问题

    本研究提出了一种名为 ITA-CBS 的增量目标指派 CBS 方法，该方法不需要计算 K 个最佳任务分配，只在搜索过程中增量计算新的最佳分配，有效避免了多个搜索树中的冲突，保证了最优解和计算效率。

    Jul, 2023

  • 团队 Agent 的最优目标分配和路径规划

    研究了已知地形中团队智能体的 TAPF（组合目标分配和路径查找）问题，提出了 CBM（基于冲突的最小成本流）算法，结合匿名和非匿名多智能体路径查找算法的思想，可用于处理各种规模的 TAPF 实例，并可适用于模拟仓库系统。

    Dec, 2016

  • 一致优先级搜索多智能体路径规划

    该研究探讨优先规划在多智能体路径规划中的应用，提出了基于冲突驱动的组合搜索框架，在实验中展示了其解决方案的先进性和成功率，并首次探讨了优先规划的完整性和最优性的局限性。

    Dec, 2018

  • 基于冲突的可解释多智能体路径规划搜索

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

    Feb, 2022

  • 双向时间计划图：为更高效的多智能体路径规划执行提供可切换的经过顺序

    多智能体路径规划问题涉及为多个智能体在共享环境中规划无碰撞路径。本研究提出了一种名为双向时序计划图（BTPG）的新图形表示，允许在执行过程中切换传递顺序以避免不必要的等待时间，并设计了两种构建 BTPG 的随时算法：BTPG-naïve 和 BTPG-optimized。实验结果表明，跟随 BTPG 相对于跟随 TPG 能更好地节约时间，减少不必要的等待时间 8-20%。

    Dec, 2023

  • 连续时间下的多智能体路径规划

    提出了一种基于 Safe interval path planning (SIPP) 和 Conflict-based search (CBS) 算法的多智能体路径规划 (Multi-Agent Pathfinding, MAPF) 方法，不依赖于网格、时间步长和动作的同时，并具有保证最优解的特点。对该算法进行了分析、讨论优劣，并在多项标准基准测试中进行了实验评估。

    Jan, 2019

  • 多智能体造地：通过环境操作实现高效多智能体路径规划

    本文介绍了一种新的 MAPF 扩展，称为 Terraforming MAPF（tMAPF），其中一些代理负责移动障碍以为其他代理清除道路。我们介绍了两种先进算法 CBS 和 PBS 的扩展来解决 tMAPF 问题，并表明它们无论在哪种静态障碍条件下都可以持续超过最佳解决方案。

    Mar, 2022

  • 含延迟概率的多智能体路径规划

    该研究提出了一个基于 Multi-Agent Path Finding (MAPF) 的两层搜索的 MAPF-DP 解决方案，包括规划具有不完美执行计划的有效 MAPF-DP 解决方案，提出了具有鲁棒性的计划执行策略以控制每个代理的行动，展示了能够生成有效 MAPF-DP 计划的两层 MAPF-DP 求解器（称为期望值最小化近似）。

    Dec, 2016