物流機(jī)器人路徑規(guī)劃仿真研究

文 / 龔志鋒 石 超 閆 豐 陳建銀

隨著電子商務(wù)高速發(fā)展，對(duì)倉(cāng)儲(chǔ)物流的效率要求越來(lái)越高，隨之而來(lái)的便是以倉(cāng)儲(chǔ)物流機(jī)器人（AGV）為代表的自動(dòng)化浪潮，智能倉(cāng)儲(chǔ)的概念也應(yīng)運(yùn)而生，以在提高倉(cāng)儲(chǔ)揀選效率的同時(shí)，應(yīng)對(duì)不斷上漲的勞動(dòng)力成本。目前，揀選作業(yè)是庫(kù)內(nèi)最主要的環(huán)節(jié)，至少占據(jù)50%的庫(kù)內(nèi)操作成本，決定著客戶的服務(wù)體驗(yàn)水平，因此如何利用物流機(jī)器人進(jìn)一步提升揀選作業(yè)效率，對(duì)倉(cāng)儲(chǔ)物流具有重要意義；而高效的路徑規(guī)劃算法，正是決定物流機(jī)器人作業(yè)效率的關(guān)鍵因素，是物流機(jī)器人能夠流暢運(yùn)行的核心之一。

一、研究背景

A＊算法是一種常用的啟發(fā)式路徑查找和圖形遍歷算法，其改進(jìn)自Dijkstra算法，擁有較好的性能與準(zhǔn)確度。但是對(duì)于AGV而言，最短路徑往往并不是最合理的路線，其路線具有更多的影響因素：

1. AGV與機(jī)動(dòng)車一樣，一般只能夠向前行走，轉(zhuǎn)向需要花費(fèi)額外的時(shí)間，因此路線應(yīng)盡可能減少轉(zhuǎn)向次數(shù)。

2. 多輛AGV同時(shí)運(yùn)行時(shí)，其互相之間路線會(huì)出現(xiàn)相交與沖突，規(guī)劃路徑時(shí)應(yīng)盡可能避免路線沖突。

3. 當(dāng)AGV不可避免的出現(xiàn)擁堵時(shí)，能夠根據(jù)當(dāng)前路況重新規(guī)劃一條新的路線。

針對(duì)以上影響因素，本次研究遵循A＊算法的基本方法，對(duì)A＊算法中的的F值計(jì)算進(jìn)行更加深入的探索，使其計(jì)算方法更加合理，能夠更好地契合AGV的路線規(guī)劃需要。

二、算法思路

本文最終將算法通過(guò)仿真程序?qū)崿F(xiàn)，考慮到影響AGV行走的各項(xiàng)因素，具體會(huì)從A＊算法的F值計(jì)算與任務(wù)管理兩方面著手，二者配合以實(shí)現(xiàn)AGV的流暢運(yùn)行。

1. 代價(jià)值計(jì)算優(yōu)化

為了使邏輯思路更加清晰，本文使用結(jié)構(gòu)體來(lái)表示每一個(gè)節(jié)點(diǎn)。

（1）轉(zhuǎn)向代價(jià)

原A＊算法中計(jì)算F值時(shí)，由移動(dòng)代價(jià)與估算成本相加得到，當(dāng)有多條最短路徑時(shí)，其只會(huì)隨機(jī)返回一條最短路徑，并沒(méi)有考慮路徑的拐彎因素，而現(xiàn)實(shí)情況是，AGV需要停止后才能進(jìn)行原地旋轉(zhuǎn)，會(huì)花費(fèi)額外的時(shí)間。對(duì)此，本文在計(jì)算中加入反映AGV旋轉(zhuǎn)的轉(zhuǎn)向代價(jià)，使得到的結(jié)果更加偏向于直線行走。

原F值計(jì)算公式為：

式中：

F，當(dāng)前節(jié)點(diǎn)的總代價(jià)；

G，從起點(diǎn)移動(dòng)到當(dāng)前節(jié)點(diǎn)的移動(dòng)代價(jià)；

H，當(dāng)前節(jié)點(diǎn)到終點(diǎn)的估算成本，

本文采用曼哈頓距離。

在公式中加入新的變量R，代表AGV的轉(zhuǎn)向代價(jià)。如圖1所示，共有3條路線，分別為ADE、BDE、CDE，當(dāng)前研究節(jié)點(diǎn)為E，其父節(jié)點(diǎn)為D，其中2條路線將會(huì)發(fā)生旋轉(zhuǎn)，因此對(duì)于節(jié)點(diǎn)E，關(guān)鍵在于判斷從D到E是否會(huì)發(fā)生旋轉(zhuǎn)。

圖1 轉(zhuǎn)向情況

從圖1中可以發(fā)現(xiàn)，ADE、CDE這兩種情況下需要進(jìn)行旋轉(zhuǎn)，BDE不需要旋轉(zhuǎn)，而A、C這兩個(gè)節(jié)點(diǎn)與E節(jié)點(diǎn)的橫縱坐標(biāo)完全不同，B節(jié)點(diǎn)與E節(jié)點(diǎn)的橫坐標(biāo)相同，由此可以做出推斷，一旦當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的父節(jié)點(diǎn)坐標(biāo)完全不一致，則由父節(jié)點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)就需要進(jìn)行轉(zhuǎn)向，否則不需要且R為0，

因此，新的F值計(jì)算公式為：

增加的R，便是轉(zhuǎn)向代價(jià)。

（2）路徑?jīng)_突代價(jià)

由于實(shí)際生產(chǎn)情況下，通常都會(huì)是幾十臺(tái)AGV同時(shí)運(yùn)行，若仍然給每臺(tái)AGV獨(dú)立規(guī)劃路徑，則必定會(huì)出現(xiàn)不同AGV的路徑相互干擾甚至沖突的狀況，因此需要在為每臺(tái)AGV進(jìn)行規(guī)劃路徑時(shí)，考慮已規(guī)劃路徑AGV的影響，引入路徑?jīng)_突代價(jià)D，從而將所有AGV間的相互干擾降至最小。

為了能夠更好地判斷各條路徑間的關(guān)系，需要構(gòu)建一張公共地圖，在地圖的每個(gè)節(jié)點(diǎn)上存儲(chǔ)當(dāng)前節(jié)點(diǎn)的信息與每條路徑對(duì)該節(jié)點(diǎn)的占用情況，以供AGV規(guī)劃路徑時(shí)進(jìn)行查詢。

判斷是否會(huì)在當(dāng)前節(jié)點(diǎn)產(chǎn)生沖突時(shí)，首先查詢當(dāng)前的地圖節(jié)點(diǎn)，讀取當(dāng)前地圖節(jié)點(diǎn)所有AGV的占用信息，然后和當(dāng)前規(guī)劃路徑進(jìn)行比對(duì)，若產(chǎn)生沖突則賦予沖突代價(jià)D一個(gè)較大的值，否則D為0。進(jìn)行判斷時(shí)，首先計(jì)算當(dāng)前規(guī)劃路徑對(duì)該地圖節(jié)點(diǎn)的占用時(shí)間區(qū)間是否與已規(guī)劃路徑的占用時(shí)間區(qū)間相交，若時(shí)間發(fā)生沖突，則進(jìn)一步判斷兩條路徑的方向是否相向，若相向，則認(rèn)為路徑?jīng)_突。

如圖2所示，中央的格子為當(dāng)前計(jì)算的地圖節(jié)點(diǎn)，O為已規(guī)劃路徑離開(kāi)當(dāng)前地圖節(jié)點(diǎn)的方向，A、B、C、D為當(dāng)前規(guī)劃路徑移動(dòng)至當(dāng)前地圖節(jié)點(diǎn)的可能方向，其中A、C、D方向的情況下，AGV只需等待一小段時(shí)間，等前面的車輛離開(kāi)便可以成功移動(dòng)，而B(niǎo)方向與已規(guī)劃路徑的離開(kāi)方向是相向的，可以認(rèn)為B方向與已規(guī)劃路徑存在沖突。

圖2 路徑?jīng)_突

此外，每當(dāng)路徑規(guī)劃完畢，便會(huì)返回一個(gè)終點(diǎn)的路徑節(jié)點(diǎn)，此時(shí)需要根據(jù)新路徑的信息對(duì)地圖節(jié)點(diǎn)進(jìn)行更新，以用于后續(xù)新路徑的規(guī)劃。

最終，總代價(jià)的計(jì)算更新為：

增加的D，便是路徑?jīng)_突代價(jià)。

2. 任務(wù)管理優(yōu)化

仿真程序主要由AGV模塊與任務(wù)管理模塊構(gòu)成，通過(guò)定時(shí)器觸發(fā)各主要對(duì)象的更新，AGV模塊與任務(wù)管理模塊通過(guò)Qt的信號(hào)與槽機(jī)制進(jìn)行交互。

路徑規(guī)劃并不能做到萬(wàn)無(wú)一失，當(dāng)現(xiàn)場(chǎng)道路狹窄而AGV數(shù)量比較多的時(shí)候，發(fā)生擁堵的概率仍然會(huì)比較高，因此在合理的時(shí)機(jī)命令被堵住的AGV重新規(guī)劃線路是十分有必要的。

圖3 AGV單次任務(wù)循環(huán)

表1 AGV任務(wù)單次循環(huán)

（1）AGV模塊

AGV僅有兩種狀態(tài)，空閑與任務(wù)，空閑時(shí)在原地等待，有任務(wù)時(shí)行走。

如圖3所示，通過(guò)定時(shí)器觸發(fā)AGV自身的任務(wù)循環(huán)，同時(shí)需要不斷更新AGV對(duì)地圖的實(shí)際占用情況以更好地規(guī)劃路徑。AGV若有任務(wù)在身時(shí)，便會(huì)首先對(duì)下一個(gè)目標(biāo)位置進(jìn)行碰撞檢測(cè)，若移動(dòng)至下一節(jié)點(diǎn)會(huì)發(fā)生碰撞則停在原地并發(fā)出碰撞信號(hào)，任務(wù)管理接收信號(hào)后便會(huì)進(jìn)行碰撞計(jì)數(shù)，若連續(xù)碰撞多次，則會(huì)觸發(fā)重新規(guī)劃路線，否則就移動(dòng)至下一節(jié)點(diǎn)并釋放上一節(jié)點(diǎn)，若AGV處于空閑狀態(tài)則要發(fā)出信號(hào)占據(jù)當(dāng)前停留節(jié)點(diǎn)。在這一循環(huán)中共有3種信號(hào)，對(duì)應(yīng)到任務(wù)管理模塊中便有3個(gè)槽進(jìn)行接收和處理。偽代碼如表1所示，可以看出AGV發(fā)出的信號(hào)都需要任務(wù)管理進(jìn)行處理。

圖4 任務(wù)管理模塊單次循環(huán)

圖5 輸入模塊與訂單輸入信息

同時(shí)，AGV需要2個(gè)槽用于接收任務(wù)管理模塊發(fā)送的信號(hào)，其具體功能為：

槽4，用于處理信號(hào)4，此時(shí)任務(wù)管理模塊發(fā)布了新的任務(wù)坐標(biāo)與路徑，AGV需要進(jìn)行接收并更改自身的目標(biāo)與路徑，并將AGV狀態(tài)更改為任務(wù)狀態(tài)。

槽5，用于處理信號(hào)5，此時(shí)AGV經(jīng)過(guò)了連續(xù)多次碰撞檢測(cè)發(fā)現(xiàn)無(wú)法繼續(xù)前進(jìn)，需要接收來(lái)自任務(wù)管理模塊新規(guī)劃的路徑，并按照新路徑的指引繼續(xù)前進(jìn)。

（2）任務(wù)管理模塊

任務(wù)管理模塊同樣擁有自身的任務(wù)循環(huán)，由定時(shí)器觸發(fā)，同時(shí)帶有4個(gè)用于處理AGV信號(hào)的槽。其中，任務(wù)管理模塊的循環(huán)主要邏輯為：遍歷所有AGV，對(duì)其中處于空閑狀態(tài)的設(shè)備發(fā)布新的任務(wù)，調(diào)用A＊算法算出路徑后，將路徑通過(guò)信號(hào)4發(fā)送給對(duì)應(yīng)的AGV，具體流程，如圖4所示。

任務(wù)管理模塊用于處理AGV信號(hào)的3個(gè)槽的具體功能為：

槽1，用于處理信號(hào)1，此時(shí)AGV處于空閑狀態(tài)并停留在了原地，此時(shí)任務(wù)管理模塊需要將地圖節(jié)點(diǎn)中對(duì)應(yīng)節(jié)點(diǎn)的agvOccupied屬性更改為true，如此在規(guī)劃路徑時(shí)便會(huì)避開(kāi)此節(jié)點(diǎn)。

圖6 動(dòng)畫(huà)模塊

槽2，用于處理信號(hào)2，此時(shí)AGV按照路徑前往下一節(jié)點(diǎn)，因此需要保證AGV即將離開(kāi)的節(jié)點(diǎn)的agvOccupied屬性為false，同時(shí)將對(duì)應(yīng)AGV的碰撞檢測(cè)計(jì)數(shù)清零。

槽3，用于處理信號(hào)3，此時(shí)AGV經(jīng)過(guò)碰撞檢測(cè)認(rèn)為移動(dòng)至下一個(gè)節(jié)點(diǎn)會(huì)發(fā)生碰撞，任務(wù)管理模塊會(huì)進(jìn)行碰撞計(jì)數(shù)，若計(jì)數(shù)達(dá)到一定次數(shù)，則會(huì)觸發(fā)重新規(guī)劃路線，并通過(guò)信號(hào)5將新的路徑發(fā)送給指定AGV。

在AGV與任務(wù)管理模塊的循環(huán)、信號(hào)、槽的相互配合下，便可以實(shí)現(xiàn)較為合理的AGV路線重規(guī)劃，從而降低堵塞概率。

三、仿真實(shí)現(xiàn)

為了驗(yàn)證路徑規(guī)劃算法的可行性，本文在Qt Creator中采用C++編程語(yǔ)言建立一個(gè)可視化仿真系統(tǒng)，用于模擬在倉(cāng)儲(chǔ)物流中物流機(jī)器人的批量路徑規(guī)劃。

圖7 規(guī)劃結(jié)果

1. 仿真系統(tǒng)介紹

仿真系統(tǒng)主要由輸入模塊與動(dòng)畫(huà)模塊構(gòu)成，輸入模塊負(fù)責(zé)接收用戶的參數(shù)，動(dòng)畫(huà)模塊負(fù)責(zé)將仿真結(jié)果實(shí)時(shí)演示給用戶。

（1）輸入模塊

如圖5所示，在輸入模塊中，用戶可以使用Excel軟件定制倉(cāng)位信息與訂單信息，仿真程序便可以讀取Excel文件，仿真開(kāi)始后程序可以根據(jù)用戶的倉(cāng)位與訂單給AGV下達(dá)揀貨任務(wù)。同時(shí)，在輸入模塊中，用戶可以自定義AGV與揀貨人員的數(shù)量從而在觀察路徑規(guī)劃算法有效性的同時(shí)得到不同人機(jī)配比下的揀貨效率。

（2）動(dòng)畫(huà)模塊

如圖6所示，動(dòng)畫(huà)模塊負(fù)責(zé)將仿真結(jié)果實(shí)時(shí)輸出到畫(huà)面上，讓用戶能夠更直觀地了解仿真的情況，觀察哪邊容易發(fā)生擁堵。同時(shí)，仿真的地圖可以根據(jù)需要進(jìn)行修改，對(duì)應(yīng)的，倉(cāng)位信息同樣需要同步修改。

2. 有效性驗(yàn)證

最后通過(guò)人為制定具體的AGV點(diǎn)對(duì)點(diǎn)任務(wù)以驗(yàn)證算法的有效性，如圖7所示，有4個(gè)點(diǎn)對(duì)點(diǎn)任務(wù)，分別指派給4臺(tái)AGV，任務(wù)具體為：A1-A2、B1-B2、C1-C2、D1-D2。

將任務(wù)導(dǎo)入程序后觀察AGV的實(shí)際行動(dòng)路線。如圖7所示，AGV的行動(dòng)路線基本符合算法的思路，在預(yù)計(jì)會(huì)產(chǎn)生沖突時(shí)，采用了繞行的路線。

此外，通過(guò)生成較多數(shù)量的AGV并派發(fā)相對(duì)重復(fù)的訂單，還原AGV產(chǎn)生擁堵的情況，經(jīng)過(guò)測(cè)試可以發(fā)現(xiàn)，當(dāng)AGV在原地?fù)矶鲁^(guò)一定時(shí)間后，其便會(huì)掉頭沿著新的路線繼續(xù)行走，如圖8所示，中間最下方的AGV的目的地為當(dāng)前巷道的上方，由于前方發(fā)生了擁堵，因此其掉頭尋找新的路線，說(shuō)明任務(wù)管理模塊發(fā)揮了作用。

圖8 自動(dòng)規(guī)劃新路線

四、結(jié)論

本文在A＊算法的基礎(chǔ)上對(duì)物流機(jī)器人的揀選路徑進(jìn)行了系統(tǒng)性研究，針對(duì)現(xiàn)場(chǎng)實(shí)際出現(xiàn)的問(wèn)題提出了對(duì)應(yīng)的解決方案，并利用C++編寫(xiě)仿真系統(tǒng)對(duì)解決方案進(jìn)行了有效性驗(yàn)證，最終得到如下結(jié)論：

1.構(gòu)建公共的地圖占用信息，有助于更加合理地進(jìn)行AGV路徑規(guī)劃。經(jīng)過(guò)本文的探索可以發(fā)現(xiàn)，AGV在預(yù)測(cè)路況的條件下可以有效避免路徑?jīng)_突的發(fā)生。

2.在A＊算法中加入轉(zhuǎn)彎代價(jià)，可以有效避免AGV在規(guī)劃路徑時(shí)因隨機(jī)性導(dǎo)致轉(zhuǎn)彎過(guò)多的情況。

3.合理的任務(wù)管理機(jī)制，可以有效疏通堵塞情況，本文采用了相對(duì)較為簡(jiǎn)單的次數(shù)觸發(fā)機(jī)制，配合地圖信息的實(shí)時(shí)更新，使AGV在狹小通道相互妨礙而停滯時(shí)能夠自動(dòng)繞路。