基于Bug算法的移動機器人路徑規劃研究

趙文瑜

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

關鍵詞：路徑規劃;Bug算法;機器人

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

1 ? ?Bug1算法

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

（1）沿直線向目標移動，直到遇見障礙物或達到目標。

（2）如果檢測到障礙物，則向左轉并沿著障礙物的整個邊界運動并測量到目標的歐幾里德距離。當再次到達最初檢測到障礙物的點時，沿著最接近目標輪廓上點的方向跟隨障礙物的輪廓，然后恢復直線向目標移動。

用Bug1算法時，機器人首先完全地圍繞障礙物，然后從距離目標最短的點離開。當然這種方法效率很低，但是可保證機器人會到達任何可達的目標。Bug1算法操作的一個例子如圖1所示。

根據圖1中Bug1算法做出的路徑規劃，在最壞的情況下，其路徑長度為障礙物輪廓的長度中的1.5倍，而不是從開始到目標的歐幾里德距離。這個距離遠比從起始點到目標點的歐幾里德距離長很多。對于從開始到目標在其路徑上檢測到的每個障礙物，算法從障礙物的邊界輪廓上找到一個起始點和一個離開點，因此不會多次檢測到障礙物，更不會在同一障礙物的邊界輪廓上走重復的路線。當算法不止一次檢測到同一障礙物時，知道在障礙物內捕獲了起點或目標點，并且可以終止路徑搜索。因為沒有可行的目標路徑，也就是圖1中最右邊的情況，因此該算法可以有效地識別無法達到的目標點。

2 ? ?Bug2算法

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

Bug2算法流程如下：

（1）遇到障礙物之前在主線上運動，直到到達目標點時停止。

（2）如果檢測到障礙物，則沿著障礙物輪廓運動，直到到達主線。

從Bug1和Bug2算法的比較可以得到以下結論：Bug1是更徹底的搜索算法，因為會評估所有的搜索算法在做出決定之前的可能性。Bug2是貪婪的算法，因為其選擇了看起來很有希望的第一個選項。在大多數情況下，Bug2算法比Bug1更有效。但是，Bug1算法的操作更容易預測。

3 ? ?基于Bug0的路徑規劃算法

Bug0算法的基本流程：

（1）向目標移動，直到檢測到障礙物或達到目標。

（2）如果檢測到障礙物，則向左（或向右，但始終在同一方向）左轉并跟隨障礙物的輪廓，直到再次朝向目標的直線運動。Bug0路徑規劃算法結果如圖3所示。

Bug0算法成功找到左側環境中目標的路徑，而右側環境中則不成功。通過對比可以看出以上3種Bug算法中，Bug0算法的路徑規劃其距離最短、效率最高。

4 ? ?仿真實驗

用Bug0算法進行移動機器人進行路徑規劃仿真實驗，根據Bug0算法，如果移動機器人距離障礙物足夠遠（>0.2 m），機器人直接向目標點運動。如果其靠近障礙物，則機器人沿著障礙物的邊界運動。在Matlab中對Bug0算法的進行仿真實驗驗證，移動機器人在10×10 m的有障礙環境中運動，將障礙物膨脹為圓型，起始點坐標和目標點坐標分別設置為（0.5，0.5）和（9.5，9.5）。其獲得的機器人路徑如圖4所示。

通過實驗結果可以看出，機器人可以準確有效地到達目標位置，能夠縮短機器人路徑冗余并提高機器人的運動效率。

[參考文獻]

[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