基于激光雷達數據的倉儲物流AGV障礙物識別方法

吳 飛, 黃 威

(武漢理工大學 機電工程學院, 湖北 武漢 430070)

隨著電子商務、物流、計算機等行業近年來的迅猛發展,消費升級下的市場壓力變大,傳統的倉儲運行模式已難以滿足海量庫存管理、提高運行效率及降低人力成本等需求.自亞馬遜將Kiva機器人運用到倉儲物流中以來,針對智能倉儲的運行模式、任務調度、AGV定位和多AGV路徑規劃等理論方法在一定程度上使得智能倉儲系統更加可靠、更有效率[1].

研究人員在路徑規劃與避碰方面提出了許多解決方案.例如,對貨架和任務選取設定規則來減少擁堵[2];引入線性時序邏輯理論,來優化任務分配和路徑[3];使用帶時間窗的多AGV路徑規劃算法,減少多臺AGV發生碰撞的可能性等[4-5].

然而在實際運行的過程中,不可避免地會出現外界干擾和運行產生定位誤差等情況,這些情況導致的誤差會隨時間不斷累積,使得原本完美的多AGV多路徑規劃出現偏差直至失效.另外,AGV運行也可能會產生一些故障而無法移動,導致整個系統無法按照原本的規劃運行.

通過分析智能倉儲的運行環境,倉儲物流AGV可能出現的沖突以及前方障礙物類別可歸納為以下幾種情況: ① 兩個AGV由于累積誤差可能在交叉路口出現爭奪路口通行優先權的情況,導致兩個AGV互相成為對方的障礙物; ② 某個AGV由于故障在通行道的某處停止運行,導致AGV占用通道而成為障礙物; ③ 貨架被錯誤地放置在了通道上而成為障礙物; ④ 原本貨架上的貨箱掉落在通道上而成為障礙物; ⑤ 智能倉儲維護人員作業時占用通道而成為障礙物.

通過上述的幾種情況,可以看出不同的障礙物對正常運行的AGV影響不同.占用通道的貨箱和貨架為永久障礙物,需AGV重新規劃路徑,需人為干預將障礙物清除;人和AGV則可能為臨時障礙物,只需等待一小段時間即可繼續通行,不必重新規劃路徑,也不必申請人為干預來清除.

鑒于此,在智能倉儲環境中,研究使用2D激光雷達數據識別AGV前方障礙物的方法,為AGV后續的精準決策提供基礎.

文中以激光雷達數據為基礎,提出了改進DBSCAN算法以及障礙物輪廓特征提取方法,使用粒子群優化參數后的SVM算法對障礙物進行識別.

1 數據預處理

由于通過激光雷達感知來避碰的范圍僅限數秒后可能的碰撞,因此AGV感知障礙物的警戒區設定為1 200 mm的范圍內.根據所用的RPLIDAR A2型號激光雷達測量范圍以及劃分的警戒區域范圍,激光雷達數據在距離上的分布如表1所示.

表1 距離分布表

為濾除激光雷達數據中的噪聲數據,需要用到聚類的算法將目標障礙物分離出來.由于不需要預先指定數據中的目標數,在障礙物數目不確定的智能倉儲環境下,基于密度的DBSCAN算法相較于其他聚類算法魯棒性較高.然而,激光雷達的數據密度并不均勻,靠近激光雷達的數據較密集,而遠離激光雷達的數據較稀疏[6].因此,提出了一種自適應鄰域半徑的DBSCAN算法來解決此問題.

經典的DBSCAN算法[7]通過一組鄰域參數(ε,MinPts)來描述樣本分布的緊密程度.在算法流程中先根據事先指定的一組鄰域參數(ε,MinPts)來遍歷樣本集以找到所有的核心對象,再隨機地選取一個核心對象找到其密度可達的所有樣本點,這些密度可達的樣本點為一個聚類簇,直至所有核心對象均被訪問過為止.其中核心對象是其鄰域ε內至少包含MinPts個樣本點的樣本點.

在改進的DBSCAN算法中,設定的鄰域半徑ε是激光雷達最小測量距離dmin處所對應的鄰域半徑值,樣本點xj處的極徑為ρj,則其自適應鄰域半徑為

(1)

在經典DBSCAN聚類算法流程中用εj代替ε作為鄰域半徑來判斷樣本點是否為核心對象,即核心對象是其鄰域εj內至少包含MinPts個樣本點的樣本點.

2 障礙物特征參數提取

為了對聚類后的聚類簇進行識別分類,將激光雷達數據特征設計為以下的特征參數: ① 聚類簇ci中包含的點集個數ki; ② 聚類簇ci中各點距離值的平均值：

(2)

③ 聚類簇ci中第1個點和最后一個點的連線所在的直線為li,ci中第j個點為點Pij,其中j∈{1,2,…,ki},點Pij中距離直線li距離最大的點為點Pim,其中m為該點的聚類簇ci中的序號且m∈{2,3,…,ki-1},點Pim與點Pi1連線所在的直線為li1m,點Pim與點Piki連線所在的直線為likm,如圖1所示.

圖1 特征提取方法示意圖

聚類簇ci中第1到m個點中,偏離直線li1m的距離值的標準差為

(3)

聚類簇ci中第m+1到ki個點中,偏離直線lmk的距離值的標準差為

(4)

總標準差為

(5)

④點Pi1與點Piki及點Pim這3個點的外接圓圓心為點Oi,外接圓半徑為ri,如圖1所示.聚類簇ci中各點偏離上述外接圓圓弧的距離標準差為

(6)

因此,聚類簇ci的特征向量:

(7)

一幀激光雷達數據可由特征向量C表示,C=[C1,C2,…,Cn],其中n為激光雷達數據完成聚類后的簇數.

3 基于粒子群算法的支持向量機

3.1 支持向量機原理

支持向量機(support vector machine, SVM)是一種定義在特征空間上間隔最大的二分類模型[8-10].

假設特征空間上的訓練數據集為

T={(x1,y1),(x2,y2),…,(xN,yN)},
xi∈Rn,yi∈{+1,-1},i=1,2,…,N.

(8)

SVM算法是在特征空間中找到一個能將實例分成不同類的分離超平面.當數據為線性可分時,SVM的目標是求出幾何間隔最大的分離超平面;當數據線性不可分時,在優化問題中引入松弛變量ξi≥0,SVM的目標變為最優化引入松弛變量后的目標函數;當數據是非線性時,引入核函數將數據映射到高維空間,SVM的目標變為尋找高維空間中的分離超平面.假設核函數為K(xi·xj)=φ(xi)·φ(xj),非線性SVM的最終優化的目標函數為

0≤αi≤C,i=1,2,…,N.

(9)

分類決策函數為

(10)

最常用且適用范圍最廣的核函數為徑向基核函數,其核函數如下：

K(x,z)=exp(-γ‖x-z‖2).

(11)

使用徑向基核函數時,需提前確定懲罰參數C和核參數γ的值,文中使用粒子群優化算法來確定.

3.2 粒子群算法原理

粒子群優化算法[11-12]是根據鳥類覓食行為提出的全局最優化算法，其流程如圖2所示.

圖2 粒子群算法流程圖

在優化過程中,每個粒子都會根據當前適應度最高的粒子來更新自己的速度和位置.具體方程如下:

vij(t+1)=ωvij(t+1)+c1r1(t)(pij(t)-

xij(t))+c2r2(t)(pgj(t)-xij(t)),

(12)

xij(t+1)=xij(t)+vij(t+1),

(13)

式中:vij表示粒子的速度;ω是慣性權重;xij是當前粒子的位置;pij表示第i粒子找到的最優解;pgj表示當前的全局最優解;r1與r2表示區間(0,1)內的均勻隨機數;c1與c2是學習因子.

4 試驗分析

4.1 數據采集

根據智能倉儲環境下障礙物種類分析結果,智能倉儲中AGV前方障礙物主要分為人、貨箱、貨架和執行其他任務的AGV共4種.為采集障礙物相應的激光點集數據,搭建了智能倉儲模擬環境.模擬環境中,“障礙物”人與真實環境一致;紙箱模擬真實環境中的貨箱;由于激光雷達采集的數據為障礙物距離地平面一定距離的平面輪廓特征,貨架則由具有相似底部支撐結構的椅子模擬;倉儲物流AGV和采集數據的AGV則是由bobac機器人模擬;激光雷達為RPLIDAR A2型號激光雷達.搭建的智能倉儲的模擬環境如圖所示3,在模擬環境中采集并去除運動畸變后的激光雷達數據如圖4所示,為顯示方便,這里只顯示了距離在1 200 mm以內的數據.

圖4中,60°至135°范圍內為人(腿)對應的激光雷達數據;0°至60°范圍內為貨箱(紙箱)對應的激光雷達數據;300°至360°范圍內為貨架(椅子)對應的激光雷達數據;225°至300°范圍內為AGV對應的激光雷達數據.

采集數據的AGV在如圖3所示的智能倉儲模擬環境中,采集得到800幀去除運動畸變后的障礙物試驗數據,每一幀數據包含一種典型障礙物.其中人(腿)、貨箱(紙箱)、貨架(椅子)和AGV這4種典型障礙物的樣本數量分別為200.在試驗中,4種典型障礙物隨機選出30%的數據,即60組,一共240組數據作為測試樣本,其余的70%,即560組數據為訓練樣本.

圖3 智能倉儲模擬環境圖

圖4 激光雷達采集數據圖

4.2 特征參數提取

根據文中提出的數據預處理方式和改進后的DBSCAN算法，對激光雷達數據進行濾波與聚類，最終得到的聚類簇作為訓練與測試用的數據樣本.使用文中提出的障礙物特征參數提取方法，計算出每一個聚類簇數據樣本的特征向量，部分結果如表2所示.由于特征參數k為數據樣本所包含點的個數，表中用整數表示，特征參數則保留小數點后4位有效數字.

表2 訓練樣本特征向量表

(續表2)

4.3 粒子群算法尋找最優參數

徑向基核SVM算法的參數包括懲罰參數C和核參數γ.其適應度定義為訓練集上使用5折交叉驗證的準確率.使用粒子群算法尋找最優參數時,粒子種群規模選為100,迭代次數為50,學習因子c1=c2=2.粒子群優化徑向基核SVM參數所得到的最優適應度曲線如圖5所示.

圖5 粒子群最優適應度曲線

迭代次數完成后,最優適應度結果為0.978 57,參數C=4.617 00,γ=0.012 87.

4.4 結果分析

在訓練集上尋找到了最優的參數并訓練好模型后,還需在測試集上對預測分類的效果進行測試.徑向基核SVM算法默認參數(C=1.0,γ=0.25)和PSO優化后參數在測試集上的混淆矩陣如圖6和圖7所示.

由圖6和7中的混淆矩陣可以得到識別正確率如表3所示.

圖6 默認參數分類混淆矩陣

圖7 粒子群優化參數分類混淆矩陣

表3 正確率對比表

由表3可知,在對4種典型障礙物進行識別分類時,默認參數下的徑向基核SVM算法識別正確率為66.25%,經過PSO優化參數后的徑向基核SVM算法識別正確率達到了94.58%.證明了使用提出的特征提取方法以及粒子群優化的徑向基核SVM對智能倉儲中典型障礙物識別有良好的效果.

5 結 論

1) 提出了一種針對激光雷達數據的DBSCAN算法的改進方式,并成功將其運用在激光雷達數據的預處理中.

2) 提出使用粒子群優化算法尋找徑向基核函數SVM的參數,在測試集上的結果表明,使用粒子群優化算法優化參數后的徑向基核函數的識別效果遠好于優化之前的效果.其結果證明了提出的特征提取方法以及粒子群優化的徑向基核SVM算法適用于基于激光雷達數據的智能倉儲典型障礙物識別.