多代理路徑尋找(Multi-agent path finding/MAPF)已在人工智能(néng)、機器人、理論計算機科學(xué)和實際操作研究中得到大量的研究。本文讨論了在將(jiāng)MAPF方法推廣到實際場景時出現的問題與解決這(zhè)些問題的四個研究方向(xiàng)。我們強調的是解決這(zhè)些問題的重要性，而不是爲MAPF問題的标準模型開(kāi)發(fā)更快的方法。

1 引言

       多代理路徑尋找(MAPF，也叫(jiào)多代理尋徑)在人工智能(néng)、機器人、理論計算機科學(xué)和實際操作研究中得到大量的研究。(标準)MAPF的任務是爲多個代理(agent)找到在給定圖(graph)中從其當前頂點(vertices)到其目标而不與其它代理發(fā)生碰撞的路徑，同時優化成(chéng)本函數(cost function)。現有的 MAPF 使用的方法包括：從可滿足性減少問題(reductions to problems from satisfiability)、整數線性規劃(integer linear programming)、回答集編程(answer set programming)[Yu and LaValle， 2013b; Erdem et al.， 2013; Surynek， 2015]、最優/有限次優(optimal，bounded-suboptimal)或次優搜索方法(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]。

       我們最近研究了將(jiāng) MAPF 推廣到實際場景時出現的各種(zhǒng)問題，包括 Kiva(Amazon Robotics)倉庫系統[Wurman et al.， 2008](圖1)和自動飛行器牽引車[Morris et al.， 2016]。這(zhè)些問題可以分爲兩(liǎng)個一般問題：

       1、爲 MAPF 問題的标準模型開(kāi)發(fā)更快的方法是不夠的，因爲在許多實際情況下，可以利用新的結構或需要新的問題模型。

       2、僅將(jiāng) MAPF 或其新的模型作爲組合優化問題進(jìn)行研究是不夠的，因爲所産生的 MAPF 解決方案也需要執行。

我們從不同的角度讨論了解決這(zhè)兩(liǎng)個問題的四個研究方向(xiàng)：

       1.在許多實際的多代理系統中，在爲所有代理找到最佳路徑之前，代理先被(bèi)劃分成(chéng)組(team)，然後(hòu)給每個組分配特定的目标，每個代理需要從所在的組中被(bèi)指定一個目标。我們已經(jīng)爲不同組的代理制定了組合目标分配和路徑查找(TAPF/target assignment and path finding)問題來解決這(zhè)個困難。我們還(hái)開(kāi)發(fā)了一個最佳 TAPF 方法，它可以擴展到幾十個組和數百個代理[Ma and Koenig， 2016]。

       2.在許多實際的多代理系統中，代理是匿名的(可交換的)，但是它們的有效載荷是非匿名的(不可交換的)，并且需要被(bèi)傳遞給給定的目标。代理通常可以在這(zhè)樣(yàng)的系統中交換其有效載荷。作爲第一次嘗試，我們設計了包裹交換機器人路由(package-exchange robot routing/PERR)問題，以解決更多一般化的(允許有效載荷轉移的)運輸問題[Ma et al.， 2016]。在這(zhè)篇文章中，我們還(hái)證明了近似最優 MAPF 解的困難性(複雜度)。

       3.在許多實際的多代理系統中，代理運動(agent motions)的一緻性和代理運動的結果可預測性是重要的(特别是在由人和代理共享的工作空間中)，但是現有的 MAPF 方法沒(méi)有考慮這(zhè)一點。我們已經(jīng)分兩(liǎng)個階段探索了給定 MAPF 例子的問題結構：在第一階段，我們開(kāi)發(fā)了一種(zhǒng)爲代理尋找路徑的方案，其中包含了由用戶提供的許多帶邊緣的高速公路(highways)，這(zhè)個方案達到了代理運動的一緻性和可預測性[Cohen et al.， 2015];在第二階段，我們開(kāi)發(fā)了自動生成(chéng)高速公路的方法[Cohen et al.， 2016]。

       4.MAPF 的靈感主要來源于多機器人系統的導航或運動規劃模塊。然而，MAPF 解決方案的最優性或有限次優性不一定意味著(zhe)它們的魯棒性，特别是考慮到現實中機器人不完美的規劃執行(plan-execution)能(néng)力。我們開(kāi)發(fā)了一個框架，它能(néng)有效地後(hòu)期處理(postprocesses)MAPF 方法的輸出，用于創建一個可以由實際的多機器人系統執行的規劃執行安排。

       圖 1 ：(左圖)自動駕駛單元和可以被(bèi)駕駛單元移動的存儲産品的存儲艙(storage pod);(右圖)典型 Kiva 倉庫系統的布局(Wurman et al.， 2008)

       爲了將(jiāng) MAPF 方法推廣到實際的場景，我們現在展示這(zhè)些研究方向(xiàng)的實用性，以證明解決這(zhè)兩(liǎng)個問題與開(kāi)發(fā)更快的 MAPF 問題的标準模型方法一樣(yàng)重要(甚至更重要)。

2 代理組的目标分配和路徑查找(TAPF)的組合

       一般來說，是按照代理所在的每個組分配目标。代理先被(bèi)劃分到組中，然後(hòu)每個代理需要從所在的組中被(bèi)指定一個目标，以便得到代理從當前頂點到其目标的路徑來優化成(chéng)本函數。例如，在 Kiva 倉庫系統中，將(jiāng)存儲艙從倉庫搬運到新存儲位置的駕駛單元(drive unit)會(huì)形成(chéng)一個組，因爲它們中的每一個需要被(bèi)分配一個可用的存儲位置。以前的 MAPF 方法假設存在目标分配程序，使得每個代理預先被(bèi)分配一個目标，但是爲了實現最優性，我們建立了 TAPF 模型，它整合了目标分配和路徑尋找問題并且爲它們定義了一個共同的目标。在 TAPF 中，代理被(bèi)分到各組中，每個組的目标數量與該組中的代理數量相同。TAPF 的任務是將(jiāng)目标分配給代理，并規劃代理從當前頂點到其目标的不會(huì)發(fā)生碰撞的路徑，使得每個代理恰好(hǎo)移動到其所在組的一個目标，從而組中的所有目标被(bèi)訪問，且最大完成(chéng)時間(當所有代理已經(jīng)到達其目标并停止移動時的最早時間步長(cháng))被(bèi)最小化。組中的每個代理都(dōu)可以被(bèi)分配到所在組的目标，并且同一組中的代理因此是可交換的。然而，不同組中的代理不可交換。TAPF 可以被(bèi)視爲(标準)MAPF 和 MAPF 的匿名變體的一般化：

• 來自 TAPF的(标準)MAPF 結果，如果每個組僅由一個代理組成(chéng)，則組的數量等于代理的數量。目标到代理的分配是預先确定的，因此代理是非匿名的(不可交換的)。

• 如果隻有一個組(包含所有代理)，則 MAPF 的匿名變量(也稱爲目标不變的 MAPF)來自 TAPF。代理可以被(bèi)分配任何目标，因此是可交換的。它可以在多項式時間内用基于流的 MAPF 方法(flow-based MAPF method)得到最優解[Yu and LaValle， 2013a; Turpin et al.， 2014].

       當前最先進(jìn)的最優 TAPF 方法——稱爲基于碰撞的最小成(chéng)本流(Conflict-Based Min-Cost Flow)[Ma and Koenig， 2016]——結合了搜索和基于流的 MAPF 方法。它可以推廣到幾十個組和數百個代理。

3 MAPF 的包裹交換機器人路由(PERR)和新的複雜度計算結果

       代理通常是匿名的，但攜帶被(bèi)分配目标的有效載荷(包裹)，因此是非匿名的。例如，在 Kiva 倉庫系統中，駕駛單元是匿名的，但是它們攜帶的存儲艙被(bèi)分配了存儲位置，因此是非匿名的。如果每個代理都(dōu)攜帶一個包裹，則該問題相當于(标準)MAPF。實際上，包裹通常可以在代理之間傳遞，這(zhè)導緻更一般的運輸問題，例如，帶有換乘的乘客共享乘車[Coltin and Veloso， 2014]和在辦公室中使用機器人的包裹遞送[Veloso et al.， 2015]。我們已經(jīng)將(jiāng) PERR 作爲理解這(zhè)些問題的第一步[Ma et al.， 2016]。在 PERR 中，每個代理運載一個包裹，相鄰頂點中的任何兩(liǎng)個代理可以交換其包裹，并且每個包需裹要被(bèi)遞送到給定目标。PERR 因此可以被(bèi)視爲(标準)MAPF 的改進(jìn)版：

• PERR 中的包裹可以被(bèi)視爲在(标準)MAPF 中的自己移動的代理。

  
  

• 允許在相鄰頂點中的兩(liǎng)個包裹在 PERR 中交換它們的頂點，但是在相鄰頂點中的兩(liǎng)個代理不允許在(标準)MAPF 中交換它們的頂點。

  
  

       K-PERR 是 PERR 的一般化，其中包裹被(bèi)分成(chéng) K 個類型，并且相同類型的包裹是可交換的。因爲在 TAPF 中，代理被(bèi)分到組中，并且同一團隊中的代理是可交換的，所以 K-PERR 可以被(bèi)視爲對(duì) K 個組的 TAPF 的改版，同樣(yàng)的原理，PERR 可以被(bèi)視爲(标準)MAPF 的改版。我們已經(jīng)證明了近似最佳 PERR 和 K-PERR 解的困難性(對(duì)于K≥2)。我們的研究的一個推論是：在任何因子小于4/3内的最大完工時間最小化，近似 MAPF 和 TAPF 是 NP-hard 的，即使是隻有兩(liǎng)個團隊的 TAPF。我們還(hái)證明了向(xiàng) MAPF 添加交換操作不會(huì)在理論上減少其複雜度，但使得 PERR 比 MAPF 更容易解決。由此産生的在不同的實際場景中的連續問題：「一個有很多包裹的代理」産生經(jīng)典的農村郵遞員問題(rural postman problem);「代理與包裹一樣(yàng)多」産生 MAPF、TAPF 或 PERR。了解這(zhè)兩(liǎng)個極端問題有助于我們解決一般問題，正如其它許多真實世界任務的要求一樣(yàng)。

圖 2：在一個模拟的 Kiva 倉庫系統中用戶提供的高速路(highway)

4 探索問題的結構和運動的可預測性

       代理與人共享工作空間，它們運動的一緻性和其運動結果的可預測性對(duì)于人類的安全是重要的，因此不考慮現有的 MAPF 方法。這(zhè)促使我們探索給定的 MAPF 例子的問題結構，并設計一個激勵代理沿著(zhe)用戶提供的邊緣(edge)集合(稱爲高速公路)移動的方案[Cohen et al.， 2015]。我們在簡單的膨脹方案(inflation scheme)的背景下使用基于經(jīng)驗圖(experience graph)的高速公路[Phillips et al.， 2012]的想法，以導出新的啓發(fā)值(heuristic values)，這(zhè)個值用來激勵 MAPF 方法返回包括高速公路邊緣的路徑，這(zhè)種(zhǒng)方法能(néng)夠避免代理之間的迎面(miàn)碰撞(head-to-head collisions)，并實現其運動的一緻性和可預測性。例如，在 Kiva 倉庫系統中，我們可以沿著(zhe)存儲位置之間的狹窄通道(dào)設計高速公路，如圖2中的箭頭所示。我們已經(jīng)在模拟的 Kiva 倉庫系統中證明，這(zhè)樣(yàng)的高速公路能(néng)夠顯著加速 MAPF 方法，同時保持期望的 MAPF 解決方案成(chéng)本的有限次優性。 TAPF 和 PERR 例子的問題結構也可以利用相同的方法。在可行性研究中，我們還(hái)開(kāi)發(fā)了與用戶提供公路相媲美的自動生成(chéng)公路的方法。

5 解決不完美的規劃執行能(néng)力

最先進(jìn)的 MAPF 或 TAPF 方法可以在合理的計算時間内爲數百個代理找到最佳的或者在用戶提供的次優性保證下的不會(huì)發(fā)生碰撞的路徑。它們甚至在雜亂而緊湊的環境中也能(néng)正常工作，如Kiva 倉庫系統。然而，代理通常具有不完美的規劃執行能(néng)力，并且不能(néng)完美地同步它們的運動，這(zhè)可以導緻頻繁的重新規劃并浪費時間。因此，我們提出了一個框架，使用一個簡單的時間網絡來有效地後(hòu)期處理 MAPF 解決方案并創建一個規劃執行安排，這(zhè)适用于非完整機器人(non-holonomic robot)，考慮到它們的最大的平移和旋轉速度，提供了一個機器人之間安全距離和松弛邊界(定義爲最新和最早進(jìn)入時間的地點的差異)的保證，以緩解不完美的規劃執行并避免在許多情況下的時間密集的重新規劃[Honig ¨ et al.， 2016]。這(zhè)個框架已經(jīng)在仿真和真實機器人中得到評估。TAPF 和 PERR 方法也可以在同一框架中應用。未來工作中要解決的問題包括增加用戶提供的安全距離、額外的運動約束、不确定性規劃和重新規劃。

6 結論

我們讨論了四個研究方向(xiàng)，以解決當將(jiāng) MAPF 方法推廣到實際場景中和探索問題結構或現有 MAPF 方法時出現的問題。我們的目标是爲在 MAPF 領域工作的研究人員指出有趣的研究方向(xiàng)。