李景，程瑞嘉，張文忠

（安徽工業(yè)大學(xué)電氣與信息工程學(xué)院，安徽 馬鞍山 243032）

隨著電子商務(wù)、快遞、互聯(lián)網(wǎng)以及新能源技術(shù)的日新月異，人們對物質(zhì)生活的需求也會越來越高，電商行業(yè)的訂單邁向多種類，小層次，高頻次的步伐。這種消費模式給傳統(tǒng)“人到貨”的揀選方式帶來巨大挑戰(zhàn)，為了應(yīng)對這種問題，現(xiàn)代的智能倉儲系統(tǒng)提出了“貨到人”的揀選理念。

在這種智能倉庫中，大多采用定制的倉庫機器人（AGV）代替人工來實現(xiàn)貨物的揀貨、分揀、搬用到派送等一些操作。根據(jù)倉庫訂單，利用中央處理單元對倉庫機器人進行分配任務(wù)，其次對整個倉庫研究分析，建立基礎(chǔ)地圖模型,分配好機器人任務(wù)，建立好地圖模型并對AGV進行路徑規(guī)劃，主要有總體路徑規(guī)劃［1］以及局部的路徑規(guī)劃［2］，本文針對整體流程做出簡介。

1 AGV地圖模型的構(gòu)建

構(gòu)建倉庫地圖模型是相當(dāng)重要的，也是之后對其調(diào)度路徑規(guī)劃的基礎(chǔ)。在研究眾多文獻后，大致可以得出以下幾種方法：

（1）簡易模型柵格化。（2）有向圖的模型地圖。（3）時空地圖模型。

1.1 簡易模型柵格化

將整個倉庫假定為區(qū)域a，以最左下角為坐標(biāo)原點，橫軸為X軸，縱軸為Y軸，建立XOY狄克爾坐標(biāo)系，機器人為一小格，等同于一像素點。而貨架等同于幾個像素點不可通過，設(shè)機器人步長為u，倉庫最大面積等于Xmax*Ymax，所以可得柵格數(shù)則為N C=Xmax/u,Nl=Ymax/u。故機器人的運動可以看成點在坐標(biāo)系的運動模型。即如圖1所示。

圖1 簡易柵格圖

1.2 有向圖的模型地圖

機器人運行空間由不同類型且相同尺寸的單位塊組成，這些單位塊用來表示站點中的出發(fā)點、分揀格口、緩沖區(qū)、路徑等。我們用端點來表示所有的單位塊，并且用有向邊來相互連接。注意同一時間內(nèi)一個單位塊只能通過一輛AGV。

首先，多輛AGV機器人可以在出貨口同時裝撿快件或暫時?？?。叉號標(biāo)示的單位塊表示分揀格口，由單行單方向的所有的路徑塊都被賦予了通行方向，并且AGV機器人在每個時間插槽內(nèi)只能夠?？恳惠v。其次字母B單位塊表示緩沖區(qū)塊，AGV機器人在這里可以暫時?？?，避免與其他工作機器人發(fā)生沖突。

1.3 時空地圖模型

利用二維元胞數(shù)組記錄各節(jié)點占用時間段集合，其中節(jié)點（x,y）的占用時間段集合表示為：

式中tin、tout分別為AGV進入、離開節(jié)點（x,y）的時刻，i表示占用節(jié)點的AGV編號。其時空地圖模型如下圖2所示：

圖2 時空地圖

2 AGV調(diào)度的路徑規(guī)劃

在為機器人分配任務(wù)以及建立好倉庫地圖模型之后，接下來更重要的一步也是整個AGV調(diào)度中最為重要的一步就是關(guān)于AGV調(diào)度的路徑規(guī)劃問題。許多學(xué)者對這部分的研究大體分為兩種：第一種是集中式系統(tǒng)規(guī)劃［3］，這種方法對中央處理單元要求性能較高，在倉庫這種級別中無法要求處理單元性能優(yōu)異。第二種就是分布式系統(tǒng)規(guī)劃［4］，這種方法對每一臺智能機器人要求性能較高，既要規(guī)劃路徑又要接受任務(wù)分配等工作，所以工作量大。

現(xiàn)在更多的學(xué)者偏向于將全局路徑規(guī)劃以及局部路徑規(guī)劃結(jié)合起來使用，常用的方法有：基于雙種群遺傳算法的路徑規(guī)劃，基于時空地圖的路徑規(guī)劃與基于時間窗的路徑規(guī)劃。

2.1 基于時間窗的路徑規(guī)劃

通過加入時間窗的方法來實現(xiàn)其路徑規(guī)劃，具體過程如下：

對于單機器人多負(fù)載路徑規(guī)劃。步驟1：每一個AGV都要有兩條及以上的備選路徑；步驟2：每條路徑都會涉及到多個路徑塊，每個路徑塊都有各自的空閑時間窗，通過統(tǒng)計全部空閑的時間窗可以算出Sch（pk），即每條備選路徑pk的通行時間安排；步驟3：選出用時最短的備選路徑，及時預(yù)定此路徑涉及到的所有路徑塊。對于步驟1，為了避免預(yù)約通行的其他AGV在相同的時間相遇，采用基于A*的帶懲罰算法來生成候選路徑集，即對每個時間格加入權(quán)重，最后通過尋找權(quán)重小的路徑展開，尋找到最合適的路徑。對于步驟2，我們給出兩種時間窗搜索的算法，分別是前向時間窗搜索算法以及重選擇時間窗搜索算法，在此基礎(chǔ)上再去計算路徑調(diào)度。

而對于多機器人負(fù)載時：首先在出發(fā)點獲取多個快件，通過每個負(fù)載快件互異的目的點，系統(tǒng)會自動規(guī)劃出無沖突的路徑方案傳遞給機器人執(zhí)行，之后AGV根據(jù)路徑行走完所有目的地后返回出發(fā)點重新加貨。

3 結(jié)論

以上討論的方法以及模型大多數(shù)是建立在如下所示的理想模型下進行的，在現(xiàn)實世界中存在著很多的不確定因素，故上述很多方法都是失效的或者說效果不佳的。理想模型：（1）AGV只能沿直角方向（即橫縱向）跨越柵格，AGV不能斜向跨越柵格。（2）將每個AGV的裝載時間、卸載時間理想化為零。（3）所有包裹在零時刻到達，所有AGV在零時刻可用。（4）AGV運行過程中保持勻速。（5）不考慮包裹到達投遞區(qū)之后的出庫過程。（6）不考慮機器人空載以及負(fù)載情況下的運貨速度，以及機器人充電時間。

今后機器人的目標(biāo)就是向著這個方向改進，首先需要考慮機器人充放電情況，雖然在這方面有一些相關(guān)的介紹，但是過于簡單，不能加以推廣應(yīng)用；其次就是機器人運動過程中可能存在一些均加速以及均減速的情況，這樣機器人在面對碰撞沖突問題上可以不用通過停下來等待來解決節(jié)點沖突以及相向沖突問題，此時也會多了一個追擊沖突。這種情況將會更加復(fù)雜，有待于進一步研究。