基于激光雷達(dá)數(shù)據(jù)的倉(cāng)儲(chǔ)物流AGV障礙物識(shí)別方法

吳 飛, 黃 威

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

隨著電子商務(wù)、物流、計(jì)算機(jī)等行業(yè)近年來(lái)的迅猛發(fā)展,消費(fèi)升級(jí)下的市場(chǎng)壓力變大,傳統(tǒng)的倉(cāng)儲(chǔ)運(yùn)行模式已難以滿足海量庫(kù)存管理、提高運(yùn)行效率及降低人力成本等需求.自亞馬遜將Kiva機(jī)器人運(yùn)用到倉(cāng)儲(chǔ)物流中以來(lái),針對(duì)智能倉(cāng)儲(chǔ)的運(yùn)行模式、任務(wù)調(diào)度、AGV定位和多AGV路徑規(guī)劃等理論方法在一定程度上使得智能倉(cāng)儲(chǔ)系統(tǒng)更加可靠、更有效率[1].

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

然而在實(shí)際運(yùn)行的過(guò)程中,不可避免地會(huì)出現(xiàn)外界干擾和運(yùn)行產(chǎn)生定位誤差等情況,這些情況導(dǎo)致的誤差會(huì)隨時(shí)間不斷累積,使得原本完美的多AGV多路徑規(guī)劃出現(xiàn)偏差直至失效.另外,AGV運(yùn)行也可能會(huì)產(chǎn)生一些故障而無(wú)法移動(dòng),導(dǎo)致整個(gè)系統(tǒng)無(wú)法按照原本的規(guī)劃運(yùn)行.

通過(guò)分析智能倉(cāng)儲(chǔ)的運(yùn)行環(huán)境,倉(cāng)儲(chǔ)物流AGV可能出現(xiàn)的沖突以及前方障礙物類別可歸納為以下幾種情況: ① 兩個(gè)AGV由于累積誤差可能在交叉路口出現(xiàn)爭(zhēng)奪路口通行優(yōu)先權(quán)的情況,導(dǎo)致兩個(gè)AGV互相成為對(duì)方的障礙物; ② 某個(gè)AGV由于故障在通行道的某處停止運(yùn)行,導(dǎo)致AGV占用通道而成為障礙物; ③ 貨架被錯(cuò)誤地放置在了通道上而成為障礙物; ④ 原本貨架上的貨箱掉落在通道上而成為障礙物; ⑤ 智能倉(cāng)儲(chǔ)維護(hù)人員作業(yè)時(shí)占用通道而成為障礙物.

通過(guò)上述的幾種情況,可以看出不同的障礙物對(duì)正常運(yùn)行的AGV影響不同.占用通道的貨箱和貨架為永久障礙物,需AGV重新規(guī)劃路徑,需人為干預(yù)將障礙物清除;人和AGV則可能為臨時(shí)障礙物,只需等待一小段時(shí)間即可繼續(xù)通行,不必重新規(guī)劃路徑,也不必申請(qǐng)人為干預(yù)來(lái)清除.

鑒于此,在智能倉(cāng)儲(chǔ)環(huán)境中,研究使用2D激光雷達(dá)數(shù)據(jù)識(shí)別AGV前方障礙物的方法,為AGV后續(xù)的精準(zhǔn)決策提供基礎(chǔ).

文中以激光雷達(dá)數(shù)據(jù)為基礎(chǔ),提出了改進(jìn)DBSCAN算法以及障礙物輪廓特征提取方法,使用粒子群優(yōu)化參數(shù)后的SVM算法對(duì)障礙物進(jìn)行識(shí)別.

1 數(shù)據(jù)預(yù)處理

由于通過(guò)激光雷達(dá)感知來(lái)避碰的范圍僅限數(shù)秒后可能的碰撞,因此AGV感知障礙物的警戒區(qū)設(shè)定為1 200 mm的范圍內(nèi).根據(jù)所用的RPLIDAR A2型號(hào)激光雷達(dá)測(cè)量范圍以及劃分的警戒區(qū)域范圍,激光雷達(dá)數(shù)據(jù)在距離上的分布如表1所示.

表1 距離分布表

為濾除激光雷達(dá)數(shù)據(jù)中的噪聲數(shù)據(jù),需要用到聚類的算法將目標(biāo)障礙物分離出來(lái).由于不需要預(yù)先指定數(shù)據(jù)中的目標(biāo)數(shù),在障礙物數(shù)目不確定的智能倉(cāng)儲(chǔ)環(huán)境下,基于密度的DBSCAN算法相較于其他聚類算法魯棒性較高.然而,激光雷達(dá)的數(shù)據(jù)密度并不均勻,靠近激光雷達(dá)的數(shù)據(jù)較密集,而遠(yuǎn)離激光雷達(dá)的數(shù)據(jù)較稀疏[6].因此,提出了一種自適應(yīng)鄰域半徑的DBSCAN算法來(lái)解決此問(wèn)題.

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

在改進(jìn)的DBSCAN算法中,設(shè)定的鄰域半徑ε是激光雷達(dá)最小測(cè)量距離dmin處所對(duì)應(yīng)的鄰域半徑值,樣本點(diǎn)xj處的極徑為ρj,則其自適應(yīng)鄰域半徑為

(1)

在經(jīng)典DBSCAN聚類算法流程中用εj代替ε作為鄰域半徑來(lái)判斷樣本點(diǎn)是否為核心對(duì)象,即核心對(duì)象是其鄰域εj內(nèi)至少包含MinPts個(gè)樣本點(diǎn)的樣本點(diǎn).

2 障礙物特征參數(shù)提取

為了對(duì)聚類后的聚類簇進(jìn)行識(shí)別分類,將激光雷達(dá)數(shù)據(jù)特征設(shè)計(jì)為以下的特征參數(shù): ① 聚類簇ci中包含的點(diǎn)集個(gè)數(shù)ki; ② 聚類簇ci中各點(diǎn)距離值的平均值：

(2)

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

圖1 特征提取方法示意圖

聚類簇ci中第1到m個(gè)點(diǎn)中,偏離直線li1m的距離值的標(biāo)準(zhǔn)差為

(3)

聚類簇ci中第m+1到ki個(gè)點(diǎn)中,偏離直線lmk的距離值的標(biāo)準(zhǔn)差為

(4)

總標(biāo)準(zhǔn)差為

(5)

④點(diǎn)Pi1與點(diǎn)Piki及點(diǎn)Pim這3個(gè)點(diǎn)的外接圓圓心為點(diǎn)Oi,外接圓半徑為ri,如圖1所示.聚類簇ci中各點(diǎn)偏離上述外接圓圓弧的距離標(biāo)準(zhǔn)差為

(6)

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

(7)

一幀激光雷達(dá)數(shù)據(jù)可由特征向量C表示,C=[C1,C2,…,Cn],其中n為激光雷達(dá)數(shù)據(jù)完成聚類后的簇?cái)?shù).

3 基于粒子群算法的支持向量機(jī)

3.1 支持向量機(jī)原理

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

假設(shè)特征空間上的訓(xùn)練數(shù)據(jù)集為

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

(8)

SVM算法是在特征空間中找到一個(gè)能將實(shí)例分成不同類的分離超平面.當(dāng)數(shù)據(jù)為線性可分時(shí),SVM的目標(biāo)是求出幾何間隔最大的分離超平面;當(dāng)數(shù)據(jù)線性不可分時(shí),在優(yōu)化問(wèn)題中引入松弛變量ξi≥0,SVM的目標(biāo)變?yōu)樽顑?yōu)化引入松弛變量后的目標(biāo)函數(shù);當(dāng)數(shù)據(jù)是非線性時(shí),引入核函數(shù)將數(shù)據(jù)映射到高維空間,SVM的目標(biāo)變?yōu)閷ふ腋呔S空間中的分離超平面.假設(shè)核函數(shù)為K(xi·xj)=φ(xi)·φ(xj),非線性SVM的最終優(yōu)化的目標(biāo)函數(shù)為

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

(9)

分類決策函數(shù)為

(10)

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

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

(11)

使用徑向基核函數(shù)時(shí),需提前確定懲罰參數(shù)C和核參數(shù)γ的值,文中使用粒子群優(yōu)化算法來(lái)確定.

3.2 粒子群算法原理

粒子群優(yōu)化算法[11-12]是根據(jù)鳥(niǎo)類覓食行為提出的全局最優(yōu)化算法，其流程如圖2所示.

圖2 粒子群算法流程圖

在優(yōu)化過(guò)程中,每個(gè)粒子都會(huì)根據(jù)當(dāng)前適應(yīng)度最高的粒子來(lái)更新自己的速度和位置.具體方程如下:

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表示粒子的速度;ω是慣性權(quán)重;xij是當(dāng)前粒子的位置;pij表示第i粒子找到的最優(yōu)解;pgj表示當(dāng)前的全局最優(yōu)解;r1與r2表示區(qū)間(0,1)內(nèi)的均勻隨機(jī)數(shù);c1與c2是學(xué)習(xí)因子.

4 試驗(yàn)分析

4.1 數(shù)據(jù)采集

根據(jù)智能倉(cāng)儲(chǔ)環(huán)境下障礙物種類分析結(jié)果,智能倉(cāng)儲(chǔ)中AGV前方障礙物主要分為人、貨箱、貨架和執(zhí)行其他任務(wù)的AGV共4種.為采集障礙物相應(yīng)的激光點(diǎn)集數(shù)據(jù),搭建了智能倉(cāng)儲(chǔ)模擬環(huán)境.模擬環(huán)境中,“障礙物”人與真實(shí)環(huán)境一致;紙箱模擬真實(shí)環(huán)境中的貨箱;由于激光雷達(dá)采集的數(shù)據(jù)為障礙物距離地平面一定距離的平面輪廓特征,貨架則由具有相似底部支撐結(jié)構(gòu)的椅子模擬;倉(cāng)儲(chǔ)物流AGV和采集數(shù)據(jù)的AGV則是由bobac機(jī)器人模擬;激光雷達(dá)為RPLIDAR A2型號(hào)激光雷達(dá).搭建的智能倉(cāng)儲(chǔ)的模擬環(huán)境如圖所示3,在模擬環(huán)境中采集并去除運(yùn)動(dòng)畸變后的激光雷達(dá)數(shù)據(jù)如圖4所示,為顯示方便,這里只顯示了距離在1 200 mm以內(nèi)的數(shù)據(jù).

圖4中,60°至135°范圍內(nèi)為人(腿)對(duì)應(yīng)的激光雷達(dá)數(shù)據(jù);0°至60°范圍內(nèi)為貨箱(紙箱)對(duì)應(yīng)的激光雷達(dá)數(shù)據(jù);300°至360°范圍內(nèi)為貨架(椅子)對(duì)應(yīng)的激光雷達(dá)數(shù)據(jù);225°至300°范圍內(nèi)為AGV對(duì)應(yīng)的激光雷達(dá)數(shù)據(jù).

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

圖3 智能倉(cāng)儲(chǔ)模擬環(huán)境圖

圖4 激光雷達(dá)采集數(shù)據(jù)圖

4.2 特征參數(shù)提取

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

表2 訓(xùn)練樣本特征向量表

(續(xù)表2)

4.3 粒子群算法尋找最優(yōu)參數(shù)

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

圖5 粒子群最優(yōu)適應(yīng)度曲線

迭代次數(shù)完成后,最優(yōu)適應(yīng)度結(jié)果為0.978 57,參數(shù)C=4.617 00,γ=0.012 87.

4.4 結(jié)果分析

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

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

圖6 默認(rèn)參數(shù)分類混淆矩陣

圖7 粒子群優(yōu)化參數(shù)分類混淆矩陣

表3 正確率對(duì)比表

由表3可知,在對(duì)4種典型障礙物進(jìn)行識(shí)別分類時(shí),默認(rèn)參數(shù)下的徑向基核SVM算法識(shí)別正確率為66.25%,經(jīng)過(guò)PSO優(yōu)化參數(shù)后的徑向基核SVM算法識(shí)別正確率達(dá)到了94.58%.證明了使用提出的特征提取方法以及粒子群優(yōu)化的徑向基核SVM對(duì)智能倉(cāng)儲(chǔ)中典型障礙物識(shí)別有良好的效果.

5 結(jié) 論

1) 提出了一種針對(duì)激光雷達(dá)數(shù)據(jù)的DBSCAN算法的改進(jìn)方式,并成功將其運(yùn)用在激光雷達(dá)數(shù)據(jù)的預(yù)處理中.

2) 提出使用粒子群優(yōu)化算法尋找徑向基核函數(shù)SVM的參數(shù),在測(cè)試集上的結(jié)果表明,使用粒子群優(yōu)化算法優(yōu)化參數(shù)后的徑向基核函數(shù)的識(shí)別效果遠(yuǎn)好于優(yōu)化之前的效果.其結(jié)果證明了提出的特征提取方法以及粒子群優(yōu)化的徑向基核SVM算法適用于基于激光雷達(dá)數(shù)據(jù)的智能倉(cāng)儲(chǔ)典型障礙物識(shí)別.