多代理路徑尋找（Multi－agent path finding／MAPF）已在人工智能、機器人、理論計算機科學和實際操作研究中得到大量的研究。本文討論了在將MAPF方法推廣到實際場景時出現(xiàn)的問題與解決這些問題的四個研究方向。我們強調(diào)的是解決這些問題的重要性，而不是為MAPF問題的標準模型開發(fā)更快的方法。
1 引言
多代理路徑尋找（MAPF，也叫多代理尋徑）在人工智能、機器人、理論計算機科學和實際操作研究中得到大量的研究。（標準）MAPF的任務是為多個代理（agent）找到在給定圖（graph）中從其當前頂點（vertices）到其目標而不與其它代理發(fā)生碰撞的路徑，同時優(yōu)化成本函數(shù)（cost function）。現(xiàn)有的 MAPF 使用的方法包括：從可滿足性減少問題（reductions to problems from satisfiability）、整數(shù)線性規(guī)劃（integer linear programming）、回答集編程（answer set programming）［Yu and LaValle， 2013b； Erdem et al．， 2013； Surynek， 2015］、最優(yōu)／有限次優(yōu)（optimal，bounded－suboptimal）或次優(yōu)搜索方法（suboptimal search method）［Silver， 2005； Sturtevant and Buro， 2006； Ryan， 2008； Wang and Botea， 2008； Standley， 2010； Standley and Korf， 2011； Wang and Botea， 2011； Luna and Bekris， 2011； Sharon et al．， 2013； de Wilde et al．， 2013； Barer et al．， 2014； Goldenberg et al．， 2014； Wagner and Choset， 2015； Boyarski et al．， 2015； Sharon et al．， 2015］。
我們最近研究了將 MAPF 推廣到實際場景時出現(xiàn)的各種問題，包括 Kiva（Amazon Robotics）倉庫系統(tǒng)［Wurman et al．， 2008］（圖1）和自動飛行器牽引車［Morris et al．， 2016］。這些問題可以分為兩個一般問題：
1、為 MAPF 問題的標準模型開發(fā)更快的方法是不夠的，因為在許多實際情況下，可以利用新的結(jié)構(gòu)或需要新的問題模型。
2、僅將 MAPF 或其新的模型作為組合優(yōu)化問題進行研究是不夠的，因為所產(chǎn)生的 MAPF 解決方案也需要執(zhí)行。
我們從不同的角度討論了解決這兩個問題的四個研究方向：
1．在許多實際的多代理系統(tǒng)中，在為所有代理找到最佳路徑之前，代理先被劃分成組（team），然后給每個組分配特定的目標，每個代理需要從所在的組中被指定一個目標。我們已經(jīng)為不同組的代理制定了組合目標分配和路徑查找（TAPF／target assignment and path finding）問題來解決這個困難。我們還開發(fā)了一個最佳 TAPF 方法，它可以擴展到幾十個組和數(shù)百個代理［Ma and Koenig， 2016］。
2．在許多實際的多代理系統(tǒng)中，代理是匿名的（可交換的），但是它們的有效載荷是非匿名的（不可交換的），并且需要被傳遞給給定的目標。代理通?？梢栽谶@樣的系統(tǒng)中交換其有效載荷。作為第一次嘗試，我們設(shè)計了包裹交換機器人路由（package－exchange robot routing／PERR）問題，以解決更多一般化的（允許有效載荷轉(zhuǎn)移的）運輸問題［Ma et al．， 2016］。在這篇文章中，我們還證明了近似最優(yōu) MAPF 解的困難性（復雜度）。
3．在許多實際的多代理系統(tǒng)中，代理運動（agent motions）的一致性和代理運動的結(jié)果可預測性是重要的（特別是在由人和代理共享的工作空間中），但是現(xiàn)有的 MAPF 方法沒有考慮這一點。我們已經(jīng)分兩個階段探索了給定 MAPF 例子的問題結(jié)構(gòu)：在第一階段，我們開發(fā)了一種為代理尋找路徑的方案，其中包含了由用戶提供的許多帶邊緣的高速公路（highways），這個方案達到了代理運動的一致性和可預測性［Cohen et al．， 2015］；在第二階段，我們開發(fā)了自動生成高速公路的方法［Cohen et al．， 2016］。
4．MAPF 的靈感主要來源于多機器人系統(tǒng)的導航或運動規(guī)劃模塊。然而，MAPF 解決方案的最優(yōu)性或有限次優(yōu)性不一定意味著它們的魯棒性，特別是考慮到現(xiàn)實中機器人不完美的規(guī)劃執(zhí)行（plan－execution）能力。我們開發(fā)了一個框架，它能有效地后期處理（postprocesses）MAPF 方法的輸出，用于創(chuàng)建一個可以由實際的多機器人系統(tǒng)執(zhí)行的規(guī)劃執(zhí)行安排。
圖 1 ：（左圖）自動駕駛單元和可以被駕駛單元移動的存儲產(chǎn)品的存儲艙（storage pod）；（右圖）典型 Kiva 倉庫系統(tǒng)的布局（Wurman et al．， 2008）
為了將 MAPF 方法推廣到實際的場景，我們現(xiàn)在展示這些研究方向的實用性，以證明解決這兩個問題與開發(fā)更快的 MAPF 問題的標準模型方法一樣重要（甚至更重要）。
2 代理組的目標分配和路徑查找（TAPF）的組合
一般來說，是按照代理所在的每個組分配目標。代理先被劃分到組中，然后每個代理需要從所在的組中被指定一個目標，以便得到代理從當前頂點到其目標的路徑來優(yōu)化成本函數(shù)。例如，在 Kiva 倉庫系統(tǒng)中，將存儲艙從倉庫搬運到新存儲位置的駕駛單元（drive unit）會形成一個組，因為它們中的每一個需要被分配一個可用的存儲位置。以前的 MAPF 方法假設(shè)存在目標分配程序，使得每個代理預先被分配一個目標，但是為了實現(xiàn)最優(yōu)性，我們建立了 TAPF 模型，它整合了目標分配和路徑尋找問題并且為它們定義了一個共同的目標。在 TAPF 中，代理被分到各組中，每個組的目標數(shù)量與該組中的代理數(shù)量相同。TAPF 的任務是將目標分配給代理，并規(guī)劃代理從當前頂點到其目標的不會發(fā)生碰撞的路徑，使得每個代理恰好移動到其所在組的一個目標，從而組中的所有目標被訪問，且最大完成時間（當所有代理已經(jīng)到達其目標并停止移動時的最早時間步長）被最小化。組中的每個代理都可以被分配到所在組的目標，并且同一組中的代理因此是可交換的。然而，不同組中的代理不可交換。TAPF 可以被視為（標準）MAPF 和 MAPF 的匿名變體的一般化：
·來自 TAPF的（標準）MAPF 結(jié)果，如果每個組僅由一個代理組成，則組的數(shù)量等于代理的數(shù)量。目標到代理的分配是預先確定的，因此代理是非匿名的（不可交換的）。
·如果只有一個組（包含所有代理），則 MAPF 的匿名變量（也稱為目標不變的 MAPF）來自 TAPF。代理可以被分配任何目標，因此是可交換的。它可以在多項式時間內(nèi)用基于流的 MAPF 方法（flow－based MAPF method）得到最優(yōu)解［Yu and LaValle， 2013a； Turpin et al．， 2014］．
當前最先進的最優(yōu) TAPF 方法——稱為基于碰撞的最小成本流（Conflict－Based Min－Cost Flow）［Ma and Koenig， 2016］——結(jié)合了搜索和基于流的 MAPF 方法。它可以推廣到幾十個組和數(shù)百個代理。
3 MAPF 的包裹交換機器人路由（PERR）和新的復雜度計算結(jié)果
代理通常是匿名的，但攜帶被分配目標的有效載荷（包裹），因此是非匿名的。例如，在 Kiva 倉庫系統(tǒng)中，駕駛單元是匿名的，但是它們攜帶的存儲艙被分配了存儲位置，因此是非匿名的。如果每個代理都攜帶一個包裹，則該問題相當于（標準）MAPF。實際上，包裹通常可以在代理之間傳遞，這導致更一般的運輸問題，例如，帶有換乘的乘客共享乘車［Coltin and Veloso， 2014］和在辦公室中使用機器人的包裹遞送［Veloso et al．， 2015］。我們已經(jīng)將 PERR 作為理解這些問題的第一步［Ma et al．， 2016］。在 PERR 中，每個代理運載一個包裹，相鄰頂點中的任何兩個代理可以交換其包裹，并且每個包需裹要被遞送到給定目標。PERR 因此可以被視為（標準）MAPF 的改進版：
·PERR 中的包裹可以被視為在（標準）MAPF 中的自己移動的代理。
·允許在相鄰頂點中的兩個包裹在 PERR 中交換它們的頂點，但是在相鄰頂點中的兩個代理不允許在（標準）MAPF 中交換它們的頂點。
K－PERR 是 PERR 的一般化，其中包裹被分成 K 個類型，并且相同類型的包裹是可交換的。因為在 TAPF 中，代理被分到組中，并且同一團隊中的代理是可交換的，所以 K－PERR 可以被視為對 K 個組的 TAPF 的改版，同樣的原理，PERR 可以被視為（標準）MAPF 的改版。我們已經(jīng)證明了近似最佳 PERR 和 K－PERR 解的困難性（對于K≥2）。我們的研究的一個推論是：在任何因子小于4／3內(nèi)的最大完工時間最小化，近似 MAPF 和 TAPF 是 NP－h(huán)ard 的，即使是只有兩個團隊的 TAPF。我們還證明了向 MAPF 添加交換操作不會在理論上減少其復雜度，但使得 PERR 比 MAPF 更容易解決。由此產(chǎn)生的在不同的實際場景中的連續(xù)問題：「一個有很多包裹的代理」產(chǎn)生經(jīng)典的農(nóng)村郵遞員問題（rural postman problem）；「代理與包裹一樣多」產(chǎn)生 MAPF、TAPF 或 PERR。了解這兩個極端問題有助于我們解決一般問題，正如其它許多真實世界任務的要求一樣。
圖 2：在一個模擬的 Kiva 倉庫系統(tǒng)中用戶提供的高速路（highway）
4 探索問題的結(jié)構(gòu)和運動的可預測性
代理與人共享工作空間，它們運動的一致性和其運動結(jié)果的可預測性對于人類的安全是重要的，因此不考慮現(xiàn)有的 MAPF 方法。這促使我們探索給定的 MAPF 例子的問題結(jié)構(gòu)，并設(shè)計一個激勵代理沿著用戶提供的邊緣（edge）集合（稱為高速公路）移動的方案［Cohen et al．， 2015］。我們在簡單的膨脹方案（inflation scheme）的背景下使用基于經(jīng)驗圖（experience graph）的高速公路［Phillips et al．， 2012］的想法，以導出新的啟發(fā)值（heuristic values），這個值用來激勵 MAPF 方法返回包括高速公路邊緣的路徑，這種方法能夠避免代理之間的迎面碰撞（head－to－h(huán)ead collisions），并實現(xiàn)其運動的一致性和可預測性。例如，在 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í)行能力，并且不能完美地同步它們的運動，這可以導致頻繁的重新規(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 方法也可以在同一框架中應用。未來工作中要解決的問題包括增加用戶提供的安全距離、額外的運動約束、不確定性規(guī)劃和重新規(guī)劃。
6 結(jié)論
我們討論了四個研究方向，以解決當將 MAPF 方法推廣到實際場景中和探索問題結(jié)構(gòu)或現(xiàn)有 MAPF 方法時出現(xiàn)的問題。我們的目標是為在 MAPF 領(lǐng)域工作的研究人員指出有趣的研究方向。
