一種移動機器人的路徑規(guī)劃算法

1引言

移動機器人路徑規(guī)劃問題是指在有障礙物的工作環(huán)境中尋找一條恰當?shù)膹慕o定起點到終點的運動路徑，使機器人在運動過程中能安全、無碰撞地繞過所有的障礙物 ［1］ 。

障礙環(huán)境中機器人的無碰撞路徑規(guī)劃 ［2］ 是智能機器人研究的重要課題之一，由于在障礙空間中機器人運動規(guī)劃的高度復雜性使得這一問題至今未能很好地解決。路徑規(guī)劃問題根據(jù)機器人的工作環(huán)境模型可以分為兩種，一種是基于模型的路徑規(guī)劃，作業(yè)環(huán)境的全部信息都是預知的；另一種是基于傳感器的路徑規(guī)劃，作業(yè)環(huán)境的信息是全部未知或部分未知的。

對機器人路徑規(guī)劃的研究，世界各國的專家學者們提出了許多不同的路徑規(guī)劃方法，主要可分為全局路徑和局部路徑規(guī)劃方法。全局路徑規(guī)劃方法有位形空間法、廣義錐方法、頂點圖像法、柵格劃歸法；局部路徑規(guī)劃方法主要有人工勢場法。這些方法都各有優(yōu)缺點 ［3］ ，也沒有一種方法能夠適用于任何場合。

本文提出一種最短切線路徑的規(guī)劃方法，其涉及的理論并不高深，計算簡單，容易實現(xiàn)，可供側(cè)重于應用的讀者參考。下面將詳細介紹該算法的基本原理，最后給出仿真實現(xiàn)的結果。

2最短切線路徑算法

2.1算法基本原理

(1)首先判斷機器人和給定的目標位置之間是否存在障礙物。如圖1所示，以B代表目標位置，其坐標為(x Ｂ ，y Ｂ ），以R、A分別代表機器人及障礙物，坐標為(x Ｒ ，y Ｒ )、(x Ａ ，y Ａ )。Ｒr和Ra表示機器人和障礙物的碰撞半徑，也就是說在其半徑以外無碰撞的危險。這里對碰撞半徑的選擇作出一點說明，碰撞半徑越 小，發(fā)生碰撞的危險度越大，但切線路徑越短；碰撞半徑越大，發(fā)生碰撞的危險度越小，但同時切線路徑越長。要根據(jù)實際情況和控制要求來確定碰撞半徑。若機器人與目標位置之間不存在障礙物，機器人可走直線直接到達目標位置，此時的直線方程可由兩點式確定：

寫成ax+by+c=0的標準形式得：

若d＞Ra+Rr，則機器人可沿直線到達目標點而不碰物體A，此時物體A不是障礙物。 若d＜Ra+Rr，機器人走直線可能碰上物體A，此時物體A應被視為障礙物。

(2)求切線路徑。如圖1所示，以A點為圓心，Ra+Rr為半徑作碰撞圓，其方程為：

k 1 ,k 2 為待求斜率，聯(lián)立方程組：

可分別求得兩切線的斜率k 1 ，k 2 ，顯然k 1 ，k 2 各有兩個值，分別對應兩條切線方程。兩組切線兩兩相交，由方程組

求得兩個交點Ｃ1、Ｃ2，稱為繞過障礙物A的中途點。由此可以得到繞過障礙物A并到達目標點B的兩條切線路徑，路徑1：R→Ｃ1→Ｂ；路徑2：R→C2→B。比較兩條路徑的長度，在圖1中，｜ＲＣ 1 ｜＋｜ＢＣ 1 ｜＜｜ＲＣ 2 ｜＋｜ＢＣ 2 ｜，可知，路徑1為最短切線路徑。

2.2多障礙物情況

對于存在多個障礙物的情形，可分成幾種情況來考慮。

(1)障礙物位于前一障礙物的中途點。也就是說，機器人要到達的中途點位于另一個障礙物的碰撞圓內(nèi)，如果機器人到達中途點就有可能碰上該障礙物，此時可以用該障礙物的坐標代替原障礙物的坐標來求這一側(cè)的中途點。對于另外一側(cè)的中途點，如果也有障礙物，同樣處理；若沒有，則中途點不變。然后，仍然計算并比較兩條路徑的長度，選擇最短的切線路徑。如圖2所示，圖中虛線表示原來的路徑1，由于中途點被障礙物Ａ2阻擋，路徑1上移。此時，｜ＲＣ 1 ｜＋｜ＢＣ 1 ｜＞｜ＲＣ 2 ｜＋｜ＢＣ 2 ｜，最短切線路徑應為路徑2。

(2)在切線路徑上存在障礙物?？砂牙@過多個障礙物到達最終位置的任務分割成若干子任務，每個子任務要求繞過一個障礙物。這樣，一個子任務就相當于前面只有一個障礙物的情況。以Ｂi、Ci分別表示第i個子任務的目標點和中途點，執(zhí)行第i個子任務時，如果在到達Bi的路徑上存在障礙物，則增加第i +1個子任務，此時目標點Bi+1就是Bi；如果在到達Ci的路徑上存在障礙物，則增加第i+1個子任務，此時目標點Bi+1是Ci。以此類推，尋找切線路徑直至到達給定的最終目標位置，計算最短切線路徑之和即為所求的最優(yōu)路徑。圖3給出了機器人繞過兩個障礙物并到達目標位置的行走路徑。

3實際應用

(1)搬運機器人對于廠房車間的移動搬運機器人，切線路徑規(guī)劃方法是一種可行而且實用的方法。首先，機器人及障礙物的位置可以實時測得，且障礙物一般為固定不動；其次，障礙物數(shù)量固定，形狀大小可預知；再次，搬運的效率要求機器人的行走路徑為最短，而且走直線比走曲線更能講究效率。
(2)足球機器人Mirosot足球機器人為兩輪驅(qū)動機器人。機器人足球比賽中，雙方機器人以及球的坐標由懸掛在球場上方的攝像頭識別并傳入計算機，比賽過程中，機器人要把球踢進對方球門而得分。機器人首先要避開其他機器人并捉到球，根據(jù)算法，把球的坐標作為目標位置，把其他阻擋其前進路線的機器人作為障礙物，進行實時路徑規(guī)劃。出于目的只是避碰，而不是完全不能碰撞(事實上比賽中碰撞是難免的)，碰撞半徑可以盡量選小，剛好包住機器人便足夠，這樣做雖然碰撞危險度上升，但切線路徑可以盡量縮短。

4仿真結果

圖4是運用該算法在Simurosot 5對5機器人足球仿真比賽平臺上進行策略編程并運行得到的仿真結果。需要說明的是，為了觀察的方便，例子中，球和障礙物設為固定不動。但這并非說這算法不能應用于運動比賽中，算法中各坐標是實時測得的，路徑是實時計算的，得到的結果應該是實時有效的。然而基于比賽過程中運動變化快速，實際效果需經(jīng)長期試驗觀察才能看出，而且效果的好壞不但取決于算法的先進與否，在很大程度上還依賴于編程者軟件水平的高低。

5結論

移動機器人路徑規(guī)劃的方法有很多，可以說各有優(yōu)缺點，也沒有一種方法能夠適用于任何場合。這樣的結果是，各種新的算法不斷涌現(xiàn)，一方面豐富了解決問題的手段，不同的情況總能找到合適的算法；另一方面也不斷吸收新的理論，促進了課題不斷向前發(fā)展。值得提出的是，一些新的算法不管實用與否，為了趕潮流，將一些剛剛研究出來的理論成果拿來就用，這些理論要么過于復雜，要么本身并未成熟，結果得到的算法冗長難懂，不切實際，無法實現(xiàn)。還有一些算法為了讓機器人走出一條平滑完美的曲線而犧牲了速度和時間，這些都是不可取的。應該說，一個好的算法，不在于其包含的理論的高深度，而在于其實用性；相反，理論簡單，計算快捷的算法更容易被接受，關鍵是要看最后實現(xiàn)的效果。本文介紹的切線路徑算法是一種幾何方法，并沒有高深的理論，容易理解，便于實現(xiàn)，而且計算簡單，能夠提高運行效率。不過，最終運行效果還得依賴于編程水平。