多功能室外智能移動機器人避障軌跡自動規劃方法

劉學文，任興貴，許 諾，徐定杰

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

1 引言

多功能室外移動機器人是一種高智能機器人系統，其可以滿足多種要求，如進行自主駕駛、輔助駕駛、車道分界線的快速視覺檢測等功能，在智能傳輸導航系統、巡檢清潔、智能農業以及工業自動化等領域都有著重要應用。路徑規劃是機器人技術的核心問題，它要求機器人能夠在室外不間斷實時感知周圍環境，迅速進行判斷，自動規劃出平滑、不碰撞的可靠路徑。其中，不斷提高移動機器人智能導航性能的關鍵技術是視覺技術和智能控制技術，許多學者對此展開了大量的研究，但是效果還不是十分理想，如文獻[3]提出的Bezier曲線算法，該算法規劃的運行軌跡存在超調，不連續等問題，文獻[4]提出的灰狼優化算法不能實時地感知周圍環境到時軌跡自動規劃效果較差。

為此本文研究一種多功能室外智能移動機器人避障軌跡自動規劃方法，該方法在復雜的室外環境下，可快速實時地規劃出最優路徑，即用最短的時間和最小的耗能到達目標點位置。本文利用改進遺傳算法對多個空間搜索而不會限于局部最優，簡化二維路徑編碼，用一維路徑編碼融合調整的適應度函數，選擇最優的適應度函數，對自適應參數進行改進，得到改進的遺傳算法，提高了遺傳算法運算效率，從而獲取穩定性高的最短路徑，提高移動機器人動態避障能力。仿真實驗結果證明所提方法可以很好地解決因局部極小值而不能到達目標的問題。在室外移動機器人的避障軌跡規劃過程中，發揮出快速、準確的優勢。

2 避障軌跡自動規劃方法設計

多功能室外智能移動機器人的傳感參量-控制-避障動作物理模型架構主要由多功能室外智能移動機器人、機器人運動機構、機器人運動控制單元、機器人避障裝置、避障處理單元和3個紅外傳感器組構成，如圖1所示。

根據圖1可知，利用3種紅外傳感器組，檢測多功能室外智能移動機器人避障軌跡，按照獲取的避障通知信號發送端位置，對多功能室外智能移動機器人和障礙物的相對位置進行估計，并依據其相對位置進行避障處理，以提高避障判斷的準確性。

采用改進遺傳算法實現多功能室外智能移動機器人避障軌跡自動規劃。遺傳算法可在進化過程中通過搜索由多個可行解構成的群體空間的不同區域，獲取近似全局最優解。通過在遺傳算法中加入自適應調整方法改進遺傳算法的自適應參數，使路徑規劃效果更好。

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

2.1 遺傳操作算子

1) 復制算子。以隨機的初始種群為起點，為群體規模，隨機產生路徑(=1，2，…，)，將與適配值成比例的概率作為標準進行個體挑選，方法如下：

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

算出選擇復制的概率：∑

算出期望的復制數：

實際算出的復制數：期望復制數遵循四舍五入取整數。

2) 雜交算子。按照雜交概率(07左右)，進行交叉繁殖，繁殖的個體是任意復制產生的配對，經過交叉后，產生一對新個體。

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

4) 優化結果。最終的優化標準就是在坐標得到的最優路徑，是通過算法不斷循環最后收斂得出的最優結果。而一個循環的結束的標志是新一代群體出現。

2.2 路徑編碼方式

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

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

2.3 選擇適應度函數

遺傳算法的優劣主要取決于適應度調整方法，為了使多功能室外智能移動機器人可以自動規劃一條最優避障路線，適應度函數的選擇顯得十分重要。

本文中選擇的適應度函數需要既能把路徑規劃的必要條件用于遺傳優化中又使用了最少的適應度函數項數。其中路邊約束、動態避障、路徑最短適應度函數，是路徑規劃的必要條件，3個條件的實現過程如下：

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

(1)

其中，路徑上所有點是。當適應度為1時，則說明各路徑點在路邊安全距離內，否則為0。

2) 動態避障適應度函數。有個重要的約束條件就是動態避障。如果機器的視覺與激光雷達可確定障礙物個數、位置、速度等信息，則規劃局部動態路徑規劃時，忽略機器人與障礙物運行速度的改變原因是：控制周期小于400 ms，且障礙物和機器人都可以假設均保持勻速直線運動，機器人運行速度被路徑跟蹤控制算法控制。機器人與障礙物的半徑和要小于各點與障礙物間最小距離，這是動態規避的基本保障。

設是機器人從點到(，)所需時間，-1是從-1(-1，-1)到(，)所需時間，則存在：

=-1+-1

(2)

(3)

其中，當前機器人運行速度為，設在時刻，第個障礙物位置是(()，())，則有：

()=()+

()=()+

(4)

其中，第個障礙物的起始坐標是(()，())，第個障礙物當前運行速度在坐標系分量是、。

設在時刻，是第個障礙物與路徑點(,)的距離，用式(5)表示：

(5)

則在任意路徑上障礙物與點的最短距離是：

=min()

(6)

其中，=1，2，…，；=1，2，…，。組成路徑點的個數為，障礙物的個數是。因此,動態避障的適度函數2是：

(7)

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

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

(8)

最終得到遺傳算法的綜合適應度函數是：

[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)的綜合適應度函數，不僅能夠規避三項加權求和的不穩定問題，還可以整合三項約束條件。

2.4 改進自適應參數

為了進一步優化遺傳算法，本文中將自適應參數進行改進，這樣就可以使用最少的運算，實現最多的路線規劃，提高了路徑規劃效率，減少紅外傳感器檢測機器人避障軌跡速度，進而得到最優避障軌跡。

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

=(-)

(10)

=(-)

(11)

其中，、為比例系數。通常同一代的不同個體、值也不同，是為了保證優良個體得以繁殖。、值越小越能為適應值優良個體提供保障，、值大表示個體的適應值差。所以、也與變異個體適應值、交叉個體適應值′有關系。具體表達式為式(11)、式(12)：

(11)

(12)

其中，0≤,,,≤10，且為常數。基于改進遺傳算法的多功能室外智能移動機器人避障軌跡自動規劃流程如圖3所示。

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

根據圖3可知，基于改進遺傳算法的多功能室外智能移動機器人避障軌跡自動規劃流程主要通過隨機初始化種群，產生第一對新個體，轉化路徑編碼方式，選擇路邊約束適應度函數、動態避障適應度函數和路徑最短適應度函數，改進自適應參數，通過交叉和變異操作，產生下一代種群，輸出最優路徑，實現多功能室外智能移動機器人避障軌跡自動規劃。

3 實驗結果

本文實驗選擇的智能移動機器人是深圳史河機器人科技有限公司生產的MR700輕型四驅移動機器人，該機器人四驅驅動搭載單懸架系統和預裝Ubuntu 64位系統。選取Gazebo作為移動機器人避障軌跡仿真實驗平臺，具有很多傳感器模型庫，可實現低中速全自主行駛，實現快速視覺檢測，通過傳感器得到傳感參量，包括溫度23 ℃、外界重力9.78 m/s等參數，MR700輕型四驅移動機器人的技術參數如表1所示。

表1 移動機器人的技術參數

采用本文中方法規劃機器人路徑，設遺傳算法和改進遺傳算法的種群大小為40，初始交叉率0.6，初始交叉變異率0.4，平滑概率0.35，偏轉角度期望值45°。安全裕度1.0。求得的最小值，也是安全范圍和平滑條件的最短路徑。具體仿真實驗結果如下：

隨著進化代數的增加，實驗分析遺傳算法以及本文中方法采用的改進遺傳算法的種群平均適應值及最優個體之間的變化關系，結果用圖4表示。

圖4 不同算法進化代數與適應值關系曲線Fig.4 Relationship between evolutionary algebra and fitness of different algorithms

由圖4可得，改進遺傳算法隨著進化代數的增加，平均值與最優值都在不斷地變化，到進化代數達到45代以后，平均值和最優值都得到有效收斂，趨于穩定和統一，最終得到最優值。該圖直觀呈現了適應度值與進化代數間關系。遺傳算法隨著進化代數的增加，平均值與最優值在進化代數達到60代后，才得到收斂，數據才相對穩定，得到最優值。

通過對比可得出，本文方法采用的改進遺傳算法，種群平均適應值及最優個體進化次數更少，更快速地得到最佳值，從而在規劃路徑時，更具有優勢。

本文方法應用的改進遺傳算法通過不斷迭代優化，尋找安全平滑的最短路徑結果如圖5所示。

圖5 優化算法與最優路徑關系圖Fig.5 Relationship between optimization algorithm and optimal path

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

為進一步驗證本文方法的避障規劃效果，與文獻[3]的Bezier曲線軌跡規劃方法與文獻[4]的改進灰狼軌跡規劃方法進行比較，設置3種情景描述移動機器人的避障所耗時間。3種方法的路徑規劃仿真對象為MR700輕型四驅移動機器人，均無負載，每種情景的起點與終點位置一致，溫度、重力、障礙物擺放位置也相同，仿真障礙物相對位置關系如圖6所示。

圖6 障礙物相對位置關系示意圖Fig.6 Relative position relationship of obstacles

仿真實驗具體情景如下。

情景A：障礙物數量為8個，起點與目標點都在安全半徑之內，障礙物與輪式機器人距離5 m。

情景B：障礙物數量為8個，起點在安全半徑內，目標位置在安全半徑之外，障礙物與輪式機器人距離10 m。

情景C：障礙物數量為12個，起點與目標位置均在安全半徑之外，障礙物與輪式機器人距離15 m。

仿真實驗結果如表2所示。

表2 移動機器人運動耗時Table 2 Comparison of time-consuming movement of mobile robots s

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

4 結論

本文研究的規劃方法主要是利用改進遺傳算法尋優的過程，實現多功能室外智能移動機器人避障軌跡的高質量自動規劃。通過仿真實驗結果得出如下結論：

1) 在設置的參數一致的情況下，本文提出的避障軌跡自動規劃方法，種群平均適應值及最優個體進化次數更少，得到最優路徑更快。

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

3) 對比傳統規劃方法，本文方法所耗時間更少，更能有效地提高移動機器人的作業效率。

4) 本文提出的多功能室外智能移動機器人避障軌跡自動規劃方法更具有實時性、穩定性。最優路徑規劃更具有避障功能，在實際的應用過程中，節省時間，提高工作效率。