多移動機器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望

1、 收稿日期:2007-08-15作者簡介:李艷宏(1978-,女,蘭州理工大學在讀研究生,主要研究方向為機械制造及自動化。多移動機器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望鄔再新,李艷宏,劉濤(蘭州理工大學 機電工程學院,甘肅 蘭州 730050摘要:移動機器人技術(shù)研究中的一個重要領(lǐng)域是路徑規(guī)劃技術(shù)。所謂移動機器人路徑規(guī)劃是指各機器人在同一工作空間中規(guī)劃一條避障導航的運動路徑,保證每一時刻機器人與機器人之間無碰撞、機器人與環(huán)境障礙物之間無碰撞。從單機器人到多機器人的路徑規(guī)劃已有很多算法,首先從多機器人協(xié)作性質(zhì)、環(huán)境信息和機器人結(jié)構(gòu)三方面分別介紹多機器人路徑規(guī)劃方法,主要有全局路徑規(guī)劃方法、局部路徑規(guī)劃方

2、法、集中式路徑規(guī)劃方法、分布式路徑規(guī)劃方法、混合式路徑規(guī)劃方法,再指出各種方法的優(yōu)點和不足,最后對多移動機器人路徑規(guī)劃技術(shù)的發(fā)展趨勢進行展望:傳統(tǒng)的規(guī)劃方法和新的智能方法的結(jié)合;多傳感器融合;性能指標的提高。關(guān)鍵詞:多移動機器人;路徑規(guī)劃;神經(jīng)網(wǎng)絡(luò)控制;模糊控制;遺傳算法;全局路徑規(guī)劃;局部路徑規(guī)劃 中圖分類號:TP24 文獻標識碼:A 文章編號:1006-0316(200801-01-04Research progress and future development on path planning for multi-robotWU Zai-xin ,LI Yan-hong ,LIU T

3、ao(Lanzhou university of Technology Electric and Mechanical engineer ,Lanzhou 730050,ChinaAbstract :Mobile robot path planning technology is one of the important domains in mobile robot technologies research. Mobile path planning is that robots reach goal point from the beginning point in unknown en

4、vironment during the path planning, nocollidance among robots and stumbling blocks. The path-planning from single robot to multi-robot has many algorithms, this article introduces the path planning from coordination, environment information and robot architecture: such as global path planning, local

5、 path planning, concentrated path planning, decentralized path planning and blended path planning. In addition ,the advantages and disadvantages of these algorithms are pointed out. At last, the trend of multiple mobile robots path planning is described: traditional and intelligent path planning int

6、egrated; multi-sensor amalgamated; capability index improved. Key words :multiple mobile robot ;path planning ;neural network control ;fuzzy control ;genetic algorithms ;global path planning ;local path planning智能移動機器人是一類通過傳感器感知環(huán)境和自身狀態(tài),實現(xiàn)在有障礙物的環(huán)境中面向目標的自主運動,從而完成一定作業(yè)功能的機器人系統(tǒng)1,2。近年來,隨著機器人生產(chǎn)線的出現(xiàn)及柔性制造系統(tǒng)的

7、應(yīng)用,研究人員對由多個機器人組成的系統(tǒng)越來越感興趣,分布式多機器人系統(tǒng)已經(jīng)成為一個活躍的、具有挑戰(zhàn)性的研究領(lǐng)域。在多移動機器人系統(tǒng)的研究和開發(fā)過程中,路徑規(guī)劃是必須解決的重要問題。所謂多機器人協(xié)調(diào)避障路徑規(guī)劃,主要是指在同一工作空間中,各自治機器人如何利用環(huán)境的信息,規(guī)劃一條避障導航的運動路徑,保證每一時刻機器人與機器人之間無碰撞、機器人與環(huán)境障礙物之間無碰撞3。1 移動機器人路徑規(guī)劃方法的分類及現(xiàn)狀移動機器人路徑規(guī)劃主要要解決三個問題:使機器人能從初始點運動到目標點;用一定的算法使機器人能夠繞開障礙物,并且經(jīng)過某些必須經(jīng)過的點;在完成以上任務(wù)的前提下,盡量優(yōu)化機器人的運行軌跡。1.1 按協(xié)調(diào)

8、性質(zhì)劃分的路徑規(guī)劃方法多機器人協(xié)作路徑規(guī)劃的算法很多,按機器人協(xié)作的性質(zhì)大致可分為:基于顯式協(xié)作的多機器人路徑規(guī)劃和基于隱式協(xié)作的多機器人路徑規(guī)劃?；陲@式協(xié)作的多機器人路徑規(guī)劃:主要是指當機器人遇到動態(tài)障礙物,首先要辨別它是一般障礙物還是別的機器人,如果動態(tài)障礙物是機器人,它們通過通訊協(xié)商確定各自的運動策略。顯式協(xié)作主要側(cè)重于通訊及協(xié)商機制的研究?；陔[式協(xié)作的多機器人路徑規(guī)劃:主要是從單機器人路徑規(guī)劃發(fā)展起來的,為了避免與靜態(tài)、動態(tài)障礙物碰撞,機器人只要遇到障礙物就執(zhí)行預(yù)先定義好的應(yīng)激性避障策略,而不考慮動態(tài)障礙物是不是機器人。目前比較有影響的多機器人隱式協(xié)作的路徑規(guī)劃方法有:人工勢場法、

9、模糊控制方法等,它們都是單機器人規(guī)劃方法的擴展。1.2 按環(huán)境信息劃分的路徑規(guī)劃方法根據(jù)環(huán)境信息的完整程度,路徑規(guī)劃方法分為:全局路徑規(guī)劃、局部路徑規(guī)劃以及環(huán)境不完全確定型路徑規(guī)劃4,5。全局路徑規(guī)劃:指在全局環(huán)境信息已知的情況下,給機器人規(guī)劃出一條從起點至終點的運動路徑。該法通?？梢詫ふ易顑?yōu)解,但需要預(yù)先知道準確的全局環(huán)境信息,計算量大,實時性差,不能較好地適應(yīng)動態(tài)非確定環(huán)境?；诃h(huán)境建模的全局路徑規(guī)劃的方法主要有:可視圖法、切線圖法、Voronoi 圖法、拓撲法、懲罰函數(shù)法、柵格法等。局部路徑規(guī)劃:前提是動態(tài)時變環(huán)境條件下,側(cè)重考慮機器人在未知環(huán)境中通過傳感器探知局部環(huán)境,自主地進行導航。

10、由于僅依靠局部信息,有時會產(chǎn)生局部極值點或振蕩無法保證機器人順利到達目標點。局部路徑規(guī)劃的方法主要有人工勢場法、模糊邏輯算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)法、模擬退火算法、蟻群優(yōu)化算法、粒子群算法和啟發(fā)式搜索法等6。環(huán)境不完全確定型路徑規(guī)劃:指在全局環(huán)境已知、但其它機器人信息未知條件下,將全局規(guī)劃路徑與實時規(guī)劃路徑相結(jié)合的規(guī)劃方法。此方法試圖結(jié)合全局和局部方法的優(yōu)點,前面提到的人工勢場法和模糊方法均可歸入局部路徑規(guī)劃和環(huán)境不完全確定型路徑規(guī)劃。1.3 按機器人控制結(jié)構(gòu)劃分的方法根據(jù)多機器人規(guī)劃的體系結(jié)構(gòu)可將多機器人路徑規(guī)劃方法分為:集中式、分布式、混合式。集中式體系結(jié)構(gòu)7:指多機器人上層具有統(tǒng)一的規(guī)

11、劃單元,規(guī)劃單元在對環(huán)境和任務(wù)充分理解的基礎(chǔ)上,對每臺機器人要走的路線進行評估和規(guī)劃,以保證系統(tǒng)總的執(zhí)行代價最小。集中式結(jié)構(gòu)的優(yōu)點在于理論背景清晰,實現(xiàn)起來較為直觀,系統(tǒng)的協(xié)調(diào)性較好,但也存在許多缺點:容錯性差、柔性差、實用性差、適應(yīng)性差,另外還存在集中規(guī)劃單元和機器人之間的通訊瓶頸問題,以及當任務(wù)復(fù)雜時集中規(guī)劃的復(fù)雜度和計算量增長迅速等問題。分布式體系結(jié)構(gòu):指整個系統(tǒng)沒有集中協(xié)調(diào)器,每個機器人作為一個Agent810,具有獨立的觀察、通訊、判斷、決定等高度自主自治能力,遇到?jīng)_突時,可通過通訊或局部感知同其它機器人協(xié)商解決。各機器人獨立運作,通過各自的動作互相影響,彼此制約,從而實現(xiàn)協(xié)同作業(yè),

12、完成相對復(fù)雜的任務(wù)。與集中式控制相比,分布式控制具有所需全局知識更少、系統(tǒng)柔性增加、完成任務(wù)更高效、容錯能力更強等優(yōu)點,所以日益成為多機器人研究的發(fā)展趨勢。其缺點是全局規(guī)劃性差,大量的信息交互受到通訊瓶頸的限制。混合式結(jié)構(gòu):又叫分布決策-中央?yún)f(xié)調(diào)結(jié)構(gòu),每一臺機器人都具有對當前規(guī)劃評價的能力和更改運動規(guī)劃的權(quán)利1114。系統(tǒng)進行初始規(guī)劃,根據(jù)規(guī)劃機器人開始運動。但在運動過程中,每臺機器人根據(jù)環(huán)境信息和自身狀態(tài),從自身局部利益出發(fā)對當前的行動路線進行評估,如果發(fā)現(xiàn)了更有利于自身的運動規(guī)劃,則把新的規(guī)劃意見提交給中央?yún)f(xié)調(diào)器。中央?yún)f(xié)調(diào)器對每臺機器人的“提議”進行總體評估和決定,如果某提議對系統(tǒng)整體沒有

13、損害,或者能獲得更好的系統(tǒng)效益,那么該提議就被采納;否則該提議被否決,系統(tǒng)仍按照原有規(guī)劃行動15。這種模式能夠發(fā)揮每臺機器人的能力,彌補中央規(guī)劃時的缺陷是系統(tǒng)更加適應(yīng)不確定性環(huán)境。然而,它還需要一個中央?yún)f(xié)調(diào)器,不具備完全的自治能力。2 移動機器人路徑規(guī)劃新的發(fā)展趨勢隨著移動機器人應(yīng)用范圍的擴大,對于規(guī)劃技術(shù)的要求也越來越高,單個規(guī)劃方法有時不能很好地解決某些規(guī)劃問題,所以新的發(fā)展趨向于將多種方法相結(jié)合,對此可從以下幾方面進行探討。2.1 傳統(tǒng)規(guī)劃方法與新的智能方法之間的結(jié)合近年來,一些新的智能技術(shù)逐漸被引入到路徑規(guī)劃中來,也促使了各種方法的融合發(fā)展,例如人工勢場與神經(jīng)網(wǎng)絡(luò)、模糊控制的結(jié)合等,其

14、中Kyun Y16的混合控制結(jié)構(gòu)先用神經(jīng)網(wǎng)絡(luò)對環(huán)境進行分類以避免陷入局部最小,并建立基于反應(yīng)式行為的控制器,再根據(jù)勢場法選擇一個特定的反應(yīng)式行為來引導移動機器人前進,該結(jié)構(gòu)有較好的魯棒穩(wěn)定性,對動態(tài)環(huán)境具有一定的適應(yīng)性。Mbede J B17設(shè)計了一種融合了模糊邏輯和人工勢場函數(shù)的模糊控制器,解決了已知環(huán)境中存在未知動態(tài)障礙的規(guī)劃問題,較大提高了運動規(guī)劃的效率,適合于實時應(yīng)用。2.2 多傳感器信息融合用于路徑規(guī)劃移動機器人在動態(tài)環(huán)境中進行路徑規(guī)劃所需的信息都是從傳感器得來18。單傳感器難以保證輸入信息的準確與可靠。多傳感器所獲得的信息具有冗余性、互補性、實時性和低代價性,且可快速并行分析現(xiàn)場環(huán)

15、境19。目前方法有采用概率方法表示信息的加權(quán)平均法、貝葉斯估計法、多貝葉斯法、卡爾曼濾波法、統(tǒng)計決策理論法、仿效生物神經(jīng)網(wǎng)絡(luò)的信息處理方法、人工神經(jīng)網(wǎng)絡(luò)法等20。2.3 路徑規(guī)劃的性能指標要不斷提高路徑規(guī)劃的性能指標包括:實時性、安全性和可達性等。在動態(tài)環(huán)境中,由于環(huán)境信息時刻變化,如果移動機器人實時性差,滯后于動態(tài)環(huán)境,就可能會導致避障失敗21。安全性和可達性也很重要。一個性能指標不好的方法,即使它能使移動機器人走出完美的軌跡,也將被淘汰。如何使性能指標更好是各種算法研究的一個重要方面。3 結(jié)論總結(jié)目前的研究可以看出:對于各種規(guī)劃方法的改進有這樣一個趨勢把某幾種方法相互結(jié)合,因此怎樣把各種方

16、法的優(yōu)點融合到一起以達到更好的效果是一個有待探討的問題;目前大多數(shù)規(guī)劃方法都只針對固定目標點而沒有考慮移動目標點的情況,此時的規(guī)劃由于要考慮機器人及目標的位置信息和速度信息而更加復(fù)雜,這方面研究也是今后發(fā)展的重點。綜上所述,多移動機器人的路徑規(guī)劃技術(shù)研究已經(jīng)取得了豐碩成果。但各種方法各有優(yōu)缺點,沒有一種方法能適用于任何場合。隨著科技不斷發(fā)展,多機器人應(yīng)用領(lǐng)域還將不斷擴大,移動機器人路徑規(guī)劃這一課題領(lǐng)域還將不斷深入。在研究這一領(lǐng)域時,要結(jié)合以前的研究成果,把握發(fā)展趨勢,以實用性作為最終目的,不斷推動其向前發(fā)展。參考文獻:1歐青立,何克忠. 室外智能移動機器人的發(fā)展及其相關(guān)技術(shù)研究J.機器人,20

17、00,22(6:519-526.2蔡自興,賀漢根,陳虹. 未知環(huán)境中移動機器人導航控制研究的若干問題J. 控制與決策,2002,17(4:385-390.3李磊,葉濤,譚民,等. 移動機器人技術(shù)研究現(xiàn)狀與未來J. 機器人,2002,24(5:475-480.4Y. UNY CAO. Cooperative Mobile Robotics: Antecedents and DirectionsJ. Autonomous Robotics,1997,(4:7-27.5孟慶浩,彭商賢,劉大維. 基于Q-M 圖啟發(fā)式搜索的移動機器人全局路徑規(guī)劃J. 機器人,1998,20(4.6蔡自興. 人工智能原理

18、及其應(yīng)用M. 北京:清華大學出版社,2003.7Suh I H,Yeo H J,et al. Design of a Supervisory Control System for Multiple Robotics SystemsJ. IEEE IROS96,1996:332-339.8Kamada T,Oikawa K,Amadeus. A Mobile, Autonomous Decentralized Utility System for Indoor TransportationJ. Proc. IEEE Int. Conf. Robot. Automat.,1998(5:2229-2

19、236.9Tao W M,How K Y. A Decentralized Approach for Cooperative Sweeping by Multiple Mobile RobotsJ. IROS'98 Proc. IEEE Int. Conf. Intell. Robot. Syst.,1998:380-385.10Azarm K G Schmidt. A Decentralized Approach for the Conflict-free Motion of Multiple Mobile RobotsJ. IEEE IROS96,1996:1667-1675.11

20、陳衛(wèi)東,董勝龍,等. 基于開放式多智能體結(jié)構(gòu)的分布式自主機器人系統(tǒng)J. 機器人,2001,23(1:45-50.12Parker L E,ALLIANCE. An Architecture for Fault Tolerant Multi(下轉(zhuǎn)第16頁才對,但壓力在模擬過程中有類似滑移速度的劇烈變化,僅僅彈性形變無法解釋這一情況。這種情況我們可以看成,當牽引力作用在滑塊上時,由于滑塊與基底之間的粘著形變導致接觸處分子之間的相互作用發(fā)生變化,使得壓力在短時間迅速降低至靜止狀況壓力值的附近。3 結(jié)論本文利用分子動力學方法,用一個簡單的模型,通過對滑移速度、摩擦力以及壓力的研究,來探討粘滑現(xiàn)象產(chǎn)生的

21、起因。結(jié)果表明:粘滑現(xiàn)象是一個基底和滑塊的分子之間集體作用的結(jié)果,特別是相接觸處分子之間的作用,當滑塊靜止在基底上時,隨著牽引力的增大,壓力由于基底與滑塊的相互粘著作用而迅速減小,而當牽引力大于最大靜摩擦力時,粘著被破壞,滑塊與基底分離,同時壓力也隨之恢復(fù)到正常狀況。因此,我們認為:原子尺度下相接觸物體之間的粘著分離是導致粘滑現(xiàn)象的主要原因。參考文獻:1Mate,C.M.,McClelland,G.M,Erlandsson,R. Atomic-scale friction of atungsten tip on a graphite surfaceJ.Phys. Rev. Lett. 1987

22、,59:194 -245.3Riedo,E,Gnecco,E,Bennewitz,et al. Interaction Potential and Hopping Dynamics Governing Sliding FrictionJ. Phys. Rev. Lett.91, 084502(2003.5Reimann,P,and Evstigneev M. Nonmonotonic Velocity Dependence of Atomic FrictionJ. Phys. Rev. Lett. 93,230802(2004.8Sills,Sand. and Overney,R.M. Cre

23、eping Friction Dynamics and Molecular Dissipation Mechanisms in Glassy PolymersJ. Phys. Rev. Lett. 91,095501(2003.11Persson,B.N. J. Friction dynamics for curved solid surfaces with long-range elasticityJ. J. Chem. Phys.113(13,5477.(2000. 12Luengo,Gustavo,Israelachvili,Jacob,Granick Steve. Generalize

24、d effects in confined fluids: new friction map for boundary lubrationJ. wear 200 (1996 328.13Aranson,I.S.,Tsimring,L.S. and Vinokur,V. M. Stick-slip friction and nucleation dynamics of ultrathin liquid filmsJ. Phys. Rev. B. 65. 125402 (2002.14Budakian,Raffi. and Putterman,Seth. J. Time scales for co

25、ld welding and the origins of stick-slip frictionJ. Phys. Rev. B. 65. 235429(2002.15Schirmeisen,A.,Jansen,L,and Fuchs.H. Tip-jump statistics of stick-slip frictionJ. Phys. Rev. B,71.245403(2005.robot CooperationJ. IEEE Transactions on Robotics and Automation, 1998,14(2:220-240.13Ueyama T,Fukuda T,Sa

26、kai A et al. Hierarchical Control Architecture with Learning and Adaptation Ability for Cellular Robotic SystemJ. Distributed Autonomous Robotic Systems,1994:16-28. 14Laengle T,Lueth T C,Rembold U,A Distributed Control Architecture for Autonomous Robot Systems,Modelling and Planning for Sensor Based Intelligent Robo