Offline Time-Independent Multiagent Path Planning
Offline Time-Independent Multiagent Path Planning
复制标题
DOI：
10.1109/tro.2023.3258690
复制
发表时间：
2021-05
影响因子：
7.8
通讯作者：
Keisuke Okumura;Franccois Bonnet;Yasumasa Tamura;Xavier D'efago
中科院分区：
文献类型：
--
作者：
Keisuke Okumura;Franccois Bonnet;Yasumasa Tamura;Xavier D'efago
本研究探讨一种新的规划问题，多个代理，不能共享持有资源，离线时间无关的多代理路径规划（OTIMAPP）。给定一个图和一组开始-目标对，要解决的问题是为每个代理分配一条路径，这样每个代理最终都会到达目的地而不会阻止其他代理，无论每个代理何时开始和完成自己的动作。这种动机源于时间的不确定性，包括规划和机器人执行之间的现实差距。与传统的解决方案相比，依赖于时间的多机器人路径规划的概念，一旦获得OTIMAPP解决方案，它们可以在机器人动作之间没有任何同步的情况下执行。此外，理论上保证所有机器人最终都能到达目的地，只要它们避免机器人之间的碰撞。本研究试图从理论和实践两方面建立OTIMAPP。具体来说，我们提出了问题的形式化、基于死锁分类的解决方案条件、表明OTIMAPP在计算上难以处理的计算复杂性、解决方案概念的实际放松、基于多智能体寻路算法解决OTIMAPP的两种算法、表明大型OTIMAPP实例的经验结果可以在一定程度上得到解决，以及异步OTIMAPP执行的机器人演示。
This study examines a novel planning problem for multiple agents that cannot share holding resources, named Offline Time-Independent Multiagent Path Planning (OTIMAPP). Given a graph and a set of start-goal pairs, the problem to be addressed is assigning a path to each agent, such that every agent eventually reaches its destination without blocking others, regardless of when each agent starts and finishes each own action. This motivation stems from timing uncertainties, including the reality gaps between planning and robot execution. In contrast to conventional solution, concepts of multirobot path planning that rely on timings, once OTIMAPP solutions are obtained, they can be executed without any synchronization between robot actions. Moreover, there is a theoretical guarantee that all robots eventually reach their destinations, provided they avoid interrobot collisions. This study attempts to establish OTIMAPP both theoretically and practically. Specifically, we present a formalization of the problem, solution conditions based on a categorization of deadlocks, computational complexities showing that OTIMAPP is computationally intractable, practical relaxation of the solution concept, two algorithms to solve OTIMAPP based on multiagent pathfinding algorithms, empirical results showing large OTIMAPP instances can be solved to some extent, as well as robot demonstrations of asynchronous OTIMAPP execution.