K－PERR 是 PERR 的一般化，其中包裹被分成 K 個類型，并且相同類型的包裹是可交換的。因為在 TAPF 中，代理被分到組中，并且同一團隊中的代理是可交換的，所以 K－PERR 可以被視為對 K 個組的 TAPF 的改版，同樣的原理，PERR 可以被視為（標(biāo)準(zhǔn)）MAPF 的改版。我們已經(jīng)證明了近似最佳 PERR 和 K－PERR 解的困難性（對于K≥2）。我們的研究的一個推論是：在任何因子小于4／3內(nèi)的最大完工時間最小化，近似 MAPF 和 TAPF 是 NP－h(huán)ard 的，即使是只有兩個團隊的 TAPF。我們還證明了向 MAPF 添加交換操作不會在理論上減少其復(fù)雜度，但使得 PERR 比 MAPF 更容易解決。由此產(chǎn)生的在不同的實際場景中的連續(xù)問題：「一個有很多包裹的代理」產(chǎn)生經(jīng)典的農(nóng)村郵遞員問題（rural postman problem）；「代理與包裹一樣多」產(chǎn)生 MAPF、TAPF 或 PERR。了解這兩個極端問題有助于我們解決一般問題，正如其它許多真實世界任務(wù)的要求一樣。

圖 2：在一個模擬的 Kiva 倉庫系統(tǒng)中用戶提供的高速路（highway）

4 探索問題的結(jié)構(gòu)和運動的可預(yù)測性
　　代理與人共享工作空間，它們運動的一致性和其運動結(jié)果的可預(yù)測性對于人類的安全是重要的，因此不考慮現(xiàn)有的 MAPF 方法。這促使我們探索給定的 MAPF 例子的問題結(jié)構(gòu)，并設(shè)計一個激勵代理沿著用戶提供的邊緣（edge）集合（稱為高速公路）移動的方案［Cohen et al．， 2015］。我們在簡單的膨脹方案（inflation scheme）的背景下使用基于經(jīng)驗圖（experience graph）的高速公路［Phillips et al．， 2012］的想法，以導(dǎo)出新的啟發(fā)值（heuristic values），這個值用來激勵 MAPF 方法返回包括高速公路邊緣的路徑，這種方法能夠避免代理之間的迎面碰撞（head－to－h(huán)ead collisions），并實現(xiàn)其運動的一致性和可預(yù)測性。例如，在 Kiva 倉庫系統(tǒng)中，我們可以沿著存儲位置之間的狹窄通道設(shè)計高速公路，如圖2中的箭頭所示。我們已經(jīng)在模擬的 Kiva 倉庫系統(tǒng)中證明，這樣的高速公路能夠顯著加速 MAPF 方法，同時保持期望的 MAPF 解決方案成本的有限次優(yōu)性。 TAPF 和 PERR 例子的問題結(jié)構(gòu)也可以利用相同的方法。在可行性研究中，我們還開發(fā)了與用戶提供公路相媲美的自動生成公路的方法。
5 解決不完美的規(guī)劃執(zhí)行能力
　　最先進的 MAPF 或 TAPF 方法可以在合理的計算時間內(nèi)為數(shù)百個代理找到最佳的或者在用戶提供的次優(yōu)性保證下的不會發(fā)生碰撞的路徑。它們甚至在雜亂而緊湊的環(huán)境中也能正常工作，如Kiva 倉庫系統(tǒng)。然而，代理通常具有不完美的規(guī)劃執(zhí)行能力，并且不能完美地同步它們的運動，這可以導(dǎo)致頻繁的重新規(guī)劃并浪費時間。因此，我們提出了一個框架，使用一個簡單的時間網(wǎng)絡(luò)來有效地后期處理 MAPF 解決方案并創(chuàng)建一個規(guī)劃執(zhí)行安排，這適用于非完整機器人（non－h(huán)olonomic robot），考慮到它們的最大的平移和旋轉(zhuǎn)速度，提供了一個機器人之間安全距離和松弛邊界（定義為最新和最早進入時間的地點的差異）的保證，以緩解不完美的規(guī)劃執(zhí)行并避免在許多情況下的時間密集的重新規(guī)劃［Honig ¨ et al．， 2016］。這個框架已經(jīng)在仿真和真實機器人中得到評估。TAPF 和 PERR 方法也可以在同一框架中應(yīng)用。未來工作中要解決的問題包括增加用戶提供的安全距離、額外的運動約束、不確定性規(guī)劃和重新規(guī)劃。
6 結(jié)論
　　我們討論了四個研究方向，以解決當(dāng)將 MAPF 方法推廣到實際場景中和探索問題結(jié)構(gòu)或現(xiàn)有 MAPF 方法時出現(xiàn)的問題。我們的目標(biāo)是為在 MAPF 領(lǐng)域工作的研究人員指出有趣的研究方向。