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

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

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