采用分區(qū)場能切換法的路徑規(guī)劃

黃 德 穎,　郭 　 戈,　王 麗 媛,　李 志 慧

( 1.大連理工大學 控制科學與工程學院, 遼寧 大連　116024；

2.大連海事大學 信息科學技術學院， 遼寧 大連　116026 )

?

采用分區(qū)場能切換法的路徑規(guī)劃

黃 德 穎1,郭 戈*2,王 麗 媛1,李 志 慧1

( 1.大連理工大學 控制科學與工程學院, 遼寧 大連116024；

2.大連海事大學 信息科學技術學院， 遼寧 大連116026 )

摘要：為解決改進人工勢場法應用中出現(xiàn)的路徑規(guī)劃失敗問題，提出了分區(qū)場能切換法，其包括地圖標定和算法設計．先對地圖中的障礙物按不同的形狀進行分類標定，然后設定最小單元，設立絕對防御區(qū)和緩沖區(qū)．在不同的區(qū)域基于改進人工勢場法重新設計算法，使機器人在絕對防御區(qū)只受斥力，在緩沖區(qū)受到斥力和引力，在緩沖區(qū)外只受引力，從而保證機器人往目標運動的過程中能快速靠近并成功避開障礙物．通過Matlab仿真實驗，在標定好的地圖中分別采用改進人工勢場法和分區(qū)場能切換法，證明了所提方法的可靠性．

關鍵詞：路徑規(guī)劃；改進人工勢場法；地圖標定；絕對防御區(qū)；分區(qū)場能切換法

0引言

在移動機器人研究領域，路徑規(guī)劃是一個重要的分支[1]．其要求機器人在障礙物復雜環(huán)境中，根據(jù)預先設定的指令從起點到目標運動，并通過一定的算法在運動過程中以最優(yōu)或者次優(yōu)的路徑避開所有障礙物[2-3]．常用的算法有模擬退火算法、模糊邏輯算法、禁忌搜索算法和人工勢場法[4]．人工勢場法是一種虛擬力法，它假設物體之間存在引力和斥力，機器人和目標之間有引力相互吸引，機器人和障礙物之間有斥力相互排斥，通過建立引力場斥力場函數(shù)進行路徑尋優(yōu)．如果各項參數(shù)選擇恰當，規(guī)劃的路徑就具有平滑、安全和簡潔的優(yōu)點[5]．傳統(tǒng)人工勢場法未能解決目標不可達的問題，改進人工勢場法在斥力函數(shù)上添加調節(jié)因子，但依然存在局部極小值或路徑穿越障礙物等路徑規(guī)劃失敗的問題，恰當?shù)剡x擇算法參數(shù)是算法能否成功應用的關鍵[6]．

針對改進人工勢場法路徑規(guī)劃失敗問題，一部分研究者將改進人工勢場法結合遺傳算法[6-8]、模糊算法[9]、稀疏搜索算法[10]等規(guī)劃出正確的路徑，但此類算法由于計算量大且復雜耗時，作為后續(xù)的路徑優(yōu)化尚可．另一部分研究者通過調整算法策略，即在不改變參數(shù)的前提下，基于人工勢場法采用相對簡單的策略來解決[11-14]：文獻[11]基于人工勢場法提出了BPF算法策略對靜態(tài)和動態(tài)的障礙物進行躲避從而規(guī)劃路徑；文獻[12]基于人工勢場法建立了勢場密度，提出名為quasi-geodesic method的路徑規(guī)劃策略實現(xiàn)避障，此策略適用于二維和三維的靜態(tài)或動態(tài)環(huán)境；文獻[13]將速度變量引入到場能函數(shù)中，通過填平勢場解決了機器人局部極小值的問題；文獻[14]在人工勢場法的基礎上引入入侵雜草算法，在全局內有指導性地產(chǎn)生最優(yōu)子目的地，引導機器人擺脫“陷阱”．上述方法雖然方便可行，但均未考慮地圖中障礙物的描述，將障礙物簡單視為一個圓或質點顯然不合理．

本文針對改進人工勢場法應用中存在的路徑規(guī)劃失敗問題，提出分區(qū)場能切換法．先對地圖中障礙物進行恰當?shù)拿枋龊蜆硕ǎ缓蠡谌斯輬龇ㄔ诓煌臉硕▍^(qū)域采用不同的引力斥力組合控制策略，簡單快速地規(guī)劃出正確的路徑．

1改進人工勢場法介紹和問題描述

人工勢場法是由Khatib于1986年提出的一種虛擬力法，在機器人活動的空間人為地定義一個抽象勢場．機器人的運動過程視為一種在虛擬人工受力場的運動，它將目標、障礙物、機器人分別簡化為質點，如圖1所示．機器人在復雜環(huán)境中的任意位置，目標與機器人之間存在引力Fa；當障礙物與機器人相距一定距離時，障礙物與機器人存在斥力Fr．機器人當前的運動方向由引力和斥力的合力F的方向決定．

圖1　機器人的受力分析示意圖

改進人工勢場法針對傳統(tǒng)人工勢場法的路徑規(guī)劃目標不可達問題對算法進行了改進．如圖1所示，引力Fa的方向由機器人指向目標，該力隨機器人趨近目標而逐漸趨近0，大小如下：

(1)

改進后的斥力為

(2)

(3)

(4)

其中m為斥力位置增益系數(shù)，n為正常數(shù)．

改進人工勢場法雖然解決了目標不可達問題，但在應用過程中依然會出現(xiàn)路徑規(guī)劃失敗．通過結合智能算法尋找最佳參數(shù)來解決，算法較復雜，計算量大；通過調整算法控制策略而非改變參數(shù)則方便可行，但通常采用的以一個圓來代替障礙物(即將障礙物壓縮為一個質點，再將其包裹在一個圓內，圓的大小能包圍整個障礙物并且根據(jù)機器人的尺寸留出一定的空間，該圓的半徑等于斥力的作用范圍)的描述方法對于類似菱形、正方形或三角形的障礙物尚可，但對于長條形障礙物，僅用一個圓進行描述顯然不合理．因此在路徑規(guī)劃前應對地圖上的障礙物進行恰當?shù)拿枋龊蜆硕ǎ?/p>

2分區(qū)場能切換法

2.1地圖標定

復雜環(huán)境中，障礙物的形狀往往是不規(guī)則的，因此不同的障礙物應采取不同的方式進行標定．

對普通障礙物的標定如圖2所示．將普通障礙物記為Oij(xj,yj,τj,γj,lj)．其中xj和yj為障礙物i的中心坐標，記為Lo(xj,yj)；τj為障礙物i的標定界半徑，表明障礙物的大小；γj為絕對防御區(qū)半徑；lj為障礙物的緩沖區(qū)半徑．這些區(qū)域的半徑應滿足1.5τj<γj-τj<2τj，2τj

圖2　普通障礙物的標定

傳統(tǒng)人工勢場法和改進人工勢場法，從算法來看只采用標定界和緩沖區(qū)外界對障礙物進行描述，如圖3所示，緩沖區(qū)外界半徑即為障礙物斥力有效范圍．

圖3　采用傳統(tǒng)和改進人工勢場法的標定

對于不規(guī)則的障礙物，通過多個最小標定單元組合并以最大的近似度來進行標定．例如，長條形障礙物可視為多個普通障礙物(最小標定單元)的線性密集排列，依據(jù)障礙物的大小來設定這組障礙物的緩沖區(qū)和絕對防御區(qū)半徑．如圖4所示，放置多個普通障礙物之間的距離應保證其絕對防御區(qū)外界相交．

圖4　長條形障礙物的標定

同樣，對于U形障礙物，當目標在U形障礙物外部時，將U形障礙物用圓進行標定，如圖5所示．當目標在U形障礙物內部時，可將U形障礙物用3個長條形障礙物進行標定．

圖5　U形障礙物的標定

2.2算法設計

分區(qū)場能切換法，結合地圖標定，基于改進人工勢場法在不同的區(qū)域調整算法控制策略，具體如下：

引力為

(5)

斥力為

(6)

分區(qū)場能切換法設立了3個區(qū)域：

分區(qū)場能切換法是基于改進人工勢場法在不同區(qū)域對引力和斥力做出的合理控制和調整，算法中使用的參數(shù)k、m、n、l與改進人工勢場法參數(shù)含義相同．

3仿真和結果分析

為了驗證算法的可靠性，在相同的地圖中，分別采用改進人工勢場法和分區(qū)場能切換法進行路徑規(guī)劃．

如圖6所示，有4個障礙物：一個U形障礙物，一個長條形障礙物，兩個長寬比較接近的普通障礙物．

圖6　復雜環(huán)境下的地圖

采用改進人工勢場法的參數(shù)為k=0.50，m=1.75，n=0.50，障礙物斥力有效范圍分別為l1=2.50，l2j=0.65(j=1,2,…,7)，l3=0.65，l4=0.70，相應的地圖標定如圖7所示.

圖7采用改進人工勢場法對復雜環(huán)境進行的地圖標定

Fig.7ThemapdefinitioninthecomplicatedenvironmentbasedontheimprovedAPFmethod

僅用質點和圓標定(只有緩沖區(qū))的改進人工勢場法路徑規(guī)劃仿真結果如圖8所示．

從圖8中可以看出，在該參數(shù)下路徑規(guī)劃失敗，規(guī)劃出的路徑并沒有繞過長條形的障礙物，而是從中穿越到達了目標．在相同的參數(shù)下，采用分區(qū)場能切換法的地圖標定如圖9所示．障礙物的緩沖區(qū)和絕對防御區(qū)的半徑分別為l1=2.50，γ1=1.0；l2j=0.65，γ2j=0.4(j=1,2,…,7)；l3=0.65，γ3=0.4；l4=0.70，γ4=0.4．

圖8　改進人工勢場法下的路徑規(guī)劃

圖9采用分區(qū)場能切換法對復雜環(huán)境進行的地圖標定

Fig.9ThemapdefinitioninthecomplicatedenvironmentbasedontheRPFSM

具有障礙物緩沖區(qū)和絕對防御區(qū)的分區(qū)場能切換法路徑規(guī)劃的結果如圖10所示．

圖10　分區(qū)場能切換法下的路徑規(guī)劃

從仿真結果可以看出，采用分區(qū)場能切換法成功地躲避了障礙物，實現(xiàn)了正確的路徑規(guī)劃．在改進人工勢場法下，目標對機器人的引力在機器人到達目標前一直存在，這樣便導致了在參數(shù)設定好后，在某些障礙物和復雜環(huán)境中，當機器人和障礙物的距離比較小時會出現(xiàn)斥力和引力的合力最終指向障礙物的情況，當機器人繼續(xù)向障礙物靠近，最后無法繞過并穿越障礙物時，造成路徑規(guī)劃失敗，如圖8所示．分區(qū)場能切換法在絕對防御區(qū)只受斥力，因此可以保證機器人一旦進入該范圍內，受到的合力方向始終為障礙物指向機器人，使機器人往遠離障礙物的方向運動，從而規(guī)劃出一條正確的路徑．

4結語

改進人工勢場法雖然能有效解決傳統(tǒng)人工勢場法目標不可達的問題，但在復雜環(huán)境中躲避某些形狀的障礙物時，即使根據(jù)算法對地圖中障礙物進行了恰當?shù)臉硕ê兔枋觯廊粫霈F(xiàn)路徑規(guī)劃失敗．本文基于改進人工勢場法提出了分區(qū)場能切換法，在絕對防御區(qū)內機器人只受斥力，使機器人與障礙物在相距較近時能順利繞過障礙物，快速且合理地實現(xiàn)了路徑規(guī)劃．仿真實驗證明了算法的可靠性．分區(qū)場能切換法是基于改進人工勢場法的，因此依然受算法參數(shù)影響，后續(xù)將結合參數(shù)最優(yōu)問題進行研究．

參考文獻：

[1]歐青力,何克忠. 室外智能移動機器人的發(fā)展及其關鍵技術研究[J]. 機器人, 2000, 22(6):519-526.

OUQing-li,HEKe-zhong.Researchonkeytechniquesanddevelopmentofoutdoorintelligentautonomousmobilerobot[J].Robot, 2000, 22(6):519-526. (inChinese)

[2]張建英,趙志萍,劉 暾. 基于人工勢場法的機器人路徑規(guī)劃[J]. 哈爾濱工業(yè)大學學報, 2006, 38(8):1306-1309.

ZHANGJian-ying,ZHAOZhi-ping,LIUDun.Apathplanningmethodformobilerobotbasedonartificialpotentialfield[J].JournalofHarbinInstituteofTechnology, 2006, 38(8):1306-1309. (inChinese)

[3]歐陽鑫玉,楊曙光. 基于勢場柵格法的移動機器人避障路徑規(guī)劃[J]. 控制工程, 2014, 21(1):134-137.

OUYANGXin-yu,YANGShu-guang.Obstacleavoidancepathplanningofmobilerobotsbasedonpotentialgridmethod[J].ControlEngineeringofChina, 2014, 21(1):134-137. (inChinese)

[4]KhatibO.Real-timeobstacleavoidanceformanipulatorsandmobilerobots[J].InternationalJournalofRoboticsResearch, 1986, 5(1):90-98.

[5]DeligiannisN,LouvrosS.HybridTOA-AOAlocationpositioningtechniquesinGSMnetworks[J].WirelessPersonalCommunications, 2010, 54(2):321-348.

[6]SciaviccoL,SicilianoB.Asolutionalgorithmtotheinversekinematicproblemforredundantmanipulators[J].IEEEJournalofRoboticsandAutomation, 1988, 4(4):403-410.

[7]張波濤,劉士榮. 基于Q-GA的人工勢場的移動機器人路徑規(guī)劃[J]. 控制工程, 2008, 15(4):451-455.

ZHANGBo-tao,LIUShi-rong.ArtificialpotentialfieldwithQ-GAbaserouteplanofmobilerobot[J].ControlEngineeringofChina, 2008, 15(4):451-455. (inChinese)

[8]GerkeM.Geneticpathplanningformobilerobots[C] //ProceedingsoftheAmericanControlConference.Piscataway:IEEE, 1999:2424-2429.

[9]朱 毅,張 濤,宋靖雁. 非完整移動機器人的人工勢場法路徑規(guī)劃[J]. 控制理論與應用, 2010, 27(2):152-158.

ZHUYi,ZHANGTao,SONGJing-yan.Pathplanningfornonholonomicmobilerobotsusingartificialpotentialfieldmethod[J].ControlTheory&Applications, 2010, 27(2):152-158. (inChinese)

[10]姚 遠,周興社,張凱龍,等. 基于稀疏A*搜索和改進人工勢場的無人機動態(tài)航跡規(guī)劃[J]. 控制理論與應用, 2010, 27(7):953-959.

YAOYuan,ZHOUXing-she,ZHANGKai-long, et al.DynamictrajectoryplanningforunmannedaerialvehiclebasedonsparseA*searchandimprovedartificialpotentialfield[J].ControlTheory&Applications, 2010, 27(7):953-959. (inChinese)

[11]MontielO,Orozco-RosasU,SepúlvedaR.Pathplanningformobilerobotsusingbacterialpotentialfieldforavoidingstaticanddynamicobstacles[J].ExpertSystemswithApplications, 2015, 42(12): 5177-5191.

[12]AgirrebeitiaJ,AvilésR,DeBustosIF, et al.AnewAPFstrategyforpathplanninginenvironmentswithobstacles[J].MechanismandMachineTheory, 2005, 40(6):645-658.

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

YUZhen-zhong,YANJi-hong,ZHAOJie, et al.Mobilerobotpathplanningbasedonimprovedartificialpotentialfieldmethod[J].JournalofHarbinInstituteofTechnology, 2011, 43(1):50-55. (inChinese)

[14]李海峰,馬 斌,陳浩男,等. 基于人工勢場法與入侵雜草法路徑規(guī)劃研究[J]. 控制工程, 2015, 22(1):38-44.

LIHai-feng,MABin,CHENHao-nan, et al.Pathplanningresearchbasedonartificialpotentialfieldmethodwithinvasiveweedmethod[J].ControlEngineeringofChina, 2015, 22(1):38-44. (inChinese)

[15]GeSS,CuiYJ.Newpotentialfunctionsformobilerobotpathplanning[J].IEEETransactionsonRoboticsandAutomation, 2000, 16(5):615-620.

Path planning by using region potential field switch method

HUANGDe-ying1,GUOGe*2,WANGLi-yuan1,LIZhi-hui1

( 1.School of Control Science and Engineering, Dalian University of Technology, Dalian 116024, China；2.Information Science and Technology College, Dalian Maritime University, Dalian 116026, China )

Abstract：To solve the path planning failure of improved artificial potential field (APF) method in application, a region potential field switch method (RPFSM) is proposed. It includes the map definition and algorithm design. Firstly, the different shape obstacles on the map are defined by classifications, then the smallest cell which includes the absolute defence zone and buffer zone is set. Based on the improved APF method the algorithm is redesigned at different zones. The redesigned algorithm makes the robots only receiving repulsion in the absolute defence zone, both repulsion and attraction in the buffer zone and only attraction outside the buffer zone. Thus, it can make the robot arrive at the aim very fast and avoid obstacles successfully. The reliability of the proposed method is testified by the Matlab simulation experiments using respectively the improved APF method and the RPFSM in the defined map.

Key words：path planning; improved artificial potential field (APF) method; map definition; absolute defence zone; region potential field switch method (RPFSM)

作者簡介:黃德穎(1991-)，女，碩士生，E-mail:hdying@mail.dlut.edu.cn；郭 戈*(1972-)，男，博士，教授，E-mail:geguo@yeah.net.

基金項目:國家自然科學基金資助項目(61273107)；中央高校基本科研業(yè)務費專項資金資助項目(3132013334)；遼寧省大連市領軍人才培養(yǎng)資助項目(61174060).

收稿日期：2015-06-26；修回日期: 2015-09-13．

中圖分類號：TP242

文獻標識碼：A

doi:10.7511/dllgxb201601006

文章編號：1000-8608(2016)01-0035-06