周 瑋， 王 棟

(濟南工程職業(yè)技術(shù)學(xué)院基礎(chǔ)部，山東濟南250200)

1 引 言

隨著科學(xué)技術(shù)的進步和計算機技術(shù)的發(fā)展，機器人的應(yīng)用越來越廣泛，在機器人的應(yīng)用中如何使機器人在其工作范圍內(nèi)為完成一項特定的任務(wù)尋找一條安全高效的行走路徑，是人工智能領(lǐng)域的一個重要問題.本文主要針對在一個場景中的各種靜態(tài)障礙物，研究機器人繞過障礙物到達指定目的地的最短路徑問題和最短時間問題.

本文以2012年“高教社”杯全國大學(xué)生數(shù)學(xué)建模競賽D題“機器人避障問題”為例進行研究.假設(shè)機器人的工作范圍為800×800的平面正方形區(qū)域，其中有12個不同形狀的靜態(tài)障礙物(具體幾何信息可參見[1])，場景圖中有4個目標(biāo)點O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，在原點處有一機器人，下面我們將研究機器人從O(0, 0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑，以及機器人從O(0, 0)出發(fā)，到達A的最短時間路徑問題.

2 靜態(tài)避障問題中機器人行走最短路徑的分析

2.1 行走路徑的設(shè)計

圖1 障礙物包絡(luò)圖

在本例中障礙物有4種不同形狀：矩形、平行四邊形、三角形和圓形.考慮到機器人本身的形狀和大小，為研究方便起見，將機器人視為一個點.機器人與障礙物之間的距離至少為10個單位，因此可以先用包絡(luò)線畫出機器人行走的危險區(qū)域(如圖1)，包絡(luò)線內(nèi)是機器人的禁入?yún)^(qū).

圖2 圖3

根據(jù)以上分析，可以確定機器人的行走路徑應(yīng)為線圓結(jié)構(gòu). 那么是否是轉(zhuǎn)彎半徑越小，行走路徑就越短呢？為此需要求在已知兩個固定點和圓弧圓心坐標(biāo)的情況下，圓弧半徑r為何值，才能使機器人的行走路徑最短.

L=AC+BD+rω

可以證明，L′>0，函數(shù)L為單調(diào)遞增函數(shù)，因此當(dāng)圓弧半徑r逐漸增加時，機器人的行走路徑會增大.根據(jù)以上分析，對于靜態(tài)障礙物機器人的行走路徑應(yīng)遵循以下三個原則.

原則一：機器人的行走路徑為線圓結(jié)構(gòu)，由兩條切線和一段圓弧組成；

原則二：每個路口至多發(fā)生一次轉(zhuǎn)彎，并以障礙物頂點為轉(zhuǎn)彎圓弧的中心；

原則三：機器人轉(zhuǎn)彎圓弧半徑為最小允許半徑10個單位.

2.2 最短路徑的選擇

從起點到達目標(biāo)點有多條路徑，根據(jù)Dijkstra算法可以找出從起點到達每一個目標(biāo)點的最短路徑.本文采用帶權(quán)的有向圖表示機器人的行走路徑，途中節(jié)點為障礙物的角點，邊表示障礙物之間的聯(lián)系，權(quán)表示線路的長度(節(jié)點之間的直線距離).從頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑就是所求最短路徑，Dijkstra算法就是按路徑的長度遞增次序產(chǎn)生最短路徑的算法[3].

圖4

下面以O(shè)→B為例，確定O→B的最短路徑.如圖4所示，根據(jù)障礙物的形狀和位置，本文給出了機器人從O(0,0)出發(fā)避過障礙物到達目標(biāo)B點的4條較優(yōu)路徑.運用Dijkstra算法算出O→B的最短路徑為O→B3→B5→B6→B7→B8→B.

O→B最短路算法如下：

1.起點O記為B0,終點B記為Bn；

2.從網(wǎng)絡(luò)的終點Bn開始，令它的標(biāo)號λn為零；

3.計算結(jié)點Bi的標(biāo)號λi，設(shè)結(jié)點Bj已標(biāo)號，

結(jié)點Bi指向Bj，則Bi的標(biāo)號可按算式：

求出，其中λi是Bi的標(biāo)號，li,j是結(jié)點Bi與Bj之間的直線距離；

4.重復(fù)上述計算，直到求得起點B0的標(biāo)號λ0為止，此標(biāo)號λ0即為最短路的長度；

5.確定最短路徑，從起點開始，順網(wǎng)絡(luò)的箭線前進，若有幾條箭線，則選取箭線所指標(biāo)號最小且滿足條件λj=λk+lj,k,k≥j+1的結(jié)點為最短路徑所經(jīng)過的結(jié)點.

應(yīng)用上述算法可得到從O點出發(fā)，分別到達各目標(biāo)點的最短路徑.

3 最短路徑長度的計算模型

機器人的行走路徑由直線段和圓弧組成，只要知道直線段的起點和終點坐標(biāo)，即切點坐標(biāo)，就能計算出每段直線段的長度，再計算出各段弧長，即可得到每條路徑的總長度.

3.1 切點坐標(biāo)的計算模型

根據(jù)前面制定的行走路徑原則，起點到目標(biāo)點無論中間障礙物有多少，最短路徑都是由若干個線圓結(jié)構(gòu)所組成，圓弧中心為障礙物的頂點，半徑為機器人轉(zhuǎn)彎最小半徑10個單位.觀察這四條路徑，發(fā)現(xiàn)所有線圓結(jié)構(gòu)的切線都可以歸結(jié)為兩種類型，一種是兩圓圓心連線與公切線相交(內(nèi)公切線)，另一種是兩圓圓心連線與公切線平行(外公切線).

圖5 圖6

3.1.1 第一種類型(內(nèi)公切線)的切點

兩圓圓心連線與公切線相交，則圓心連線的中點在切線上，可由兩圓圓心坐標(biāo)確定中點坐標(biāo)，則問題轉(zhuǎn)化為求圓弧外的點與障礙物的轉(zhuǎn)彎圓弧形成的切線的切點(如圖5的C點).設(shè)切點C(x,y),起點O(x1,y1),圓心M(x2,y2)，求切點C的坐標(biāo).

在Rt△OCM中OC2=OM2-CM2，又因為切點C在圓M上，故C點坐標(biāo)滿足以下方程，聯(lián)立方程組

運用MATLAB解方程[4]，求出切點C(x,y)的坐標(biāo).類似地，要求D點坐標(biāo)，只需求出DE中點的坐標(biāo)，就可以利用上述模型計算出來.

3.1.2 第二種類型(外公切線)的切點

第二種類型的切點是兩圓圓心連線與公切線平行(外公切線)的切點，如果能找到圓弧外一點的坐標(biāo)，就可以利用第一種類型切點的模型計算[5].

兩圓連線OO′與公切線DE平行(如圖6)，切點為D.已知圓心O(x1,y1),圓心O′(x2,y2)，半徑為r=10,求切點D的坐標(biāo).解法如下：

在兩圓心連線上找出中點G(x3,y3)，過G作DE的垂線，交DE于Hx,y點.

根據(jù)中點坐標(biāo)公式可得G點坐標(biāo)

由于OD⊥DE,O′E⊥DE,故ODEO′為矩形,H為DE的中點，且GH=r，根據(jù)勾股定理，

由兩點間距離公式，

因此，對于Hx,y點的坐標(biāo)，有

利用MATLAB解方程,求出H點的坐標(biāo)，就可以利用類型一求切點的方法，確定切點D和E的坐標(biāo).

3.2 弧長的計算模型

3.2.1 單個目標(biāo)點的最短路徑的弧長

機器人從O點出發(fā)，到達一個目標(biāo)的的路徑為單個目標(biāo)的的路徑，比如求O→A、O→B、和O→C的最短路徑.觀察機器人行走的所有路徑中的圓弧，發(fā)現(xiàn)所有圓弧都可歸結(jié)為以下三種類型：

圖7 線圓結(jié)構(gòu)1 圖8 線圓結(jié)構(gòu)2 圖9 線圓結(jié)構(gòu)3

設(shè)O(x1,y1)為起點，A(x2,y2)為目標(biāo)點，C和D分別為直線與轉(zhuǎn)彎圓弧的切點，障礙物的頂點M(x3,y3)(即轉(zhuǎn)彎圓弧的圓心)，圓的半徑為r，OA的長度為a，OM的長度為b，AM的長度為c，

∠OMA=φ, ∠OMC=α, ∠AMD=β, ∠CMD=θ,

對于這種線圓結(jié)構(gòu)，需要做簡單的變換，利用中點公式，確定切線的中點坐標(biāo)，將類型二轉(zhuǎn)換為類型一，才能求出A→B的路徑中圓弧的長度.

假設(shè)兩圓心坐標(biāo)分別為O(x1,y1)和O′(x2,y2),M點為兩圓心連線和兩圓內(nèi)公切線的交點，這樣就可以利用類型一中的方法，分兩段求解.同理如果有更多類似的轉(zhuǎn)彎，同樣可以按照此種方法分解.

已知起點、目標(biāo)點、障礙物頂點坐標(biāo)，可以用與類型一同樣的方法計算出弧長.

3.2.2 多個目標(biāo)點的最短路徑

圖10

機器人從起點出發(fā)，依次經(jīng)過指定的中間目標(biāo)點最后到達終點，是多個目標(biāo)點的最短路徑問題,比如O→A→B→C→O的最短路徑的計算.由于機器人的行走路線為線圓結(jié)構(gòu)，不能折線轉(zhuǎn)彎，因此中間目標(biāo)點應(yīng)位于某個半徑為r的圓周上. 這里我們?nèi)园凑兆钚≡试S半徑為10個單位，則只需計算出過A,B,C三點的圓心位置即可，這樣就將多目標(biāo)點的最短路徑問題轉(zhuǎn)化成了單目標(biāo)點的最短路徑問題.求過A,B,C三點的圓心位置的問題可通過建立非線性規(guī)劃模型求得.

(i) 過A點圓弧的圓心如圖10，障礙物頂點O180,210,

建立非線性規(guī)劃模型

圖11

(ii)過B點圓弧的圓心如圖11，障礙物頂點O1150,600,頂點O2270,680,B100,700,r=10，過B的圓弧圓心Om,n，最短路徑為LB,則

LB=OO1+rθ+OO2.

建立非線性規(guī)劃模型

圖12

(iii)過C點圓弧的圓心(如圖12)，障礙物頂點O1670,730,頂點O2720,600,C700,640,r=10，過C的圓弧圓心Om,n，圓O與圓O2的公切線為AB,切點Ax1,y1，Bx2,y2，圓O與圓O1的公切線為EF,切點Ex3,y3，F(xiàn)x4,y4，最短路徑為LC,則

LC=EF+AB+rθ，

其中

建立非線性規(guī)劃模型

運用LINGO對模型求解，可得過A，B，C的圓弧圓心坐標(biāo)計算結(jié)果. 根據(jù)以上模型可計算出O→A，O→B，O→C以及O→A→B→C→O的所有切點坐標(biāo)，直線段長度和圓弧長度.

4 最短時間路徑模型的建立和求解

機器人的行走速度與轉(zhuǎn)彎半徑有關(guān)，假設(shè)行走速度v與轉(zhuǎn)彎半徑ρ之間滿足

圖13

其中v0為直線行走速度，那么與最短路徑問題不同，轉(zhuǎn)彎半徑不再是越小越好，轉(zhuǎn)彎半徑越小. 雖然行走的距離也越短，但是速度會變慢，這樣行走速度反而可能會增加. 因此，應(yīng)選擇一個適當(dāng)?shù)霓D(zhuǎn)彎半徑，使得行走時間最短[6].

以O(shè)→A為例，研究最短時間路徑問題，建立非線性規(guī)劃模型[7].如圖13，起點O0,0，目標(biāo)點A300,300，障礙物5的頂點M80,210，切點Cx1,y1,Dx2,y2，轉(zhuǎn)彎圓弧的圓心M′m,n，圓心角∠CM′D為θ，半徑為r，O→A的路徑為L，時間為t，則

建立目標(biāo)函數(shù)

編寫LINGO程序求解，可求得圓弧圓心坐標(biāo)和半徑以及最短時間.

5 總結(jié)與討論

本文將機器人避障行走路線設(shè)計為若干個線圓結(jié)構(gòu)組成，通過建立數(shù)學(xué)模型計算出各切點坐標(biāo)和各圓弧長度，用解析幾何方法進行計算，精確度較高.但是在障礙物較多且形狀不規(guī)則時，模型顯得較為繁瑣.如果障礙物較多，到達目標(biāo)點的路徑就較多，這時可應(yīng)用網(wǎng)絡(luò)模型計算最短路.本文給出的最優(yōu)設(shè)計還可以應(yīng)用于貨物運輸、管道輸送等領(lǐng)域，應(yīng)用此模型能較好地解決運輸線路最短、輸送管道最短等問題.

[參 考 文 獻]

[1] 全國大學(xué)生數(shù)學(xué)建模競賽組委會.2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽賽題:[2012-09-07].http:∥www.mcm.edu.cn/problem/2012/cumcm2012problems.rar .

[2] 百度文庫.行走機器人避障問題:[2012-09-08].http:∥/wenku.baidu.com/view/251ee65677232f60ddcca17b.html.

[3] 邦迪.圖論及其應(yīng)用[M].西安:西安科學(xué)出版社,1984.

[4] 章棟恩，馬玉蘭.MATLAB高等數(shù)學(xué)實驗[M].北京：電子工業(yè)出版社，2010.

[5] 杜龍斌、楊亞運、付文，機器人避障問題. [2013-01-20].http:∥www.jpkc.sdu.edu.cn/sddxs/html/shuxuejianmoyouxiuzuopin/20130315/2495.html.

[6] 王琦.線性-二次雙層規(guī)劃的滿意解與基于LP與NLP過程的算法[J].系統(tǒng)工程理論與踐,2007,27(8)：84-91.

[7] 任競爭，譚世語，周志明.LINGO及其在化工過程優(yōu)化中的應(yīng)用[J].計算機與應(yīng)用化學(xué), 2010, 27(7)：975-977.