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

1引言

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

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

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

本文提出一種最短切線路徑的規(guī)劃方法，其涉及的理論并不高深，計(jì)算簡單，容易實(shí)現(xiàn)，可供側(cè)重于應(yīng)用的讀者參考。下面將詳細(xì)介紹該算法的基本原理，最后給出仿真實(shí)現(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ī)器人和障礙物的碰撞半徑，也就是說在其半徑以外無碰撞的危險(xiǎn)。這里對(duì)碰撞半徑的選擇作出一點(diǎn)說明，碰撞半徑越 小，發(fā)生碰撞的危險(xiǎn)度越大，但切線路徑越短；碰撞半徑越大，發(fā)生碰撞的危險(xiǎn)度越小，但同時(shí)切線路徑越長。要根據(jù)實(shí)際情況和控制要求來確定碰撞半徑。若機(jī)器人與目標(biāo)位置之間不存在障礙物，機(jī)器人可走直線直接到達(dá)目標(biāo)位置，此時(shí)的直線方程可由兩點(diǎn)式確定：

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

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

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

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

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

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

2.2多障礙物情況

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

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

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

3實(shí)際應(yīng)用

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

4仿真結(jié)果

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

5結(jié)論

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