K－PERR 是 PERR 的一般化，其中包裹被分成 K 个类型，并且相同类型的包裹是可交换的。因为在 TAPF 中，代理被分到组中，并且同一团队中的代理是可交换的，所以 K－PERR 可以被视为对 K 个组的 TAPF 的改版，同样的原理，PERR 可以被视为（标准）MAPF 的改版。我们已经证明了近似最佳 PERR 和 K－PERR 解的困难性（对于K≥2）。我们的研究的一个推论是：在任何因子小于4／3内的最大完工时间最小化，近似 MAPF 和 TAPF 是 NP－hard 的，即使是只有两个团队的 TAPF。我们还证明了向 MAPF 添加交换操作不会在理论上减少其复杂度，但使得 PERR 比 MAPF 更容易解决。由此产生的在不同的实际场景中的连续问题：「一个有很多包裹的代理」产生经典的农村邮递员问题（rural postman problem）；「代理与包裹一样多」产生 MAPF、TAPF 或 PERR。了解这两个极端问题有助于我们解决一般问题，正如其它许多真实世界任务的要求一样。

图 2：在一个模拟的 Kiva 仓库系统中用户提供的高速路（highway）

4 探索问题的结构和运动的可预测性
　　代理与人共享工作空间，它们运动的一致性和其运动结果的可预测性对于人类的安全是重要的，因此不考虑现有的 MAPF 方法。这促使我们探索给定的 MAPF 例子的问题结构，并设计一个激励代理沿着用户提供的边缘（edge）集合（称为高速公路）移动的方案［Cohen et al．， 2015］。我们在简单的膨胀方案（inflation scheme）的背景下使用基于经验图（experience graph）的高速公路［Phillips et al．， 2012］的想法，以导出新的启发值（heuristic values），这个值用来激励 MAPF 方法返回包括高速公路边缘的路径，这种方法能够避免代理之间的迎面碰撞（head－to－head collisions），并实现其运动的一致性和可预测性。例如，在 Kiva 仓库系统中，我们可以沿着存储位置之间的狭窄通道设计高速公路，如图2中的箭头所示。我们已经在模拟的 Kiva 仓库系统中证明，这样的高速公路能够显著加速 MAPF 方法，同时保持期望的 MAPF 解决方案成本的有限次优性。 TAPF 和 PERR 例子的问题结构也可以利用相同的方法。在可行性研究中，我们还开发了与用户提供公路相媲美的自动生成公路的方法。
5 解决不完美的规划执行能力
　　最先进的 MAPF 或 TAPF 方法可以在合理的计算时间内为数百个代理找到最佳的或者在用户提供的次优性保证下的不会发生碰撞的路径。它们甚至在杂乱而紧凑的环境中也能正常工作，如Kiva 仓库系统。然而，代理通常具有不完美的规划执行能力，并且不能完美地同步它们的运动，这可以导致频繁的重新规划并浪费时间。因此，我们提出了一个框架，使用一个简单的时间网络来有效地后期处理 MAPF 解决方案并创建一个规划执行安排，这适用于非完整机器人（non－holonomic robot），考虑到它们的最大的平移和旋转速度，提供了一个机器人之间安全距离和松弛边界（定义为最新和最早进入时间的地点的差异）的保证，以缓解不完美的规划执行并避免在许多情况下的时间密集的重新规划［Honig ¨ et al．， 2016］。这个框架已经在仿真和真实机器人中得到评估。TAPF 和 PERR 方法也可以在同一框架中应用。未来工作中要解决的问题包括增加用户提供的安全距离、额外的运动约束、不确定性规划和重新规划。
6 结论
　　我们讨论了四个研究方向，以解决当将 MAPF 方法推广到实际场景中和探索问题结构或现有 MAPF 方法时出现的问题。我们的目标是为在 MAPF 领域工作的研究人员指出有趣的研究方向。