移動(dòng)機(jī)器人路徑規(guī)劃方法研究

高涵　高柏軍

[摘 要] 本文介紹了幾種路徑規(guī)劃方法的優(yōu)缺點(diǎn)以及改進(jìn)方法。針對(duì)人工勢(shì)場(chǎng)法的不足提出改進(jìn)算法，并對(duì)該方法進(jìn)行仿真分析。展示利用模糊神經(jīng)網(wǎng)絡(luò)法避障實(shí)例，應(yīng)用結(jié)果表明該方法可以有效地避開障礙物到達(dá)目標(biāo)位置。

[關(guān)鍵詞] 路徑規(guī)劃；人工勢(shì)場(chǎng)；啟發(fā)式算法；蟻群算法；遺傳算法

中圖分類號(hào)： TP242.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-5200（2015）05-014-04

[Abstract] The paper illustrates several trajectory palnning algorithms principles，merits and demerits and improved algorithms.Then， the paper presents improved algorithm for disadvantages of APF and makes simulation.Finally， the paper gives an example of avoiding obstacle by using fuzzy neural network .The results show that it can avoid obstacles effectively.

[Key words] Trajectory planning；artificial potential fields；heuristic algorithm；ant colony optimization algorithm；genetic algorithm

路徑規(guī)劃技術(shù)是移動(dòng)機(jī)器人研究領(lǐng)域中的重要組成部分[1]，主要方法有可視圖法[2]、柵格法[3]、人工勢(shì)場(chǎng)法[4]、模糊邏輯法[5-6]、神經(jīng)網(wǎng)絡(luò)法[7]、蟻群算法[8]等智能算法。本文介紹了幾種路徑規(guī)劃方法特點(diǎn)和國(guó)內(nèi)外研究學(xué)者提出的改進(jìn)算法；其次，針對(duì)人工勢(shì)場(chǎng)法的不足提出了一種改進(jìn)方法并對(duì)其做了仿真分析；最后，列舉了模糊神經(jīng)網(wǎng)絡(luò)法實(shí)例，應(yīng)用結(jié)果表明該方法可以有效地避開障礙物到達(dá)目標(biāo)位置。

1 幾種路徑規(guī)劃方法

1.1 人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法 （Artificial Potential Field）是由Khatib于1986年提出的一種虛擬力法[9]，它的基本思想是建立一個(gè)虛擬勢(shì)場(chǎng)函數(shù)，該勢(shì)場(chǎng)函數(shù)可以按一定的規(guī)律對(duì)機(jī)器人產(chǎn)生虛擬力。此算法優(yōu)點(diǎn)是規(guī)劃的路徑較為平滑，但存在局部極小值、目標(biāo)不可達(dá)問題。

針對(duì)上述問題，國(guó)內(nèi)外研究學(xué)者提出了有效解決方法。國(guó)內(nèi)哈爾濱工業(yè)大學(xué)于振中等[10]構(gòu)造改進(jìn)的人工勢(shì)場(chǎng)模型，使用勢(shì)場(chǎng)強(qiáng)度代替力矢量進(jìn)行路徑規(guī)劃。劉傳領(lǐng)[11]提出當(dāng)機(jī)器人陷入局部最小值狀態(tài)時(shí)，引入逃脫力函數(shù)使其擺脫局部最小的限制。于魁龍等[12]提出模糊控制和人工勢(shì)場(chǎng)相結(jié)合的路徑規(guī)劃方法。王麗[13]引入了“follow-wall行為”，使機(jī)器人沿著障礙物邊界行走，能迅速擺脫局部極小值問題。國(guó)外Prahlad Vadakkepat[14]在勢(shì)場(chǎng)函數(shù)中引入了逃脫力，使機(jī)器人擺脫局部最小的限制。Josu Agirrebeitia等[15]建立一個(gè)新的勢(shì)場(chǎng)函數(shù)和短程曲線實(shí)現(xiàn)路徑規(guī)劃，可以解決局部最小值問題。TingChen等[16]利用柵格法建立模型，然后采用人工勢(shì)場(chǎng)法與遺傳算法相結(jié)合的方法生成避障路徑。Jean Bosco Mbede等[17]利用人工勢(shì)場(chǎng)法與模糊邏輯控制法相結(jié)合的方法來解決局部最小值問題。

1.2 A*算法

A*（A-star）算法是一種典型的啟發(fā)式搜索算法，是基于柵格地圖法的一種路徑搜索算法[18]。該算法從起點(diǎn)開始，檢查其相鄰的方格，尋求估值函數(shù)最小值，然后向四周擴(kuò)展，直至找到目標(biāo)。該算法搜索速度很快，但用它搜索出的路徑受柵格的限制仍然無法保證規(guī)劃的路徑最短。

針對(duì)上述問題，國(guó)內(nèi)北京工業(yè)大學(xué)張曉[19]利用傳統(tǒng)A*算法搜索出路徑，然后優(yōu)化路徑點(diǎn)。陳圣群 [20]

采用A*算法和D*算法結(jié)合方法搜索出最優(yōu)路徑。史輝等[21]改進(jìn)A*算法估值函數(shù)，再利用K-d樹空間索引結(jié)構(gòu)，動(dòng)態(tài)加載節(jié)點(diǎn)信息實(shí)現(xiàn)路徑規(guī)劃。國(guó)外Daniel Cagigas[22]改進(jìn)了A*算法，構(gòu)造地圖并利用預(yù)先計(jì)算路徑（物化路徑的成本）方式，使得算法運(yùn)行速度更快、時(shí)間更短、規(guī)劃出的路徑最優(yōu)。Sloman Aaron[23]用動(dòng)態(tài)A*算法尋找次優(yōu)無碰路徑，再用蟻群算法優(yōu)化次優(yōu)路徑，算法結(jié)合改善了收斂速度，提高了效率。Marija Dakulovi?等[24]利用Witkowski算法[25]和動(dòng)態(tài)A*算法相結(jié)合，可以尋求最短路徑。

1.3 蟻群算法

蟻群算法（Ant Colony Optimization，簡(jiǎn)稱ACO）是意大利學(xué)者Dorigo M等在20世紀(jì)90年代初提出的一種仿生類智能算法[26]。它是利用螞蟻找尋食物過程中釋放的信息素（也稱外激素）使一定范圍內(nèi)的其他螞蟻能夠感覺到這種物質(zhì)，并朝著物質(zhì)強(qiáng)度高的方向移動(dòng)，從而實(shí)現(xiàn)路徑規(guī)劃。蟻群算法具有信息反饋機(jī)制以及分布式計(jì)算特征，但求解速度慢，易陷入局部最優(yōu)，且初期信息素匱乏會(huì)導(dǎo)致算法停滯。

針對(duì)上述問題，國(guó)內(nèi)外研究人員相繼提出路徑規(guī)劃的改進(jìn)蟻群算法。國(guó)內(nèi)復(fù)旦大學(xué)的陳雄等[27]引入限定信息素和自適應(yīng)信息素?fù)]發(fā)系數(shù)來解決蟻群算法應(yīng)用中的停滯現(xiàn)象和搜索能力差的問題。毛琳波[28]利用蟻群算法搜索，在螞蟻搜索到死角時(shí)建立相應(yīng)的死角表，同時(shí)用懲罰函數(shù)更新軌跡強(qiáng)度，從而改善算法的性能，避免機(jī)器人路徑規(guī)劃出現(xiàn)死鎖。鄧高峰等[29]充分利用粒子算法和蟻群算法的優(yōu)點(diǎn)，收斂到全局最優(yōu)。南開大學(xué)任春明等[30]改進(jìn)了蟻群算法收斂速度慢的不足，融入了遺傳算法的交叉、變異操作來加快算法收斂。趙百鐵[31]提出了一種四叉樹和蟻群算法相結(jié)合的思想，可以解決機(jī)器人在大范圍二維平面區(qū)域路徑規(guī)劃的問題。國(guó)外T.Stutzle [32]提出設(shè)置信息素上下限來避免算法出現(xiàn)過早停滯現(xiàn)象。Kwang-Seon Yoo[33]提出了基于蟻群算法動(dòng)態(tài)拓?fù)鋬?yōu)化的二維結(jié)構(gòu)，改善了傳統(tǒng)算法計(jì)算效率問題。Rana Forsati等[34]通過調(diào)整信息素值來防止過早收斂。M.A. Porta Garcia等[35]提出實(shí)時(shí)更新信息素可以改善蟻群算法的不足，并用模糊控制法進(jìn)行優(yōu)化。

1.4 遺傳算法

遺傳算法（Genetic Algorithms，簡(jiǎn)稱GA）最初是由美國(guó)密歇根大學(xué)Holland 教授于1969年提出的，它是通過模擬自然界生物遺傳機(jī)制和生物進(jìn)化論而形成的一種隨機(jī)搜索最優(yōu)解的方法[36]。遺傳算法操作簡(jiǎn)單，能克服人工勢(shì)場(chǎng)法局部最優(yōu)解導(dǎo)致死鎖的問題，搜索從群體出發(fā)，具有潛在的并行性，實(shí)時(shí)性好等優(yōu)點(diǎn)。但運(yùn)算速度慢，局部尋優(yōu)能力差，存在早熟收斂，隨機(jī)游走會(huì)導(dǎo)致收斂性差、搜索時(shí)間長(zhǎng)等問題。

針對(duì)上述缺點(diǎn)，國(guó)內(nèi)外學(xué)者提出了改進(jìn)算法。何娟等[37]先利用遺傳算法計(jì)算初始信息素分布，然后再用蟻群算法優(yōu)化。有效地結(jié)合了遺傳算法的快速收斂性和蟻群算法的信息正反饋機(jī)制，改善了各自的不足。徐美清[38]引入路徑修復(fù)機(jī)制來提高遺傳算法的收斂速度。丁彪[39]利用概率快速隨機(jī)搜索算法生成初始路徑，再利用遺傳算法優(yōu)化，不僅降低計(jì)算復(fù)雜度，而且加快了收斂速度。張榮松[40]將復(fù)雜的二維編碼問題簡(jiǎn)化為一維編碼問題，優(yōu)化并改進(jìn)了標(biāo)準(zhǔn)遺傳算法的選擇算子和交叉算子，以移動(dòng)機(jī)器人最短路徑作為適應(yīng)度函數(shù)進(jìn)行優(yōu)化，克服了遺傳算法早熟收斂和運(yùn)算結(jié)果不穩(wěn)定等問題。Hong Qu等[41] 通過改變遺傳算子尋求最優(yōu)路徑。Tuncer等[42]針對(duì)機(jī)器人動(dòng)態(tài)路徑規(guī)劃提出了改進(jìn)遺傳算法，避免了早熟收斂問題。

2 仿真

本文利用MATLAB 2010a軟件針對(duì)人工勢(shì)場(chǎng)法進(jìn)行仿真分析。

仿真主要步驟是先初始化起始點(diǎn)、目標(biāo)點(diǎn)以及障礙物的位置，設(shè)定增益系數(shù)，障礙物的影響距離和機(jī)器人移動(dòng)步長(zhǎng)，然后計(jì)算機(jī)器人引斥力、合力、航向角及下一點(diǎn)位置，最后判斷是否到達(dá)目標(biāo)點(diǎn)。仿真流程圖如圖1所示。

仿真結(jié)果表明，改變斥力勢(shì)函數(shù)可以解決人工勢(shì)場(chǎng)法目標(biāo)不可達(dá)問題。仿真結(jié)果如圖2所示。圖中黑色實(shí)體為障礙物，白色圓圈為目標(biāo)點(diǎn)。

3 避障實(shí)例

本實(shí)驗(yàn)室采用模糊神經(jīng)網(wǎng)絡(luò)的方法實(shí)現(xiàn)機(jī)器人避障[43]，編程在VisualC++ 6.0環(huán)境中實(shí)現(xiàn)。表2為模糊控制規(guī)則表。實(shí)驗(yàn)用到的移動(dòng)機(jī)器人為四輪式HEBUT-Ⅱ型移動(dòng)機(jī)器人，如圖3所示。圖4為在C++環(huán)境中制作的模糊神經(jīng)網(wǎng)絡(luò)界面，圖5為控制面板上實(shí)際移動(dòng)機(jī)器人避障軌跡圖，圖6可以看到移動(dòng)機(jī)器人正在躲避障礙物，實(shí)驗(yàn)表明，HEBUT-Ⅱ移動(dòng)機(jī)器人可以有效地避開障礙物。

4 結(jié)束語

本文針對(duì)人工勢(shì)場(chǎng)法的不足提出了改進(jìn)算法并對(duì)其做了仿真分析。對(duì)于HEBUT-Ⅱ的路徑規(guī)劃問題采用模糊神經(jīng)智能方法，實(shí)例結(jié)果表明該方法可以順利躲避障礙物到達(dá)目標(biāo)位置。該實(shí)例為日后路徑規(guī)劃研究奠定了基礎(chǔ)。

參 考 文 獻(xiàn)

[1] 朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010，25（7）：961-967.

[2] 楊淮清，肖興貴，姚棟.一種基于可視圖法的機(jī)器人全局路徑規(guī)劃算法[J].沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2009（2）：225-229.

[3] 王娟娟，曹凱.基于柵格法的機(jī)器人路徑規(guī)劃[J].農(nóng)業(yè)裝備與車輛工程，2009（4）：14-17.

[4] 張殿富，劉福.基于人工勢(shì)場(chǎng)法的路徑規(guī)劃方法研究及展望[J].計(jì)算機(jī)工程與科學(xué)，2013，35（6）：88-95.

[5] 朱長(zhǎng)順，趙永升. 應(yīng)用于汽車操縱穩(wěn)定性試驗(yàn)的轉(zhuǎn)向機(jī)器人控制器設(shè)計(jì)[J].現(xiàn)代儀器與醫(yī)療，2013，19（2）：20-23.

[6] 蘇治寶，陸際聯(lián).用模糊邏輯法對(duì)移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃的研究[J].北京理工大學(xué)學(xué)報(bào)，2003，23（3）：290-293.

[7] 邢軍，王杰.神經(jīng)網(wǎng)絡(luò)在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用研究[J].微計(jì)算機(jī)信息，2005（22）：110-111.

[8] Wang Zhangqi ，Zhu Xiaoguang ，Han Qingyao.Mobile Robot Path Planning based on Parameter Optimization Ant Colony Algorithm[J].Procedia Engineering，2011 （15）：2738-2741.

[9] 趙榮奇.基于人工勢(shì)場(chǎng)法的機(jī)器人路徑規(guī)劃研究[D].山東：山東大學(xué)機(jī)械制造及其自動(dòng)化，2008.

[10] 于振中，閆繼宏，趙杰，等.改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2011，43（1）：50-55.

[11] 劉傳領(lǐng).基于勢(shì)場(chǎng)法和遺傳算法的機(jī)器人路徑規(guī)劃技術(shù)研究[D].南京：南京理工大學(xué)計(jì)算機(jī)學(xué)院，2012.

[12] 于魁龍，賈小平，曹有輝，等.基于混合算法的局部路徑規(guī)劃[J].裝甲兵工程學(xué)院學(xué)報(bào)，2008，22（2）：43-45.

[13] 王麗.移動(dòng)機(jī)器人路徑規(guī)劃方法技術(shù)研究[D].西安：西北工業(yè)大學(xué)航海學(xué)院，2007.

[14] Prahlad Vadakkepat，Tong Heng Lee，Liu Xin.Application of Evolutionary Artificial Potential Field in Robot Soccer System[J].IEEE，2011：2781-2785.

[15] Josu Agirrebeitia，Rafael Aviles et al.A new APF strategy for path planning in environmentswith obstacles[J].Mechanism and Machine Theory，2005（ 40）： 645-658.

[16] Qiushi Zhang， Dandan Chen， Ting Chen. An Obstacle Avoidance Method of Soccer Robot Based on Evolutionary Artificial Potential Field[J].Energy Procedia， 2012 （16）：1792-1798.

[17] Jean Bosco Mbede，Xinhan Huang，Min Wang.Fuzzy motion planning among dynamic obstacles using arti?cial potential ?elds for robot manipulators[J].Robotics and Autonomous Systems， 2000 （32） ：61-72.

[18] 吳超帥.改進(jìn)A*算法及其在ASR移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[D].湘潭：湘潭大學(xué)信息工程學(xué)院，2012.

[19] 張曉.全方位移動(dòng)平臺(tái)的設(shè)計(jì)以及定位和路徑規(guī)劃[D].北京：北京工業(yè)大學(xué)機(jī)械工程學(xué)院，2013.

[20] 陳圣群，董林飛.Dijkstra和A-star算法在智能導(dǎo)航中的應(yīng)用分析[J].重慶科技學(xué)院學(xué)報(bào)（自然科學(xué)版），2010，12（6）：159-161.

[21] 史輝，曹聞，朱述龍，朱寶山.A*算法的改進(jìn)及其在路徑規(guī)劃中的應(yīng)用[J].測(cè)繪與空間地理信息，2009，32（6）：208-211.

[22] Daniel Cagigas.Hierarchical D*algorithm with materialization of costs for robot path planning[J].Robotics and Autonomous Systems， 2005（52）：190-208.

[23] TAN Guan-Zheng，HE Huan，SLOMAN Aaron.Ant Colony System Algorithm for Real-Time Globally Optimal Path Planning of Mobile Robots[J].Acta Automatica Sinica，2007，33（3）：279-285.

[24] Marija Dakulovi?， Ivan Petrovi?.Two-way D* algorithm for path planning and replanning[J]. Robotics and Autonomous Systems， 2011 （59）： 329-342.

[25] C. Witkowski， A parallel processor algorithm for robot route planning， in： Int.Joint Conf. on Artificial Intelligence， IJCAI， Karlsruhe， West Germany， 1983， 827–829.

[26] Fan Xiaoping. Optimal path planning for mobile robots based on intensified ant colony optimization algorithm[C].Proceedings of 2003 IEEE International Conference on Robotics， Intelligence Systems and Signal Processing， 2003.131-136.

[27] 陳雄，袁楊.一種機(jī)器人路徑規(guī)劃的蟻群算法[J].系統(tǒng)工程與電子技術(shù)，2008，30（5）：952-955.

[28] 毛琳波，劉士榮，俞金壽.移動(dòng)機(jī)器人路徑規(guī)劃的一種改進(jìn)蟻群算法[J].華東理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2006，32（8）：997-1001.

[29] 鄧高峰，張雪萍，劉彥萍.一種障礙環(huán)境下機(jī)器人路徑規(guī)劃的蟻群粒子群算法[J].控制理論與應(yīng)用，2009，26（8）：879-883.

[30] 任春明，張建勛.基于優(yōu)化蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程，2008，34（15）：1-3.

[31] 趙百軼，張利軍，賈鶴鳴.基于四叉樹和改進(jìn)蟻群算法的全局路徑規(guī)劃[J].應(yīng)用科技.2011，38（10）：23-28.

[32] T.stutzle and T.Hoos.Max-Min ant system and local search for combinatorial optimization problems[M].In S.Voβ，S.Martello，I.H.Osman，andC.Roucairol，editors Meta-Heuristics：Advances and Trends in Local Search Paradigms for optimization，Kluwer Boston，1998.

[33] Kwang-Seon Yooa， Seog-Young Han.A modified ant colony optimization algorithm for dynamic topology optimization[J].Computers and Structures， 2013 （123）： 68-78.

[34] Rana Forsatia， Alireza Moayedikiaa， Richard Jensenc.Enriched ant colony optimization and its application in feature selection[J].Neurocomputing， 2014 （142）： 354-371.

[35] M.A. Porta Garcia， Oscar Montiel， Oscar Castillo， etal， Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost function evaluation[J]. Applied Soft Computing， 2009 （9）： 1102–1110.

[36] Holland JH.Adaption in natural and artificial systems[M].Ann Arbor University of Michigan.1975.

[37] 何娟，涂中英，牛玉剛.一種遺傳蟻群算法的機(jī)器人路徑規(guī)劃方法[J].計(jì)算機(jī)仿真，2010，27（3）：170-174.

[38] 徐美清，孫晨亮.基于柵格地圖的遺傳算法路徑規(guī)劃[J].科技信息，2011（31）：76-77.

[39] 丁彪.基于改進(jìn)遺傳算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].自動(dòng)化應(yīng)用，2014（1）：1-3.

[40] 張榮松，包家漢.基于改進(jìn)遺傳算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，19（7）：20-23.

[41] Hong Qu， Ke Xing， Takacs Alexander.An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots[J].Neurocomputing ，2013 （120） ：509-517.

[42] Adem Tuncer， Mehmet Yildirim， Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers and Electrical Engineering， 2012，38（6） ：1564-1572.

[43] 邢國(guó)芬.基于多傳感器信息融合的移動(dòng)機(jī)器人環(huán)境感知研究[D].天津：河北工業(yè)大學(xué)，2008.