馬曉輝，丁洪偉，王夢(mèng)瑤，趙一帆

(1.中國(guó)人民武裝警察部隊(duì)昆明市支隊(duì)，昆明　650220；2.云南大學(xué)　信息學(xué)院，昆明　650091)

?

·實(shí) 驗(yàn) 技 術(shù)·

基于BUG理論的平行主線(xiàn)改進(jìn)算法

馬曉輝1，丁洪偉2，王夢(mèng)瑤2，趙一帆2

(1.中國(guó)人民武裝警察部隊(duì)昆明市支隊(duì)，昆明650220；2.云南大學(xué)信息學(xué)院，昆明650091)

基于Pioneer3機(jī)器人平臺(tái)提出一種未知環(huán)境中的機(jī)器人路徑規(guī)劃的改進(jìn)算法。在BUG理論的基礎(chǔ)上，通過(guò)先鋒機(jī)器人實(shí)時(shí)讀取機(jī)器人角度偏差的能力，即時(shí)重新規(guī)劃?rùn)C(jī)器人到達(dá)目標(biāo)點(diǎn)的路線(xiàn)。改進(jìn)算法縮短了BUG理論中的運(yùn)動(dòng)路徑，提高了機(jī)器人避障的效率。

先鋒3；BUG理論；平行主線(xiàn)；算法

機(jī)器人路徑規(guī)劃是移動(dòng)機(jī)器人研究的一個(gè)重要課題[1]，根據(jù)工作環(huán)境的不同大致可以分為兩種：一種是基于模型的路徑規(guī)劃，其作業(yè)環(huán)境的全部信息是預(yù)知的；另一種是基于傳感器的路徑規(guī)劃，作業(yè)環(huán)境的信息是全部未知或部分未知的[2-3]?；谖粗h(huán)境的算法有BUG算法、HGVG方法等，但此類(lèi)算法都存在著一定的不足[4]。本文主要是在BUG理論的基礎(chǔ)上，利用先鋒3機(jī)器人的特點(diǎn)提出了改進(jìn)算法并進(jìn)行了仿真實(shí)驗(yàn)，以證明改進(jìn)算法的可行性和有效性。

1　Pioneer3機(jī)器人簡(jiǎn)介

MobileRobots公司常年致力于大學(xué)及研究機(jī)構(gòu)的智能機(jī)器人系統(tǒng)的研制與開(kāi)發(fā)，先后開(kāi)發(fā)出先鋒系列3代(Pioneer3)機(jī)器人及面向研究的軟件平臺(tái)系統(tǒng)，如圖1所示。Pioneer3機(jī)器人具有16個(gè)聲吶環(huán)，有物體檢測(cè)、距離檢測(cè)、自動(dòng)避障、面貌識(shí)別、定位以及導(dǎo)航等功能，聲吶靈敏度可調(diào)，可以為機(jī)器人提供360°無(wú)縫檢測(cè)。Pioneer3機(jī)器人還為用戶(hù)提供了豐富的軟件系統(tǒng)，包括機(jī)器人控制器軟件系統(tǒng)和機(jī)器人客戶(hù)端軟件系統(tǒng)。在使用系統(tǒng)軟件時(shí)可以結(jié)合機(jī)器人的聲吶實(shí)時(shí)讀取機(jī)器人的方向角度。這也是本文提出的平行主線(xiàn)改進(jìn)算法得以實(shí)現(xiàn)的重要基礎(chǔ)和保障。

圖1　Pioneer3機(jī)器人平臺(tái)

2　BUG理論

BUG理論[5]是在移動(dòng)機(jī)器人路徑規(guī)劃研究中較早被提出的理論，其主要思想類(lèi)似于現(xiàn)代定向運(yùn)動(dòng)理論中繞過(guò)障礙物的方法[6]，即：將起始點(diǎn)與目標(biāo)點(diǎn)的連接線(xiàn)作為機(jī)器人運(yùn)動(dòng)的主線(xiàn)(M-line)，開(kāi)始移動(dòng)時(shí)機(jī)器人沿M-line運(yùn)動(dòng)，當(dāng)遇到障礙物時(shí)，機(jī)器人改變移動(dòng)策略，沿著障礙物的邊緣運(yùn)動(dòng)，直至再次回到主線(xiàn)，并且其與終點(diǎn)的距離較前一次離開(kāi)主線(xiàn)時(shí)有所減少時(shí)，機(jī)器人繼續(xù)沿主線(xiàn)前進(jìn)，直至到達(dá)終點(diǎn)。

BUG算法簡(jiǎn)單地將機(jī)器人在未知環(huán)境中的運(yùn)動(dòng)分為“沿墻走”和“沿主線(xiàn)走”兩種模式，簡(jiǎn)單實(shí)用，可有效地在二維環(huán)境中找到到達(dá)目標(biāo)點(diǎn)的路徑。但這種算法會(huì)存在冗余，尤其在障礙物不是規(guī)則物體的情況下，往往會(huì)造成機(jī)器人路徑的較多冗余[7]。如圖2所示，障礙物邊緣較為復(fù)雜時(shí)，障礙物的邊緣較為冗長(zhǎng)，這樣機(jī)器人“沿墻走”的路徑也會(huì)變得很冗長(zhǎng)，比直線(xiàn)到達(dá)目標(biāo)點(diǎn)會(huì)形成許多不必要的浪費(fèi)，移動(dòng)的效率也較低[8]。

圖2　BUG理論造成的路徑冗余

3　BUG算法的改進(jìn)和實(shí)驗(yàn)仿真

基于BUG算法會(huì)在復(fù)雜未知環(huán)境中造成的路線(xiàn)冗余和Pioneer3機(jī)器人自身的特點(diǎn)，本文提出了“平行主線(xiàn)”的改進(jìn)算法。其基本思想為：機(jī)器人開(kāi)始按照BUG理論的方式產(chǎn)生起點(diǎn)到目標(biāo)點(diǎn)的主線(xiàn)，并沿主線(xiàn)行走，遇到障礙物后進(jìn)入“沿墻走”模式，并在沿墻走中實(shí)時(shí)讀取自己的位置角度，當(dāng)自己的位置與主線(xiàn)平行時(shí)，退出“沿墻走”模式，并以此點(diǎn)為起點(diǎn)重新生成主線(xiàn)，并沿新的主線(xiàn)行走直至達(dá)到目標(biāo)點(diǎn)。

如圖3所示，Pioneer3機(jī)器人在得到目標(biāo)點(diǎn)位置信息后，先將自己所在坐標(biāo)設(shè)為起點(diǎn)坐標(biāo)A(XA，YA，θA)，其中XA，YA為二維坐標(biāo)值，θA為機(jī)器人的角度，機(jī)器人能夠隨著移動(dòng)實(shí)時(shí)讀取偏轉(zhuǎn)的角度。機(jī)器人得到指定的目標(biāo)點(diǎn)B(XB，YB，θB)后，生成一條連接A、B兩點(diǎn)的主線(xiàn)(M-line)并計(jì)算出主線(xiàn)的斜率k，而后機(jī)器人沿主線(xiàn)向目標(biāo)點(diǎn)移動(dòng)。當(dāng)達(dá)到點(diǎn)P時(shí)，檢測(cè)到前方有障礙物，機(jī)器人按照BUG算法進(jìn)入“沿墻走”模式，并實(shí)時(shí)檢測(cè)自身的方向偏差率k′，k′=tanθ。當(dāng)機(jī)器人移動(dòng)到點(diǎn)R時(shí)，k′和主線(xiàn)斜率k相等，此時(shí)，機(jī)器人退出“沿墻走”模式，并以點(diǎn)R為新的起點(diǎn)生成新的主線(xiàn)，沿新主線(xiàn)移動(dòng)至終點(diǎn)B，完成點(diǎn)A到點(diǎn)B的移動(dòng)。

圖3　改進(jìn)算法原理圖

根據(jù)幾何知識(shí)容易得知：在圖3中，當(dāng)構(gòu)建三角形△QRB時(shí)，QR與QB之和明顯大于RB，即QR+QB>RB，又因?yàn)榍€(xiàn)RQ的長(zhǎng)度會(huì)大于直線(xiàn)RQ的長(zhǎng)度，所以機(jī)器人在與主線(xiàn)平行的點(diǎn)退出“沿墻走”模式并重新設(shè)定主線(xiàn)的路徑會(huì)大大縮短，從而提高了機(jī)器人運(yùn)動(dòng)的效率。由此可以簡(jiǎn)單判斷出，改進(jìn)算法可以提高機(jī)器人移動(dòng)的效率，達(dá)到減少路徑的冗余度的目的。

圖4　二次遇到障礙物

另外，在復(fù)雜環(huán)境中運(yùn)動(dòng)時(shí)機(jī)器人可能會(huì)二次遇到障礙物[9]，此時(shí)只需要再次使用“平行主線(xiàn)策略”，即可以使機(jī)器人在順利到達(dá)目標(biāo)點(diǎn)的同時(shí)又縮短移動(dòng)的距離，減少路徑的冗余，達(dá)到提高機(jī)器人移動(dòng)效率的目的。如圖4所示，當(dāng)機(jī)器人遇到障礙物時(shí)執(zhí)行“平行主線(xiàn)策略”，在斜率與主線(xiàn)相同的點(diǎn)重新規(guī)劃路徑，生成“主線(xiàn)2”并沿其運(yùn)動(dòng)，在沿“主線(xiàn)2”運(yùn)動(dòng)的過(guò)程中再次遇到障礙物，此時(shí)機(jī)器人調(diào)用“沿墻走”模式，直至運(yùn)動(dòng)路徑平行于“主線(xiàn)2”時(shí)，再次執(zhí)行“平行主線(xiàn)策略”，重新規(guī)劃直線(xiàn)路徑并運(yùn)動(dòng)到目標(biāo)點(diǎn)B，完成既定目標(biāo)。

為了驗(yàn)證算法的可行性，本文在Matlab平臺(tái)上進(jìn)行了實(shí)驗(yàn)仿真，仿真結(jié)果如圖5所示：粗線(xiàn)為機(jī)器人的運(yùn)動(dòng)軌跡，細(xì)線(xiàn)為BUG算法中的主線(xiàn)(M-line)。通過(guò)仿真結(jié)果可以看出，利用改進(jìn)算法后機(jī)器人少走了部分彎路，并且能夠直接到達(dá)目標(biāo)點(diǎn)。表1為在仿真實(shí)驗(yàn)中不同障礙物的情況下兩種算法的路徑長(zhǎng)度比較，通過(guò)數(shù)據(jù)也可以明顯看到，隨著障礙物的增大和復(fù)雜性的增加，改進(jìn)算法能夠更有效地減少路徑長(zhǎng)度，提高機(jī)器人的效率。

圖5　仿真實(shí)驗(yàn)結(jié)果

障礙物BUG算法改進(jìn)算法157.87854.405260.12254.736365.09155.128

4　結(jié)束語(yǔ)

本文在先鋒3機(jī)器人的運(yùn)行環(huán)境中提出了一種基于BUG理論的、在未知環(huán)境中的移動(dòng)機(jī)器人路徑

規(guī)劃算法。改進(jìn)算法根據(jù)機(jī)器人能實(shí)時(shí)讀取自身運(yùn)動(dòng)角度的特性，提前退出BUG算法中的“沿墻走”模式，及時(shí)重新規(guī)劃路徑，在能準(zhǔn)確到達(dá)目標(biāo)位置的基礎(chǔ)上，大大減少了路徑的冗余，提高了機(jī)器人運(yùn)動(dòng)的效率。

[1]都志輝，陳諭，劉鵬.網(wǎng)格計(jì)算[M].北京：清華大學(xué)出版社，2002.

[2]付巖.智能水下機(jī)器人全局及局部路徑規(guī)劃技術(shù)研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2004.

[3]李彩虹，李貽斌，范晨.移動(dòng)機(jī)器人動(dòng)態(tài)避障算法[J].山東大學(xué)學(xué)報(bào)：工學(xué)版，2007，37(5)： 60-64.

[4] 蔡自興，賀漢根，陳虹. 未知環(huán)境中移動(dòng)機(jī)器人導(dǎo)航控制研究的若干問(wèn)題[J]. 控制與決策，2002，30(7)：385-390.

[5] LUMDSKY V，STEPANOV A.Path-planning stralegles for a point mobile automation moving amidst unknown obstacles of arbitrary shape[J].Algorithmica，1987，11(2)：403-430.

[6]康亮，趙春霞，郭劍輝.未知環(huán)境下基于三次螺線(xiàn)Bug算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].工程圖學(xué)學(xué)報(bào)，2010，23(1)：30-38.

[7]KAMON I，RIVLIN E.Sensory based motion planning with global proofs[C]//HIROS’95.Pittsburgh，PA，USA:[s.n.]，1995：435-440.

[8] 禹建麗，ROUMOV V，孫增圻.一種不確定環(huán)境下移動(dòng)機(jī)器人避障規(guī)劃算法[J].機(jī)器人，2007，23(3)：201-205.

[9] 席裕庚.動(dòng)態(tài)不確定環(huán)境下廣義控制問(wèn)題的預(yù)測(cè)控制[J].控制理論與應(yīng)用，2007，17(5)：665-670.

Improved Algorithm Based on the Parallel Main Line of BUG Theory

MA Xiaohui1，DING Hongwei2，WANG Mengyao2，ZHAO Yifan2

(1.Kunming Detachment of Chinese Armed Police Force，Kunming 650220,China;2.School of Information，Yunnan University，Kunming 650091，China)

One of the improved algorithms for robot path planning in an unknown environment is proposed in this paper under the background in Pioneer3 robot platform. Based on the BUG theory and using the ability to read real time deviation of robot angle by pioneer robot，the robot plans a rode to reach the goal point immediately. The improved algorithm reduces the motion path in the BUG theory and improves the efficiency of the robot obstacle avoidance.

Pioneer 3;BUG theory;parallel main line;algorithm

2014-10-12；修改日期: 2014-11-13

國(guó)家自然科學(xué)基金(6146105)。

馬曉輝(1987-)，男，碩士生，主要從事無(wú)線(xiàn)傳感器網(wǎng)絡(luò)、移動(dòng)機(jī)器人控制方面的研究。

TP242.6

A

10.3969/j.issn.1672-4550.2016.01.001