張俊溪，米國際，王 鑫，蔣江紅

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

0 引 言

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

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

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

1.1 GP算法用于分類問題的個體描述方法

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

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

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

(2)遺傳操作。

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

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

1.2 GP算法用于解決分類問題的過程描述

GP算法用于解決分類問題，其過程描述分為8個步驟。設(shè)進化代數(shù)為G，個體數(shù)目為M，節(jié)點層數(shù)為N，種群中當前個體為x，第i個個體的輸出值為Ti(x)。則GP算法在分類問題中的描述如圖1所示。

圖1 GP算法用于分類問題的過程描述

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

2 分類器的設(shè)計

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

1.個體編碼。

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

圖2 算法流程

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

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

(1)

3.操作算子。

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

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

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

(4)輸出。

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

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

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

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

圖3 模糊控制算法框圖

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

表1 模糊規(guī)則庫

隸屬度取各個語言變量的隸屬度函數(shù)形狀為對稱的三角形且模糊分割是對稱的。根據(jù)不同的目標方向確定合適的模糊規(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)用重心法對這些模糊輸出指令進行去模糊化處理，最后得到精確的控制指令。

4 仿真實驗

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

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

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

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

5 結(jié)束語

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

參考文獻:

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

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

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

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

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

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

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

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

[9] 張明路,彭商賢,曹作良,等.用于移動機器人避障的人工神經(jīng)網(wǎng)絡(luò)和模糊邏輯控制技術(shù)[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] 柳長安,鄢小虎,劉春陽,等.基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法[J].電子學(xué)報,2011,39(5):1220-1224.

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

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

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

[17] 云慶夏.進化算法[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.