馬曉輝，丁洪偉，王夢瑤，趙一帆

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

?

·實 驗 技 術(shù)·

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

馬曉輝1，丁洪偉2，王夢瑤2，趙一帆2

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

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

先鋒3；BUG理論；平行主線；算法

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

1　Pioneer3機器人簡介

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

圖1　Pioneer3機器人平臺

2　BUG理論

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

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

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

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

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

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

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

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

圖4　二次遇到障礙物

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

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

圖5　仿真實驗結(jié)果

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

4　結(jié)束語

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

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

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

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

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

[4] 蔡自興，賀漢根，陳虹. 未知環(huán)境中移動機器人導(dǎo)航控制研究的若干問題[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)境下基于三次螺線Bug算法的移動機器人路徑規(guī)劃[J].工程圖學(xué)學(xué)報，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)境下移動機器人避障規(guī)劃算法[J].機器人，2007，23(3)：201-205.

[9] 席裕庚.動態(tài)不確定環(huán)境下廣義控制問題的預(yù)測控制[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

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

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

TP242.6

A

10.3969/j.issn.1672-4550.2016.01.001