1、第30卷第2期 2008年3月文章編號:1002-0446(2008)02-0097-05機器人ROBOTVo.l30,No.2March,2008移動機器人路徑規劃方法研究曲道奎,杜振軍,徐殿國,徐方(1.哈爾濱工業大學,黑龍江哈爾濱 150001;2.中國科學院沈陽自動化研究所,遼寧沈陽 110016; 3.中國科學院研究生院,北京 100049)1,22,32摘 要:針對室內動態非結構化環境下的移動機器人路徑規劃問題,提出了一種能夠將全局路徑規劃方法和局部路徑規劃方法相結合、將基于反應的行為規劃和基于慎思的行為規劃相結合的路徑規劃方法.全局路徑規劃器采用A*算法生成到達目標點的子目標節點

2、序列;局部路徑規劃器采用改進的人工勢場方法對子目標節點序列中相鄰兩節點進行路徑平滑和優化處理.在考慮了移動機器人運動學約束的前提下,該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙信息.仿真研究與在室內復雜環境下的實際運行結果驗證了該方法的有效性.關鍵詞:移動機器人;路徑規劃;動態環境中圖分類號: TP24 文獻標識碼: BResearchonPathPlanningforaMobileRobotQUDao-kui,DUZhen-jun,XUDian-guo,XUFang(1.HarbinInstituteofTechnology,Harbin150001,

3、China;2.ShenyangInstituteofAutomation,ChineseAcademyofSciences,Shenyang110016,China;3.GraduateSchooloftheChineseAcademyofSciences,Beijing100049,China)Abstract:Apathplanningmethodbasedonboththebenefitsofglobalandlocalpathplannersandthoseofdeliberateand1,22,32reactivebehaviorplannersisproposedforindoo

4、rmobilerobotpathplanningindynamicandunstructuredenvironments.TheglobalpathplannerusesA*algorithmtogenerateaseriesofsub-goalnodestothetargetnode,andthelocalpathplanneradoptsanimprovedpotentialfieldmethodtosmoothandoptimizethepathbetweentheadjacentsub-goalnodes.Takingintofullconsiderationthekinematica

5、lconstraintsofthemobilerobot,thismethodcannotonlyeffectivelygenerateaglobalopt-imalpathusingtheknowninformation,butalsohandlethestochasticobstacleinformationintime.Resultsofsimulationsandrealisticrunningincomplexindoorenvironmentsvalidatetheeffectivenessofthepresentedalgorithm. Keywords:mobilerobot;

6、pathplanning;dynamicenvironment1 引言(Introduction)移動機器人的路徑規劃問題是移動機器人研究領域的熱點問題,可以描述為:移動機器人依據某個或某些優化準則(如工作代價最小、行走路線最短、行走時間最短等),在運動空間中找到一條從起始狀態到目標狀態、可以避開障礙物的最優或者接近最1,2優的路徑.在以往的研究中,移動機器人路徑規劃方法大體上可以分為三種類型:其一是基于環境模型的路徑規劃,它能處理完全已知環境(障礙物的位置和形狀預先給定)下的路徑規劃,而當環境變化(出現移動障礙物)時,此方法效果較差,具體方法有:A方法、可視圖法和拓撲圖法等;其二是基于傳感器

7、信息的局部路徑規劃方法,其具體方法有:人工勢場法、模糊邏輯法等;其三是基于行為的路徑規劃法,它把導航問題分解為多個相對獨立的導航行為單元,如避碰、跟蹤、目標制導等,這些單元彼此協調工作,完成總體導航任務.此外,一些學者將一些人工智能方法應用到路徑規劃中,也取得一定的研究進展3*.3一個好的路徑規劃方法需要滿足如下指標:基金項目:國家863計劃資助項目(2007AA041700);山東省科技發展計劃資助項目(2006GG1104014). :04-98機 器 人2008年3月合理性 返回的任何路徑都是合理的,或者說任何路徑對控制機器人運動都是可執行的.完備性 如果客觀上存在一條從起點到達終點的無

8、碰路徑,該算法一定能找到;如果環境中沒有路徑可通行,會報告規劃失敗.最優性 算法規劃的結果路徑在某個測度(如時間、距離、能量消耗等)上是最優的.實時性 規劃算法的復雜度(時間需求、存儲需求等)能滿足機器人運動的需要.環境變化適應性 算法具有適應環境動態改變的能力,隨著環境改變,不必全部重新計算.滿足約束 支持移動機器人運動時的完整性和非完整性運動約束.對于在未知的(或部分已知的)、動態的非結構環境下的服務機器人而言,傳統的路徑規劃方法很難達到前面提出的指標要求.本文提出了一種將全局路徑規劃方法和局部路徑規劃方法相結合、將基于反應的行為規劃和基于慎思的行為規劃相結合的路徑規劃方法,其思路如下:機

9、器人采用A算法進行全局路徑規劃,生成到達目標點的子目標節點序列,同時采用改進的人工勢場方法對子目標節點序列中相鄰兩節點進行路徑平滑和優化處理.該方法不但能夠充分利用已知環境信息生成全局最優路徑,而且還能及時處理所遇到的隨機障礙信息,從而提高機器人整體路徑規劃的性能.*新規劃從當前位置到目標點的路徑.如此循環直至5機器人到達目標點或者發現目標點不可達.但如果機器人在動態環境或者未知環境中運動的時候,機器人很可能非常頻繁地遇到當前探測環境信息和先驗環境信息不匹配的情形,這就需要進行路徑再規劃.重新規劃算法仍然是個從當前位置到目標點的全局搜索的過程,運算量較大.在重新規劃期間,機器人或者選擇停下來等

10、待新的生成路徑,或者按照錯誤的路徑繼續運動.因此,快速的重新規劃算法是非常重要的6,7.A方法采用柵格表示地圖,柵格*粒度越小,障礙物的表示也就越精確,但是同時算法搜索的范圍會按指數增加.采用改進人工勢場的局*部路徑規劃方法對A方法進行優化,可以有效增大A方法的柵格粒度,達到降低A方法運算量的目的.對于移動機器人而言,不僅需要采用上述方法規劃出二維路徑點序列,還需要能夠控制機器人按照所生成的序列點運動,并且盡量保證機器人的運動軌跡是最優的和平滑的.A方法是在二維X-Y平面進行路徑規劃的,相鄰兩點之間的夾角一定是 /4的整倍數7*,如圖1所示.采用A方法規劃出的最*優路徑并沒有考慮到機器人的運動

11、學約束,即使機*器人可以采用A方法規劃出一條最優路徑,機器人也未必可以沿著這條路徑運動.2 相關研究(Relatedresearch)2.1 A原理在最佳優先搜索的研究中,最廣為人知的形式稱為A搜索.其基本思想*4*是:它把到達節點的代價g(n)和從該節點到目標節點的代價h(n)結合起來對節點進行評價:f(n)=g(n)+h(n)(1)因為g(n)給出了從起始節點到節點n的路徑代價,而h(n)給出了從節點n到目標節點的最低代價路徑的估計代價值,因此f(n)就是經過節點n到目標節點的最低代價解的估計代價.因此,如果想要找到最低代價解,首先嘗試找到g(n)+h(n)值的最小節點是合理的.并且,倘若

12、啟發函數h(n)滿足一定的條件,則A搜索既是完備的又是最優的*4圖1 A*方法中相鄰節點角度示意圖Fig.1 DiagramofanglesbetweenadjacentnodesinA*method2.2 人工勢場法原理人工勢場法是由Khatib提出的一種虛擬力法8.采用A方法用于移動機器人的路徑規劃時,機器人首先按照已知的環境地圖規劃出一條路徑,然后沿著這條軌跡運動,當機器人傳感器探測到的環境信息和原有的環境信息不一致的時候,機器人重.其基本思想是將機器人在環境中的運動視為一種機器人在虛擬的人工受力場中的運動.障礙物對機器人產生斥力,目標點產生引力,引力和斥力的合力作為機器人的加速力,來控

13、制機器人的運動方第30卷第2期 曲道奎等: 移動機器人路徑規劃方法研究99向和計算機器人的位置.人工勢場方法結構簡單,便于低層的實時控制,在實時避障和平滑的軌跡控制方面得到了廣泛的應用,但是人工勢場法存在4個固有缺陷(1)存在陷阱區域;(2)在相近的障礙物群中不能識別路徑;(3)在障礙物前振蕩;(4)在狹窄通道中擺動.除此之外,人工勢場法還存在著障礙物附近目標不可達問題109器中實現的,更新子目標節點以及控制機器人不斷朝向子目標節點運動并最終到達總目標節點是在局部路徑規劃器中實現的.下面分別介紹.3.2 全局路徑規劃方法全局路徑規劃器采用柵格地圖來描述環境模*型,采用A方法進行路徑規劃.由于局

14、部路徑規劃器具有躲避動態障礙物的功能,所以柵格粒度可以較大,以降低系統的存儲空間和A方法的搜索空間.在用A搜索最優路徑時,A搜索起始點設為機器人當前位置在柵格坐標系下的坐標,A搜索目標點設為機器人目標點位置在柵格坐標系下的坐標.*在柵格坐標系下,A方法生成一條從初始點到目標點的目標序列子節點.序列中除了全局目標節點外,每個節點都有一個指向其父節點的指針.然后把這些子節點投影到機器人所在的世界坐標系下,就是子節點在世界坐標系下的坐標.在機器人沒有達到最終目標點所在柵格的時候,機器人受到引力的節點是機器人所在柵格的父節點在世界坐標系下的位置;當機器人達到最終目標點所在柵格的時候,機器人受到的引力是

15、機器人目標節點的引力.A方法生成的只是子目標節點序列,還需要對*于A方法所生成的路徑點進行平滑優化.本文采用改進的人工勢場方法進行目標序列點之間的局部路徑規劃,使機器人的整條運動軌跡顯得比較平滑并達到實時避障的目的.3.3 局部路徑規劃方法局部路徑規劃方法以人工勢場方法為基礎,采用了三種改進策略,使之更適合于動態環境下移動機器人的實時控制,并使得運動軌跡更為平滑.3.3.1 設置有效障礙區域在機器人運動過程中,并不是周圍的所有障礙物都會對機器人產生影響,例如,與機器人運動方向夾角在 arad之間的障礙物可能會影響到機器人的運動,如a= /2,在此范圍之外的障礙物影響到機器人的運動的可能性就很小

16、.在局部路徑規劃中,我們認為與機器人運動方向夾角在 arad之間的障礙物會對機器人產生排斥勢場,其它的障礙物不會對機器人產生排斥勢場.采用這種方法可以有效地讓機器人快速穿越障礙物群,減少由勢場方法產生的局部最小點(見圖5).當機器人進入目標終點所在的柵格時,忽視機器人周圍障礙物斥力的影響,即機器人僅僅受到目標終點的引力作用,就可以解決障礙物10*:.根據人工勢場方法原理可知,引力勢場的范圍比較大,而斥力的作用范圍只是局部的,當機器人和障礙物的距離超過障礙物影響范圍的時候,機器人不受排斥勢場的影響.因此,勢場法只能解決局部空間的避障問題,它缺乏全局信息,這樣,它就很容易陷入局部最小值.所謂局部最

17、小值點,就是在引力勢場函數和斥力勢場函數的聯合分布的空間內,在某些區域,受到多個函數的作用,造成了局部最小點.當機器人位于局部最小點的時候,機器人容易產生振蕩或者停滯不前.障礙物越多,產生局部最小點的可能性就越大,產生局部最小點的數量也就越多.如前所述的人工勢場法的4種固有缺陷以及障礙物附近目標不可達問題,根源也就在于此2.3 路徑規劃方法(Pathplanningmethod)3.1 路徑規劃方法描述如果S表示機器人起始點狀態,G表示機器人目標點狀態,X表示當前機器人狀態,M是柵格地圖表示的環境地圖,那么本文所提出的路徑規劃方法可以描述為:(1)保存當前已知的和估計的環境信息到M;令X=S;

18、(2)基于環境信息M,規劃出從X到G的全局最優路徑,生成子目標節點序列;如果沒有最優路徑,則返回搜索失敗;(3)確定當前子目標節點;(4)機器人以第(3)步生成的子目標節點作為當前目標點,按照局部路徑規劃方法進行運動控制,直到到達目標點所在的柵格,進入步驟(3);或者機器人傳感器探測到新的環境和原有地圖M不匹配,并且環境變化會影響到機器人后續路徑規劃的執行;(5)按照傳感器信息更新地圖M,令S=X,跳轉到第(1)步.見圖100機 器 人2008年3月3.3.2 弧線運動規劃策略由勢場法僅能得到機器人當前受力方向,弧線運動規劃策略提出了一種能夠讓機器人沿著平滑軌跡按照勢場力方向運動到期望目標點的

19、方法.如圖2所示,弧線運動規劃的原理是:在機器人坐標系下,圓點O表示機器人當前位置.OY(即Y軸正方向)表示機器人當前方向;虛線圓表示機器人下一步可能到達的位置在該圓上的某一點,也就是說該圓的半徑為機器人的步長;A、B、C是機器人下一步可能到達的圓上的三個點,圓弧L1、L2、L3就是機器人從當前時刻到下一時刻所行走的路線.動學約束的.圖3 線速度、角速度效果圖Fig.3 Linearandangularvelocities4 仿真及實驗結果(Resultsofsimulationsandexperiments)4.1 全局路徑規劃效果全局路徑規劃器生成了全局最優路徑的目標序列點,機器人采用改進

20、的人工勢場方法進行目標序列點之間的局部路徑規劃.圖4中(a)(d)顯示了機器人從初始位置到達最終目標節點的過程.圖2 弧形規劃算法Fig.2 Arcpathplanningalgorithm假設以B點作為機器人下一時刻的位置,OB方向是由勢場法得到的機器人當前受力方向, a為機器人當前方向與受力方向的夾角,那么機器人將沿著圓弧L1運動到B點.需要說明的一點是,當機器人需要轉動角度過大時,如當 a>60 時,可以將機器人先轉動一定角度后,再按上面的步驟規劃速度.3.3.3 考慮運動學約束的運動控制仲裁在用上面的方法生成機器人的角速度和線速度后,運動控制仲裁負責把機器人的線速度和角速度控制轉

21、換為對移動機器人的左輪和右輪的位置閉環控制.閉環控制的輸出量是機器人左輪輪速v1和右輪輪速vr.如果計算得出的左右輪輪速超出電機所能承受的最大輪速,那么需要對機器人的線速度和角速度限速.圖3是經過限速后的機器人線速度和角速度以及左右輪輪速(速度圖中用虛線表示).從圖3,圖4 機器人到達目標點示意圖Fig.4 Thediagramofrobotreachingthegoal圖5第30卷第2期 曲道奎等: 移動機器人路徑規劃方法研究101果圖,從圖中可以看出,本文提出的方法能夠克服人9工勢場法存在的4個固有缺陷,機器人能夠有效地繞過陷阱區域,在相近的障礙物群中不僅能識別路徑,而且還能避免在在障礙物

22、群附近振蕩,同時,在狹窄通道中也不會出現擺動現象.當目標點在障礙物附近的時候,機器人依舊可以達到目標點.6(b)中機器人進入子目標點柵格所在的區域,這時候機器人探測到動態障礙物,圖6(c)中顯示了機器人能夠利用局部路徑規劃器有效繞行動態障礙物,圖6(d)中顯示機器人繼續趨向目標節點運動.本文所提方法在新松公司的家用智能服務機器人平臺上實現.該機器人曾在多種展會上展出(圖7),機器人能夠較好地躲避動態人群并到達指定的目標點,實現其在非結構化環境下的運動規劃與實時避障功能.圖5 全局路徑規劃效果圖Fig.5 Globalpathplanningdiagram4.2 局部避障效果實驗圖6是機器人利用

23、局部路徑規劃器有效繞行動態障礙物并繼續向目標節點運動的效果圖.圖7 新松公司智能服務機器人Fig.7 SIASUNintelligentservicerobot5 結論與展望(Conclusionandfuturework)本文對移動機器人動態環境下的路徑規劃技術進行了研究探索,提出了一種能夠將全局路徑規劃方法和局部路徑規劃方法相結合、將基于反應的行為規劃和基于慎思的行為規劃相結合的路徑規劃解決思路,提出了一種能使機器人局部軌跡規劃更平滑的基于弧線運動的規劃方法,提出的方法能夠解決傳統人工勢場方法的4種缺陷目標點不可達問題109以及障礙物附近.*目前的算法中,采用A方法作為全局路徑規劃器,在進

24、一步的研究中,將考慮用DynamicA(D)*6方法和FieldD方法*7作為全局路徑規劃器,使之更適合在動態不確定性的環境應用.圖6 局部路徑規劃和避障效果圖Fig.6 Localpathplanningandobstacleavoidancediagram參考文獻 (References)1石鴻雁,孫昌志.非結構環境下移動機器人的運動規劃J.機器人,2004,26(1):27-31.(下轉第106頁)圖6(a)中機器人朝向下一個子目標點運動,圖106機 器 人2008年3月境標定.實驗結果表明,標定后T形管工件虛擬環境模型的算術平均誤差為0 6mm,標準誤差為0 7mm,單個空間點的最大誤

25、差為1mm.由于FTC傳感器的被動柔順范圍是 1mm,因此虛擬環境模型精度能夠滿足以被動柔順方式完成接觸遙控焊接任務的需要,為實現基于監督控制的遙控焊接接觸任務策略奠定了堅實的基礎.參考文獻 (References)1KimWS.VirtualrealitycalibrationforteleroboticservicingA.ProceedingsoftheIEEEInternationalConferenceonRoboticsandAutomationC.2775.Piscataway,NJ,USA:IEEE,1994.2769-圖10 虛擬環境標定誤差分析示意圖Fig.10 Error

26、analysisonvirtualenvironmentcalibration2宋月娥.弧焊機器人系統協調運動精度及離線編程標定技術研究D.哈爾濱:哈爾濱工業大學,2002.3魏秀權.基于人機交互的機器人遙控焊接虛擬環境標定D.哈爾濱:哈爾濱工業大學,2005.4FitzgibbonA,PiluM,FisherRB.Directleastsquarefittingofe-llipsesJ.IEEETransactionsonPatternAnalysisandMachineIn-telligence,1999,21(5):476-480.6 結論(Conclusion)本文針對T形管工件進行了

27、基于機器人力控制表面跟蹤的遙控焊接虛擬環境標定實驗,采用基于力覺傳感器坐標系橫切面輪廓線的力控制策略跟蹤工件表面.在精確測量跟蹤過程中接觸點空間位置的基礎上,對橢圓跟蹤軌跡進行直接最小二乘擬合,通過T形管工件標定算法,實現了高精度的虛擬環作者簡介:魏秀權(1982-),男,博士生.研究領域:機器人遙控焊接,力覺傳感與控制,虛擬環境標定.(上接第101頁)2樊曉平,李雙艷,陳特放.基于新人工勢場函數的機器人動態避障規劃J.控制理論與應用,2005,22(5):703-707.3劉華軍,楊靜宇,陸建峰,等.移動機器人運動規劃研究綜述J.中國工程科學,2006,8(1):85-94.456NilssonNJ.PrinciplesofArtificialIntelligenceM.Berlin,Ger-many:Springer,1980.ZelinskyA.AmobilerobotexplorationalgorithmJ.IEE