激光數(shù)據(jù)聚類和Morphin算法下的機器人避障研究①

, ,

(安徽工程大學 安徽省電氣傳動與控制重點實驗室,安徽 蕪湖 241000)

0 引 言

在機器人導航中，障礙物是不可避免的、隨機出現(xiàn)且形狀不可預知的[1-3]。目前，在避障問題上常使用激光傳感器，其探測距離遠，測量精度高。

黃如林等[6]提出一種基于動態(tài)障礙物幾何特征和障礙物回波脈沖寬度特征融合的動態(tài)障礙物檢測與跟蹤方法。雖然較好的實現(xiàn)對障礙物的檢測，但缺乏對障礙物運動軌跡的預測和避撞策略的描述。劉杰等[7]利用靜態(tài)障礙物和目標點之間的位置關(guān)系，提出一種通過調(diào)節(jié)自適應閾值的改進矢量場直方圖避障算法，但該方法缺乏對動態(tài)障礙物檢測和預測的闡述。楊月全等[8]針對一類圓形動態(tài)障礙物，采用最小二乘法對障礙物邊緣進行擬合，實現(xiàn)避障規(guī)劃，但該方案受限于動態(tài)障礙物的形狀。

目前，利用激光傳感進行避障的相關(guān)研究大多數(shù)是針對避障問題中某個過程的研究，但是關(guān)于整個避障體系的闡述很少且存在部分局限性,對激光數(shù)據(jù)采集，進行障礙物檢測、預測及避撞研究，闡述一套完整的避障體系。

1 障礙物檢測

利用激光傳感器在不同時刻的掃描數(shù)據(jù)區(qū)分環(huán)境中存在的動態(tài)和靜態(tài)障礙物，并求解出動態(tài)障礙物的運動狀態(tài)。在障礙物檢測過程中，以機器人為中心設(shè)定圓形窗口，在窗口內(nèi)進行利用激光傳感器進行數(shù)據(jù)采集，對所獲得的激光數(shù)據(jù)進行聚類、匹配和分類操作區(qū)分出動靜障礙物，對動態(tài)障礙物進行分析確定障礙物的運動速度和方向角度。記錄障礙物和機器人運動信息，繪制當前窗口內(nèi)的動態(tài)地圖，動態(tài)地圖隨著圓形窗口不斷更新。

1.1 激光傳感器數(shù)據(jù)采集

柵格地圖[9]具有易于構(gòu)建和維護的特點且不需要其他參數(shù)，因此采用柵格地圖建立環(huán)境模型。現(xiàn)規(guī)定機器人攜帶的激光傳感器和機器人本身采用同一坐標系以及機器人的出發(fā)點與世界坐標系的原點重合。同時，通過激光傳感器對周圍障礙物的掃描獲取環(huán)境信息。

采用德國SICK公司生產(chǎn)的二維激光傳感器，根據(jù)激射出的脈沖紅外激光束碰到物體發(fā)生反射，由接收器接接收，通過時間間隔來計算出目標距離。它的角度分辨率為0.5°，在180°的掃描范圍內(nèi)可獲得361個障礙物距離數(shù)據(jù)點。障礙物的位置信息可以表示為(ρo,θo)(o=1,2,...361)，其中：ρo、θo分別表示機器人到障礙物的距離及角度。障礙物位置(xo,yo)在機器人世界坐標系中的表示如式(1)所示。

(1)

再通過式(2)映射到柵格地圖中的位置。

(2)

1.2 障礙點聚類

機器人在圓形窗口運動，利用激光傳感器掃描障礙物獲得的是一些孤立的點集，為了確定這些點集所屬的目標障礙物，提出一種自適應閾值的最近鄰聚類方法。

規(guī)定圓形窗口內(nèi)獲得的激光數(shù)據(jù)為有效數(shù)據(jù)，對其進行聚類。采樣時刻t時，通過比較連續(xù)障礙點的距離和預先設(shè)定閾值的關(guān)系判斷是否屬于同一障礙物：當兩點間的距離小于閾值，則認為兩個點屬于同一障礙物；若兩點間的距離大于閾值，則認為兩點不屬于同一障礙物，即表示有新障礙物出現(xiàn)，依次將每個數(shù)據(jù)點與它前一個點進行比較完成聚類。自適應閾值的設(shè)定如式(3)、(4)所示。

d≈r·sin(0.5°)

(3)

d'=λ·d

(4)

d表示相鄰兩激光反射點之間的距離，r表示激光束的長度，λ表示自適應參數(shù)。

聚類后可以得到若干個障礙聚類子集Ok(t)構(gòu)成的障礙物鏈Ob_list(t)，如式(5)、(6)所示。

Ob_list(t)={O1(t),O2(t),···,OK(t)}

(5)

Ok(t)={IDk(t),Zk(t),Sk(t),Vk(t)}

(6)

IDk(t)表示障礙物的狀態(tài)量；Zk(t)表示質(zhì)心；Sk(t)表示區(qū)域面積；Vk(t)表示動態(tài)障礙物的速度。

對先前聚類的障礙數(shù)據(jù)進行時間關(guān)聯(lián)性分析來確定獲得的障礙物類型及運動障礙物的運動信息，評估函數(shù)如式(7)所示。

(7)

(8)

其中，F(xiàn)表示障礙子集質(zhì)心間的距離；G表示兩障礙子集不重合面積占總面積的比重；λF，λG表示系數(shù)。

根據(jù)評估函數(shù)的大小得到的障礙物類型如圖1所示。

圖1 障礙物聚類結(jié)果

如圖1(a)所示，在相鄰時刻，C值最大，可認定障礙物為靜態(tài)障礙物。

如圖1(b)所示，在相鄰時刻，C值最小，可認定障礙物為兩個不同的障礙物。

如圖1(c)所示，在相鄰時刻，C值處于最大最小值之間，可認定障礙物為動態(tài)障礙物。

1.3 匹 配

機器人不斷地運動，激光傳感器時刻采集障礙物數(shù)據(jù)，為了確定不同時刻得到的障礙物是否來自同一個障礙物，需要對當前時刻障礙物鏈表Ob_list(t)中的障礙物和上一時刻障礙物鏈表Ob_list(t-1)中的障礙物進行配對操作。配對的障礙物是同一個障礙物的條件是兩個障礙物數(shù)據(jù)關(guān)聯(lián)評估函數(shù)的取值大于預先設(shè)定的閾值c。具體實現(xiàn)過程如圖2所示 。

圖2 障礙物匹配流程圖

1.4 分 類

完成配對的同一個障礙物，需要進行分類來區(qū)分是靜態(tài)障礙物還是動態(tài)障礙物。具體實現(xiàn)過程如圖3所示。其中ηk表示障礙子集合的點重合度。

圖3 障礙物分類流程圖

1.5 運動障礙物運動信息

對聚類后獲得的動態(tài)障礙物進一步分析計算出其運動的速度以及角度。

圖4 障礙物運動過程

(9)

(10)

(11)

(12)

其中，γ表示機器人的航向角；vO、αO分分別表示障礙物運動的速度和方向角度。

2 障礙物預測

障礙物預測是根據(jù)障礙物的運行軌跡來預測移動機器人和運動障礙物的碰撞關(guān)系。機器人在行走過程中，會遇到突發(fā)的障礙物，機器人根據(jù)自身攜帶的激光傳感器對運動障礙物進行檢測，獲得運動信息并結(jié)合自身的運行信息繪制出圓形窗口內(nèi)的動態(tài)地圖來預測碰撞情況。這里針對以下可能發(fā)生碰撞的幾種情況進行討論。

圖5 預測情況1

如圖5所示，當機器人緩慢行走時，探測前方有障礙物以較快速度運動，得出障礙物的運動方向和速度，預測不會與障礙物相撞。

圖6 預測情況2

如圖6所示，機器人探測到前方有動態(tài)障礙物以較慢速度運動，得出障礙物的運動方向和速度，預測兩者發(fā)生碰撞的位置。

如圖7所示，機器人探測到對向而來的動態(tài)障礙物，兩者相撞不可避免，預測發(fā)生碰撞的位置。

圖7 預測情況3

3 障礙物避撞

這個過程主要是決策規(guī)劃出合理的行走路徑來進行靜態(tài)或動態(tài)障礙物避讓，利用Morphin算法進行實現(xiàn)。

Morphin算法是一種基于地面分析以及對先驗柵格地圖進行可行性統(tǒng)計分析的局部路徑避障算法。如圖8所示，機器人探測到障礙物時會在位置前設(shè)置數(shù)條避開障礙物的備選路徑，再根據(jù)機器人當前狀態(tài)以及備選路徑的評價函數(shù)選出一條最優(yōu)避障路徑。

圖8 Morphin算法備選路徑

以機器人當前位置和障礙物的連線作為Morphin算法的中心線，其方向始終朝向障礙物，在中心線左右兩側(cè)各畫若干條弧線，并采用式(13)對每條弧線進行評價。

(13)

其中，D表示每條弧線路徑的長度；M表示每條弧線路徑的拐點參數(shù)；ΔL表示弧線所經(jīng)過的每個柵格點到子目標點距離的平均值；W表示弧線終點與子目標點連線與障礙物柵格相交的次數(shù)；ε1、ε2、ε3、ε4表示各個參數(shù)的權(quán)值。當障礙物位于弧線上時，評價函數(shù)y的值為無窮大，y值最小的那條弧線表示局部最優(yōu)路徑。

圖9 總體流程圖

圖10 仿真結(jié)果圖

機器人行走過程中，遇到靜態(tài)障礙物和各種動態(tài)障礙物，采取不同的避障策略。

當檢測到靜態(tài)障礙物時，直接調(diào)用Morphin算法；當遇到圖5所示的情況，機器人不采取任何措施，繼續(xù)運行；當遇到圖6所示的情況，機器人將停止運行直到障礙物離開預測的碰撞點；當遇到圖7所示的情況，機器人在到達碰撞點之前調(diào)用Morphin算法。

4 仿真實驗

為了說明上述所提的算法對移動機器人在未知環(huán)境中避障的有效性，在Matlab進行仿真驗證。算法總體流程圖如圖9所示。

仿真結(jié)果如圖10所示。V1、V2、V3、V4表示圓形窗口；S1、S2、S3、S4表示檢測到的靜態(tài)障礙物；D1、D2、D3-1、D3-2、D4表示檢測到的動態(tài)障礙物；B、C、E表示機器人檢測到動態(tài)障礙物位置；A、D、F表示機器人避障發(fā)生的位置。窗口內(nèi)其他黑色圓形表示檢測到的其他障礙物；窗口外灰色圓形表示無效區(qū)域內(nèi)的障礙物，不參與任何避障操作。

表1 障礙物運動速度和角度

從圖10和表1看出，機器人在V1窗口內(nèi)運動，構(gòu)建出動態(tài)窗口地圖，在該地圖內(nèi)，機器人在A點檢測到障礙物S1調(diào)用Morphin算法進行避障，在A到B段，檢測到動態(tài)障礙物D1的運行速度為450mm/s，角度為80.83°；一旦機器人超出V1的有效區(qū)域，立即構(gòu)建V2的圓形窗口，在C到D段檢測到動態(tài)障礙物D2的運動運行速度為760mm/s，角度為62.47°，并在D處檢測到障礙物S3立即調(diào)用Morphin算法。同樣地，超出V2有效區(qū)域，構(gòu)建V3的圓形窗口，當運行到E點時，檢測到障礙物D3-1運行速度為510mm/s，角度為91.05°，在O1處發(fā)生碰撞，此時機器人將采取暫停運行操作，但檢測到障礙物D3-2遠離碰撞點時，則開始運行；當在V4窗口內(nèi)運行到F點時，檢測到對向而來的障礙物，其運行速度為805mm/s，角度為180.09°，預測碰撞不可避免，并預測到碰撞位置發(fā)生在O2處，此時機器人提前做出避障措施調(diào)用Morphin算法避開障礙物。

5 結(jié) 語

針對未知環(huán)境中移動機器人避障問題，提出一種基于激光傳感器的障礙物檢測、預測及避障方法。首先，設(shè)定圓形窗口作為機器人有效掃描區(qū)域，根據(jù)采用自適應閾值的最近鄰聚類方法對激光數(shù)據(jù)進行聚類，通過匹配和分類算法確定障礙物類型，完成運動障礙物速度和方向角的檢測；再通過實時繪制窗口內(nèi)的動態(tài)局部地圖來預測移動機器人和障礙物碰撞的關(guān)系，結(jié)合Morphin算法做出相應避障措施。仿真實驗表明，移動機器人能夠有效地檢測出障礙物，進行碰撞預測，并做出合理地避障措施。下一步，將該算法用于實驗室機器人上進行驗證，并考慮與其他傳感器的融合，進一步提高避障性能。