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