一種移動(dòng)機器人的路徑規劃算法

1引言

移動(dòng)機器人路徑規劃問(wèn)題是指在有障礙物的工作環(huán)境中尋找一條恰當的從給定起點(diǎn)到終點(diǎn)的運動(dòng)路徑，使機器人在運動(dòng)過(guò)程中能安全、無(wú)碰撞地繞過(guò)所有的障礙物 ［1］ 。

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

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

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

2最短切線(xiàn)路徑算法

2.1算法基本原理

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

寫(xiě)成ax+by+c=0的標準形式得：

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

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

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

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

求得兩個(gè)交點(diǎn)Ｃ1、Ｃ2，稱(chēng)為繞過(guò)障礙物A的中途點(diǎn)。由此可以得到繞過(guò)障礙物A并到達目標點(diǎn)B的兩條切線(xiàn)路徑，路徑1：R→Ｃ1→Ｂ；路徑2：R→C2→B。比較兩條路徑的長(cháng)度，在圖1中，｜ＲＣ 1 ｜＋｜ＢＣ 1 ｜＜｜ＲＣ 2 ｜＋｜ＢＣ 2 ｜，可知，路徑1為最短切線(xiàn)路徑。

2.2多障礙物情況

對于存在多個(gè)障礙物的情形，可分成幾種情況來(lái)考慮。

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

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

3實(shí)際應用

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

4仿真結果

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

5結論

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