1 引言

　　移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人學(xué)的一個(gè)基本也是復(fù)雜的問(wèn)題，它被描述成： 給定一個(gè)移動(dòng)機(jī)器人所處的環(huán)境（環(huán)境可以通過(guò)移動(dòng)機(jī)器人視覺(jué)系統(tǒng)或者別的途徑獲得），一個(gè)起始點(diǎn)和一個(gè)期望的終止點(diǎn)，移動(dòng)機(jī)器人路徑規(guī)劃就是根據(jù)一定的任務(wù)要求尋求一條連接起始點(diǎn)到終止點(diǎn)且能避開(kāi)環(huán)境中障礙物的移動(dòng)機(jī)器人的運(yùn)動(dòng)軌跡，即或次優(yōu)有效路徑。

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

　　本文提出一種短切線路徑的規(guī)劃方法，其涉及的理論并不高深，計(jì)算簡(jiǎn)單，容易實(shí)現(xiàn)，可供側(cè)重于應(yīng)用的讀者參考。

　　2 短切線路徑算法

　　2.1 算法基本原理

　?。?）首先判斷機(jī)器人和給定的目標(biāo)位置之間是否存在障礙物。如圖1所示，以B代表目標(biāo)位置，其坐標(biāo)為（x Ｂ ，y Ｂ ），以R、A分別代表機(jī)器人及障礙物，坐標(biāo)為（x Ｒ ，y Ｒ ）、（x Ａ ，y Ａ ）。這里對(duì)碰撞半徑的選擇作出一點(diǎn)說(shuō)明，碰撞半徑越 小，發(fā)生碰撞的危險(xiǎn)度越大，但切線路徑越短；碰撞半徑越大，發(fā)生碰撞的危險(xiǎn)度越小，但同時(shí)切線路徑越長(zhǎng)。若機(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，稱為繞過(guò)障礙物A的中途點(diǎn)。由此可以得到繞過(guò)障礙物A并到達(dá)目標(biāo)點(diǎn)B的兩條切線路徑，路徑1：R→Ｃ1→Ｂ；路徑2：R→C2→B。比較兩條路徑的長(zhǎng)度，在圖1中，｜ＲＣ 1 ｜＋｜ＢＣ 1 ｜＜｜ＲＣ 2 ｜＋｜ＢＣ 2 ｜，可知，路徑1為短切線路徑。

　　2.2 多障礙物情況

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

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

　?。?）在切線路徑上存在障礙物?？砂牙@過(guò)多個(gè)障礙物到達(dá)終位置的任務(wù)分割成若干子任務(wù)，每個(gè)子任務(wù)要求繞過(guò)一個(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ì)算短切線路徑之和即為所求的路徑。圖3給出了機(jī)器人繞過(guò)兩個(gè)障礙物并到達(dá)目標(biāo)位置的行走路徑。



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

　?。?）搬運(yùn)機(jī)器人對(duì)于廠房車間的移動(dòng)搬運(yùn)機(jī)器人，切線路徑規(guī)劃方法是一種可行而且實(shí)用的方法。首先，機(jī)器人及障礙物的位置可以實(shí)時(shí)測(cè)得，且障礙物一般為固定不動(dòng)；然后，障礙物數(shù)量固定，形狀大小可預(yù)知；，搬運(yùn)的效率要求機(jī)器人的行走路徑為短，而且走直線比走曲線更能講究效率。

　?。?）足球機(jī)器人Mirosot足球機(jī)器人為兩輪驅(qū)動(dòng)機(jī)器人。機(jī)器人足球比賽中，雙方機(jī)器人以及球的坐標(biāo)由懸掛在球場(chǎng)上方的攝像頭識(shí)別并傳入計(jì)算機(jī)，比賽中，機(jī)器人要把球踢進(jìn)對(duì)方球門而得分。機(jī)器人首先要避開(kāi)其他機(jī)器人并捉到球，根據(jù)算法，把球的坐標(biāo)作為目標(biāo)位置，把其他阻擋其前進(jìn)路線的機(jī)器人作為障礙物，進(jìn)行實(shí)時(shí)路徑規(guī)劃。出于目的只是避碰，而不是完全不能碰撞，碰撞半徑可以盡量選小，剛好包住機(jī)器人便足夠，這樣做雖然碰撞危險(xiǎn)度上升，但切線路徑可以盡量縮短。

　　4 仿真結(jié)果

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

　　5 結(jié)論

　　移動(dòng)機(jī)器人路徑規(guī)劃的方法有很多，可以說(shuō)各有優(yōu)缺點(diǎn)，也沒(méi)有一種方法能夠適用于任何場(chǎng)合。一個(gè)好的算法，不在于其包含的理論的高深度，而在于其實(shí)用性；理論簡(jiǎn)單，計(jì)算快捷的算法更容易被接受，關(guān)鍵是要看實(shí)現(xiàn)的效果。本文介紹的切線路徑算法是一種幾何方法，沒(méi)有高深的理論，容易理解、便于實(shí)現(xiàn)，且計(jì)算簡(jiǎn)單，能夠提高運(yùn)行效率。不過(guò)，終運(yùn)行效果還得依賴于編程水平。