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 領域工作的研究人員指出有趣的研究方向。