大规模仓库中的双层多智能体取送货:多机器人重排布
本文研究带延迟的 Multi-Agent Pickup and Delivery 问题,提出了两种算法,基于 Token Passing 算法提供确定性和概率性的保证,在实验中,算法表现出了较好的有效性和健壮性,尤其是减少了重规划的次数。
Mar, 2023
本文研究了多智能体取送问题的一个生命周期版本,提出了两种算法 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
本论文研究了如何通过优化仓库布局提高多智能体路径规划算法在自动化仓库中的吞吐量,并通过扩展现有自动生成场景方法来优化仓库布局,从而降低拥堵和提高自动化仓库的可扩展性,该方法能生成具有用户指定多样性指标的布局。
May, 2023
本研究介绍了一个处理多智能体运输问题的新算法,使用组合搜索算法 SIPPwRT 进行单智能体路径规划,并考虑了实际机器人的动力学约束,相比于现有算法更为高效和有效。
Dec, 2018
该研究提出了一个 RHCR-based 方法,称之为 Terraforming MAPD,旨在解决机器人在仓库的货物存取问题中,只限于完成特定任务且无法动态移动其他货物对路径规划的限制。该方法可以提高仓库的吞吐量和服务质量,而不会显著影响运行时间。
May, 2023
本文研究了在大型自动化仓库等场景下,智能体不断需要寻找新的目标点的长期多智能体路径规划问题。我们提出了一种新的解决方案,Rolling-Horizon Collision Resolution 框架,通过将问题分解成一系列窗口 MAPF 实例来解决,其中窗口 MAPF 解决器仅在有限时间范围内解决智能体路径的冲突,并忽略其外的冲突。我们通过模拟仓库实例,经验性地评估了 RHCR,并与各种 MAPF 解算器进行了比较,在多达 1000 个智能体的情况下(= 地图上 38.9%的空单元格),RHCR 可以产生高质量的解决方案,显着优于现有工作。
May, 2020
该研究提出了一种叫做 “基于等待的死锁避免”(SBDA) 的死锁避免方法,可以提高迷宫般的环境中多代理人搬运物资的运输效率。该方法通过实时使用割点算法来确定待机节点,并保证智能体在那里停留一定的时间,从而有效减少阻塞或死锁的情况。实验证明,与传统方法相比,该方法的性能更好。也分析了用于选择待机节点的参数如何影响性能。
Jan, 2022
该研究提出了一个基于 Multi-Agent Path Finding (MAPF) 的两层搜索的 MAPF-DP 解决方案,包括规划具有不完美执行计划的有效 MAPF-DP 解决方案,提出了具有鲁棒性的计划执行策略以控制每个代理的行动,展示了能够生成有效 MAPF-DP 计划的两层 MAPF-DP 求解器(称为期望值最小化近似)。
Dec, 2016
通过提出两种最优算法,基于减少 MAPF-DL 的流问题和后续抽象的多种商品流网络的紧凑整数线性规划和基于新的组合搜索算法,我们正式规范具有截止日期的多智能体路径规划问题。
Jun, 2018