论文标题
反馈方案通过持续优化可切换动作依赖图图来重新排序多代理执行时间表
A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph
论文作者
论文摘要
在本文中，我们考虑了多个自动化的引导车辆（AGV），该车辆浏览了一个共同的工作空间，以完成各种内部学术任务，通常以多代理路径查找（MAPF）问题为例。为了保持计划执行无僵局，一种方法是构建一个动作依赖图（ADG），该图形编码AGV沿其路线进行的订购。使用这种方法，延迟的AGV偶尔会要求其他人在交叉口等待它们，从而影响计划的执行效率。如果工作空间由人类或第三方机器人等动态障碍共享，则AGV可以遇到巨大的延误。一种常见的缓解方法是使用电流延迟的AGV位置重新解决MAPF。但是，解决MAPF的时间很耗时，使这种方法效率低下，尤其是对于大型AGV团队而言。在这项工作中，我们提出了一种在线方法，可以反复修改给定的无环ADG，以最大程度地减少每个AGV的路线完成时间。我们的方法持续保持无环性ADG，这对于无僵硬的计划执行所必需。我们通过考虑对执行的随机干扰的模拟来评估该方法，并显示基于基准ADG的执行管理方法的路线完成时间更快。
In this paper we consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks, typically formulated as the Multi-Agent Path Finding (MAPF) problem. To keep plan execution deadlock-free, one approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. Using this method, delayed AGVs occasionally require others to wait for them at intersections, thereby affecting the plan execution efficiency. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. A common mitigation approach is to re-solve the MAPF using the current, delayed AGV positions. However, solving the MAPF is time-consuming, making this approach inefficient, especially for large AGV teams. In this work, we present an online method to repeatedly modify a given acyclic ADG to minimize route completion times of each AGV. Our approach persistently maintains an acyclic ADG, necessary for deadlock-free plan execution. We evaluate the approach by considering simulations with random disturbances on the execution and show faster route completion times compared to the baseline ADG-based execution management approach.
