May, 2022

使用临时优先级的优先级继承解决多智能体取送问题的死锁自由方法

PDF
TL;DR本文提出了一种方法，将优先级继承与回溯（PIBT）方法扩展到更一般的环境中，以解决多智能体取送问题（MAPD 问题），该方法允许在一定范围内存在树形路径，防止死锁，并通过与标准方法的比较表明，其效率非常高。
multi-agent pickup and delivery problempriority inheritance with backtrackingdeadlocktree-shaped pathsefficiency
发现论文，激发创造
  • 基于回溯的优先级继承策略用于迭代式多智能体路径规划

    本文提出了一种名为 PIBT 的子优化算法，可以有效地解决在自动化仓库等实际地图中，数百甚至更多的机器人的多智能体路径规划问题，并用实际机器人进行了演示和验证。

    Jan, 2019

  • 具有延迟的强大多智能体取送货

    本文研究带延迟的 Multi-Agent Pickup and Delivery 问题，提出了两种算法，基于 Token Passing 算法提供确定性和概率性的保证，在实验中，算法表现出了较好的有效性和健壮性，尤其是减少了重规划的次数。

    Mar, 2023

  • 多智能体接送任务的基于备用的死锁避免方法

    该研究提出了一种叫做 “基于等待的死锁避免”(SBDA) 的死锁避免方法，可以提高迷宫般的环境中多代理人搬运物资的运输效率。该方法通过实时使用割点算法来确定待机节点，并保证智能体在那里停留一定的时间，从而有效减少阻塞或死锁的情况。实验证明，与传统方法相比，该方法的性能更好。也分析了用于选择待机节点的参数如何影响性能。

    Jan, 2022

  • 在线接送任务的终身多智能体路径规划

    本文研究了多智能体取送问题的一个生命周期版本，提出了两种算法 Token Passing 与 Token Passing with Task Swaps，其中 TP 算法对于拥有数百个智能体和任务的 MAPD 实例仍然有效，可全面推广为全分布式 MAPD 算法，TPTS 需要少量智能体之间的通信，TP 算法适用于需要实时计算的情况，TPTS 算法则在 TP 算法与集中式 MAPD 算法之间做出了平衡。

    May, 2017

  • 多目标多智能体接送

    本研究提出两种算法变种 - LNS-PBS 和 LNS-wPBS 来解决实时多智能体拾送配送问题（MAPD）及一般版 (MG-MAPD)，并采用大邻域搜索（LNS）和基于优先级的搜索（PBS）算法，实验结果表明，相比现有的完整 MAPD 算法 CENTRAL 和可扩展的 MAPD 算法 HBH+MLA*，LNS-PBS 与 LNS-wPBS 不仅在效率和稳定性上更优，而且能够有效地处理成千上万的任务和代理。

    Aug, 2022

  • 多智能体取送货生命周期运动规划

    本研究介绍了一个处理多智能体运输问题的新算法，使用组合搜索算法 SIPPwRT 进行单智能体路径规划，并考虑了实际机器人的动力学约束，相比于现有算法更为高效和有效。

    Dec, 2018

  • 多智能体取送货的环境干预及调整技术 -- 以可居住星球开发为例

    该研究提出了一个 RHCR-based 方法，称之为 Terraforming MAPD，旨在解决机器人在仓库的货物存取问题中，只限于完成特定任务且无法动态移动其他货物对路径规划的限制。该方法可以提高仓库的吞吐量和服务质量，而不会显著影响运行时间。

    May, 2023

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

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

    Dec, 2023

  • 面向终身多智能体路径规划的公路研究

    本文主要研究如何在 lifelong MAPF 中使用 highway 方法解决地图规模增大、密度增大等问题，以减少 deadlocks 现象并优化 throughput，实验证明 runtime 得到改进。

    Apr, 2023

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

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

    Dec, 2018