On an assigned graph, the problem of Multi-Agent Pathfinding (MAPF) consists in finding paths for multiple agents, avoiding collisions. Finding the minimum-length solution is known to be NP-hard, and computation times grows exponentially with the number of agents. However, in industrial applications, it is important to find feasible, suboptimal solutions, in a time that grows polynomially with the number of agents. Such algorithms exist for undirected and biconnected directed graphs. Our main contribution is to generalize these algorithms to the more general case of strongly connected directed graphs. In particular, given a MAPF problem with at least two holes, we present an algorithm that checks the problem feasibility in linear time with respect to the number of nodes, and provides a feasible solution in polynomial time.

翻译：在指定的图表中,多方代理探索(MAPF)的问题在于寻找多种物剂的路径,避免碰撞。 找到最短长度的溶液已知是NP硬的,而计算时间随着物剂的数量而成倍增长。 但是,在工业应用中,重要的是在与物剂数量多而多的时期找到可行的、不最优的解决方法。 这种算法存在于非方向和双向定向图形中。 我们的主要贡献是将这些算法概括到更一般的、紧密相连的图形中。 特别是,考虑到MAPF问题至少有两个洞,我们提出了一个算法,用以在线性时间检查节点数量的问题的可行性,并在多面时间提供可行的解决办法。