殷新凱 茅健 周玉鳳 陳曉平

摘? 要： 描繪了排爆機器人路徑規(guī)劃問題，提出了混合混沌序列與遺傳算法的排爆機器人路徑規(guī)劃算法。針對遺傳算法易于陷入局部收斂，在尋優(yōu)過程中易于出現(xiàn)抖振，算法收斂精度不高等問題，在遺傳算法中引入Logistic混沌序列，生成與機器人路徑選擇更加匹配的優(yōu)化算法。運用MATLAB進行算法仿真，分析比較經(jīng)典遺傳算法和優(yōu)化后的算法。仿真結(jié)果顯示，算法優(yōu)化后機器人行走路徑更加合理，算法的收斂精度提高。

關(guān)鍵詞： 排爆機器人; 遺傳算法; Logistic混沌序列; 路徑規(guī)劃

中圖分類號：TP242.3? ? ? ? ? 文獻標(biāo)志碼：A? ? ?文章編號：1006-8228（2019）07-05-04

Abstract： This paper describes the path planning problem of explosive disposal（EOD） robot， and proposes the path planning algorithm with hybrid chaotic sequence and genetic algorithm. Aiming at the problem that genetic algorithm is easy to fall into local convergence， it is prone to chattering in the optimization process， and the convergence accuracy of the algorithm is not high. Logistic chaotic sequences are introduced into the genetic algorithm to generate an optimized algorithm which is more suitable for robot path selection. MATLAB is used to simulate the algorithm， analyze and compare the classical genetic algorithm and the optimized algorithm， the simulation results show that the walking path of the robot with optimized algorithm is more reasonable and the convergence accuracy of the algorithm is improved.

Key words： explosive disposal robot; genetic algorithm; Logistic chaotic sequence; path planning

0 引言

隨著機器人技術(shù)的發(fā)展，以排爆為目標(biāo)的特種機器人的應(yīng)用日益廣泛。排爆機器人大大保護了排爆人員的安全，減少了排爆工作的危險程度。在排爆機器人從遠程控制到智能化的過程中，排爆機器人的路徑規(guī)劃是排爆機器人系統(tǒng)設(shè)計的重要問題之一。路徑規(guī)劃是指空間內(nèi)，機器人躲避障礙物，完成指定任務(wù)的合理路徑的選擇（合理一般是指時間最少或者能量損耗最小）[1]。因為工作環(huán)境的限制，要求排爆機器人能實現(xiàn)智能化路徑規(guī)劃，高效安全地完成自主避障路徑規(guī)劃的任務(wù)。

針對多機器人路徑規(guī)劃問題，孫樹棟等采用鏈接圖法標(biāo)識多機器人，簡化了機器人的工作環(huán)境，同時在遺傳算法基礎(chǔ)上引入適應(yīng)度值調(diào)整矩陣，對適應(yīng)度函數(shù)進行合理優(yōu)化，實現(xiàn)對多機器人運動路徑的優(yōu)化調(diào)整[2]。李慶中等將遺傳算法初始二維編碼問題簡化為一維編碼問題，針對傳統(tǒng)算法中適應(yīng)度函數(shù)評價標(biāo)準(zhǔn)過于復(fù)雜，簡化了評價指標(biāo)，優(yōu)化后的遺傳算法具有良好的動態(tài)避障功能[3]。陳曦等以具有精英保留的免疫遺傳算法和柵格法為基礎(chǔ)，引入刪除和插入算子，有效地優(yōu)化了算法精度[4]。Castillo等把長度和困難程度歸為對機器人路徑評價的標(biāo)準(zhǔn)，并在傳統(tǒng)遺傳算法基礎(chǔ)上擴展成多個目標(biāo)的遺傳算法，完成對兩種算法的性能測量和模擬結(jié)果[5]。Cai等采用新型協(xié)調(diào)進化自適應(yīng)遺傳算法，提出了一種新的固定長度十進制編碼機制，同時討論了多機器人系統(tǒng)的路徑規(guī)劃，驗證了算法的魯棒性[6]。

本文提出了混合Logistic混沌序列與遺傳算法的排爆機器人路徑規(guī)劃算法，在遺傳算法的交叉、變異操作中引入Logistic混沌序列，減少算法在尋優(yōu)過程中出現(xiàn)的抖振，提高算法收斂精度。

1 算法介紹

1.1 經(jīng)典遺傳算法

遺傳算法是一種基于自然選擇原理和遺傳機制的搜索算法，它通過模擬自然界生物的進化衍變，從而在人工系統(tǒng)中實現(xiàn)指定目標(biāo)的優(yōu)化過程[7]。

遺傳算法是移動機器人路徑規(guī)劃過程中使用較廣泛的一種算法。與其他常用算法如蟻群算法、粒子群算法和模擬退火算法相比較，遺傳算法優(yōu)點在易于找到最優(yōu)解，處理大數(shù)據(jù)上效率更高，缺點在于容易局部收斂和早熟的情況，同時還會出現(xiàn)尋優(yōu)抖振問題。

1.2 Logistic混沌序列

混沌是非線性科學(xué)的重要概念，它是確定性系統(tǒng)的一種類隨機現(xiàn)象[8]。混沌這一概念，應(yīng)用的最為廣泛的定義為Li-Yorke定義。具體的定義為：閉區(qū)間I上的連續(xù)自映射f（x）如果滿足以下三個條件，那么這個映射即為混沌的[9]。

⑴ f（x）的周期沒有上界;

⑵ 閉區(qū)間I上存在不可數(shù)子集S，S中無周期點;

⑶ ，有，其中，表示n重函數(shù)，Per（f）是f（x）的周期點的集合。

在以上定義的基礎(chǔ)上，一個混沌系統(tǒng)應(yīng)該具有三大性質(zhì)：一是存在所有階的周期軌道;二是存在一個不可數(shù)的集合，該集合不存在漸進周期軌道;三是混沌軌道高度不穩(wěn)定[9]。混沌系統(tǒng)存在著許多典型的混沌映射，其中，Logistic混沌序列是其中一種具有代表性的混沌映射。通過Logistic混沌序列描述種群的變化過程，其數(shù)學(xué)形式非常簡單但卻是具有重要意義的一維非線性迭代方程，其定義為：

其中，;分支參數(shù)，當(dāng)時序列進入混沌狀態(tài)，迭代產(chǎn)生的序列值處于一種類隨機分布的狀態(tài)，由不同的初始x1所生成的序列具有隨機性強的特點，且對初始值十分敏感[10-11]。

2 算法設(shè)計

遺傳算法的特點是：對于非線性問題，在大規(guī)模參數(shù)與解下，能夠迅速地找出局部最優(yōu)解?；具z傳算子當(dāng)中的交叉和變異是遺傳算法實現(xiàn)上述功能的關(guān)鍵。為了保證算法收斂精度，削弱尋優(yōu)過程中出現(xiàn)的抖振問題，本文對遺傳算法優(yōu)化，首先將交叉操作獨立于選擇、變異兩大算子，然后在交叉操作中引入Logistic混沌序列，成功地將混沌序列與遺傳算法聯(lián)系在一起，再利用混沌序列隨機性強的特點，確定交叉點，實現(xiàn)交叉操作，從而實現(xiàn)算法的優(yōu)化設(shè)計。依據(jù)此設(shè)計思路，機器人路徑規(guī)劃主要分為以下幾個步驟。

⑴ 實例設(shè)計

在長寬已知的平面上放置機器人、目標(biāo)物（根據(jù)要求將上述分別放在平面上兩個對角落）。同時在兩者的直線路徑上放置不同形狀大小的障礙物，如圖1所示。

⑵ 路徑構(gòu)造

將整個平面進行分塊命名，并且把各塊的邊界線上的中點找出連接，設(shè)為各區(qū)域的最短路徑。將出發(fā)點與目標(biāo)位置之間所有可能經(jīng)過的區(qū)域的最短路徑一一相連，可得到整體的最短路徑。如圖2所示。

⑶ 編碼設(shè)計

采用十進制的一維編碼方法，用隨機數(shù)列作為染色體，其中每一個隨機序列都對應(yīng)著各區(qū)域最短路徑。編碼i代表對應(yīng)區(qū)域代號。

⑷ 種群產(chǎn)生

初始種群，即為各區(qū)域最短距離的組合，所有從出發(fā)點到目標(biāo)位置的可能的總和。

⑸ 目標(biāo)函數(shù)

目標(biāo)函數(shù)為每條路徑的優(yōu)劣程度。本文中，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。適應(yīng)度函數(shù)的評價指標(biāo)是遺傳算法的重要組成部分。與傳統(tǒng)遺傳算法不同的是，對于排爆機器人適應(yīng)度評價指標(biāo)指的是機器人行走的距離和時間長短。排爆式機器人行走距離和時間主要考慮機器人行走時拐角的數(shù)量和拐角大小，當(dāng)拐角數(shù)越多，拐角越大時，機器人行走的時間也會隨之增加，因此，適應(yīng)度函數(shù)要求機器人行走距離和行走時間盡可能地減少。因此，適應(yīng)度函數(shù)確定為：

3 仿真分析

運用MATLAB對優(yōu)化后的算法進行仿真，并分析結(jié)果。

圖4分別為使用遺傳算法和優(yōu)化后的遺傳算法下機器人行走路徑。通過兩者對比，可以發(fā)現(xiàn)在使用改進后的算法后，機器人行走路徑更加平緩，行走距離減少。仿真實驗表明，優(yōu)化后的算法能使排爆機器人更快找到最短路徑。

圖5為在優(yōu)化遺傳算法與經(jīng)典遺傳算法兩種算法下，算法迭代次數(shù)與排爆機器人最短距離的關(guān)系圖。從圖5可以看出，改進后的算法，在初期，降低了算法有效解的范圍，減少了算法的搜索時間，在后期，減少機器人的最短距離。本文提出的算法要優(yōu)于傳統(tǒng)算法。

4 結(jié)束語

本文針對傳統(tǒng)遺傳算法在解決排爆機器人路徑規(guī)劃問題中，收斂精度不高等問題，提出了將Logistic混沌序列引入到遺傳算法中，實現(xiàn)對遺傳算法的優(yōu)化改進。該算法能夠有效地實現(xiàn)排爆機器人路徑規(guī)劃，該算法仍有繼續(xù)優(yōu)化的空間。

參考文獻（References）：

[1] 王仲民.移動機器人路徑規(guī)劃與軌跡跟蹤[M].兵器工業(yè)出版社，2008.

[2] 孫樹棟，林茂.基于遺傳算法的多移動機器人協(xié)調(diào)路徑規(guī)劃[J].自動化學(xué)報，2000.5：672-676

[3] 李慶中，顧偉康，葉秀清.基于遺傳算法的移動機器人動態(tài)避障路徑規(guī)劃方法[J].模式識別與人工智能，2002.15（2）：161-166

[4] 陳曦，譚冠政，江斌.基于免疫遺傳算法的移動機器人實時最優(yōu)路徑規(guī)劃[J].中南大學(xué)學(xué)報（自然科學(xué)版），2008.3：577-583

[5] Castillo O， Trujillo L， Melin P. Multiple Objective GeneticAlgorithms for Path-planning Optimization in Autonomous Mobile Robots[J]. Soft Computing，2007.11（3）：269-279

[6] Cai Z， Peng Z. Cooperative Coevolutionary AdaptiveGenetic Algorithm in Path Planning of Cooperative Multi-Mobile Robot Systems[J]. Journal of Intelligent and Robotic Systems：Theory and Applications，2002.33（1）：61-71

[7] 司守奎，孫璽菁.數(shù)學(xué)建模算法與應(yīng)用[M].國防工業(yè)出版社，2017.

[8] 江六林.基于混沌映射和DNA編碼的圖像加密技術(shù)的研究與實現(xiàn)[D].南京郵電大學(xué)，2016.

[9] 劉金波.基于DSP的混沌圖像加密系統(tǒng)的實現(xiàn)[D].大連理工大學(xué)，2008.

[10] 湯任君.Logistic混沌序列和DES算法的圖像加密方法[J].計算機應(yīng)用，2017.37（1）：89-92

[11] 劉睿.基于改進Logistic混沌映射的圖像自適應(yīng)加密算法[J].計算機與現(xiàn)代化，2016.7：13-17，23

[12] 王洲，張毅，楊銳敏.基于遺傳算法的移動機器人路徑規(guī)劃[J].微計算機信息，2008.24（26）：187-189

[13] 王楓紅，鄧志燕，陳熾坤.基于傳統(tǒng)遺傳算法的改進排爆機器人路徑規(guī)劃研究[J].圖學(xué)學(xué)報，2012.33（3）：41-45