將多代理路徑尋找推廣到真實世界應用：四大研究方向概覽

機器之心報道

參與：吳攀

近日，來自南加州大學、喬治亞理工學院和德州大學奧斯汀分校的研究者在 arXiv 上發布了一篇概述論文《Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios》，探討了將多代理路徑尋找方法推廣到實際場景時出現的問題與解決這些問題的四個研究方向。

摘要

多代理路徑尋找（Multi-agent path finding/MAPF）已在人工智慧、機器人、理論計算機科學和實際操作研究中得到大量的研究。本文討論了在將 MAPF 方法推廣到實際場景時出現的問題與解決這些問題的四個研究方向。我們強調的是解決這些問題的重要性，而不是為 MAPF 問題的標準模型開發更快的方法。

1 引言

多代理路徑尋找（MAPF，也叫多代理尋徑）在人工智慧、機器人、理論計算機科學和實際操作研究中得到大量的研究。（標準）MAPF的任務是為多個代理（agent）找到在給定圖（graph）中從其當前頂點（vertices）到其目標而不與其它代理髮生碰撞的路徑，同時優化成本函數（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]。

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

1. 為 MAPF 問題的標準模型開發更快的方法是不夠的，因為在許多實際情況下，可以利用新的結構或需要新的問題模型。

2. 僅將 MAPF 或其新的模型作為組合優化問題進行研究是不夠的，因為所產生的 MAPF 解決方案也需要執行。

我們從不同的角度討論了解決這兩個問題的四個研究方向：

1.在許多實際的多代理系統中，在為所有代理找到最佳路徑之前，代理先被劃分成組（team），然後給每個組分配特定的目標，每個代理需要從所在的組中被指定一個目標。我們已經為不同組的代理制定了組合目標分配和路徑查找（TAPF/target assignment and path finding）問題來解決這個困難。我們還開發了一個最佳 TAPF 方法，它可以擴展到幾十個組和數百個代理[Ma and Koenig, 2016]。

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

3.在許多實際的多代理系統中，代理運動（agent motions）的一致性和代理運動的結果可預測性是重要的（特別是在由人和代理共享的工作空間中），但是現有的 MAPF 方法沒有考慮這一點。我們已經分兩個階段探索了給定 MAPF 例子的問題結構：在第一階段，我們開發了一種為代理尋找路徑的方案，其中包含了由用戶提供的許多帶邊緣的高速公路（highways），這個方案達到了代理運動的一致性和可預測性[Cohen et al., 2015]；在第二階段，我們開發了自動生成高速公路的方法[Cohen et al., 2016]。

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

圖 1 ：（左圖）自動駕駛單元和可以被駕駛單元移動的存儲產品的存儲艙（storage pod）；（右圖）典型 Kiva 倉庫系統的布局（Wurman et al., 2008）

為了將 MAPF 方法推廣到實際的場景，我們現在展示這些研究方向的實用性，以證明解決這兩個問題與開發更快的 MAPF 問題的標準模型方法一樣重要（甚至更重要）。

2 代理組的目標分配和路徑查找（TAPF）的組合

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

• 來自 TAPF的（標準）MAPF 結果，如果每個組僅由一個代理組成，則組的數量等於代理的數量。目標到代理的分配是預先確定的，因此代理是非匿名的（不可交換的）。

• 如果只有一個組（包含所有代理），則 MAPF 的匿名變數（也稱為目標不變的 MAPF）來自 TAPF。代理可以被分配任何目標，因此是可交換的。它可以在多項式時間內用基於流的 MAPF 方法（flow-based MAPF method）得到最優解[Yu and LaValle, 2013a; Turpin et al., 2014].

當前最先進的最優 TAPF 方法——稱為基於碰撞的最小成本流（Conflict-Based Min-Cost Flow）[Ma and Koenig, 2016]——結合了搜索和基於流的 MAPF 方法。它可以推廣到幾十個組和數百個代理。

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

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

• PERR 中的包裹可以被視為在（標準）MAPF 中的自己移動的代理。

• 允許在相鄰頂點中的兩個包裹在 PERR 中交換它們的頂點，但是在相鄰頂點中的兩個代理不允許在（標準）MAPF 中交換它們的頂點。

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

致謝和參考文獻（略）