機(jī)器人最短路徑最小時(shí)間路徑分析

鄭 文

（重慶電子工程職業(yè)學(xué)院，重慶 401331）

0 引言

現(xiàn)有一個(gè)800×800的平面場(chǎng)景圖，在原點(diǎn)O(0,0)點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面場(chǎng)景范圍內(nèi)活動(dòng)。場(chǎng)景中有12個(gè)不同形狀的障礙物，機(jī)器人移動(dòng)時(shí)不能與之發(fā)生碰撞，障礙物的數(shù)學(xué)描述如表1所示。

表1 障礙物的形狀與位置

在平面場(chǎng)景圖中，障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)（要求目標(biāo)點(diǎn)與障礙物的距離至少超過(guò)10個(gè)單位）。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧是機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個(gè)或多個(gè)相切的圓弧路徑組成，但每個(gè)圓弧的半徑最小為10個(gè)單位。為了不與障礙物發(fā)生碰撞，同時(shí)要求機(jī)器人行走線路與障礙物間的最近距離為10個(gè)單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機(jī)器人無(wú)法完成行走。機(jī)器人直線行走的最大速度為 v0=5個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為其中r是轉(zhuǎn)彎半徑。如果超過(guò)該速度，機(jī)器人將發(fā)生側(cè)翻，無(wú)法完成行走。

通過(guò)建立數(shù)學(xué)模型來(lái)分析機(jī)器人在區(qū)域中從O ( 0 ,0)→ C (700,640)的避障最短路徑和從O ( 0 ,0)→ A (300,300) 的最短時(shí)間路徑。

1 問(wèn)題的分析

1.1 機(jī)器人移動(dòng)時(shí)的避障策略

圖1 機(jī)器人的避障策略圖

機(jī)器人在可行域內(nèi)由起始點(diǎn)T ( 一個(gè)子目標(biāo))繞過(guò)障礙物W駛向目標(biāo)點(diǎn)Q( 下一個(gè)子目標(biāo)) 的過(guò)程中；要使經(jīng)過(guò)的路徑最短，在經(jīng)過(guò)障礙物區(qū)域時(shí)應(yīng)盡量貼近該障礙物, 繞過(guò)障礙物后，若目標(biāo)在機(jī)器人的視覺(jué)范圍內(nèi)，應(yīng)以直線移動(dòng)的方式駛向目標(biāo)點(diǎn) Q[1]；如圖1所示。

由于機(jī)器人不能折線轉(zhuǎn)彎，所以轉(zhuǎn)彎路徑應(yīng)由與直線路徑相切的一段圓弧組成，由起點(diǎn)T經(jīng)障礙物W到目標(biāo)點(diǎn)Q的最短路徑是：兩直線段與圓弧長(zhǎng)之和，即

1.2 機(jī)器人從起點(diǎn)ST到終點(diǎn)SQ的 可行路徑

機(jī)器人從起點(diǎn)到終點(diǎn)的可行路徑就是在可行域內(nèi)（與障礙物至少保持10個(gè)單位的區(qū)域），尋找從起點(diǎn)ST 到終點(diǎn)SQ的安全避障路徑所經(jīng)過(guò)的一系列點(diǎn)的集合。

在障礙物數(shù)量有限的情況下，從起點(diǎn)到終點(diǎn)尋找一條可行路徑的算法[2]如下：

步驟1 機(jī)器人由起始點(diǎn)ST 駛向終點(diǎn)SQ的過(guò)程中, vi和V分別表示第i個(gè)避碰點(diǎn)和避碰點(diǎn)的集合,初始條件

步驟2 機(jī)器人移動(dòng)方向正對(duì)著終點(diǎn)SQ, 如果終點(diǎn)SQ在機(jī)器人的視覺(jué)范圍內(nèi) , 執(zhí)行步驟5, 否則執(zhí)行步驟3；

步驟3 機(jī)器人搜索障礙物的周圍區(qū)域, 并根據(jù)視覺(jué)信息決定避碰點(diǎn) vi+1；

步驟4 機(jī)器人移動(dòng)至 vi+1, 避碰點(diǎn) vi添加到集合V中, i = i+1, 然后執(zhí)行步驟2；

步驟5 機(jī)器人向終點(diǎn)SQ 移動(dòng), 當(dāng)機(jī)器人到達(dá)終點(diǎn)SQ時(shí), 就得到了一條從起點(diǎn)到終點(diǎn)的可行路。

以此規(guī)則來(lái)確定機(jī)器人在可行域中的行進(jìn)路線。

按此算法，結(jié)合避障策略，作出機(jī)器人在可行域內(nèi)從 CO→ 的行進(jìn)路徑，在避碰點(diǎn)處，機(jī)器人與障礙物相距10個(gè)單位,如圖2所示。

圖2 機(jī)器人從 CO→ 的可行進(jìn)路徑

2 機(jī)器人從 O (0 ,0)出發(fā)， O → C 的最短路徑

從圖2可看出，從 CO→ 的可行路徑構(gòu)成了一個(gè)賦權(quán)網(wǎng)絡(luò)圖N．頂點(diǎn)集合：

為了表示的方便，圖中的頂點(diǎn)用相應(yīng)的數(shù)字表示。

應(yīng)用求切點(diǎn)坐標(biāo)的方法，求出V中各點(diǎn)坐標(biāo)、圓弧圓心坐標(biāo)、直線段及圓弧長(zhǎng)．?dāng)?shù)據(jù)如表2所示。

表2 數(shù)據(jù)信息表

從O到C的最短路徑問(wèn)題就轉(zhuǎn)化為在網(wǎng)絡(luò)圖N中找一條從O到C的最短路，以D表示從O到C的所有路徑之集， )(Pd 表示路徑P的長(zhǎng)度，則得數(shù)學(xué)模型：

求解算法[4]如下：

設(shè)W為圖N的帶權(quán)鄰接矩陣， ()lv表示從頂點(diǎn) 0u到v的一條路的權(quán)， ()zv表示v的父節(jié)點(diǎn)，用以確定最短路的路線。

根據(jù)上述算法求出的 ()lv就是0u到v的最短路的權(quán)，從v的父節(jié)點(diǎn)標(biāo)記 ()zv追溯到0u，就得到0u到v的最短路的路線．用matlab語(yǔ)言編程可求得：

機(jī)器人從O移動(dòng)到C的最短距離為：

3 機(jī)器人從 O ( 0,0)出發(fā)， O → A 的最短時(shí)間路徑

3.1 從起點(diǎn)ST 到終點(diǎn)SQ最短時(shí)間路徑分析

在圓弧上機(jī)器人的移動(dòng)速度v與圓弧半徑r有如下關(guān)系：

其中v0是直線段上的移動(dòng)速度。由于，所以移動(dòng)速度v是圓弧半徑r的增函數(shù)；因圓弧長(zhǎng)L= r θ，所以在圓弧上，移動(dòng)速度隨圓弧長(zhǎng)的增大而增大；因此機(jī)器人從起點(diǎn)到終點(diǎn)的最短路徑并非最短時(shí)間路徑。下面建立最短時(shí)間路徑模型。

圖3 機(jī)器人從避障物i經(jīng)過(guò)避障物j的行進(jìn)路線

由于切點(diǎn)、圓弧長(zhǎng)與半徑r有關(guān)，所以aij、Lij、v都是半徑r的函數(shù)，從而Tij是半徑r的函數(shù)．

我們引入0-1變量來(lái)選取從起點(diǎn)ST到終點(diǎn)SQ 的路徑經(jīng)過(guò)的轉(zhuǎn)彎點(diǎn)，令

則從起點(diǎn)到終點(diǎn)路徑的時(shí)間為

所以從起點(diǎn)ST 到終點(diǎn)SQ的最短時(shí)間路徑模型可表示如下

由于障礙物所處的位置不同，對(duì)切點(diǎn)的限制條件也就不一樣，所以對(duì)每個(gè)避障點(diǎn)的限制條件應(yīng)具體問(wèn)題具體分析。

3.2 機(jī)器人從 O ( 0,0)出發(fā)， O → A 的最短時(shí)間路徑分析

從圖4可看出，從 O → A 有兩條可行路徑 P1、P2可走,因此最短時(shí)間目標(biāo)函數(shù)為：

圖4 機(jī)器人從 AO→ 的最短時(shí)間路徑分析圖

先分析在 P1段上的最短時(shí)間路徑，如圖4所示，設(shè)圓心坐標(biāo)為 ( x0,y0)，半徑為r，是圓弧上連接點(diǎn) O ( 0,0)和 A ( 300,300)的兩個(gè)切點(diǎn)． P1是機(jī)器人從O移到A的一條可行路，頂點(diǎn)集合 V = { O ,v1,v2,A}．從O到A的移動(dòng)時(shí)間是兩直線段上的移動(dòng)時(shí)間與圓弧上的移動(dòng)時(shí)間之和

約束條件:障礙物5左上角的頂點(diǎn)與圓弧的距離大于等于10、兩直線段與園相切、切點(diǎn) v1、 v2的選擇。

于是，可行路徑 P1的優(yōu)化模型如下:

下面我們采用搜索的方法，借助計(jì)算機(jī)來(lái)求解模型。

根據(jù)避障策略，機(jī)器人在經(jīng)過(guò)障礙物區(qū)域時(shí)應(yīng)盡量貼近該障礙物,在圓弧的半徑發(fā)生改變時(shí)，我們始終保證圓弧距障礙物的最近距離是10個(gè)單位．因此圓心只能在CD上，且由C向D移動(dòng)，如圖4畫出的幾個(gè)圓。

下面以C(80,210)為障礙物點(diǎn)，找機(jī)器人在路徑 P1上移動(dòng)的最短時(shí)間，搜索算法如下：

步驟1：用matlab命令solve求出切點(diǎn) v1、 v2的一般性坐標(biāo)。令初值r=10，增量Δr=0.1。

步驟2：當(dāng)r＞220時(shí)，轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟3。

步驟3：1）計(jì)算下一個(gè)園的圓心坐標(biāo)：

2）判斷并計(jì)算切點(diǎn)1v、2v的具體坐標(biāo)，計(jì)算圓心角θ。

3）計(jì)算直線段1d 、2d及弧長(zhǎng)θrL=，圓弧上的移動(dòng)速度v。

4）計(jì)算時(shí)間。

5）記錄切點(diǎn) v1、 v2的坐標(biāo)、圓心坐標(biāo)、半徑、時(shí)間。

步驟4：回到步驟2。

用matlab編程求解，運(yùn)行程序得：

最短時(shí)間T1=94.2283秒；

最短時(shí)間路徑：

圓心坐標(biāo)(80.28,209.72)，圓弧半徑r=12.4，圓弧上的速度 v = 4.995。

與求在可行路徑 P1上的最短時(shí)間一樣，可求得在可行路徑 P2上的最短時(shí)間是T2=96.5632秒。

所以從 O → A 的最短時(shí)間T = min{T1,T2}=94.2283秒，最短時(shí)間路徑如上所述。

4 結(jié)束語(yǔ)

由于機(jī)器人在圓弧上的移動(dòng)速度隨圓弧半徑的增大而增大，所以機(jī)器人從起點(diǎn)到終點(diǎn)的最短路徑并非最短時(shí)間路徑；從 O → A 可看出，移動(dòng)距離是半徑的增函數(shù)；當(dāng)r＜r0=12.4時(shí)移動(dòng)時(shí)間是半徑的減函數(shù)，當(dāng)r＞r0=12.4時(shí)移動(dòng)時(shí)間是半徑的增函數(shù)，r0=12.4是移動(dòng)時(shí)間的極小值點(diǎn)；所以在從起點(diǎn)到終點(diǎn)路徑的選擇上，應(yīng)在距離和時(shí)間上作權(quán)衡，做出決策。

[1] 金秀慧,伊連云.基于通用運(yùn)動(dòng)學(xué)模型的移動(dòng)機(jī)器人避障路徑規(guī)劃[J].機(jī)械工程師,2005,12.

[2] 羅熊,樊曉平.具有大量不規(guī)則障礙物的環(huán)境下機(jī)器人路徑規(guī)劃的一種新型遺傳算法X,機(jī)器人ROBOT,2004.

[3] 席志紅,原新.基于視覺(jué)的移動(dòng)機(jī)器人實(shí)時(shí)避障和導(dǎo)航哈爾濱工程[J],大學(xué)學(xué)報(bào),2002.

[4] 趙靜,但琦.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M].高等教育出版社 2010.

[5] 任善強(qiáng).數(shù)學(xué)模型(第二版)[M].重慶大學(xué)出版社,1993.

[6] 王學(xué)輝.Matlab 6.1[M].中國(guó)水利水電出版社.2002.