未知環(huán)境中移動(dòng)機(jī)器人的路徑規(guī)劃與探索算法

高 揚(yáng)，鄒 丹，胡大偉，王來軍，楊京帥

（1.長安大學(xué) 汽車學(xué)院,陜西 西安 710064；2.西北工業(yè)大學(xué) 明德學(xué)院,陜西 西安 710072）

未知環(huán)境中移動(dòng)機(jī)器人的路徑規(guī)劃與探索算法

高 揚(yáng)1，鄒 丹2，胡大偉1，王來軍1，楊京帥1

（1.長安大學(xué) 汽車學(xué)院,陜西 西安 710064；2.西北工業(yè)大學(xué) 明德學(xué)院,陜西 西安 710072）

未知環(huán)境中移動(dòng)機(jī)器人如何快速到達(dá)目標(biāo)，如何盡量獲取環(huán)境信息以繪制地圖，是常見問題，也是難點(diǎn)問題。針對此二問題，論文綜述了路徑規(guī)劃、探索算法領(lǐng)域的相關(guān)研究成果，指出了它們的特點(diǎn)與不足。最后對路徑規(guī)劃、探索算法的發(fā)展趨勢進(jìn)行了展望。

移動(dòng)機(jī)器人;局部路徑規(guī)劃;自由路徑;盲區(qū)

移動(dòng)機(jī)器人是一種在復(fù)雜環(huán)境下工作的具有自規(guī)劃、自組織、自適應(yīng)能力的機(jī)器人，無需外部干預(yù)即能自主移動(dòng)至目標(biāo)以完成任務(wù)。自第一個(gè)移動(dòng)機(jī)器人Shakey用于人工智能研究以來，在國防、航天、消防、工業(yè)、交通、科研等眾多領(lǐng)域，移動(dòng)機(jī)器人受到廣泛關(guān)注與應(yīng)用，其應(yīng)用環(huán)境也由陸地延伸到了空間、水下等領(lǐng)域。正是源于其廣闊的市場前景，移動(dòng)機(jī)器人技術(shù)的發(fā)展也備受各國重視。各發(fā)達(dá)國家、地區(qū)圍繞不同領(lǐng)域的移動(dòng)機(jī)器人技術(shù)均各有側(cè)重，例如美國主要側(cè)重于對各種室外移動(dòng)機(jī)器人的研究，日韓等國則主要側(cè)重于人形機(jī)器人方面的研究，歐洲地區(qū)這側(cè)重于城市、建筑環(huán)境中的移動(dòng)機(jī)器人研究。

現(xiàn)實(shí)中移動(dòng)機(jī)器人通常需工作于未知環(huán)境，即：無預(yù)知環(huán)境信息，也無額外定位信息來源的環(huán)境。此類未知環(huán)境中移動(dòng)機(jī)器人如何以某種指標(biāo)最優(yōu)的方式到達(dá)目標(biāo)，是制約其走向?qū)嵱玫囊淮箅y點(diǎn)問題。與此同時(shí)，路徑規(guī)劃等多種上層任務(wù)往往依賴環(huán)境地圖，如何盡可能的獲取環(huán)境信息以繪制地圖是制約移動(dòng)機(jī)器人發(fā)展的另一問題。目前，在實(shí)際應(yīng)用時(shí)多使移動(dòng)機(jī)器人先以其他方式引導(dǎo)(例如人為介入)實(shí)現(xiàn)對環(huán)境的繪圖，待繪成地圖后再進(jìn)行路徑規(guī)劃、自主移動(dòng)并完成任務(wù)。有鑒于此種模式需要額外的繪圖工作準(zhǔn)備，近年來也有學(xué)者提出一類探索算法, 該類算法部分采用路徑規(guī)劃思想，以實(shí)現(xiàn)自主繪制地圖為目標(biāo)，尋找最有利于繪圖的機(jī)器

人移動(dòng)路徑。因此后文將分別介紹路徑規(guī)劃算法及探索算法。

1 路徑規(guī)劃

移動(dòng)機(jī)器人技術(shù)日益受到各國重視，圍繞不同領(lǐng)域各國、各地區(qū)均各有側(cè)重(如表1所示)[1]。自從1968年Nilsson利用啟發(fā)式搜索算法為機(jī)器人尋找一條無碰、最短路徑開始，路徑規(guī)劃技術(shù)已成為機(jī)器人學(xué)領(lǐng)域的研究熱點(diǎn)。依據(jù)所用信息層次不同，現(xiàn)有路徑規(guī)劃算法可分成全局式、局部式和復(fù)合式3大類。

表1 世界主要國家、地區(qū)的移動(dòng)機(jī)器人技術(shù)研究特點(diǎn)Tab.1 Character of the research of robotic in the world

1）全局路徑規(guī)劃

全局路徑規(guī)劃利用預(yù)知的全局環(huán)境信息，可在事先建好的環(huán)境模型中尋優(yōu)，以獲得全局范圍內(nèi)的最優(yōu)路徑。作為較早提出的方法，全局路徑規(guī)劃可以保證路徑的可達(dá)性及最優(yōu)性。進(jìn)一步，此類方法可分解為兩大部分：對構(gòu)型空間的描述方法，以及在構(gòu)型空間中搜尋最優(yōu)路徑的搜索算法[2]。典型方法中前者主要有：可視圖(VisibilltyGraph)、Voronoi圖、柵格圖、頂點(diǎn)圖(Vertex graph)、拓?fù)鋱D等。后者則主要包括：圖搜索類算法(從起始點(diǎn)出發(fā)向目標(biāo)點(diǎn)搜索的算法)，如各種貪心算法、Dijkstra 算法、以A*為代表的各種啟發(fā)式搜索算法、可以在動(dòng)態(tài)圖上搜索到最短路徑的D*算法(改良Dijkstra 算法)、D* Lite算法等[3]；各種隨機(jī)采樣類算法；在各種可行單元間搜索最優(yōu)組合的單元分解法；一些智能算法如神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法、粒子群算法等。

可以看出：全局路徑規(guī)劃依賴準(zhǔn)確的全局環(huán)境模型，一旦環(huán)境信息發(fā)生變化則需重新規(guī)劃，難以適應(yīng)頻繁變化的地圖。雖然有學(xué)者針對此問題，提出一系列對全局路徑進(jìn)行局部修訂的算法[4]，但對地圖變化范圍較大的未知環(huán)境仍然難以適應(yīng)。此外，由于算法通常運(yùn)算量較大需離線運(yùn)行，也難以對地圖及機(jī)器人感知信息的變化及時(shí)反應(yīng)。

2）局部路徑規(guī)劃

局部路徑規(guī)劃通常并不規(guī)劃一條完整的路徑，而是規(guī)劃機(jī)器人的最優(yōu)運(yùn)動(dòng)，建立機(jī)器人運(yùn)動(dòng)與感知信息間的映射關(guān)系，將局部范圍內(nèi)的最優(yōu)路徑信息隱含在對機(jī)器人運(yùn)動(dòng)的控制命令中，力圖通過連續(xù)的局部最優(yōu)實(shí)現(xiàn)全局優(yōu)化。此類方法通常是在線使用的反應(yīng)式算法，僅依賴傳感器所得局部環(huán)境感知信息，常用算法有：人工勢場法、模糊控制方法、矢量場圖類方法(VFH)、神經(jīng)網(wǎng)絡(luò)法、動(dòng)態(tài)窗口法、bug算法等[5]。

由于對環(huán)境信息依賴較小，此類方法對未知環(huán)境表現(xiàn)出較強(qiáng)的適應(yīng)能力，已有針對未知環(huán)境中路徑規(guī)劃問題的研究也多集中于此類方法。然而由于缺乏對全局信息的利用，形成了只顧眼前的短視機(jī)制，導(dǎo)致局部路徑規(guī)劃通常不能保證到達(dá)目標(biāo)，也不能保證獲得全局最優(yōu)路徑，有可能陷入死區(qū)、局部最小等問題。

3）復(fù)合路徑規(guī)劃

近年來有學(xué)者將前兩類方法取長補(bǔ)短加以結(jié)合，提出一類復(fù)合式路徑規(guī)劃方法。此類方法利用全局路徑規(guī)劃保證全局范圍的最優(yōu)性與可達(dá)性，利用局部路徑規(guī)劃在線運(yùn)行提供對局部環(huán)境的適應(yīng)能力，因而兼具兩者的優(yōu)點(diǎn)。已有研究包括：Zhuoning Dong 等人利用A*算法與勢場法結(jié)合提出一種復(fù)合式路徑規(guī)劃算法[6]；Urdiales C等人認(rèn)為在未知環(huán)境中，應(yīng)充分利用局部路徑規(guī)劃的高適應(yīng)性與魯棒性，只需使其在總體上保持與全局路徑一致即可，并提出一種基于子目標(biāo)的復(fù)合式路徑規(guī)劃算法[7]；Shuzhi Sam Ge等人在路徑跟蹤行為與障礙物邊緣跟蹤行為間依情況不同而切換，并以此提出一種復(fù)合式規(guī)劃方法[8];Xiaoyu Yang等利用模糊控制器選取子目標(biāo)點(diǎn)，以引導(dǎo)局部路徑規(guī)劃[9]; Wooden D等人將機(jī)器人路徑規(guī)劃劃分為上下兩層：上層負(fù)責(zé)全局的任務(wù)，下層負(fù)責(zé)應(yīng)對局部環(huán)境[10]。

由于同時(shí)利用了全局、局部環(huán)境信息，已有復(fù)合式路徑規(guī)劃算法表現(xiàn)出一定優(yōu)勢，但仍然存在不足，例如：全局層規(guī)劃仍采用傳統(tǒng)全局路徑規(guī)劃算法，并未考慮到SLAM技術(shù)繪制所得增量式地圖帶來的影響；全局路徑規(guī)劃龐大的運(yùn)算量仍然會(huì)影響到復(fù)合路徑規(guī)劃的效率；全局規(guī)劃與局部規(guī)劃分別進(jìn)行，未考慮到兩層規(guī)劃方法間的相互影響，且使得兩種規(guī)劃結(jié)果的融合存在一定困難。

2 未知環(huán)境中的探索算法

探索算法主要研究如何利用已有信息選擇下一步移動(dòng)目標(biāo)，或者規(guī)劃下一運(yùn)動(dòng)以使機(jī)器人移動(dòng)至未知區(qū)域，獲得更多環(huán)境信息，以便繪制環(huán)境地圖。早期的探索算法主要采用隨機(jī)行走以及沿墻行走等簡單策略?，F(xiàn)有研究多將探索算法歸結(jié)為三類：未知區(qū)域驅(qū)動(dòng)類算法、基于Next Best View(NBV)的探索算法、基于路徑規(guī)劃的探索算法。

未知區(qū)域驅(qū)動(dòng)算法利用感知信息，識(shí)別未知區(qū)域，并引導(dǎo)機(jī)器人向該區(qū)域移動(dòng)。典型如基于邊界的探索算法，識(shí)別未知區(qū)域與已知區(qū)域間的邊界，并引導(dǎo)機(jī)器人向最近邊界移動(dòng)，從而獲取新的環(huán)境信息，擴(kuò)大地圖范圍。

NBV源于機(jī)器視覺領(lǐng)域，表示下一步的最佳視野。基于NBV的探索算法對下一步的候選視點(diǎn)定義性能函數(shù)，根據(jù)當(dāng)前已獲取信息及性能函數(shù)選擇下一步的最佳視點(diǎn)使機(jī)器人具有最佳的感知信息，從而利用最佳視點(diǎn)引導(dǎo)機(jī)器人對未知環(huán)境的探索行為。對此類算法的研究主要集中于候選視點(diǎn)的生成方法以及性能函數(shù)的構(gòu)建兩方面。

其中最佳視點(diǎn)的生成可以分為3種[11],分別是前沿(Frontier)理論，隨機(jī)算法和這兩種方法的混合算法。前沿理論總是傾向于將候選位置設(shè)在已探測區(qū)域和未探測區(qū)域的邊界上。此類方法容易給機(jī)器人獲得較大的信息收益，然而也正因此使其容易增加定位困難，降低機(jī)器人定位精度。隨機(jī)算法在一定范圍內(nèi)隨機(jī)生成視點(diǎn)，再進(jìn)行篩選。此類方法應(yīng)用簡單，然而難以平衡計(jì)算量與后續(xù)的搜索最優(yōu)視點(diǎn)效果。對性能函數(shù)的構(gòu)建一般則考慮信息收益、路徑成本和定位的不確定性，構(gòu)建各種效用函數(shù)。

基于路徑規(guī)劃的探索算法則主要從已有路徑規(guī)劃算法出發(fā)，以路徑覆蓋的區(qū)域面積最大為目標(biāo)進(jìn)行路徑規(guī)劃。例如基于柵格地圖的harmonic function方法，基于RRT路徑規(guī)劃的方法等[12]。

3 結(jié)束語

作為移動(dòng)機(jī)器人技術(shù)的核心，路徑規(guī)劃算法與探索算法事實(shí)上存在某種相似性。兩者的目標(biāo)均為路徑，但規(guī)劃路徑的目標(biāo)有所不同，且探索算法也部分借鑒了路徑規(guī)劃的研究成果。路徑規(guī)劃方面，如何在保證可達(dá)性的同時(shí)減少計(jì)算量，提高規(guī)劃速度，提高對動(dòng)態(tài)環(huán)境的適應(yīng)能力，是其重點(diǎn)發(fā)展方向。此外，如何在三維環(huán)境中提高規(guī)劃能力，減少對環(huán)境信息的依賴也將是其一大發(fā)展方向。探索算法方面，如何以某種指標(biāo)最優(yōu)的方式引導(dǎo)機(jī)器人移動(dòng)，使其繪制全局地圖將始終是其主要研究方向。

事實(shí)上，路徑規(guī)劃，定位，地圖繪制作為移動(dòng)機(jī)器人三大核心技術(shù)存在相互依賴的特性。未知環(huán)境中，機(jī)器人的定位必須依賴環(huán)境地圖，而對地圖的繪制又反過來依賴于機(jī)器人定位結(jié)果，因此定位與繪圖間相互依賴，互相影響。其次，機(jī)器人欲實(shí)現(xiàn)以某種指標(biāo)最優(yōu)的方式到達(dá)目標(biāo)，需進(jìn)行路徑規(guī)劃結(jié)果，而各種路徑規(guī)劃算法又不同程度依賴于環(huán)境地圖與定位信息。反之，地圖的繪制要求機(jī)器人必須在移動(dòng)中感知環(huán)境，而機(jī)器人的移動(dòng)卻又受控于路徑規(guī)劃或探索算法的結(jié)果。因此繪圖、定位與路徑規(guī)劃間相互依賴。從影響來看：一方面，定位精度、繪圖效果直接影響到路徑規(guī)劃效果；另一方面，已知路徑規(guī)劃結(jié)果有助于定位時(shí)降低搜索范圍，提高精度，并進(jìn)一步改善繪圖效果。因此未知環(huán)境中，定位、地圖繪制與路徑規(guī)劃間互相依賴，互相影響。如何進(jìn)一步利用三者間相互依賴的特性可能是未來進(jìn)一步需要考慮的課題。

[1] Fox D. International assessment of research and development in robotics[R].Arlington,VA,USA:World Technology Evaluation Center,2006.

[2] Sariff N, Buniyamin N. An overview of autonomous mobile robot path planning algorithms:4th Student Conference on Research and Development ＂Towards Enhancing Research Excellence in the Region＂.2006[C]. Shah Alam, Malaysia:IEEE,2006:183-188.

[3] Sun X, Yeoh W, Koenig S. Moving Target D* Lite:International Joint Conference on Autonomous Agents and Multiagent Systems(AAMAS).2010[C]. 2010:67-74.

[4] Nasrollahy AZ, Javadi H. Using Particle Swarm Optimization for Robot Path Planning in Dynamic Environments with Moving Obstacles and Target:UKSim 3rd European Modelling Symposium on Computer Modelling and Simulation.2009[C].Athens, Greece:IEEE,2009:60-65.

[5] Yang G, Shu-dong S. Local Path Planning of Mobile Robots in Dynamic Unknown Environment Based on Prediction of Collision:International Conference on Measuring Technology and Mechatronics Automation.2009[C].Zhangjiajie, Hunan, China: IEEE Computer Society,2009:84-88.

[6] D Z, C Z, Z R, Z R. A hybrid approach of virtual force and A*search algorithm for UAV path replanning:IEEE Conference on Industrial Electronics and Applications (ICIEA).2011[C].Beijing: IEEE, 2011:1140-1145.

[7] Urdiales C,Perez EJ,Sandoval F,Vazquez-Salceda J.A hybrid architecture for autonomous navigation using a CBR reactive layer:IEEE/WIC International Conference on IntelligentAgent Technology.2003[C].Banff,Canada:Int. Assoc. of Science and Technology for Development,2003:225-232.

[8] Ge SS, Lai X-C, Al Mamun A. Sensor-based path planning for nonholonomic mobile robots subject to dynamic constraints[J].Robotics and Autonomous Systems,2007,55(7):513-526.

[9] Xiaoyu Y, Moallem M, Patel RV. A layered goal-oriented fuzzy motion planning strategy for mobile robot navigation[J].IEEE Transactions on Systems,Man, and Cybernetics,Part B:Cybernetics,2005,35(6):1214-1224.

[10] Wooden D, Powers M, MacKenzie DC, Balch T, Egerstedt M.Control-driven mapping and planning:2007 IEEE/RSJ International Conference on Intelligent Robots and Systems,IROS 2007.2007[C].San Diego,CA,USA:IEEE,2007:3056-3061.

[11] 王立.機(jī)器人室內(nèi)未知環(huán)境探測規(guī)劃研究[D].杭州: 浙江大學(xué), 2010.

[12] Julia M, Gil A, Reinoso O. A comparison of path planning strategies for autonomous exploration and mapping of unknown environments[J].Autonomous Robots,2012,33(4): 427-444.

Path planning of mobile robots in unknown environment

GAO Yang1, ZOU Dan2, HU Da-wei1, WANG Lai-jun1, YANG Jing-shuai1
（1. School of Automobile, Chang An University, Xi’an 710064, China; 2. Ming De College, Northwestern Polytechnical University, Xi’an 710072, China）

Either to reach the destination or mapping the environment quickly in unknown environment is a hard and common problem for a mobile robot. Thus this paper proposed an overview to the path planning and discovery algorithms which are designed for that two problem separately. Finally the trends of them are described.

mobile robot; local path planning; free load; discovery

TN83

A

1674-6236(2014)03-0001-03

2013–05–20 稿件編號(hào)：201305214

中央高校基金(CHD2011JC176,HD2011JC105);國家自然科學(xué)基金(51108040);博士后基金(2013M531999)

高 揚(yáng)(1982—)，男，陜西西安人，博士，講師。研究方向：計(jì)算機(jī)控制，機(jī)器人技術(shù)，物流工程技術(shù)。