We study the problem of optimal multi-robot path planning on graphs MPP over
four distinct minimization objectives: the makespan (last arrival time), the
maximum (single-robot traveled) distance, the total arrival time, and the total
distance. In a related paper, we show that these objectives are distinct and
NP-hard to optimize. In this work, we focus on efficiently algorithmic
solutions for solving these optimal MPP problems. Toward this goal, we first
establish a one-to-one solution mapping between MPP and network-flow. Based on
this equivalence and integer linear programming (ILP), we design novel and
complete algorithms for optimizing over each of the four objectives. In
particular, our exact algorithm for computing optimal makespan solutions is a
first such that is capable of solving extremely challenging problems with
robot-vertex ratio as high as 100%. Then, we further improve the computational
performance of these exact algorithms through the introduction of principled
heuristics, at the expense of some optimality loss. The combination of ILP
model based algorithms and the heuristics proves to be highly effective,
allowing the computation of 1.x-optimal solutions for problems containing
hundreds of robots, densely populated in the environment, often in just
seconds.

通过与网络流的等价性和整数线性规划，我们设计了用于解决四个不同目标的新颖和完整算法，从而解决了最佳多机器人路径规划问题。采用基于 ILP 算法模型和启发式算法的组合方法，能够在几秒钟内计算出包含数百个机器人，环境密集的问题的 1.x - 最优解。