基于混合混沌序列與遺傳算法的排爆機(jī)器人路徑規(guī)劃

殷新凱 茅健 周玉鳳 陳曉平

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

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

中圖分類號：TP242.3? ? ? ? ? 文獻(xiàn)標(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 引言

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

針對多機(jī)器人路徑規(guī)劃問題，孫樹棟等采用鏈接圖法標(biāo)識多機(jī)器人，簡化了機(jī)器人的工作環(huán)境，同時在遺傳算法基礎(chǔ)上引入適應(yīng)度值調(diào)整矩陣，對適應(yīng)度函數(shù)進(jìn)行合理優(yōu)化，實(shí)現(xiàn)對多機(jī)器人運(yù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等把長度和困難程度歸為對機(jī)器人路徑評價的標(biāo)準(zhǔn)，并在傳統(tǒng)遺傳算法基礎(chǔ)上擴(kuò)展成多個目標(biāo)的遺傳算法，完成對兩種算法的性能測量和模擬結(jié)果[5]。Cai等采用新型協(xié)調(diào)進(jìn)化自適應(yīng)遺傳算法，提出了一種新的固定長度十進(jìn)制編碼機(jī)制，同時討論了多機(jī)器人系統(tǒng)的路徑規(guī)劃，驗(yàn)證了算法的魯棒性[6]。

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

1 算法介紹

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

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

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

1.2 Logistic混沌序列

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

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

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

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

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

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

2 算法設(shè)計

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

⑴ 實(shí)例設(shè)計

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

⑵ 路徑構(gòu)造

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

⑶ 編碼設(shè)計

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

⑷ 種群產(chǎn)生

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

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

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

3 仿真分析

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)（References）：

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

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

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

[4] 陳曦，譚冠政，江斌.基于免疫遺傳算法的移動機(jī)器人實(shí)時最優(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ù)的研究與實(shí)現(xiàn)[D].南京郵電大學(xué)，2016.

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

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

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

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

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