在實際應(yīng)用中，一個倉庫內(nèi)多個AGV協(xié)作完成訂單是不可或缺的部分，而且多個AGV機器人共同運輸?shù)倪^程中同時進行路徑規(guī)劃需要一定的算法做支撐，本文在一個倉庫內(nèi)多個AGV協(xié)作進行路徑規(guī)劃的方向上進行算法的研究，對其原理和實現(xiàn)進行分析和介紹。
2. 分析
首先，我們的背景設(shè)置在物流倉庫，針對倉庫中常見的入庫、揀貨、出庫等具體的任務(wù)細節(jié)進行分析，來了解我們AGV所面臨的場景。
傳統(tǒng)的方式一般采用靜止的貨架，入庫時將商品運輸?shù)街付ㄘ浖芮埃斯ど霞苋霂欤瑨洉r人工去到指定的貨架揀選訂單對應(yīng)的商品打包出庫，引入AGV之后，模式將發(fā)生改變，我們會在倉庫規(guī)劃指定的入庫區(qū)、揀選區(qū)，AGV會將包含訂單的貨架動態(tài)地運輸?shù)綊x區(qū)，排隊等待人工或者機械臂揀選到指定的訂單揀選筐內(nèi)打包出庫，完成揀選后將貨架運輸至指定位置。
所以，引入AGV之后，我們面臨的問題是為了最大限度的提高效率，多個AGV如何避免擁堵和碰撞，如何對每個AGV規(guī)劃出更好的行走路線，怎樣才能讓每個AGV花最小的代價，完成更多的任務(wù)，將是此文討論的重點。
3.問題拆解
要使得多個機器人在道路規(guī)劃上最優(yōu)，無非是在單個小車規(guī)劃路徑時考慮其他小車的行駛路線，進而選取最優(yōu)的一個行駛方案。另外，不同于室外場景，我們在倉庫中規(guī)劃小車路徑，整個道路都是可以設(shè)計的，所以我們的問題可拆解為：
(1) 倉庫中道路的設(shè)計；
(2) 獲取到其他小車的路徑行駛狀態(tài)；
(3) 定義可能的道路擁堵；
(4)規(guī)劃最短路徑；
(5) 交通管制。
3.1 倉庫中的道路設(shè)計
一些常見的道路設(shè)計如圖1和圖2，根據(jù)實際的應(yīng)用場景來布局，考慮的因素包括倉庫的結(jié)構(gòu)，商品的種類等，根據(jù)實際測試或模擬來選取最優(yōu)的設(shè)計。
圖1： V字型道路設(shè)計
圖2： 井字型道路設(shè)計
3.2 獲取到其他小車的路徑行駛狀態(tài)
要做到全局路徑規(guī)劃，必須得到每一個時刻小車的位置和運行狀態(tài)，所以必須和小車建立起穩(wěn)定的通信系統(tǒng)，一般采用無線局域網(wǎng)的方式，用TCP建立連接，選取合適的WIFI通道來保證小車和全局路徑規(guī)劃系統(tǒng)的通信的穩(wěn)健。
3.3 定義可能的道路擁堵
在倉庫的道路規(guī)劃完成之后，首先要考慮的因素是可能的道路擁堵情況，一般小車在倉庫中都是直線行走，需要轉(zhuǎn)彎時要停在原地，原地旋轉(zhuǎn)90°或180°之后繼續(xù)直線行走，所以每個轉(zhuǎn)彎都有機會造成當前道路擁堵。另外，同一條道路車流量較大時，也會造成道路擁堵，加上路口會車的情況，主要造成道路擁堵的有轉(zhuǎn)彎、會車和車流量較大3種常見的可能情況。
3.4 規(guī)劃最短路徑
最短路徑規(guī)劃是全局路徑規(guī)劃的核心，要從地圖上的一個位置到達另一個位置，在中間有障礙物以及考慮到可能的道路擁堵情況，必須使用一個路徑搜索算法來尋找從初始點到目標點的一條最短路徑，常見的搜索路徑的算法有廣度優(yōu)先算法、深度優(yōu)先算法、Dijkstra算法、A*算法等，廣度優(yōu)先算法和深度優(yōu)先算法適用于樹形結(jié)構(gòu)求解最短路徑或最小權(quán)重的場景，環(huán)狀結(jié)構(gòu)求解最短路徑一般采用Dijkstra算法，A*算法是靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法。
每一種算法都有其應(yīng)用場景，對于我們?nèi)致窂揭?guī)劃的場景，我們的地圖更容易轉(zhuǎn)換成柵格地圖，而A*算法在柵格地圖上搜索最短路徑有明顯的優(yōu)勢，而且方便于修改加上我們道路擁堵場景的考量，所以我們以A*算法為首選最短路徑算法，進而分析實現(xiàn)全局路徑規(guī)劃。
3.5 交通管制
交通管制主要應(yīng)用于會車和并流場景，一方面為了避免車輛碰撞，另一方面路口會車比較常見，處理不好會導(dǎo)致車輛死鎖，車輛相互等待，進而導(dǎo)致任務(wù)無法完成，也是全局路徑規(guī)劃的核心算法，常見的會車場景如圖3。
圖3： 路口會車
4. 核心算法實現(xiàn)
路徑規(guī)劃算法的核心主要在于最短路徑的規(guī)劃和交通管制，這里將對一種最短路徑規(guī)劃算法和交通管制算法進行算法剖析，進而設(shè)計出一套完整的全局路徑規(guī)劃算法。
4.1 A*算法規(guī)劃最短路徑
A*算法類似于圖論中尋找最優(yōu)樹，通常是通盤考慮選擇某一路徑的路徑耗費，在所有可通過的路徑中總有一條路徑相對于其他任何可通行的路徑來說是耗費最少的。在圖論中尋找最佳路徑時每一條的路徑耗費是已知且固定的，但在用A*算法求解最佳路徑時，沿著不同的路徑前進，盡管是同一節(jié)點但其耗費可能是不同的，這便是啟發(fā)式尋路的精髓。
運用此方式時，首先將實際問題抽象出來，用矩陣的形式表示問題中的各元素，包括起點位置，目標點位置，以及出現(xiàn)的障礙物。我們會逐漸地發(fā)現(xiàn)在尋路方面都是將實際問題抽象地用矩陣表示，之后通過對矩陣的操作模擬實現(xiàn)尋路過程。
其基本思想是以起點為中心，其周圍緊鄰的8個點都通過指針指向它，在其周圍點內(nèi)選擇最佳路徑點并以它為中心點將其還未建立指針聯(lián)系的周圍點（可行的，這在后文中解釋）通過指針指向它，并選擇最佳路徑點再以此點為中心尋路直到尋找到點的周圍點中有目標點，這樣尋找的路徑就通過指針一一連接起來了，最后通過輸出這些點就是尋找的路徑了。
下文主要通過以下幾個方面來逐步分析A*算法的尋路過程：
(1)將實際問題抽象化為矩陣表示
抽象出的矩陣如圖4，其中綠色區(qū)域表示起始點，紅色區(qū)域表示目標點，中間藍色區(qū)域表示障礙物（如不可通過的高山或是河流），黑色區(qū)域表示可產(chǎn)生路徑的區(qū)域。
(2)以起點為中心尋找到下一節(jié)點
如圖5所示，以起點為中心與之緊密相鄰的8個點是其所尋路徑上可到的下一點，且都以指針的形式將中間當前點作為與其緊鄰的周圍點的父節(jié)點。對于這8個點，應(yīng)該選擇哪一點作為尋路的下一個起點呢，A*算法中建立了兩個列表，一個為開啟列表（用于存儲所有當前點的可到點（除去已經(jīng)在關(guān)閉列表中的點、障礙物點）），另一個為關(guān)閉列表（里面存儲已經(jīng)到過的點，已經(jīng)在關(guān)閉列表中的點在下一次尋路的過程中是不會再次檢查的，這也說明尋路的線路不會有相交的可能）。
(3)選擇下一節(jié)點
將起點加入關(guān)閉列表，在以后的尋路過程中不再對其進行檢查，接下來就是在這8個點中選擇一個作為下一路徑點，選擇的原則是在其中尋找路徑耗費最小的節(jié)點，
其權(quán)值用F表示，F(xiàn)=G+H
其中G表示從起點開始，沿著產(chǎn)生的路徑，移動到指定方格上的路徑耗費；如圖6所示，以起點為中心其緊鄰周圍點有上下左右、對角線方向上的8個點，以上下左右移動路徑耗費為10，對角線耗費為√2*10，約為14。
其中H表示從路徑所在的當前點到終點的移動路徑耗費，計算方法為當前點到目的點之間水平和垂直的方格的數(shù)量總和，然后把結(jié)果乘以10。
從圖7可以看出，起始點右邊點的權(quán)值F最小，故將其作為下一路徑點。
(4) 繼續(xù)搜索
把路徑點從開啟列表中刪除，并添加到關(guān)閉列表中。檢查與此點緊鄰的8個點（忽略在關(guān)閉列表中或者不可通過的點），把他們添加進開啟列表，如果存在還有點沒有添加進開啟列表，則將路徑點作為此類點的父節(jié)點并添加進開啟列表。
如果所有可行的緊鄰點已經(jīng)在開啟列表中，對每一緊鄰點檢查目前這條路徑到是否比上一路徑點到這一緊鄰點的路徑耗費要小，如果不是則什么都不用做（如圖8所示）從原始起點到其緊鄰的右下方的點，按照新產(chǎn)生路徑G值：G1=10+10=20，而原始路徑G值G2=14，即新產(chǎn)生路徑的G值比原始路徑的G值大，而它們的H值相同（為同一點）故原始路徑的F值比新產(chǎn)生路徑的F值要小，不做任何處理，繼續(xù)下一步尋路。如果是，那就把相鄰方格的父節(jié)點改為目前選中的方格，說明新產(chǎn)生的路徑的移動耗費更小。
(5) 重復(fù)上一搜索過程直至結(jié)束
搜尋過程結(jié)束分為兩種情況：一種是目標點加入關(guān)閉列表，搜索正常結(jié)束，找到路徑。另一種情況是目標點未找到但開啟列表已經(jīng)為空，意味著沒有找到從起始點到目標點的路徑，搜索結(jié)束。
搜索過程如圖9所示，從中可以看出從起點到目標點之間有指針指向一致的一條路徑，這便A*算法是搜尋到的路徑。在路徑點上添加紅色點突出顯示，此即為從起始點到終點的一條路徑。
整個尋路過程整理如下：
1) 起始格加入開啟列表；
2) 重復(fù)如下的工作：
a) 尋找開啟列表中F值最低的點。我們稱它為當前點；
b) 把它加入關(guān)閉列表；
c) 對緊鄰的8格中的每一點
* 如果它不可通過或者已經(jīng)在關(guān)閉列表中，略過它。反之如下：
* 如果它不在開啟列表中，把它添加進去。把當前點作為這一格的父節(jié)點。記錄這一點的F、G和H值；
* 如果它已經(jīng)在開啟列表中，用G值為參考檢查新的路徑是否更好。更低的G值意味著更好的路徑。如果是這樣，就把這一點的父節(jié) 點改成當前點，并且重新計算這一點的G和F值。改變之后需要重新對開啟列表按F值大小排序。如果不是則不需要做后面改變指針指向并重新計算G、F值的工作；
3) 停止搜索，分為兩種情況：
* 當目標點添加入了關(guān)閉列表，這時候路徑被找到，搜索正常結(jié)束；
* 沒有找到目標點，但開啟列表已經(jīng)空了，此時未找到合適的路徑，搜索結(jié)束；
4) 保存路徑。從目標點開始，沿著每一點的指針指向移動，直到回到起始點，輸出路徑。
4.2 基于鎖格機制的交通管制
車輛道路規(guī)劃完成后，多個小車同時開始行走，多條道路小車會車的情況不可避免，會車時候車輛主要會出現(xiàn)跟隨，相向而行，十字路口或丁字路口的情況，跟隨的時候車輛前方會有傳感器避免跟隨碰撞，為了避免十字路和丁字路會車碰撞，會車時候采取鎖格的方式，即：
(1) 每輛小車行走一步，將前面即將行走的兩步的點鎖住；
(2) 小車鎖格時發(fā)現(xiàn)即將鎖的地圖的點已經(jīng)被鎖住，則兩車協(xié)商看哪個優(yōu)先級高，哪輛車先行，另一輛車停車等待；
(3) 小車走過之后將解鎖，等待的時候可以重新鎖住即將行駛的點，繼續(xù)往前行走；
(4) 循環(huán)一直每一步都進行鎖格操作。
4.3 全局路徑規(guī)劃
在規(guī)劃當前小車路徑時，要在考慮到道路擁堵的情況下去規(guī)劃最短路徑，以滿足整體規(guī)劃結(jié)果最優(yōu)，使用A*算法，用G值為參考檢查新的路徑是否更好， 將地圖中其他小車規(guī)劃的路徑的點的G值增加，即可盡量避免搜索到相同的路徑，同樣的道理，在車輛需要轉(zhuǎn)彎的時候，也同樣增加轉(zhuǎn)彎下一點的G值，從而規(guī)劃路徑盡量避免轉(zhuǎn)彎的情況出現(xiàn)，來達到整體效率最高，全局路徑最優(yōu)。
此外，由于路徑規(guī)劃都是靜態(tài)規(guī)劃的路徑，車輛在行走過程中同時需要對每輛小車進行鎖格的交通管制，來保證車輛不會相撞。
5.總結(jié)
本文主要對倉庫內(nèi)多AGV協(xié)作的全局路徑規(guī)劃進行了研究，并介紹了一種可能的實現(xiàn)算法方案，從倉庫中道路的設(shè)計，擁堵的考量等角度簡單全局路徑規(guī)劃需要考慮的維度，對最短路徑規(guī)劃和交通管制策略進行的詳細的分析和應(yīng)用設(shè)計。（文章來源于IT刊百家號）
