基于進(jìn)化算法和模糊控制的機(jī)器人路徑規(guī)劃

張俊溪，米國(guó)際，王 鑫，蔣江紅

(1.西安航空學(xué)院 車(chē)輛工程學(xué)院，陜西 西安 710077；2.陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

0 引 言

機(jī)器人在軍事領(lǐng)域及民用領(lǐng)域的應(yīng)用凸顯了重要的實(shí)用價(jià)值。隨著應(yīng)用的廣泛，其活動(dòng)空間環(huán)境也更加復(fù)雜，路徑規(guī)劃逐漸成為機(jī)器人研究的熱點(diǎn)問(wèn)題。移動(dòng)機(jī)器人路徑規(guī)劃是路徑規(guī)劃問(wèn)題的典型應(yīng)用，根據(jù)機(jī)器人對(duì)環(huán)境信息的把握程度，可將其分為全局路徑規(guī)劃(靜態(tài)規(guī)劃)和局部路徑規(guī)劃(動(dòng)態(tài)規(guī)劃)兩種類(lèi)型。全局路徑規(guī)劃需要掌握全部的環(huán)境信息，局部路徑規(guī)劃則需要掌握部分環(huán)境信息或者對(duì)環(huán)境信息完全未知[1]。機(jī)器人在動(dòng)態(tài)復(fù)雜環(huán)境下的局部路徑規(guī)劃是機(jī)器人和人工智能研究領(lǐng)域的一個(gè)重要課題[2-3]。環(huán)境信息完全未知的局部路徑規(guī)劃主要依靠傳感器采集參數(shù)，通過(guò)傳感器融合技術(shù)，判斷機(jī)器人的行動(dòng)信息[4]?？傮w上講，提高機(jī)器人對(duì)當(dāng)前環(huán)境感知信息的快速理解及識(shí)別，快速而準(zhǔn)確地避開(kāi)障礙物，提高自主性和智能性，是當(dāng)前移動(dòng)機(jī)器人研究的焦點(diǎn)。基于模糊邏輯技術(shù)的移動(dòng)機(jī)器人避障問(wèn)題，已經(jīng)有較多的研究成果[5-8]，多數(shù)是將多傳感器的信息直接作為模糊控制器的輸入來(lái)實(shí)現(xiàn)環(huán)境認(rèn)知，但該方案由于模糊控制器復(fù)雜的模糊規(guī)則導(dǎo)致運(yùn)算速率下降。也有學(xué)者采用人工神經(jīng)網(wǎng)絡(luò)[9]、蟻群算法[10]等與模糊邏輯相結(jié)合實(shí)現(xiàn)對(duì)當(dāng)前環(huán)境感知的理解和快速分類(lèi)，或者通過(guò)人工勢(shì)場(chǎng)法、單純神經(jīng)網(wǎng)絡(luò)、蟻群算法、螢火蟲(chóng)算法等對(duì)機(jī)器人路徑進(jìn)行全局規(guī)劃或全局與局部規(guī)劃相結(jié)合[11-15]?；谝陨戏治?，文中提出采用遺傳規(guī)劃算法對(duì)機(jī)器人傳感器獲得的環(huán)境感知信息進(jìn)行識(shí)別和模式分類(lèi)[16]，然后采用模糊控制算法建立模糊規(guī)則庫(kù)，并通過(guò)解模糊產(chǎn)生精確的驅(qū)動(dòng)命令使機(jī)器人正確識(shí)別障礙信息，順利達(dá)到指定地點(diǎn)。

1 遺傳規(guī)劃模式分類(lèi)

遺傳規(guī)劃(genetic programming,GP)是進(jìn)化計(jì)算[17]的一個(gè)重要分支，又叫遺傳程序設(shè)計(jì)。它能動(dòng)態(tài)產(chǎn)生預(yù)測(cè)分析的最優(yōu)非線(xiàn)性結(jié)構(gòu)，而且不需要數(shù)據(jù)統(tǒng)計(jì)分布的預(yù)處理知識(shí)，就能自動(dòng)發(fā)現(xiàn)某一類(lèi)數(shù)據(jù)判別式的特征[18-19]。目前GP算法已經(jīng)成功應(yīng)用于預(yù)測(cè)分析[20]、數(shù)據(jù)挖掘[21]、機(jī)器人控制[22]、符號(hào)回歸[23]等方面。

1.1 GP算法用于分類(lèi)問(wèn)題的個(gè)體描述方法

個(gè)體的描述方法包括終端集的選擇、函數(shù)集的選擇、適應(yīng)度函數(shù)的定義、算法控制參數(shù)的確定和終止條件的選擇等。程序樹(shù)的葉節(jié)點(diǎn)由輸入變量和常量構(gòu)成，葉節(jié)點(diǎn)的選擇也就是終端集的選擇。文中通過(guò)對(duì)待分類(lèi)對(duì)象的特征進(jìn)行分析，提取出對(duì)象的特征值構(gòu)成特征向量，作為GP算法的終端集。函數(shù)集包括了算術(shù)運(yùn)算符、常見(jiàn)的數(shù)學(xué)函數(shù)以及邏輯判斷等。

(1)適應(yīng)度函數(shù)的確定。

適應(yīng)度函數(shù)的確定直接影響著遺傳規(guī)劃算法的進(jìn)化程度和運(yùn)算效果。適應(yīng)度函數(shù)是對(duì)個(gè)體目標(biāo)函數(shù)的基本評(píng)價(jià)，其選擇將會(huì)影響種群中個(gè)體的優(yōu)良程度。適應(yīng)度函數(shù)的算法控制參數(shù)包括種群的大小和遺傳操作的概率。初始群體由眾多獨(dú)立的個(gè)體組成，用算法樹(shù)表示。文中采用混合法生成初始隨機(jī)樹(shù)，部分個(gè)體采用生長(zhǎng)法產(chǎn)生，部分采用完全法，生成方法隨機(jī)。

(2)遺傳操作。

文中采用競(jìng)技選擇方法進(jìn)行遺傳操作，每次從群體中隨機(jī)選擇N個(gè)個(gè)體，復(fù)制所有個(gè)體中適應(yīng)度值最大的個(gè)體，通過(guò)不斷調(diào)整N的大小來(lái)改變種群的規(guī)模，N越大則被選中的較優(yōu)個(gè)體越多。

文中的變異方法采用的是子樹(shù)變異法，執(zhí)行變異時(shí)，在隨機(jī)選取的個(gè)體算法樹(shù)中選擇其函數(shù)點(diǎn)或者終止符點(diǎn)作為變異點(diǎn)，并將變異點(diǎn)及其以下的子樹(shù)刪除，用產(chǎn)生的新子樹(shù)替換刪除的舊子樹(shù)。采用混合終止準(zhǔn)則，即當(dāng)超過(guò)最大容許進(jìn)化代數(shù)或者當(dāng)預(yù)先設(shè)定的問(wèn)題求解成功后，進(jìn)化過(guò)程立即停止。

1.2 GP算法用于解決分類(lèi)問(wèn)題的過(guò)程描述

GP算法用于解決分類(lèi)問(wèn)題，其過(guò)程描述分為8個(gè)步驟。設(shè)進(jìn)化代數(shù)為G，個(gè)體數(shù)目為M，節(jié)點(diǎn)層數(shù)為N，種群中當(dāng)前個(gè)體為x，第i個(gè)個(gè)體的輸出值為T(mén)i(x)。則GP算法在分類(lèi)問(wèn)題中的描述如圖1所示。

圖1 GP算法用于分類(lèi)問(wèn)題的過(guò)程描述

在過(guò)程描述的第二步進(jìn)化代數(shù)G=1時(shí)，需要隨機(jī)產(chǎn)生一個(gè)第一代個(gè)體，其產(chǎn)生的算法過(guò)程為初始化，根據(jù)N層節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目判斷N+1層的節(jié)點(diǎn)數(shù)，從函數(shù)集、變量集、常數(shù)集中選擇N+1層所有節(jié)點(diǎn)并迭代，如果N層節(jié)點(diǎn)中的變量個(gè)數(shù)等于輸入變量個(gè)數(shù)，則節(jié)點(diǎn)數(shù)M+1，否則循環(huán)，直至M達(dá)到規(guī)定的一代種群中的個(gè)體數(shù)目。其中，對(duì)于N層節(jié)點(diǎn)變量個(gè)數(shù)的判定，如果N大于規(guī)定層數(shù)，則轉(zhuǎn)到初始化階段，重新生成個(gè)體樹(shù)；如果N小于規(guī)定層數(shù)，則繼續(xù)根據(jù)N層節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目之和判斷N+1層的節(jié)點(diǎn)數(shù)目。

2 分類(lèi)器的設(shè)計(jì)

遺傳算法用于分類(lèi)設(shè)計(jì)過(guò)程。首先初始化路徑群體，然后進(jìn)行遺傳操作，如選擇、交叉、復(fù)制、變異。經(jīng)過(guò)若干代進(jìn)化以后，停止進(jìn)化，輸出當(dāng)前最優(yōu)個(gè)體。文中通過(guò)遺傳規(guī)劃分類(lèi)器進(jìn)行分類(lèi)后，將所得分類(lèi)結(jié)果用于模糊控制器的規(guī)則庫(kù)信息，遺傳規(guī)劃與模糊控制相結(jié)合的算法的計(jì)算過(guò)程如圖2所示。

1.個(gè)體編碼。

遺傳規(guī)劃的個(gè)體編碼方式采用層次結(jié)構(gòu)，以二叉樹(shù)的形式存儲(chǔ)，但隨著迭代的增加，二叉樹(shù)的深度會(huì)逐漸增加，因此可采用鏈表形式進(jìn)行存儲(chǔ)，便于下一步的選擇交叉操作。

圖2 算法流程

2.適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)是遺傳規(guī)劃算法計(jì)算的核心內(nèi)容，適應(yīng)度函數(shù)選擇的好壞直接影響算法的輸出結(jié)果。文中采用特征向量法提取個(gè)體的數(shù)據(jù)信息，任意輸入信息Pi的特征向量為Pi=[θi,Vi,Di]，其中θi為位置信息，Vi為速度信息，Di為距離信息，包含前、左、右三個(gè)方向的距離信息。選取Pi與Pi+1的距離信息最小值的倒數(shù)為適應(yīng)度函數(shù)值，當(dāng)兩點(diǎn)距離最小時(shí)歸為一類(lèi)，其倒數(shù)為適應(yīng)度函數(shù)值，取最大值作為算法運(yùn)算終止的條件。適應(yīng)度函數(shù)F(P)見(jiàn)式1：

(1)

3.操作算子。

(1)隨機(jī)初始化群體P(0)，計(jì)算群體P(0)中個(gè)體的適應(yīng)度；

(2)計(jì)算適應(yīng)度函數(shù)F(P)，如果滿(mǎn)足條件則轉(zhuǎn)第三步，不滿(mǎn)足則繼續(xù)執(zhí)行選擇、交叉、變異操作；

(3)由p(t)通過(guò)遺傳操作形成新的種群p(t+1)，計(jì)算p(t+1)中個(gè)體的適應(yīng)度，如果滿(mǎn)足條件則輸出，不滿(mǎn)足則繼續(xù)執(zhí)行遺傳操作；

(4)輸出。

3 模糊控制器設(shè)計(jì)

模糊控制器的一般設(shè)計(jì)步驟包括模糊推理、建立模糊規(guī)則庫(kù)、解模糊以及輸出控制變量。模糊控制器的輸入是各傳感器采集的距離信息，包括機(jī)器人所在位置與目標(biāo)方向夾角θ、運(yùn)動(dòng)速度v以及機(jī)器人與物體之間的距離D。輸出是移動(dòng)機(jī)器人的左右輪加速度的信息a以及舵機(jī)轉(zhuǎn)向信息α。

將距離D定義為{NEAR，MIDDLE，F(xiàn)AR}；將當(dāng)前運(yùn)動(dòng)速度v定義為{SLOW，MIDDLE，F(xiàn)AST}；將目標(biāo)方位θ定義為{LEFT，F(xiàn)RONT，RIGHT}；將移動(dòng)機(jī)器人的轉(zhuǎn)向角α定義為{LVL，LL，LM，LS，ZO，RS，RM，RL，RVL}；將移動(dòng)機(jī)器人后輪加速度a劃分為{NB，NS，Z，PS，PB}。

模糊控制算法流程如圖3所示。

圖3 模糊控制算法框圖

通過(guò)以上定義，并結(jié)合遺傳規(guī)劃分類(lèi)結(jié)果，將分類(lèi)結(jié)果模糊化，構(gòu)建模糊規(guī)則庫(kù)，如表1所示。

表1 模糊規(guī)則庫(kù)

隸屬度取各個(gè)語(yǔ)言變量的隸屬度函數(shù)形狀為對(duì)稱(chēng)的三角形且模糊分割是對(duì)稱(chēng)的。根據(jù)不同的目標(biāo)方向確定合適的模糊規(guī)則，其形式為：

ifDisDiandvisvjandθisθkthenαisαlandaisam

其中，i=NEAR,MIDDLE，F(xiàn)AR；j=SLOW，MIDDLE，F(xiàn)AST；k=LEFT，F(xiàn)RONT，RIGHT；l=LVL，LL，LM，LS，ZO，RS，RM，RL，RVL；m=NB，NS，Z，PS，PB。這些規(guī)則把輸入模糊變量變換成模糊輸出指令(即轉(zhuǎn)向角和加速度)，再應(yīng)用重心法對(duì)這些模糊輸出指令進(jìn)行去模糊化處理，最后得到精確的控制指令。

4 仿真實(shí)驗(yàn)

為驗(yàn)證文中路徑規(guī)劃算法的有效性，將提出的遺傳規(guī)劃算法(GP)路徑規(guī)劃與蟻群算法路徑規(guī)劃收斂特性進(jìn)行比較。從圖4(a)、(b)可以看出，蟻群算法的收斂過(guò)程較為平滑，最終在迭代600次以后收斂于適應(yīng)度值680，GP在前300次迭代過(guò)程中呈現(xiàn)震蕩形態(tài)，但在400次以后收斂于650，并且表現(xiàn)較為穩(wěn)定，說(shuō)明GP較早獲得最優(yōu)解，且收斂后較為穩(wěn)定。

圖4 遺傳規(guī)劃與蟻群算法收斂過(guò)程比較

圖5 采用遺傳規(guī)劃與模糊控制的局部

圖5是采用遺傳規(guī)劃與模糊控制的局部路徑規(guī)劃搜索結(jié)果以及采用蟻群算法和模糊控制的局部路徑規(guī)劃搜索結(jié)果。設(shè)定環(huán)境為20×20有固定障礙物的柵格環(huán)境，圖5(b)相較于圖5(a)有一段明顯的無(wú)效路徑，即(5,15)～(10,5)。總體仿真結(jié)果表明，遺傳規(guī)劃與模糊控制相結(jié)合的局部路徑規(guī)劃算法在收斂效率和路徑搜索的穩(wěn)定性方面優(yōu)于蟻群算法和模糊控制的局部路徑規(guī)劃算法。

5 結(jié)束語(yǔ)

提出一種基于進(jìn)化算法和模糊控制算法相結(jié)合的智能路徑規(guī)劃策略。采用GP對(duì)移動(dòng)機(jī)器人的環(huán)境信息進(jìn)行識(shí)別和分類(lèi)，并將分類(lèi)結(jié)果作為模糊控制器計(jì)算的依據(jù)；然后將障礙物位置和目標(biāo)信息模糊化，并在進(jìn)化算法分類(lèi)的基礎(chǔ)上建立規(guī)劃庫(kù)，通過(guò)解模糊產(chǎn)生驅(qū)動(dòng)命令，并使機(jī)器人按照最優(yōu)路徑達(dá)到指定目的地；最后將該算法與GP路徑規(guī)劃及模糊控制路徑規(guī)劃仿真結(jié)果進(jìn)行比較。結(jié)果表明，提出的智能路徑規(guī)劃策略可以使移動(dòng)機(jī)器人對(duì)未知環(huán)境信息的分類(lèi)更加準(zhǔn)確，識(shí)別更加高效。

參考文獻(xiàn):

[1] 王耀南.機(jī)器人智能控制工程[M].北京:科學(xué)出版社,2004.

[2] 熊開(kāi)封,張 華.基于改進(jìn)型FNN的移動(dòng)機(jī)器人未知環(huán)境路徑規(guī)劃[J].制造業(yè)自動(dòng)化,2013,35(11):1-4.

[3] 魏 唯，歐陽(yáng)丹彤，呂 帥，等.動(dòng)態(tài)不確定環(huán)境下多目標(biāo)路徑規(guī)劃方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(5):836-846.

[4] 張德惠,王利輝.移動(dòng)機(jī)器人復(fù)雜路徑規(guī)劃優(yōu)化方法研究[J].制造業(yè)自動(dòng)化,2012,34(5):98-101.

[5] 陳衛(wèi)東,朱奇光.基于模糊算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].電子學(xué)報(bào),2011,39(4):971-974.

[6] 劉國(guó)榮,張揚(yáng)名.移動(dòng)機(jī)器人軌跡跟蹤的模糊PID-P型迭代學(xué)習(xí)控制[J].電子學(xué)報(bào),2013,41(8)：1536-1541.

[7] 付宜利,顧曉宇,王樹(shù)國(guó).基于模糊控制的自主機(jī)器人路徑規(guī)劃策略研究[J].機(jī)器人,2004,26(6):548-552.

[8] 陳衛(wèi)東，李寶霞，朱奇光.模糊控制在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2009，45(31)：221-223.

[9] 張明路,彭商賢,曹作良,等.用于移動(dòng)機(jī)器人避障的人工神經(jīng)網(wǎng)絡(luò)和模糊邏輯控制技術(shù)[J].中國(guó)機(jī)械工程,1997,8(2):21-24.

[10] LIU Chuanling,LIU Huaiwang,YANG Jingyu.A path planning method based on adaptive genetic algorithm for mobile robot[J].Journal of Information and Computational Science,2011,8(5):808-814.

[11] KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J].International Journal of Robotics Research,1986,5(1):90-98.

[12] KOREN Y, BORENSTEIN J. Potential field methods and their inherent limitations for mobile robot navigation[C]//Proceedings of IEEE conference on robotics and automation.Sacramento,CA,USA:IEEE,1991:1398-1404.

[13] 柳長(zhǎng)安,鄢小虎,劉春陽(yáng),等.基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法[J].電子學(xué)報(bào),2011,39(5):1220-1224.

[14] 杜鵬楨，唐振民，陸建峰,等.不確定環(huán)境下基于改進(jìn)螢火蟲(chóng)算法的地面自主車(chē)輛全局路徑規(guī)劃方法[J].電子學(xué)報(bào),2014,42(3):616-624.

[15] 劉 玲,王耀南,況 菲,等.基于神經(jīng)網(wǎng)絡(luò)和遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用研究,2007,24(2):264-265.

[16] 周 慶，牟 超,楊 丹.教育數(shù)據(jù)挖掘研究進(jìn)展綜述[J].軟件學(xué)報(bào),2015,26(11):3026-3042.

[17] 云慶夏.進(jìn)化算法[M].北京:冶金工業(yè)出版社,2000.

[18] DOWNEY C,ZHANG Mengjie.Parallel linear genetic programming[C]//Proceedings of the 14th European conference on genetic programming.Torino,Italy:[s.n.],2011:178-189.

[19] KUO C S,HONG T P,CHEN C L.A knowledge-acquisition strategy based on genetic programming[J].Cybernetics and Systems,2008,39(7):670-683.

[20] ETEMADI H,ROSTAMY A A A,DEHKORDI H F.A genetic programming model for bankruptcy prediction:empirical evidence from Iran[J].Expert Systems with Applications,2009,36(2):3199-3207.

[21] ALAVI A H,GANDOMI A H.A robust data mining approach for formulation of geotechnical engineering systems[J].Engineering Computations,2011,28(3):242-274.

[22] OUANNES N,DJEDI N E,DUTHEN Y,et al.Gait evolution for humanoid robot in a physically simulated environment[M]//Intelligent computer graphics.[s.l.]:[s.n.],2012:157-173.

[23] GELLY S,TEYTAUD O,BREDECHE N,et al.A statistical learning theory approach of bloat[C]//Genetic and evolutionary computation conference.Washington DC,USA:IEEE,2005:1783-1784.