點擊藍字

關注我們

AI TIME歡迎每一位AI愛好者的加入！

李嬌陽：南加州大學計算機系博士四年級學生，導師Sven Koenig, 本科畢業于清華大學自動化系。目前主要的研究方向為人工智能，多智能體規劃，組合優化，搜索算法等。以第一作者在AAAI，IJCAI，ICAPS，AAMAS等頂級會議上發表論文十余篇。曽擔任Artificial Intelligence, IEEE Robotics and Automation Letters等期刊審稿人，AAAI，IJCAI，ICAPS等會議評審委員會委員，IJCAI會議評審委員會資深委員， 并組織舉辦了IJCAI-2020多智能體路徑規劃研討會。曾獲得2019年南加州大學技術商業化獎，2020年高通獎學金，2020年ICAPS最佳學生論文， 以及2020年NeurIPS Flatland挑戰賽（Multi-Agent Reinforcement Learning on Trains）第一名。本次報告的其中一項工作（論文1）在Amazon Robotics實習期間完成。

一、背景

多智能體路徑規劃，英文叫Multi-Agent Path Finding，簡稱為MAPF。它本質上是一個數學問題，通過給每個機器人規劃一條路徑，保證這些路徑不相撞，并最小化總的運行時間。

它有很多實際應用，其中一個是倉儲系統。近年來機器人倉儲系統吸引了很多人的注意，出現了各種各樣的倉儲系統，比較典型的有亞馬遜的Kiva system，以及sorting center，和一些比較新的系統。這些系統本質上是給成百上千個機器人同時做規劃路徑，然后保證它們既不相撞，同時又能很快的到達目的地。

傳統方法采用single-agent方法，通過給每一個機器人規劃它們的最短路，或者最小時間路徑。如果兩個機器人可能相撞，就用一些簡單的交通規則處理，比如說其中一個機器人減速或換一條路。但這種方法在簡單的系統中工作較好，一旦機器人數量或密度增大，就會出現擁堵，導致整個系統效率變低。而MAPF solver把所有機器人的路徑一起規劃，會考慮到各種碰撞的可能性。在同等情況下，MAPF solver可以很好的去調度所有的機器人的路徑，使得它們可以順暢的到達目的地。

這張圖展示了不同機器人個數下，系統吞吐量的變化。可以看到在一開始的時候，兩種方法很接近，基本上保持線性增加，但是當機器人個數到一定值的時候，Single-agent會出現擁堵，導致系統的吞吐量增長率開始下降，經過巔峰之后，增長率開始下降，這是因為系統中出現了嚴重的交通擁堵，導致系統開始癱瘓。而對于MAPF solver來說，在測試的1000個機器人之內，吞吐量幾乎保持線性增長。

除了倉儲系統，其還可以應用于交通系統，比如火車調度的例子。MAPF solution可以在幾分鐘之內調度3000多個火車到他們的目的地。

除火車調度以外，一個類似的應用是飛機調度，這是我之前和NASA合作的項目，我們如何用MAPF的方法來控制飛機的起飛與降落。這個問題的難點在于，飛機的控制包含有很多不確定性因素，例如天氣干擾，人為因素干擾，所以我們要把MAPF模型和隨機模型結合起來，考慮到各種因素干擾，控制整體的調度與運行。

MAPF還可以被用到很多機器人系統中，比如說自動叉車，自動停車系統，無人車、無人機以及一些水下機器人。對這些系統一方面要避免碰撞，另一方面要去考慮各種機器人不同的動力學約束，比如說速度、加速度、轉角，以及各種干擾的約束。如何把MAPF與這種約束結合起來，也是一個難點。

那么總的來說，其實MAPF的研究主要有兩大方向：

• 一個是針對MAPF本身的問題，如何提高現有的算法效率和解的質量。

• 然后另一個是把MAPF應用到實際問題當中的時候，如何處理不同問題所帶來的不同約束。

本次AAAI，我一共有4篇文章被選中，我會依次介紹它們。

• 第一篇文章是關于如何利用Heuristic方法加速現有的MAPF算法。

• 第二篇文章研究了MAPF的一個延伸問題，叫K-Robust MAPF，它的邏輯就是很多情況下機器人是不會嚴格的執行每一個動作，可能會有延遲。所以當我們考慮到有一定延遲的時候，我們仍然希望最終給的解保證沒有碰撞。這種情況下，這個問題會帶來很多的 Symmetry因素，如何去消除這些因素，就是這篇文章所要解決的問題。

• 第三篇文章就是剛才提到的倉儲系統，如何去應對實時的、大規模的、不斷動態變化的倉儲系統，用我們現有的MAPF solver來解決這種Lifelong MAPF問題。

• 第四個也是剛才提到的，考慮到機器人的動力學約束的時候，如何把它和MAPF模型結合起來。

進一步定義MAPF，假設時間是離散化的，在每一個行動點，機器人可以選擇兩種動作，一種是移動到相鄰的位置，一種是在當前位置等待，兩種動作只需要一個行動點，而且他們的cost也是1。碰撞被稱為collisions或者是conflicts，其有兩種類型，一個叫vertex conflict，即在任意時刻內，有兩個agent在同一時間到達同一位置；另一種叫edge conflict，即兩個agent在同一時間去交換彼此的位置，或經過同一條邊。所以我們的任務就是生成指令，使機器人既能到達目的地，也不會發生碰撞，同時具有最小旅行時間和。

這里有一個比較主流且具有較好效果的MAPF算法叫Conflict-Based search或者CBS。它是一個兩層的算法，其邏輯為假設一個機器人想從A2到D3，一個機器人想從B1到C4。CBS最開始先給每一個機器人規劃一條最短路，忽略另一個機器人或忽略其他機器人。檢查當前的最短路有沒有collisions，算法根據其中一個機器人是否執行當前指令分別生成兩個子樹并且加一個額外的約束。之后在各自的子樹中重新規劃路線，左邊給agent 2重新規劃一條路，右邊給agent 1重新規劃一條路。重復之前的過程，直到找到一個節點，里面的路徑沒有任何collisions。

二、EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding

第一篇我們提出了一個新的算法叫EECBS，這個算法從heuristic search的角度來分析如何來加速CBS。heuristic search中最經典的算法就是A*，CBS的上層和下層都使用了A*，如果想讓其運算更快，一個很常見的算法是用wA*。通過給h乘一個w，使得f更偏向于h的值，這樣可以更快找到解，并且解在最壞情況下不超過w倍最優解。但是其表現會比CBS更差。這是因為在CBS中，h的值沒有考慮中途可能包含的碰撞信息。于是在1982年有人提出算法來解決這種問題。A*_ε里有兩個heurisitic，一個是傳統的A*會用到的admissible cost heuristic，然后另一個是distance to go heuristic d。這個d表示當前節點到goal node還需要展開多少個節點，heuristic用于估計這個事情。當人們把放到CBS框架中替換A*之后，發明了算法ECBS，它是目前最好的bounded suboptimal MAPF solver。

ECBS通過一個open list存入所有的節點，并且按照f的值去排列。最小的叫f min，其是最優解的一個lower bound。而bounded suboptimal的要求只需要最終解的cost比wf min小。所以ECBS用d在橙色區域內選擇合適的node作為解。但是實際中會有兩個缺陷，第一個是因為f min基本不會變，也就意味著橙色區域沒有解的情況下也不會發生變化，第二個是獲得的解會比真實解大。

為了解決上述的弊端，我們提出了explicit estimation CBS，EECBS。這個算法中包含了explicit estimation search和三個heuristic。第一個是A*中的h，第2個中的distance-to-go d，第三個是cost-to-go heuristic h’。第三個h’用于估計cost的增加量，并且不需要admissible，比h的準確度更高。

?1. 第一個heuristic將問題轉換為vertex cover，然后求解。

?2. 第二個heuristic計算collisions的個數。

?3. 第三個是online learning方法，在搜索過程中觀察前面h和d的誤差，然后反饋矯正得到更精確的h’的預估計。

?4. 結合三個heuristic就可以克服之前ECBS提到兩個缺陷。

?5. 此外，我們在EECBS中增加了近年來一些新的CBS improvements。

通過實驗對比，CBS最多能解決的agent個數小于200，而EECBS可以達到1000個以上，而解的質量與最優解只有2%的誤差。

三、Symmetry Breaking for k-Robust Multi-Agent Path Finding

第二個工作關于對稱性以及K-robust MAPF。觀察上圖發現每一個機器人可以有多條不同的路徑。但是任意一條路徑在黃色區域都有交集，這被稱為symmetry。右圖中，橫坐標代表黃色區域的面積，縱坐標代表解決相撞問題時CBS的節點個數，圖像顯示隨著面積增加，節點個數指數增大，尤其超過8×8后趨于不現實。

因為機器人不能夠精準的以預定速度執行命令，所以需要k-robust MAPF制定計劃，即對于任意數量的agent，延遲不超過k個時間單位，仍然可以保證不相撞，在左圖中表現為后面的尾巴。但是這樣也造成了更多的對稱性缺點，中間圖中是黃色面積圖的延伸，可以看到隨著k的增加，CBS需要的節點數也在增加。而右圖顯示的是隨著k增加，rectangle symmetry出現的頻率也在增加，會嚴重影響CBS效率。

為了解決上述問題，我們采用了一種名為symmetry-breaking constraints的想法，其運算邏輯是通過設計constraint來消除symmetry，從而縮小搜索空間，加速算法。應用于CBS中，當出現一個symmetry時，就子樹添加多個constraints，從而消除潛在的collision。而constraint的設計要遵循兩個原則，第一個是盡可能多的消除collision，第二個是盡可能保留潛在的解。

本篇文章的核心是如何設計constraints，主要從三類symmetry入手：

?1. 第一個是rectangle。

?2. 第二個corridor symmetry，它需要解決兩個機器人如何從不同方向經過一個狹窄的過道。

?3. 第三個target symmetry，它面對的是一個agent已經到了它的目的地并且停止運動，另一個agent如何越過它。

我們在多種地圖的情況下進行了測試，例如隨機生成地圖、游戲地圖、倉庫和火車網絡，本文的方法對CBS有著顯著的提高，對比之前可以對多一倍的數量求解。

四、Lifelong Multi-Agent Path Finding in Large-Scale Warehouses

第三個是在亞馬遜實習是完成的，稱為Lifelong MAPF，意圖解決機器人在到達目的地后立即獲得新任務的實時動態系統。

目前有三種方法：

?1. 第一種從一個解決新問題的角度來思考，但是這種算法速度極慢，圖中的文章只能解決20個agent。而且還需要知道所有的goal location，這對于倉儲系統不現實。

?2. 第二種是在每個行動點多運行一次MAPF solver，這個方法雖然只關心起始點，但是需要獲得新任務后重新計算，造成重復性工作。此外實際系統中，機器人不會在每個time step中等待系統重新制定計劃。

?3. 第三種是只針對有新任務的機器人做路徑規劃，機器人嚴格執行這個計劃，并且不會進行改變。這個方法的缺點是解的質量差，且會出現擁堵，而且因為只涉及一部分agent，所以會出現無解的情況，只能使用于某一類地圖，而且它同樣要求每個行動點進行replan。

本文提供了一個新的思路來解決這個問題，稱為Rolling-Horizon Collision Resolution。這個算法首先由用戶提供參數h，之后每h timestep都進行replan。因為系統是在動態變化的，所以我們在當前replan只處理當前的collision，即在每h timesteps去處理一個windowed MAPF instance。之所以叫windowed MAPF基于兩點，第一點是前w個行動點的collision，其中w大于等于h；第二點是一個agent可能會有多個目的地，為的是在h timestep之前能夠保持持續行動。上圖是一個大概的展示，橫軸為時間，在0的時刻，給所有agent完整的plan，但是只處理前w步的collision，到第h個timestep時，重復上述步驟。

對于這個算法，一共進行了兩組對比實驗，第一組是和之前的方法三做對比。可以看到質量要比方法三好，但是時間在不考慮解的質量時要略遜色于方法三。所有對于適合的地圖，并且單純追求速度的話可以使用方法三，但是追求質量的話，本文的方法更合適。

第二個實驗選擇了方法三不適用的地圖，在此基礎上使用了不同的w大小，觀察對解的質量的影響。首先觀察吞吐量，隨著w的增加，吞吐量變化不大，這是因為只處理眼前的collision而不是所有之后可能發生的collision。另一方面，算法的速度隨著w的增加會減慢，而且還涉及了能夠處理agent的數量，例如當w趨于無窮，能解700個agent，而w為5或10就可以解1000個以上的agent。

這個方法有4個優點：

• 它適用于任何地圖

• 我們不需要每個時刻都去replan，而是由用戶決定其頻率

• 有了W之后，算法速度提升明顯

• 在提升速度的同時能夠保證解的質量

五、Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances

最后一篇文章是如何將MAPF和機器人的各種constraint結合，稱為multi-robot motion planning。這里有一個比較典型的二輪車模型，我們會獲得機器人所在位置的x、y，以及方向θ，速度和轉速。輸入是兩個control input，一個是力，一個是力矩。因為考慮到機器人不會精確執行每一個動作，面臨非線性，nonholonomic，high-dimension dynamics，以及外界干擾的情況，所以成為一個離散空間和離散時間的問題。

重新思考MAPF算法，其本質就是考慮很多路徑會不會有相撞情況，如果有就處理其中的conflict。而這里我們沒有采用CBS，因為其對于連續時間中，取一個點，會使得constraint沒有意義，因為其需要一個位置和一個timestep。所以我們采用了priority-based search，即PBS，其與CBS的區別在于，當我們要處理一個conflict的時候，它給兩個機器人的其中一個指派一個更高優先級，優先級低的那個 agent就要去避免和優先級高的那個agent去撞。左圖就是agent 1優先級高于agent 2，所以要給agent 2重新規劃路徑。這樣對于collision的問題就迎刃而解，接下來就是在不斷的plan和replan的情況下，如何使得算法運行快。

我們將piecewise linear path作為介質，稱為PWL path。它將一個時間點和位置，即x，t組合成一個微point，兩個微point之間通過直線段連接。在機器人實際執行過程中，我們用tracking controller作為跟蹤器，讓機器人跟隨這條路徑。而機器人會有誤差，所以我們做了reachability envelop去分析，例如直線情況下，機器人的偏離誤差，即maximum tracking error，以及最壞情況下，它至少需要花多久時間，從一個點移到另一個點，minimum tracking duration。計算出這兩個誤差的bound之后，通過MAPF solver獲得最終解。

這里舉個例子，如果有兩個機器人，要通過中間的過道。

第一步先獲得maximum tracking error，增大o1,o2障礙物面積，從而保證只要機器人的piecewise linear path在白色區域，那么就不會與障礙物相撞。

第二步給每個機器人找一條piecewise linear path，通過PBS邏輯檢查是否會相撞。當前情況下會相撞，于是賦予機器人1更高的優先級，對于機器人2來說，機器人1就是移動的障礙物。同時考慮到其覆蓋面積，編碼時通過這些約束就獲得另一條規劃路徑。之后通過tracking controller，使得機器人跟隨兩條路徑，就可以保證不相撞的情況下到達目的地。

上圖是算法的框架圖，稱為S2M2，它包含了三部分：

• 第一部分Reachability Analysis，用于計算maximum tracking error和minimum tracking duration。

• 第二部分給每一個機器人規劃一條piecewise linear path，將其編碼成混合整數規劃問題。

• 第三部分把Single Agent Motion Planner和PBS結合，去處理agent之間的碰撞，得到collision free piecewise linear path，保證機器人能無碰撞的到達目的地。

第一個實驗在2D環境下與ECBS-CT方法做對比。不論從時間還是質量來看，我們的方法都占據優勢，最好的情況能減少一半的時間，尤其是預處理時間。我們的預處理只做reachability analysis，大概只需要1s；而ECBS-CT則最多花費1800 s以上。

我們還在3D環境下與當前最好的求解器做了對比。我們解的質量隨著agent的數量，優勢盡顯。對于時間，我們的預處理依然很快，而對方需要1500 s以上做離散化處理。

六、結論

最開始說到MAPF的研究主要有兩大方向，一個是如何改進現有的算法，一個是在實際應用中如何處理約束。這4篇文章契合了這幾個方向。

第一篇利用heuristic search方法，來指導搜索方向，從而加速算法。第二篇通過設計symmetry-breaking constraints來減小搜索空間，從而加速搜索算法。

剩余兩篇將目光集中于應用，第一個是在講在lifelong MAPF問題中，我們提出rolling-horizon collision resolution框架，通過只處理眼前的collision，從而加速算法。

最后一個在multi-robot motion planning的時候，考慮robot dynamics。通過piecewise linear path為介質，把tracking controller和MAPF就結合起來，設計了高效求解multi-robot motion planning的算法。

REF

個人主頁：

https://jiaoyangli.me/

論文標題：

Lifelong Multi-Agent Path Finding in Large-Scale Warehouses

EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding

Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances

Symmetry Breaking for k-Robust Multi-Agent Path Finding

論文鏈接：

https://arxiv.org/abs/2005.07371

https://arxiv.org/abs/2010.01367

https://arxiv.org/abs/2012.09052

https://arxiv.org/abs/2102.08689

整理：閆? ?昊

審稿：李嬌陽

排版：岳白雪

AI TIME歡迎AI領域學者投稿，期待大家剖析學科歷史發展和前沿技術。針對熱門話題，我們將邀請專家一起論道。同時，我們也長期招募優質的撰稿人，頂級的平臺需要頂級的你！

請將簡歷等信息發至yun.he@aminer.cn！

微信聯系:AITIME_HY

AI TIME是清華大學計算機系一群關注人工智能發展，并有思想情懷的青年學者們創辦的圈子,旨在發揚科學思辨精神，邀請各界人士對人工智能理論、算法、場景、應用的本質問題進行探索，加強思想碰撞，打造一個知識分享的聚集地。

更多資訊請掃碼關注

?

（直播回放：https://www.bilibili.com/video/BV1X54y1h7qm?share_source=copy_web）

（點擊“閱讀原文”下載本次報告ppt）

總結

以上是生活随笔為你收集整理的大规模多智能体路径规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。