機器人最短路徑最小時間路徑分析

鄭 文

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

0 引言

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

表1 障礙物的形狀與位置

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

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

1 問題的分析

1.1 機器人移動時的避障策略

圖1 機器人的避障策略圖

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

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

1.2 機器人從起點ST到終點SQ的 可行路徑

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

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

步驟1 機器人由起始點ST 駛向終點SQ的過程中, vi和V分別表示第i個避碰點和避碰點的集合,初始條件

步驟2 機器人移動方向正對著終點SQ, 如果終點SQ在機器人的視覺范圍內(nèi) , 執(zhí)行步驟5, 否則執(zhí)行步驟3；

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

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

步驟5 機器人向終點SQ 移動, 當機器人到達終點SQ時, 就得到了一條從起點到終點的可行路。

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

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

圖2 機器人從 CO→ 的可行進路徑

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

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

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

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

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

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

求解算法[4]如下：

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

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

機器人從O移動到C的最短距離為：

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

3.1 從起點ST 到終點SQ最短時間路徑分析

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

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

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

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

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

則從起點到終點路徑的時間為

所以從起點ST 到終點SQ的最短時間路徑模型可表示如下

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

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

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

圖4 機器人從 AO→ 的最短時間路徑分析圖

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

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

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

下面我們采用搜索的方法，借助計算機來求解模型。

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

下面以C(80,210)為障礙物點，找機器人在路徑 P1上移動的最短時間，搜索算法如下：

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

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

步驟3：1）計算下一個園的圓心坐標：

2）判斷并計算切點1v、2v的具體坐標，計算圓心角θ。

3）計算直線段1d 、2d及弧長θrL=，圓弧上的移動速度v。

4）計算時間。

5）記錄切點 v1、 v2的坐標、圓心坐標、半徑、時間。

步驟4：回到步驟2。

用matlab編程求解，運行程序得：

最短時間T1=94.2283秒；

最短時間路徑：

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

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

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

4 結(jié)束語

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

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

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

[3] 席志紅,原新.基于視覺的移動機器人實時避障和導航哈爾濱工程[J],大學學報,2002.

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

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

[6] 王學輝.Matlab 6.1[M].中國水利水電出版社.2002.