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

1引言

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

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

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

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

2最短切線路徑算法

2.1算法基本原理

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

寫成ax+by+c=0的標(biāo)準(zhǔn)形式得：

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

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

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

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

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

2.2多障礙物情況

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

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

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

3實際應(yīng)用

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

4仿真結(jié)果

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

5結(jié)論

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