高涵　高柏軍

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

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

中圖分類號： TP242.6 文獻標識碼：A 文章編號：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ī)劃技術是移動機器人研究領域中的重要組成部分[1]，主要方法有可視圖法[2]、柵格法[3]、人工勢場法[4]、模糊邏輯法[5-6]、神經(jīng)網(wǎng)絡法[7]、蟻群算法[8]等智能算法。本文介紹了幾種路徑規(guī)劃方法特點和國內(nèi)外研究學者提出的改進算法；其次，針對人工勢場法的不足提出了一種改進方法并對其做了仿真分析；最后，列舉了模糊神經(jīng)網(wǎng)絡法實例，應用結(jié)果表明該方法可以有效地避開障礙物到達目標位置。

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

1.1 人工勢場法

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

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

1.2 A*算法

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

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

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

1.3 蟻群算法

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

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

1.4 遺傳算法

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

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

2 仿真

本文利用MATLAB 2010a軟件針對人工勢場法進行仿真分析。

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

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

3 避障實例

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

4 結(jié)束語

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

參 考 文 獻

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

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

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

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

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

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

[7] 邢軍，王杰.神經(jīng)網(wǎng)絡在移動機器人路徑規(guī)劃中的應用研究[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] 趙榮奇.基于人工勢場法的機器人路徑規(guī)劃研究[D].山東：山東大學機械制造及其自動化，2008.

[10] 于振中，閆繼宏，趙杰，等.改進人工勢場法的移動機器人路徑規(guī)劃[J].哈爾濱工業(yè)大學學報，2011，43（1）：50-55.

[11] 劉傳領.基于勢場法和遺傳算法的機器人路徑規(guī)劃技術研究[D].南京：南京理工大學計算機學院，2012.

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

[13] 王麗.移動機器人路徑規(guī)劃方法技術研究[D].西安：西北工業(yè)大學航海學院，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] 吳超帥.改進A*算法及其在ASR移動機器人路徑規(guī)劃中的應用[D].湘潭：湘潭大學信息工程學院，2012.

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

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

[21] 史輝，曹聞，朱述龍，朱寶山.A*算法的改進及其在路徑規(guī)劃中的應用[J].測繪與空間地理信息，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] 陳雄，袁楊.一種機器人路徑規(guī)劃的蟻群算法[J].系統(tǒng)工程與電子技術，2008，30（5）：952-955.

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

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

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

[31] 趙百軼，張利軍，賈鶴鳴.基于四叉樹和改進蟻群算法的全局路徑規(guī)劃[J].應用科技.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] 何娟，涂中英，牛玉剛.一種遺傳蟻群算法的機器人路徑規(guī)劃方法[J].計算機仿真，2010，27（3）：170-174.

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

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

[40] 張榮松，包家漢.基于改進遺傳算法的機器人路徑規(guī)劃[J].計算機技術與發(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] 邢國芬.基于多傳感器信息融合的移動機器人環(huán)境感知研究[D].天津：河北工業(yè)大學，2008.