趙文瑜

摘 ? 要：當(dāng)移動(dòng)機(jī)器人具有有限的計(jì)算能力時(shí)，Bug算法是最簡(jiǎn)單有效的路徑規(guī)劃算法，適用于環(huán)境地圖未知或環(huán)境快速變化的情況，這些算法從機(jī)器人傳感器，如激光雷達(dá)傳感器來獲得的本地信息和全局目標(biāo)信息，以朝向目標(biāo)的直線運(yùn)動(dòng)和沿著障礙的邊界運(yùn)動(dòng)這兩種簡(jiǎn)單的運(yùn)動(dòng)方式來到達(dá)目標(biāo)點(diǎn)。文章對(duì)此展開了分析。

關(guān)鍵詞：路徑規(guī)劃;Bug算法;機(jī)器人

基于Bug的路徑規(guī)劃算法有3種，分別為Bug0，Bug1，Bug2。使用這些算法的移動(dòng)機(jī)器人可以避開障礙物并朝著目標(biāo)前進(jìn)。其需要使用的內(nèi)存低，并且獲得的路徑通常遠(yuǎn)非最佳。Lumelsky等[1-2]首先實(shí)現(xiàn)Bug算法，然后進(jìn)行了一些改進(jìn)[3-4]。文章在下面內(nèi)容主要描述了Bug算法中的3個(gè)基本算法，并使用Bug0算法在Matlab中進(jìn)行仿真，驗(yàn)證其算法的有效性。

1 ? ?Bug1算法

與Bug0相比，Bug1算法需要使用更多內(nèi)存來運(yùn)行更多計(jì)算。在每次迭代中，其需要計(jì)算到目標(biāo)點(diǎn)位置的歐幾里德距離并記住障礙物圓周上與目標(biāo)的最近點(diǎn)。其操作流程如下：

（1）沿直線向目標(biāo)移動(dòng)，直到遇見障礙物或達(dá)到目標(biāo)。

（2）如果檢測(cè)到障礙物，則向左轉(zhuǎn)并沿著障礙物的整個(gè)邊界運(yùn)動(dòng)并測(cè)量到目標(biāo)的歐幾里德距離。當(dāng)再次到達(dá)最初檢測(cè)到障礙物的點(diǎn)時(shí)，沿著最接近目標(biāo)輪廓上點(diǎn)的方向跟隨障礙物的輪廓，然后恢復(fù)直線向目標(biāo)移動(dòng)。

用Bug1算法時(shí)，機(jī)器人首先完全地圍繞障礙物，然后從距離目標(biāo)最短的點(diǎn)離開。當(dāng)然這種方法效率很低，但是可保證機(jī)器人會(huì)到達(dá)任何可達(dá)的目標(biāo)。Bug1算法操作的一個(gè)例子如圖1所示。

根據(jù)圖1中Bug1算法做出的路徑規(guī)劃，在最壞的情況下，其路徑長(zhǎng)度為障礙物輪廓的長(zhǎng)度中的1.5倍，而不是從開始到目標(biāo)的歐幾里德距離。這個(gè)距離遠(yuǎn)比從起始點(diǎn)到目標(biāo)點(diǎn)的歐幾里德距離長(zhǎng)很多。對(duì)于從開始到目標(biāo)在其路徑上檢測(cè)到的每個(gè)障礙物，算法從障礙物的邊界輪廓上找到一個(gè)起始點(diǎn)和一個(gè)離開點(diǎn)，因此不會(huì)多次檢測(cè)到障礙物，更不會(huì)在同一障礙物的邊界輪廓上走重復(fù)的路線。當(dāng)算法不止一次檢測(cè)到同一障礙物時(shí)，知道在障礙物內(nèi)捕獲了起點(diǎn)或目標(biāo)點(diǎn)，并且可以終止路徑搜索。因?yàn)闆]有可行的目標(biāo)路徑，也就是圖1中最右邊的情況，因此該算法可以有效地識(shí)別無法達(dá)到的目標(biāo)點(diǎn)。

2 ? ?Bug2算法

用Bug2算法時(shí)，機(jī)器人開始跟蹤物體的輪廓，但當(dāng)它能直接移動(dòng)至目標(biāo)時(shí)，就立即偏離障礙物的邊緣。這個(gè)改進(jìn)的算法，使機(jī)器人行走具有非常短的總路徑。Bug2算法總是嘗試在主線上移動(dòng)，該主線則為連接起始點(diǎn)和目標(biāo)點(diǎn)的直線，如圖2所示。

Bug2算法流程如下：

（1）遇到障礙物之前在主線上運(yùn)動(dòng)，直到到達(dá)目標(biāo)點(diǎn)時(shí)停止。

（2）如果檢測(cè)到障礙物，則沿著障礙物輪廓運(yùn)動(dòng)，直到到達(dá)主線。

從Bug1和Bug2算法的比較可以得到以下結(jié)論：Bug1是更徹底的搜索算法，因?yàn)闀?huì)評(píng)估所有的搜索算法在做出決定之前的可能性。Bug2是貪婪的算法，因?yàn)槠溥x擇了看起來很有希望的第一個(gè)選項(xiàng)。在大多數(shù)情況下，Bug2算法比Bug1更有效。但是，Bug1算法的操作更容易預(yù)測(cè)。

3 ? ?基于Bug0的路徑規(guī)劃算法

Bug0算法的基本流程：

（1）向目標(biāo)移動(dòng)，直到檢測(cè)到障礙物或達(dá)到目標(biāo)。

（2）如果檢測(cè)到障礙物，則向左（或向右，但始終在同一方向）左轉(zhuǎn)并跟隨障礙物的輪廓，直到再次朝向目標(biāo)的直線運(yùn)動(dòng)。Bug0路徑規(guī)劃算法結(jié)果如圖3所示。

Bug0算法成功找到左側(cè)環(huán)境中目標(biāo)的路徑，而右側(cè)環(huán)境中則不成功。通過對(duì)比可以看出以上3種Bug算法中，Bug0算法的路徑規(guī)劃其距離最短、效率最高。

4 ? ?仿真實(shí)驗(yàn)

用Bug0算法進(jìn)行移動(dòng)機(jī)器人進(jìn)行路徑規(guī)劃仿真實(shí)驗(yàn)，根據(jù)Bug0算法，如果移動(dòng)機(jī)器人距離障礙物足夠遠(yuǎn)（>0.2 m），機(jī)器人直接向目標(biāo)點(diǎn)運(yùn)動(dòng)。如果其靠近障礙物，則機(jī)器人沿著障礙物的邊界運(yùn)動(dòng)。在Matlab中對(duì)Bug0算法的進(jìn)行仿真實(shí)驗(yàn)驗(yàn)證，移動(dòng)機(jī)器人在10×10 m的有障礙環(huán)境中運(yùn)動(dòng)，將障礙物膨脹為圓型，起始點(diǎn)坐標(biāo)和目標(biāo)點(diǎn)坐標(biāo)分別設(shè)置為（0.5，0.5）和（9.5，9.5）。其獲得的機(jī)器人路徑如圖4所示。

通過實(shí)驗(yàn)結(jié)果可以看出，機(jī)器人可以準(zhǔn)確有效地到達(dá)目標(biāo)位置，能夠縮短機(jī)器人路徑冗余并提高機(jī)器人的運(yùn)動(dòng)效率。

[參考文獻(xiàn)]

[1]LUMELSKY V，STEPANOV P.Dynamic path planning for a mobile automaton with limited information on the environment[J].IEEE Transactions on Automatic Control，1986（11）：1058-1063.

[2]SANKARAN A A，VIDYASAGAR M.A new path planning algorithm for moving a point object amidst unknown obstacles in a plane[C].Honolulu：IEEE Conference on Robotics and Automation，1990.

[3]KAMON I，RIVLIN E.Sensory-based motion planning with global proofs[J].IEEE Transactions on Robotics and Automation，1997（6）：814-821.

[4]LAUBACH S，BURDICK J.An autonomous sensor-based path-planner for planetary microrovers[C].Detroit：IEEE Conference on Robotics and Automation，1999.

Research on mobile robot path planning based on Bug algorithm

Zhao Wenyu

（School of Electronic & Information Engineering， North China Institute of Science and Technology， Sanhe 065201， China）

Abstract：Bug algorithms are the simplest path planning algorithms that assume only local knowledge and do not need a map of the environment. Therefore， they are appropriate in situations where an environment map is unknown or it is changing rapidly and also when the mobile platform has very limited computational power. These algorithms use local information obtained from their sensors （e.g.， distance sensor） and global goal information. Their operation consists of two simple behaviors： motion in a straight line toward the goal and obstacle boundary following. This paper analyzes it.

Key words：path planning; Bug algorithm; robot