劉學(xué)文，任興貴，許 諾，徐定杰

(1.哈爾濱工業(yè)大學(xué)，哈爾濱 150000；2.廣州華夏職業(yè)學(xué)院，廣州 510935)

1 引言

多功能室外移動(dòng)機(jī)器人是一種高智能機(jī)器人系統(tǒng)，其可以滿足多種要求，如進(jìn)行自主駕駛、輔助駕駛、車(chē)道分界線的快速視覺(jué)檢測(cè)等功能，在智能傳輸導(dǎo)航系統(tǒng)、巡檢清潔、智能農(nóng)業(yè)以及工業(yè)自動(dòng)化等領(lǐng)域都有著重要應(yīng)用。路徑規(guī)劃是機(jī)器人技術(shù)的核心問(wèn)題，它要求機(jī)器人能夠在室外不間斷實(shí)時(shí)感知周?chē)h(huán)境，迅速進(jìn)行判斷，自動(dòng)規(guī)劃出平滑、不碰撞的可靠路徑。其中，不斷提高移動(dòng)機(jī)器人智能導(dǎo)航性能的關(guān)鍵技術(shù)是視覺(jué)技術(shù)和智能控制技術(shù)，許多學(xué)者對(duì)此展開(kāi)了大量的研究，但是效果還不是十分理想，如文獻(xiàn)[3]提出的Bezier曲線算法，該算法規(guī)劃的運(yùn)行軌跡存在超調(diào)，不連續(xù)等問(wèn)題，文獻(xiàn)[4]提出的灰狼優(yōu)化算法不能實(shí)時(shí)地感知周?chē)h(huán)境到時(shí)軌跡自動(dòng)規(guī)劃效果較差。

為此本文研究一種多功能室外智能移動(dòng)機(jī)器人避障軌跡自動(dòng)規(guī)劃方法，該方法在復(fù)雜的室外環(huán)境下，可快速實(shí)時(shí)地規(guī)劃出最優(yōu)路徑，即用最短的時(shí)間和最小的耗能到達(dá)目標(biāo)點(diǎn)位置。本文利用改進(jìn)遺傳算法對(duì)多個(gè)空間搜索而不會(huì)限于局部最優(yōu)，簡(jiǎn)化二維路徑編碼，用一維路徑編碼融合調(diào)整的適應(yīng)度函數(shù)，選擇最優(yōu)的適應(yīng)度函數(shù)，對(duì)自適應(yīng)參數(shù)進(jìn)行改進(jìn)，得到改進(jìn)的遺傳算法，提高了遺傳算法運(yùn)算效率，從而獲取穩(wěn)定性高的最短路徑，提高移動(dòng)機(jī)器人動(dòng)態(tài)避障能力。仿真實(shí)驗(yàn)結(jié)果證明所提方法可以很好地解決因局部極小值而不能到達(dá)目標(biāo)的問(wèn)題。在室外移動(dòng)機(jī)器人的避障軌跡規(guī)劃過(guò)程中，發(fā)揮出快速、準(zhǔn)確的優(yōu)勢(shì)。

2 避障軌跡自動(dòng)規(guī)劃方法設(shè)計(jì)

多功能室外智能移動(dòng)機(jī)器人的傳感參量-控制-避障動(dòng)作物理模型架構(gòu)主要由多功能室外智能移動(dòng)機(jī)器人、機(jī)器人運(yùn)動(dòng)機(jī)構(gòu)、機(jī)器人運(yùn)動(dòng)控制單元、機(jī)器人避障裝置、避障處理單元和3個(gè)紅外傳感器組構(gòu)成，如圖1所示。

根據(jù)圖1可知，利用3種紅外傳感器組，檢測(cè)多功能室外智能移動(dòng)機(jī)器人避障軌跡，按照獲取的避障通知信號(hào)發(fā)送端位置，對(duì)多功能室外智能移動(dòng)機(jī)器人和障礙物的相對(duì)位置進(jìn)行估計(jì)，并依據(jù)其相對(duì)位置進(jìn)行避障處理，以提高避障判斷的準(zhǔn)確性。

采用改進(jìn)遺傳算法實(shí)現(xiàn)多功能室外智能移動(dòng)機(jī)器人避障軌跡自動(dòng)規(guī)劃。遺傳算法可在進(jìn)化過(guò)程中通過(guò)搜索由多個(gè)可行解構(gòu)成的群體空間的不同區(qū)域，獲取近似全局最優(yōu)解。通過(guò)在遺傳算法中加入自適應(yīng)調(diào)整方法改進(jìn)遺傳算法的自適應(yīng)參數(shù)，使路徑規(guī)劃效果更好。

圖1 多功能室外智能移動(dòng)機(jī)器人的傳感 參量-控制-避障動(dòng)作物理模型架構(gòu)框圖Fig.1 Physical model architecture of sensing parameter control obstacle avoidance action of multifunctional outdoor intelligent mobile robot

2.1 遺傳操作算子

1) 復(fù)制算子。以隨機(jī)的初始種群為起點(diǎn)，為群體規(guī)模，隨機(jī)產(chǎn)生路徑(=1，2，…，)，將與適配值成比例的概率作為標(biāo)準(zhǔn)進(jìn)行個(gè)體挑選，方法如下：

算出個(gè)體適配值：(=1，2，…，)

算出選擇復(fù)制的概率：∑

算出期望的復(fù)制數(shù)：

實(shí)際算出的復(fù)制數(shù)：期望復(fù)制數(shù)遵循四舍五入取整數(shù)。

2) 雜交算子。按照雜交概率(07左右)，進(jìn)行交叉繁殖，繁殖的個(gè)體是任意復(fù)制產(chǎn)生的配對(duì)，經(jīng)過(guò)交叉后，產(chǎn)生一對(duì)新個(gè)體。

3) 變異算子。變異是隨意打亂群體中的基因，為避免過(guò)度成熟而丟失重要遺傳信息，每個(gè)基因的變異概率在0000 9～009。變異要和雜交混合使用。但為保證下一代結(jié)構(gòu)不會(huì)被破壞，變異要低概率進(jìn)行。

4) 優(yōu)化結(jié)果。最終的優(yōu)化標(biāo)準(zhǔn)就是在坐標(biāo)得到的最優(yōu)路徑，是通過(guò)算法不斷循環(huán)最后收斂得出的最優(yōu)結(jié)果。而一個(gè)循環(huán)的結(jié)束的標(biāo)志是新一代群體出現(xiàn)。

2.2 路徑編碼方式

采用遺傳算法進(jìn)行路徑規(guī)劃過(guò)程中，在線計(jì)算的時(shí)間跟編碼的長(zhǎng)度與搜索空間有關(guān)。所以本文的規(guī)劃方法是選擇了一種將路徑的二維碼變成一維碼的簡(jiǎn)化編碼長(zhǎng)度的方式，如圖2所示。多功能室外智能移動(dòng)機(jī)器人當(dāng)前的位置為起點(diǎn)，預(yù)測(cè)的局部路徑為目標(biāo)點(diǎn)，起點(diǎn)和目標(biāo)點(diǎn)之間的距離是規(guī)劃路徑。最優(yōu)路徑點(diǎn)序列坐標(biāo)可通過(guò)路邊限制區(qū)域得到，調(diào)整二維路徑點(diǎn)序列坐標(biāo)需在原地面坐標(biāo)系內(nèi)完成，最終得到新坐標(biāo)，該過(guò)程能夠使得編碼長(zhǎng)度減少。起點(diǎn)與目標(biāo)點(diǎn)間連線是軸，將其劃分成個(gè)相同段，一維坐標(biāo)編碼改進(jìn)過(guò)程可以看成是簡(jiǎn)化的改進(jìn)的路徑的過(guò)程。

圖2 簡(jiǎn)化路徑編碼方式示意圖Fig.2 Schematic diagram of path coding mode

2.3 選擇適應(yīng)度函數(shù)

遺傳算法的優(yōu)劣主要取決于適應(yīng)度調(diào)整方法，為了使多功能室外智能移動(dòng)機(jī)器人可以自動(dòng)規(guī)劃一條最優(yōu)避障路線，適應(yīng)度函數(shù)的選擇顯得十分重要。

本文中選擇的適應(yīng)度函數(shù)需要既能把路徑規(guī)劃的必要條件用于遺傳優(yōu)化中又使用了最少的適應(yīng)度函數(shù)項(xiàng)數(shù)。其中路邊約束、動(dòng)態(tài)避障、路徑最短適應(yīng)度函數(shù)，是路徑規(guī)劃的必要條件，3個(gè)條件的實(shí)現(xiàn)過(guò)程如下：

1) 路邊約束適應(yīng)度函數(shù)。圖2所示的路徑編碼方式中折線方式描述的機(jī)器視覺(jué)獲取的信息，可求出路邊各折線方程。由于解空間范圍被路邊約束限定，所以要在路邊約束區(qū)域中選取不同值，選取過(guò)程為：確定路兩邊折線與軸所有垂直直線的2個(gè)交點(diǎn)的軸坐標(biāo)值和所有位置;基于機(jī)器人中心與大于移動(dòng)機(jī)器人最高半徑的路邊安全距離，則可得到路中心收縮量。選定的范圍(1,2)。用式(1)描述路邊約束適應(yīng)度函數(shù)1：

(1)

其中，路徑上所有點(diǎn)是。當(dāng)適應(yīng)度為1時(shí)，則說(shuō)明各路徑點(diǎn)在路邊安全距離內(nèi)，否則為0。

2) 動(dòng)態(tài)避障適應(yīng)度函數(shù)。有個(gè)重要的約束條件就是動(dòng)態(tài)避障。如果機(jī)器的視覺(jué)與激光雷達(dá)可確定障礙物個(gè)數(shù)、位置、速度等信息，則規(guī)劃局部動(dòng)態(tài)路徑規(guī)劃時(shí)，忽略機(jī)器人與障礙物運(yùn)行速度的改變?cè)蚴牵嚎刂浦芷谛∮?00 ms，且障礙物和機(jī)器人都可以假設(shè)均保持勻速直線運(yùn)動(dòng)，機(jī)器人運(yùn)行速度被路徑跟蹤控制算法控制。機(jī)器人與障礙物的半徑和要小于各點(diǎn)與障礙物間最小距離，這是動(dòng)態(tài)規(guī)避的基本保障。

設(shè)是機(jī)器人從點(diǎn)到(，)所需時(shí)間，-1是從-1(-1，-1)到(，)所需時(shí)間，則存在：

=-1+-1

(2)

(3)

其中，當(dāng)前機(jī)器人運(yùn)行速度為，設(shè)在時(shí)刻，第個(gè)障礙物位置是(()，())，則有：

()=()+

()=()+

(4)

其中，第個(gè)障礙物的起始坐標(biāo)是(()，())，第個(gè)障礙物當(dāng)前運(yùn)行速度在坐標(biāo)系分量是、。

設(shè)在時(shí)刻，是第個(gè)障礙物與路徑點(diǎn)(,)的距離，用式(5)表示：

(5)

則在任意路徑上障礙物與點(diǎn)的最短距離是：

=min()

(6)

其中，=1，2，…，；=1，2，…，。組成路徑點(diǎn)的個(gè)數(shù)為，障礙物的個(gè)數(shù)是。因此,動(dòng)態(tài)避障的適度函數(shù)2是：

(7)

式中:表示起始坐標(biāo)與障礙物之間的半徑；表示安全半徑。綜合上述分析能夠得出：遇到障礙物時(shí)，要想使得機(jī)器人可以成功實(shí)現(xiàn)避障，應(yīng)該確保其同障礙物間的安全半徑和低于路徑各點(diǎn)同不同障礙物的最低距離，且該種情況下適應(yīng)度是1，否則是0。

3) 路徑最短適應(yīng)度函數(shù)。選擇路徑最短的適應(yīng)度函數(shù)如式(8)：

(8)

最終得到遺傳算法的綜合適應(yīng)度函數(shù)是：

[1]Laufer,B.&P.,Nation.(1999).A Vocabulary Size Test of Controlled Productive Ability,Language Testing,16(1).33-51.

=1×2×3

(9)

式(9)的綜合適應(yīng)度函數(shù)，不僅能夠規(guī)避三項(xiàng)加權(quán)求和的不穩(wěn)定問(wèn)題，還可以整合三項(xiàng)約束條件。

2.4 改進(jìn)自適應(yīng)參數(shù)

為了進(jìn)一步優(yōu)化遺傳算法，本文中將自適應(yīng)參數(shù)進(jìn)行改進(jìn)，這樣就可以使用最少的運(yùn)算，實(shí)現(xiàn)最多的路線規(guī)劃，提高了路徑規(guī)劃效率，減少紅外傳感器檢測(cè)機(jī)器人避障軌跡速度，進(jìn)而得到最優(yōu)避障軌跡。

種群最優(yōu)個(gè)體適應(yīng)值用表示，同一種群平均適應(yīng)值用表示，從關(guān)系式=-中可得出，當(dāng)局部最優(yōu)和過(guò)早收斂的可能性大時(shí)，種群個(gè)體間適應(yīng)值差別小，的值也小；反之則值大。種群收斂程度用平均適應(yīng)值和最優(yōu)適應(yīng)值之間的差距描述。-也可以決定交叉概率和變異概率的參數(shù)。實(shí)際上，式(10)、式(11)的描述反映出、值是和-成反比關(guān)系的。

=(-)

(10)

=(-)

(11)

其中，、為比例系數(shù)。通常同一代的不同個(gè)體、值也不同，是為了保證優(yōu)良個(gè)體得以繁殖。、值越小越能為適應(yīng)值優(yōu)良個(gè)體提供保障，、值大表示個(gè)體的適應(yīng)值差。所以、也與變異個(gè)體適應(yīng)值、交叉?zhèn)€體適應(yīng)值′有關(guān)系。具體表達(dá)式為式(11)、式(12)：

(11)

(12)

其中，0≤,,,≤10，且為常數(shù)?；诟倪M(jìn)遺傳算法的多功能室外智能移動(dòng)機(jī)器人避障軌跡自動(dòng)規(guī)劃流程如圖3所示。

圖3 基于改進(jìn)遺傳算法的多功能室外智能 移動(dòng)機(jī)器人避障軌跡自動(dòng)規(guī)劃流程框圖Fig.3 Flow chart of obstacle avoidance trajectory automatic planning of multifunctional outdoor intelligent mobile robot based on improved genetic algorithm

根據(jù)圖3可知，基于改進(jìn)遺傳算法的多功能室外智能移動(dòng)機(jī)器人避障軌跡自動(dòng)規(guī)劃流程主要通過(guò)隨機(jī)初始化種群，產(chǎn)生第一對(duì)新個(gè)體，轉(zhuǎn)化路徑編碼方式，選擇路邊約束適應(yīng)度函數(shù)、動(dòng)態(tài)避障適應(yīng)度函數(shù)和路徑最短適應(yīng)度函數(shù)，改進(jìn)自適應(yīng)參數(shù)，通過(guò)交叉和變異操作，產(chǎn)生下一代種群，輸出最優(yōu)路徑，實(shí)現(xiàn)多功能室外智能移動(dòng)機(jī)器人避障軌跡自動(dòng)規(guī)劃。

3 實(shí)驗(yàn)結(jié)果

本文實(shí)驗(yàn)選擇的智能移動(dòng)機(jī)器人是深圳史河機(jī)器人科技有限公司生產(chǎn)的MR700輕型四驅(qū)移動(dòng)機(jī)器人，該機(jī)器人四驅(qū)驅(qū)動(dòng)搭載單懸架系統(tǒng)和預(yù)裝Ubuntu 64位系統(tǒng)。選取Gazebo作為移動(dòng)機(jī)器人避障軌跡仿真實(shí)驗(yàn)平臺(tái)，具有很多傳感器模型庫(kù)，可實(shí)現(xiàn)低中速全自主行駛，實(shí)現(xiàn)快速視覺(jué)檢測(cè)，通過(guò)傳感器得到傳感參量，包括溫度23 ℃、外界重力9.78 m/s等參數(shù)，MR700輕型四驅(qū)移動(dòng)機(jī)器人的技術(shù)參數(shù)如表1所示。

表1 移動(dòng)機(jī)器人的技術(shù)參數(shù)

采用本文中方法規(guī)劃?rùn)C(jī)器人路徑，設(shè)遺傳算法和改進(jìn)遺傳算法的種群大小為40，初始交叉率0.6，初始交叉變異率0.4，平滑概率0.35，偏轉(zhuǎn)角度期望值45°。安全裕度1.0。求得的最小值，也是安全范圍和平滑條件的最短路徑。具體仿真實(shí)驗(yàn)結(jié)果如下：

隨著進(jìn)化代數(shù)的增加，實(shí)驗(yàn)分析遺傳算法以及本文中方法采用的改進(jìn)遺傳算法的種群平均適應(yīng)值及最優(yōu)個(gè)體之間的變化關(guān)系，結(jié)果用圖4表示。

圖4 不同算法進(jìn)化代數(shù)與適應(yīng)值關(guān)系曲線Fig.4 Relationship between evolutionary algebra and fitness of different algorithms

由圖4可得，改進(jìn)遺傳算法隨著進(jìn)化代數(shù)的增加，平均值與最優(yōu)值都在不斷地變化，到進(jìn)化代數(shù)達(dá)到45代以后，平均值和最優(yōu)值都得到有效收斂，趨于穩(wěn)定和統(tǒng)一，最終得到最優(yōu)值。該圖直觀呈現(xiàn)了適應(yīng)度值與進(jìn)化代數(shù)間關(guān)系。遺傳算法隨著進(jìn)化代數(shù)的增加，平均值與最優(yōu)值在進(jìn)化代數(shù)達(dá)到60代后，才得到收斂，數(shù)據(jù)才相對(duì)穩(wěn)定，得到最優(yōu)值。

通過(guò)對(duì)比可得出，本文方法采用的改進(jìn)遺傳算法，種群平均適應(yīng)值及最優(yōu)個(gè)體進(jìn)化次數(shù)更少，更快速地得到最佳值，從而在規(guī)劃路徑時(shí)，更具有優(yōu)勢(shì)。

本文方法應(yīng)用的改進(jìn)遺傳算法通過(guò)不斷迭代優(yōu)化，尋找安全平滑的最短路徑結(jié)果如圖5所示。

圖5 優(yōu)化算法與最優(yōu)路徑關(guān)系圖Fig.5 Relationship between optimization algorithm and optimal path

從圖5數(shù)據(jù)可得出，本文方法應(yīng)用的改進(jìn)遺傳算法在迭代優(yōu)化過(guò)程中，路徑發(fā)生顯著改變。從路徑變化可得出，隨著不斷優(yōu)化，適應(yīng)值不斷收斂，機(jī)器人避障軌跡逐漸清晰，到第56代時(shí)，可以非常快速且清晰地找到最優(yōu)路徑，完成避障，仿真實(shí)驗(yàn)結(jié)果表明本文中方法的避障軌跡規(guī)劃效果較好。

為進(jìn)一步驗(yàn)證本文方法的避障規(guī)劃效果，與文獻(xiàn)[3]的Bezier曲線軌跡規(guī)劃方法與文獻(xiàn)[4]的改進(jìn)灰狼軌跡規(guī)劃方法進(jìn)行比較，設(shè)置3種情景描述移動(dòng)機(jī)器人的避障所耗時(shí)間。3種方法的路徑規(guī)劃仿真對(duì)象為MR700輕型四驅(qū)移動(dòng)機(jī)器人，均無(wú)負(fù)載，每種情景的起點(diǎn)與終點(diǎn)位置一致，溫度、重力、障礙物擺放位置也相同，仿真障礙物相對(duì)位置關(guān)系如圖6所示。

圖6 障礙物相對(duì)位置關(guān)系示意圖Fig.6 Relative position relationship of obstacles

仿真實(shí)驗(yàn)具體情景如下。

情景A：障礙物數(shù)量為8個(gè)，起點(diǎn)與目標(biāo)點(diǎn)都在安全半徑之內(nèi)，障礙物與輪式機(jī)器人距離5 m。

情景B：障礙物數(shù)量為8個(gè)，起點(diǎn)在安全半徑內(nèi)，目標(biāo)位置在安全半徑之外，障礙物與輪式機(jī)器人距離10 m。

情景C：障礙物數(shù)量為12個(gè)，起點(diǎn)與目標(biāo)位置均在安全半徑之外，障礙物與輪式機(jī)器人距離15 m。

仿真實(shí)驗(yàn)結(jié)果如表2所示。

表2 移動(dòng)機(jī)器人運(yùn)動(dòng)耗時(shí)Table 2 Comparison of time-consuming movement of mobile robots s

由表2可得，3種情境下，本文方法避障軌跡規(guī)劃時(shí)間均少于其他2種方法。可以有效地提高移動(dòng)機(jī)器人的作業(yè)效率。本文將路徑的二維碼變成一維碼的簡(jiǎn)化編碼長(zhǎng)度，并通過(guò)選擇適應(yīng)度函數(shù)，縮短了移動(dòng)機(jī)器人運(yùn)動(dòng)耗時(shí)，提高了多功能室外智能移動(dòng)機(jī)器人避障軌跡自動(dòng)規(guī)劃的運(yùn)算效率。

4 結(jié)論

本文研究的規(guī)劃方法主要是利用改進(jìn)遺傳算法尋優(yōu)的過(guò)程，實(shí)現(xiàn)多功能室外智能移動(dòng)機(jī)器人避障軌跡的高質(zhì)量自動(dòng)規(guī)劃。通過(guò)仿真實(shí)驗(yàn)結(jié)果得出如下結(jié)論：

1) 在設(shè)置的參數(shù)一致的情況下，本文提出的避障軌跡自動(dòng)規(guī)劃方法，種群平均適應(yīng)值及最優(yōu)個(gè)體進(jìn)化次數(shù)更少，得到最優(yōu)路徑更快。

2) 隨著本文方法應(yīng)用改進(jìn)遺傳算法不斷優(yōu)化，適應(yīng)值收斂，機(jī)器人在第56代時(shí)，可以快速且清晰地找到最優(yōu)路徑，完成避障。

3) 對(duì)比傳統(tǒng)規(guī)劃方法，本文方法所耗時(shí)間更少，更能有效地提高移動(dòng)機(jī)器人的作業(yè)效率。

4) 本文提出的多功能室外智能移動(dòng)機(jī)器人避障軌跡自動(dòng)規(guī)劃方法更具有實(shí)時(shí)性、穩(wěn)定性。最優(yōu)路徑規(guī)劃更具有避障功能，在實(shí)際的應(yīng)用過(guò)程中，節(jié)省時(shí)間，提高工作效率。