機器人避障問題的數(shù)學模型

1、2012高教社杯全國大學生數(shù)學建模競賽承諾書我們仔細閱讀了中國大學生數(shù)學建模競賽的競賽規(guī)則 我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵 件、網(wǎng)上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問 題。我們知道，抄襲別人的成果是違反競賽規(guī)則的，如果引用別人的成果或其他 公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻的表述方式在正 文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反 競賽規(guī)則的行為，我們將受到嚴肅處理。我們授權(quán)全國大學生數(shù)學建模競賽組委會， 可將我們的論文以任何形式進行 公開展示（包括進行網(wǎng)

2、上公示，在書籍、期刊和其他媒體進行正式或非正式發(fā)表 等）。我們參賽選擇的題號是（從 A/B/C/D中選擇一項填寫）：D題我們的參賽報名號為（如果賽區(qū)設置報名號的話）： 所屬學校（請?zhí)顚懲暾娜簠①愱爢T（打印并簽名）：1.2.3.指導教師或指導教師組負責人（打印并簽名）：日期：2012年_9_月10日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：編號專用頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進行編號）：機器人避障問題的數(shù)學模型摘要本文解決了機器人避障問題。根據(jù)

3、要求在多個靜態(tài)障礙場景中，實現(xiàn)機器人 短時、短距地到達目標點，甚至完成回路過程，在處理躲避障礙物時，我們提出 了障礙物頂點最小圓法，完全意義下實現(xiàn)了既安全躲障，又行駛路最短路線。對 于最短時間路徑的處理，我們在分析障礙物限制下，給出了頂點最小圓半徑增大 范圍，并建立了非線性優(yōu)化模型，實現(xiàn)了最短時間路徑的計算。根據(jù)所給數(shù)據(jù)及 場景，具體得到了以下數(shù)據(jù)基本結(jié)果：1最短線路數(shù)據(jù)：最優(yōu)路線及距離列表名稱路線最短距離OA0- Vi -A471.26OB0 - V5 - V6 - V8 - V9-V11- B853.70OC0- V4 - V21 - V33 - V31 - V30 -C1088.20AB

4、A- V9 - V11 -B838.63BCB- V13 - V14 - V15 - V17 - V18 -C701.21OABCOO-V2 - A - V9-V11 - B - V13 - V14 - V15 - V17 - V18 - V30 - V31 - V34 -V23 - V4 - V4 - 02497.892.從0到A到達的最短時間及路徑數(shù)據(jù):最短到達時間：98.46280秒最大頂點圓半徑：12.78175（個單位），圓心坐標（80,210 ）最短時間路徑：O (0,0) Pi(91.67,204.78) P? (75.80,222.07) A (300,300)關鍵詞：頂點最小

5、圓 最短路徑障礙非線性最優(yōu)化、問題敘述圖1是一個800X800的平面場景圖，在原點0(0, 0)點處有一個機器人，它只能 在該平面場景范圍內(nèi)活動。圖中有12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰 撞的障礙物，障礙物的數(shù)學描述如下表：編號障礙物名 稱左下頂點坐 標其它特性描述1正方形(300, 400)邊長2002圓形圓心坐標(550, 450)，半徑703平行四邊 形(360, 240)底邊長140,左上頂點坐標(400, 330)4三角形(280, 100)上頂點坐標(345, 210)，右下頂點坐標(410,100)5正方形(80, 60)邊長1506三角形(60, 300)上頂點坐標(1

6、50, 435)，右下頂點坐標(235,300)7長方形(0, 470)長220,寬608平行四邊 形(150, 600)底邊長90,左上頂點坐標(180, 680)9長方形(370, 680)長60,寬12010正方形(540, 600)邊長13011正方形(640, 520)邊長8012長方形(500, 140)長300,寬60在圖1的平面場景中，障礙物外指定一點為機器人要到達的目標點(要求目 標點與障礙物的距離至少超過10個單位)。規(guī)定機器人的行走路徑由直線段和圓 弧組成，其中圓弧是機器人轉(zhuǎn)彎路徑。機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線 路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧

7、路徑組成， 但每個圓 弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路 與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無 法完成行走。機器人直線行走的最大速度為v°=5個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速 度為v二v()Vk_，其中'是轉(zhuǎn)彎半徑。如果超過該速度，機器人將發(fā)生，1+e .側(cè) 翻，無法完成行走。請建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的數(shù)學模型。對場景圖中 4個點 0(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具 體計算：(1) 機器人從0(0, 0)出

8、發(fā)，OA、dB、OC和OA B CO 的最短 路徑。 機器人從O (0, 0)出發(fā)，到達A的最短時間路徑。注:要給出路徑中每段直線段或圓弧的起點和終點坐標、圓弧的圓心坐標以2及機器人行走的總距離和總時間800600400I I200200-1006008003#圖1800 X 800平面場景圖、模型假設與符號說明1、模型假設（1）.把機器人看作一個質(zhì)點，機器人移動相當于質(zhì)點的運動。（2）.機器人在路線行駛過程中，運動速度為勻速運動。即不考慮機器人的啟動 加速和轉(zhuǎn)彎減速，整個運行速度按轉(zhuǎn)彎最大速度移動。（3）.尋找運動路線時對于明顯耗時、距離遠的路線不再考慮，以便減少計算。（4）.計算精度保留小

9、數(shù)后兩位，結(jié)果系程序計算所得，可獲得更高精度。2、符號說明Vi :表示障礙物形狀各頂點（i =1,2,3n ）R（Xi,yi）:表示運動路線點頂點處的切點坐標（i =1,2,3n）r :表示頂點i處各圓的半徑。ki :表示某些直線的斜率。二：表示圓弧所對應的 圓心角。S :表示機器人所走路程。t :表示機器人經(jīng)過某段路程所用的時間。三、建立模型移動機器人路徑規(guī)劃問題是指在有障礙物的工作環(huán)境中尋找一條恰當?shù)膹?給定起點到終點的運動路徑，使機器人在運動過程中能安全、無碰撞地繞過所有 的障礙物而到達目標點。由問題所給場景圖，結(jié)合機器人的運動規(guī)則：（1）行走路線：機器人的行走路徑由直線段和圓弧組成，其

10、中圓弧是機器人轉(zhuǎn)彎路徑。 機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成， 也可以由兩 個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為 10個單位。（2）碰撞 距離：為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距 離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無法完成行走。在路線行駛中，要使運動距離最短，最基本的思維規(guī)則是：任何兩點之間的 直線距離最短。因此，若出發(fā)點與目標點連線周圍 10個單位內(nèi)無障礙物，則直 接走直線到達目標點距離最短。記機器人出發(fā)點坐標（ xR， yR），目標點坐標為（Xt，yj，則行走的直線方程為:(1)y = yR k(x -

11、Xr)：二 ax by c = 0 ，其中a = k,b = -1,c = yR -kxR，這里k二yTyR為直線的斜率。若設障礙物上點 Xt - XrP（ Xp， yp），則P到上述直線的距離由下述公式給出:(2)axp byp ca2 b2從而，若d<10,機器人走直線可能碰上物體 P,此時P點所對應物體應被視為障 礙物。一般地，若一個障礙物是某個幾何體，通過作出幾何體的外接圓半徑加 10的圓，再判定直線與該圓是否有交點來確定幾何體是否障礙物。對于如圖1所示的場景，障礙物分布密集，如果每個障礙物都做外接圓勢必 很難尋找到適合的行走路徑，即可行 路線都幾乎找不到，因此需要尋求其 它的避

12、障方法。按圖1所示場景，為躲避障礙， 獲得可行路線，我們在處理問題時采 用每個障礙物幾何體頂點做圓法：即 通過對幾何體障礙物頂點做最小符合 條件的圓（這里為半徑 10單位的圓 周）來光滑地由一個路徑連接點點過 渡到下一個路徑連接點。如下圖2所 示。圖2機器人從0到B的一條光滑可行路徑 其它可行路線處理方法相同。于是，得到機器人行走路線0-A，0-B，0-C，0-A-B-C-0的可行路徑由如下圖3,圖4,圖5,圖6所示。4圖4從0到B的幾條較優(yōu)化路徑圖5從0到C的運動路徑5#圖6從B到C的運動路徑1、運動最短路徑計算:頂點最小圓處理時既可躲避障礙，又注意到兩點之間直線距離最短，所以用 可使轉(zhuǎn)彎行

13、駛路徑最短。下面在計算中需 要處理幾個環(huán)節(jié)：1）點-圓切點計算。如下圖7所示，記 0 （ xr，yR ）為機器人出發(fā)點坐標，R（xi,yj為障礙物5左上角圓周左上切點坐標，則x1， y2應滿足:#6線圖圖7點圓切#在 R 直線OR上：yi -yR=k(Xi -Xr)p1 在頂點圓上：(捲 _xc1)2 (% -yc1)2 =102其中Oc(Xd，ycJ為頂點圓坐標。Pi為圓的切點，故(xi - xr )(x - Xc1 ) (yi - yR)(yi - yc1 ) = 0即向量OR”與向量0cP；垂直，數(shù)量積為0. o聯(lián)立 可求出未知變量：X”，yi, k o此方法可用于求出發(fā)點和到 達目標點

14、一端頂點圓的切點坐標。記P2(x2, y2)為目標點A(xa,ya)向障礙物5左上角頂點圓引出切點坐標，代入已知數(shù)據(jù)，得到：出發(fā)點：xR = yR =0， xci =80，yci=210=x =70.05，= 213.14。終點：Xa 二 ya =300，Xci =80，yci=210=X2 =76.61，y? =219.41。從而由O到A左上移動路徑所經(jīng)過線路及特定點坐標如下：路線 1: O- R- F2 -A各點坐標依次為：O(0, 0)，P1(70.05, 213.14) ，P2(76.61, 219.41)，A(300, 300).同理算得由O到A右下移動路徑所經(jīng)過線路及特定點坐標如下

15、：路線 2： O-P3- F4-A各點坐標依次為：O(0, 0)，P3(70.05, 213.14)，卩2(76.61, 219.41)，A(300, 300).2) 圓-圓切點的計算。若在路徑中出現(xiàn)下圖8所示切線情形，仍記P(Xi,yi)， 巳(X2,y2)分別為頂點圓Ci,C2上的切點坐標，則切點坐標可由下列關系式聯(lián)立求 得：Pi,P2共線：y2 yi -k( k為Pi, P2直線斜率，待定)x2 _片P1在C1上：2丄22(xi - Xci)(yi -yci)亍P 在 C2 上:(X2 -Xc2)2 (y2 -yc2)2 =T22Pi是G的切點，故Of丄RP2 ，從而：% Xd）（x2

16、十）（ -yd）® -yj = oF2是C2的切點，故O2P2 _RP2，從而：（X2 - Xc2 ）（X2 _X1） （y _yc2）（y _ yi 0聯(lián)立可解出：xY，X2,丫2 ,k。p=Pl/Pf圖8圓-圓切線圖注：（1）上述公式中，對幾何體的頂點圓而言，rr2 =10，但在處理 如圖1中障礙物2時，可取其中某一半徑為r =80 10，計算切點同此方法。（2）機器人移動路徑中OB，OC，AB，BC等中間連接點兩圓切點統(tǒng)一都按 此法計算。3）距離的計算。問題要求整個移動的最短路徑，而行駛路線只有一些線段和 一些圓弧線組成，因而在曲線的計算中分情況逐段計算， 求和，可最終求得某一

17、 可行路徑的總距離。直線段距離的計算：設R（X1，yJ，F(xiàn)2（X2,y2）為線段上兩點，則P1P2的距離為:d = .（X2 - 人）2 厲 一 yj2（ 3）圓弧線段的計算：設P1 （x1 , y1）， P?（X2,y2）為同一圓周一段弧的兩個端點，若已知圓的圓心Oc（Xc1，yJ，半徑為r，貝U丨=r舊其中二為圓弧所對應的圓心角，由以下公式計算：口 |OcR Icosr 22(X1 Xc1)(y1 - y“)二 r +|OcP2|2 IP1P2 |2 2r2 c2 cos22|OcPi | |OcP2 |2r2這里v按余弦公式獲得，c = （X2 - Xi）2 （y2 - yj2。(4)(

18、5)2、最短移動時間的計算注意到：時間=路程/速度，由于機器人直線行走的最大速度為 Vo =5個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為V二v（）：00亍，其中'是轉(zhuǎn)彎半徑。（6）1 +e如果超過該速度，機器人將發(fā)生側(cè)翻，無法完成行走。若假設機器人在運動過程 中勻速運動，這樣不再考慮運動加減速過程，由于 V：:Vo，因此要獲得最短移動 時間，則應讓V盡可能大，接近于Vo，由公式（6）可知，運動過程中經(jīng)過圓弧 的轉(zhuǎn)彎半徑越大，速度越大，于是為節(jié)省時間，需要增大轉(zhuǎn)彎半徑，然而，按常規(guī)：V：Vo，若在精度要求下，近似達到V=Vo，則認為速度不在增大，此時 應考慮獲得最短路程，因為圓弧越大，可能

19、會使得行走路程變大。綜合考慮上述 因素，建立下列非線性優(yōu)化模型：(X2V =Vo(7)1o -o.1r力y ya - k2(X2 Xa)o蘭日蘭兀，1o蘭r <55X1,y1,X2, y2 -o上述模型中，1o乞r55，下限1o為了躲避障礙物應 滿足的最低要求，那么最大值55如何獲得呢？其基本原理如下圖示：（右圖只要三點 烏，P3，A共線，不難理解）sr jx； y r v .(X2 -Xa)2(y2 - ya)2 (X1 Xo)(x2 Xo) +(y1 yo)(y2 yo)四、模型求解按模型建立過程中所列舉計算方法， 結(jié)合軟件編程，對各種情形下的目標點 路徑進行計算，即可得到各線路行駛

20、最短路徑及最短距離1.障礙物基本數(shù)據(jù)匯總：v1(80,60), V2(80,210) ,V3(230,210) ,V4(230,60) ,V5(60,300), V6(150,435), V7(235,300), V8(220,470) , V9(220,530) ,(240,600) , Vn(150,600) , (180,680) ,(270,680), v14 (370,680), v15 (430,680) , v16 (540,600), v17 (540,730) ,v18 (670,730), v19 (280,100)， V20 (345,210)，v21(410,100)，

21、v22(360,240)，v23(400,330)，v24(540,330)，v25(500,240)，v26(300,400)，v27(300,600)，v28(500,600)，v29 (640,520)，V3o（720,600），V31 （720,520），V32（500,140），V33（500,200），V34（550,450），2.列舉各種較短的一些行走路線及節(jié)點坐標：（按圖10所示頂點標注路線，中間每個頂點包含頂點圓的兩個切點）：11#圖10#OA 路線： 路線 1：O- v1 -A坐標為： O(0, 0)，P1(70.05, 213.14) ，P2(76.61, 219.41)

22、，A(300,300). 總距離 L： 471.26(個單位)路線 2：O-v4 -A坐標為： O(0, 0) ， P1( 232.11, 50.23) ， P2(239.70, 57.59) ， A(300, 300) .總距離 L： 498.64(個單位)最短路徑為：O-w-A,最短路徑：L=471.26 (個單位)OB 路線：路線 1： O-v5-v6-v8-v9-v11-B坐標為：O(0, 0) ， P1 (50.14, 301.64)， P2 (51.68, 305.55) ， P3(141.68, 440.55)，P4 (147.96, 444.79) ， P5(222.04, 4

23、60.21)， P6 ( 230,4 70)， P7(230, 530) ，P8(225.50,538.33) ， P9 (144.50, 591.65) ， P10(140.69, 596.35) ， B(100, 700)?？偩嚯x L： 853.70(個單位)路線 2：O- v5-v6-v8-v13-B坐標為：O(0，0)，P1(50.14，301.64)，P2(51.68，305.55)，P3(141.68，440.55)，P4 (147.96， 444.79)， P5 (222.04， 460.21)， P6 (229.73， 467.68)，P7 (279.73， 677.68)，

24、P8 (270.59， 689.98)， B(100， 700).總距離 L： 971.23(個單位)路線 3： O- v2-v7-v9-v11-B坐標為：O(0，0)，P1(70.51，213.14)，P2(75.97，219.15)，P3(239.03，290.85)，P4 (244.98，300.65)， P5 (229.98，530.65)， P6 (225.50，538.35)，P7 (144.50，591.65)， P8 (140.69，596.35)， B(100， 700).總距離 L： 877.38(個單位)路線 4： O- v4 -v7-v9 -v11-B坐標為：O(0，0

25、)， P1 (232.11，50.23)， P2 (240.00，59.79)， P3 (245.00，299.79)，P4 (244.98，300.65)， P5 (229.98，530.65)， P6 (225.50，538.35)，P7 (144.50，591.65)， P8 (140.69，596.35)，B(100，700).總距離 L： 945.95(個單位)路線 5： O-v4-v13 -B坐標為：O(0，0)， P1 (232.11，50.23)， P2 (239.98，59.36)， P3 (299.98，679.36)，P4 (270.59，689.98)， B(100，

26、700).總距離 L ：1058.35(個單位)最短路徑為：O-v5-v6-v8-v9-% - B ,最短路徑：L=853.70 (個單位)OC 路線：路線 1： O-v5 -v6 -v8 -v27 -v15 -v17 -v18 -C坐標為：O(0， 0)， P1 (50.14,， 301.64)， P2 (51.68， 305.55)， P3 (141.68， 440.55)，P4(147.96， 444.79)，P5(222.04，460.21)，P6(229.13， 465.92)，P7(290.87， 604.08)，P8(295.92，609.13)，P9(434.08， 670.8

27、7)，P10 (435.59， 671.71)， P11 (534.41， 738.29)， P12 (540， 740)，P13 (670， 740)， P11 (679.77， 732.14)， C(700， 640).總距離 L： 1239.82(個單位)路線 2：O- v5 - v6 - v26 - v33 - v31 - v30 -C 坐標為：O(0， 0)， P1 (50.14,，301.64)， P2 (51.68，305.55)， P3 (141.68，440.55)，P4 (153.52，444.36)， P5 (296.48，390.64)， P6 (299.19，390.

28、03)，P7 (543.55，370.26)， P8 (660.33，393.20)， P9 (727.04，512.90)，P10 (730.00，520.00)，P11 (730.00，600.00)，P12 (727.72，606.36)，C(700，640). 總距離 L： 1243.67(個單位)路線 3：O- v2 - v23- v34 - v31 - v30 -C 坐標為：O(0，0)， P1(70.51，213.14)， P2 (76.49，219.36)， P3(396.49，339.36)，P4 (398.14，339.83)， P5 (564.88，371.40)， P6

29、 (606.33，393.20)，P7 (727.04，512.90)， P8 (730.00，520.00)， P9 (730.00，600)，P10 (727.72，606.36)，C(700，640). 總距離 L： 1098.35(個單位)路線 4：O- v4 - v23- v34 - v31 - v30 -C坐標為：O(0，0)， P1 (232.11，50.23)， P2 (238.78，55.21)， P3 (391.22，334.79)，P4 (398.14，339.83)， P5 (564.88，371.40)， P6 (606.33，393.20)，P7 (727.04，5

30、12.90)， P8 (730.00，520.00)， P9 (730.00，600.00)，P10 (727.72，606.37)，C(700，640). 總距離 L： 1094.80(個單位)路線 5： O-v4 -v20 -v25-v31 -v30 -C坐標為：O(0，0)， P1 (232.11，50.23)， P2 (238.54,54.79)， P3 (336.46，215.21)，P4 (344.36，219.98)， P5 (500.64，230.02)， P6 (507.86，233.82)，P7 (727.86，513.82)， P8 (730，520)， P9 (730，

31、 600)，P10 (727.72，606.36)， C(700，640).總距離 L： 1101.36(個單位)路線 6： O-v4 - v21- v33 -v31 -v30 -C坐標為：O(0，0)， P1 (232.11，50.23)， P2 (232.17,50.24)， P3 (412.17,90.24)，P4 (418.34，94.49)， P5 (491.66，205.51)， P6 (492.06，206.08)，P7 (727.94，513.92)， P8 (730.00，520.00)， P9 (730.00，660.00)，P10 (727.72，606.36)，C (

32、700，640).總距離 L： 1088.20最短路線為： O- v4 - v21 - v33 - v31 - v30 -C； 最短距離為： L=1088.20 (個單位)AB 路線：路線 1：A- v9 - v11 -B經(jīng)過點的坐標依次為： A(300，300)， P1 (229.57，532.89)， P2 (225.50，538.35)，P3 (144.50，591.65)， P4 ( 140.69，596.35)， P5 (222.04，460.21)，B (100，700). 總距離 L： 838.63(個單位)路線 2：A- v26-v13 -B經(jīng)過點的坐標依次為： A(300，3

33、00)， P1 (290.05，399.00)， P2 (290.01，399.64)，P3 (279.99，680.36)， P4 (270.59，689.98)，B (100，700).總距離 L： 871.05最短路徑為：A-V9-V11-B, L=838.63 (個單位)BC 路線：路線 1： B-V13 -V14 -V15 -V17 -V18 -C經(jīng)過點的坐標依次為： B (100， 700)， P1 (270.59， 689.98)， P2 (272.00， 689.80)， P3 (368，670.20)， P4 (370，670，)，P5 (430，670)， P6 (435.

34、59，671.71)， P7 (534.41，738.29)，P8 (540，740)，P9 (640，740)，P10 (679.77，732.14)，C (700， 640).總距離 L： 701.21(個單位)路線 2：B- v11 -v10 v15 -v17 -v18 -C經(jīng)過點的坐標依次為： B (100，700)，P1 (140.69，596.35)，P2 (150，590)，P3 (240， 590)，P4 (243.88，590.78)，P5 (433.88，670.78)，P6 (435.59，671.71)，P7 (534.41， 738.29)， P8 (540，740)

35、，P9 (670，740)， P10 (679.77，732.14)，C (700，640). 總距離 L： 788.39(個單位)路線 3： B-v13 -v28 v29 -v31 -v30 -C經(jīng)過點的坐標依次為： B (100，700)， P1 (270.59，689.98)，P2 (273.29，689.44)， P3 (503.29，609.44)，P4(506，608)， P5 (634，512)， P6 (640，510)， P7 (720， 510)， P8 (730，520)， P9 (730，600)， P10 (727.72，597.64)，C (700，640). 總距

36、離 L： 816.31最短路徑為：B- v13 - v14 - v15 - v17 - v18 -C, L=701.21 (個單位)OABCO 路線：經(jīng)過的點坐標依次為： O (0,0) ， P1 (70.51,213.14)， P2( 76.88， 219.50)， P3( 293.12,290.50) ， P4(299.57,302.91)， P5(229.57,532.91)， P6(225.50,538.35)， P7(144.50,591.65)， P8(140.72,596.29)， P9(100.72,696.29.)， P10(111.24,709.92)， P1(1 271.

37、24,689.92)， P12(272.00,689.80)， P1(3 368.00,670.20)， P1(4 370.00,670.00)， P15(430.00， 670.00)， P16(435.59,671.71)， P17(534.41， 738.29)， P18(540.00,740。 00)， P19(670,740)， P20(679.14,734.06)， P21(700,637)， P22(719.70,642.43)， P23(729.70,602.43)， P24 (730,600)， P25(730,520)， P26(727.94,513.92)， P27(49

38、2.06,206.08), P28 (491.66,205.51, P29 (418.34,94.49), P30 (412.17,90.24),P (232.17,50.24),巳2 (232.11,50.23, O (0,0)最短路徑行駛路線在場景圖中具體如下各圖所示。從0到A的可行路線173.最短移動速度求解從B到C的可行路線利用非線性規(guī)劃求解 Lingo軟件計算非 線性優(yōu)化模型，得到獲得最大轉(zhuǎn)彎半徑為 12.78 (個單位)，從0到A沿左上角路線 最短移動時間為98.46 秒具體行駛路線節(jié)點為：O (0,0) Pi (91.67,204.78) P2 (75.80,222.07) A

39、(300,300)行駛轉(zhuǎn)彎速度v=4.99個單位/秒。4 最優(yōu)路線匯總:最優(yōu)路線表名稱路線最短距離OAO- Vi -A471.26OBO-V5-V6-V8-V9-V11- B853.70OCO- V4 - V21 - V33 - V31 - V30 -C1088.20ABA- V9-V11-B838.63BCB- V13 - V14 - V15 - V17 - V18 -C701.21OABCOO- V2 - A - V9 - V11 - B - V13 - V14 - V15 - V17 - V18 - V30 - V31 - V34 - V23 _ V4 _ v4- O2497.89五、模

40、型分析及推廣對機器人路徑規(guī)劃的研究，世界各國的專家學者們提出了許多不同的路徑規(guī) 劃方法，主要可分為全局路徑和局部路徑規(guī)劃方法。全局路徑規(guī)劃方法有位形空 間法、廣義錐方法、頂點圖像法、柵格劃歸法；局部路徑規(guī)劃方法主要有人工勢 場法。這些方法都各有優(yōu)缺點。本文針對多障礙問題提出了頂點最小圓法，優(yōu)點：（1）實現(xiàn)了靜態(tài)障礙下 機器人的安全移動。（2）找到了到各目標點全局最短路徑。（3）基本理論涉及簡單的幾何問題及其計算，可操作性強，容易實現(xiàn)。缺點：整個過程我們按勻速 運動處理運動速度，對機器人的啟動加速，減速停止都沒有詳盡的考慮。實際應用上，可考慮以下問題：廠房車間機器人搬運。對于移動搬運機器人，頂點

41、最小圓方法是一種可行而 且實用的方法。首先，機器人及障礙物的位置可以實時測得， 且障礙物一般為固 定不動；其次，障礙物數(shù)量固定，形狀大小可預知；再次，搬運的效率要求機器 人的行走路徑為最短，而且走直線比走曲線更能講究效率。當然，其它方面的應用還待深入的開發(fā)，我們拭目以待！參考文獻1】 周杏鵬 .傳感器與檢測技術(shù) .北京:清華大學出版社 ,2010.2】 （美） 理查德.摩雷.（中）李澤湘 . （美）夏恩卡 .薩思特里機器人操作的數(shù) 學導論 .北京:機械工業(yè)出版社 ,2007.3】 吳翔,吳孟達 ,成禮智 .數(shù)學建模的理論與實踐 .長沙:國防科技大學出版 社,1999.4】 殷劍宏 ,吳開亞.圖

42、論及其算法 .合肥:中國科學技術(shù)大學出版社 ,2003.【5】 李胡錫.Matlab循序漸進.上海:上海交通大學出版社，1997.6】 王家文 .MATLAB7.0 圖形圖像處理 .北京:國防工業(yè)出版社 ,2006.7】 葉湘濱 熊飛麗 張文娜 羅武勝. 傳感器與測試技術(shù) . 國防工業(yè)出版社， 2007.19附錄附錄一：模型一的 maple 部分程序如下：> restart:> with(plots):Warning, the name changecoords has been redefined> xR:=0:yR:=0:xA:=300:yA:=300:xB:=100:y

43、B:=700:xC:=700:yC:=6 40:r:=10:> btanpoint:=proc(x0,y0,xc,yc)global X,Y,K,Q;local P;P:=solve(Y=yO+K*(X-xO),(X-xcF2+(Y-ycF2=rA2,(X-xc)+K*(Y-yc)=0,K,X,Y);Q:=evalf(allvalues(P);return Q;end proc: mtanpoint:=proc(xc1,yc1,xc2,yc2) global X1,Y1,X2,Y2,K,Q; local P;if xc1<>xc2 thenP:=solve(Y2-Y1=K*(

44、X2-X1),(X1-xc1)A2+(Y1-yc1)A2=rA2, (X2-xc2)A2+(Y2-yc2)A2=rA2,(X1-xc1)+K*(Y1-yc1)=0,(X2-xc2)+ K*(Y2-yc2)=O,K,X1,Y1,X2,Y2);Q:=map(evalfallvalues,P);return Q;elseP:=solve(X1=X2,(X1-xc1)A2+(Y1-yc1)A2=rA2, (X2-xc2)A2+(Y2-yc2)A2=rA2,(X1-xc1)*(X2-X1)+(Y1-yc1)*(Y2-Y 1)=0,(X2-xc2)*(X2-X1)+(Y2-yc2)*(Y2-Y1)=0,K

45、,X1,Y1,X2,Y2 );Q:=map(evalfallvalues,P);return Q;fi:end proc: ctanpoint:=proc(xc1,yc1,xc2,yc2,a,b) global X1,Y1,X2,Y2,K,Q; local P;if xc1<>xc2 thenP:=solve(Y2-Y仁K*(X2-X1),(X1-xc1F2+(Y1-yc1F2=aA2, (X2-xc2F2+(Y2-yc2F2=bA2,(X1-xc1)+K*(Y1-yc1)=0,(X2-xc2)+ K*(Y2-yc2)=0,K,X1,Y1,X2,Y2);Q:=map(evalfal

46、lvalues,P);return Q;elseP:=solve(X1=X2,(X1-xc1)A2+(Y1-yc1)A2=aA2, (X2-xc2)A2+(Y2-yc2)A2=bA2,(X1-xc1)*(X2-X1)+(Y1-yc1)*(Y2-Y 1)=0,(X2-xc2)*(X2-X1)+(Y2-yc2)*(Y2-Y1)=0,K,X1,Y1,X2,Y2 );Q:=map(evalfallvalues,P);return Q;fi:end proc: line_dist:=proc(x0,y0,xt,yt) local d;d:=sqrt(x0-xt)A2+(y0-yt)A2);return

47、evalf(d);end proc:arc_dist:=proc(x0,y0,xt,yt)local a,b,c,cth,th,d;a:=10;b:=10;c:=sqrt(x0-xt)A2+(y0-yt)A2);cth:=(aA2+bA2-cA2)/(2*a*b); th:=evalf(abs(arccos(cth); d:=10*th;return d;end proc:pline:=proc(x0,y0,xt,yt)plot(x0,y0,xt,yt);end proc:parc:=proc(xc,yc)implicitplot(x-xc)A2+(y-yc)A2=100,x=xc-10.xc

48、+10,y=yc-10 .yc+10):end proc:OC 的一路線程序：>xx1:=80:yy1:=210:xx2:=400:yy2:=330:xx3:=550:yy3:=450:xx4: =720:yy4:=520:xx5:=720:yy5:=600: btanpoint(xR,yR,xx1,yy1):Q;x1:=subs(Q1,X);y1:=subs(Q1,Y);L1:=line_dist(xR,yR,x1,y1): mtanpoint(xx1,yy1,xx2,yy2):Q;x2:=subs(Q3,X1);y2:=subs(Q3,Y1);x3:=subs(Q3,X2);y3: =subs(Q3,Y2);L2:=arc_dist(x1