機器人避障模型論文

1、機器人避障模型摘要本文針對機器人避障問題進行分析與研究，在800X 800的平面場景擺放有12 個不同形狀的障礙物，以 O（0， 0）點為起點，對 A、B、C、O 為目標點， 通過分析，我們假設(shè)在圓弧的半徑為 10個單位，且下建立模型，由出發(fā)點到達 目標點可以有很多條路徑行走， 所以就有不同的幾種方案可以到達目標點， 據(jù)題 意；我們把機器人行走的路徑都看成是由直線和拐角圓弧線組成的， 根據(jù)這個原 理，我們對機器人可行走的路徑分析直線與拐角圓弧的關(guān)系， 將所有路徑都轉(zhuǎn)化 為若干個線圓結(jié)構(gòu)來進行求解， 對于途中經(jīng)過的拐角圓弧， 我們都將只考慮半徑 最小的情況， 然后建立解析幾何圖形模型對可行走的不

2、同路徑進行求解， 從而得 到最短路徑。對于問題一： 我們根據(jù)幾何圖形模型很容易求解出可能行走的路徑，然后列出二種明顯的方案進行比較，得到最終的求出最短路徑：O A 最短路徑為： 471.2219O B 最短路徑為： 607.5783O C 最短路徑為： 1090.942X A B CO 最短路徑為：2843.1693對于問題二，我們采用 Dijkstra 算法（見附錄三），解出最短時間路徑為： 462.4194。本模型在建立過程中，始終以圓的公切線和弦為理論基礎(chǔ)，確保模型的正確 性，在求解數(shù)據(jù)過程中，因數(shù)據(jù)量大而繁瑣，我們用到了 MATLAB 軟件對模型 求解，確保了結(jié)果的準確性和有效性，適用

3、于生活中開車、賽車，對安全實際問 題起到作用，有很強的實用性和借鑒性。關(guān)鍵詞： 最短路徑 幾何圖形Dijkstra 算法 MATLAB 軟件機器人避障模型一、問題重述根據(jù)圖(附錄一)的一個800X800的平面場景圖，在原點0(0, 0)點處有一個 機器人，它只能在該平面場景范圍內(nèi)活動。圖中有12個不同形狀的區(qū)域是機器人 不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述見附錄二：在圖(附錄一)的平面場景中，障礙物外指定一點為機器人要到達的目標點 (要求目標點與障礙物的距離至少超過10個單位)。規(guī)定機器人的行走路徑由直 線段和圓弧組成，其中圓弧是機器人轉(zhuǎn)彎路徑。機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑 由與直線路徑

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

5、算：機器人從0(0, 0)出發(fā)，dA、dB、dC和OA B CO 的最短 路徑。 機器人從O (0, 0)出發(fā)，到達A的最短時間路徑。注:要給出路徑中每段直線段或圓弧的起點和終點坐標、圓弧的圓心坐標以及機器人行走的總距離和總時間。二、問題分析問題一、根據(jù)問題的分析，題目要求按照目標點與障礙物的距離至少超過 10 個單位，以定點0(0,0 )行走繞過障礙物到達目標點的最短路徑，機器人不能與 障礙物碰撞、不能折線轉(zhuǎn)彎的因素下，到達的點有，機器人從0(0, 0)出發(fā)，OA、 CB、CC 和C A B CO 的最短路徑，A、B、C 的坐標為 A(300, 300)， B(100, 700)，C(700

6、, 640)，我們采用幾何圖形來描繪出起點到達終點的路線。先 用包絡(luò)線畫出機器人行走的危險區(qū)域路線，拐角處就是一個半徑為10的圓弧，采用劃直線的方法尋找可能的最短路徑 (比如求0和A之間的最短路動徑，就可以連 接0和A之間的每條線段，求出0到 A的線段長度便是0到A的一條可能的最短路徑)， 然后采用解析幾何、平面圖形、避障路徑規(guī)劃、決策算法解決最短路徑。列出O到每個目標點的可能路徑的最短路徑，然后比較其大小便可得出0到目標點的最短路徑。(1)、在0到 A點時，有二條最短路徑，在0到 B點時，有一條最短路徑。 在0到C點時，有三條路徑。(2)、0到A到B到C到O點的最短路徑。根據(jù)每一個障 礙物的

7、特點，運用不同的線圓結(jié)構(gòu)和幾何圖形，計算出達到每一個目標點的最短 距離。問題二、對問題二的分析，在問題一分析的基礎(chǔ)上，以O(shè)點到達A點的最短 時間路徑，從起始點0(0, 0)經(jīng)過中間的若干個障礙物，按照解析幾何的規(guī)則 繞過障礙物到達目標點， 我們應(yīng)該考慮經(jīng)過障礙物拐點的問題和經(jīng)過路徑中的目 標點處轉(zhuǎn)彎的問題， 這時簡單的線圓結(jié)構(gòu)就不能解決這種問題， 我們在拐點及途 中目標點處都采用最小轉(zhuǎn)彎半徑的形式，也可以適當(dāng)?shù)淖儞Q拐點處的拐彎半徑， 在拐點處增大或縮小圓的半徑， 提高機器人的速度， 使機器人能夠沿直線到達目 標點，用集合把每條線段的值表達出來， 用幾何圖形建立模型， 采用長線段距離 大于短線段

8、的距離，三角形中的，兩邊之和大于第三邊，兩邊之差小于第邊。然 后采用 Dijkstra 算法二種方案進行比較，最終求得最短時間路徑。三、模型假設(shè)1、假設(shè)轉(zhuǎn)彎時， 機器人行走線路與障礙物間的最近距離大于等于 10個單位， 設(shè) 定為 10 個單位。2、假設(shè)障礙物全是矩形。3、假設(shè)機器人是一個圓點或一個圓。4、假設(shè)機器人轉(zhuǎn)彎時，都是一個圓。5、假設(shè)保留四位小數(shù)。四、符號說明：轉(zhuǎn)彎半徑V:最大轉(zhuǎn)彎速度e：取 2.71828So : 0Af Bf CO 的最短路徑。R : 圓的半徑五、模型建立與求解根據(jù)本文的已知和要求，我們仔細的分析了題目， 0點每到一個目標點的距 離最短，而且要避開障礙物， 在拐角時

9、也不能折線轉(zhuǎn)彎。 運用了不同顏色的線段 在平面上標出基本的最短路徑，在平面上也可以比較的最短路徑。如圖 1 OA黑線 OB :鮮綠線 OC :藍色線這是0點到目標點的可能的最短路徑，幾種路徑進行分析比較模型一、根據(jù)問題的分析，已知圖 2機器人從0（0，0）坐標出發(fā)，O到A 點的最短路徑。A （300，300），5到6圖形距離為70,用平面坐標畫出A點的 路徑，從平面上可以看出，結(jié)合圖形在坐標中的每一個坐標，可以得到圖2為O到A點的最短路徑，求出O點到A點的距離，我們采用解析幾何圖形進行分析與 建立此模型，進行求解。O到A路徑圖（見附錄十三）一、第一種方案設(shè)機器人是一個小圓或一個小點在移動，在轉(zhuǎn)

10、彎的時候，產(chǎn) 生了一條弧形。而弧形也是機器人所走的路徑，如圖3,圓就是機器人，以H點為圓心，OD AG是圓的公切線。切點為 D G HD垂直于OD HG垂直于AG根 據(jù)附錄一、附錄二的圖和坐標，算出OH AH運用線性結(jié)構(gòu)的算法得到最短路徑為 OA=OD+DG+,GA由 O（xi，yi）點為起點，A（X5, y5）為終點，D（x3, y 3）和 G（ X4,y4）以 H（沁出） 為圓心，A 點的坐標為（300，300）、H （80，210）。半徑為 r （r 10） ,OA=a OH=b AH=c / OHA=、/ OHD=、/ AHG=、/ DHG=。求弧 ODGA 的長度， 設(shè)為Loa.即方

11、程組為: TOC o 1-5 h z a(X5xi)2(ysyi)2b,(x2xi)2(y2yi)2c(X2x5)(y2ys)解得到邊長 a=424.264i, b=224.722i, c=237.6973.根據(jù)三角形的性質(zhì)與定理，算出、的度數(shù)2 2 2在 OHA 中： arccos ( c)=1332bcr在 Rt OHD 中:arccos =87b在 Rt AHG 中：arccos - =87c2 -=53Loa OD DG GA 即Loab2 r2c2 r2 r =471.2219通過matlab軟件計算（見附錄五），1到90余弦函數(shù)值（見附錄四），解得O 到目標點A的第一種方案的最短距

12、離為471.2219.2、通過O起點到達A目標點第二種方案，分析最短路徑。采用長線段距離大于 短線段的距離，三角形中的，兩邊之和大于第三邊，兩邊之差小于第邊的原理，根據(jù)圓的弧形求出弧長，弧長公式：ln r180建立模型,求出路徑，見圖四:已知O點的坐標（0, 0） ,A（300,300）,H（230,60） 。 OD AG是線圓切線切點于D G,設(shè)O（x,y）為起點，A（ X2, y2）為目標點，路徑過D（ X3, y）和G（X4,）與H （洛，yj為圓心，r（r10）以半徑為圓的切點，OA=a OH=b HA=g角/ OHA= , / OHD= , / AHG=，/ DHG=。令 OA=a

13、OH=b HA=g 求出 DG的弧長和OA的最短路徑。方程組如下：a-(X2X)2(y2y)2b；.(X1X)2(y1y)2c . (X2XJ2(y2y）解得方程為：a=424.2641 b=237.6973 c=250”2 2 2在 Rt OHA中:arccos ( c) =1202bcr在 Rt ODH中:arccos- =88br在 Rt OAGH中:arccos =87c2 -=55Loa OD DG GA 即Loa b2 r2. c2 r2 r =493.0218通過matlab軟件計算（見附錄六），1到90余弦函數(shù)值（見附錄四）解得O到目標點A第二種方案的最短距離為493.0218

14、。綜上所述，第一種方案得471.2219，第二種方案得493.0218。第一種方案小于 第二種方案，比較得到第一種方案為最優(yōu)最短距離， 同理，其它方案也沒有第一 種方案最短，所以O(shè)到目標點A的最短距離為471.2219。二、第一種方案，從O起點到B點的最短距離。機器人要經(jīng)過三個障礙物的拐角 點，這個三個拐角點，用小圓表示出來，根據(jù)圖 1中平面圖形路徑。我們選擇 了一條最短路徑，得到一個用線圓和公切線組成了一個圖4。采用圖形和點的坐標，計算出每一條線段的值。圖（見附錄一、附錄二），根據(jù)圖形5建立以下模型：H2Hla5由0(x, y)出發(fā)，經(jīng)過 D (X3,y3),G(X4,y4), A(X5,y

15、5)D(X7, y?)和G,X8,y8)以Higye)為圓心， 經(jīng)過D2,G2切點，以H 2為圓心。半徑為r(r 10)的圓的切點，A 300,300 ,B 100,700 ,H 80,210 ,H1 300,400 , H2 150,600 , AH1 c, AH 2 a , H1H2 b, H1B d, BH 2 e, H M MH 2H1H2 f. AH 1H 21, AH 1D11, MH 1G11, G1H1D11 , H1H2B 2, BG2 H 22, MD2 H 22, G2H2D22,求 OD GA AD1G D BG G2D2,設(shè) L1 AD1G1D2, L2 BGG2 D

16、2.X5X92y5y9X13M(X13,y13)即M點是圓H1與圓H2的圓心距離與公切線的交點，得到以下模型:a.(X9X5)2(y9y5)2b-(X9X6 )2(y9y )2c.( X6X5)2(y6y5)2d(X12X6)2(y12y6)2e.(X9X12)(y9yjfJX13X6)2(y13y6)2g2f2 ry13f=80.1561g=161.2451在AH1H2中:arc躺2bc155r在 Rt AH1D1 中：1 arccos 87CirL1 L 2 =471.2219+293.5317+111.8786=876.6322在Rt MH 1G沖：1 arccos 78所以L22.1C

17、1r2 f2 r2r293.5317在H1H 2 B 中：2b22 ,2e -d160aiccos2be在RtBG2 H 2 中:2r arccos-e85在RtMD2H2 中：r2 arccos78所以2 2 - 2 -2 3即l22 2丄 e -rr2 =111.878611 1 10LobL O A通過matlab軟件計算（見附錄七），1到90余弦函數(shù)值（見附錄四），解得O 到目標點B第一方案的最短距離為876.6322。2、從O到B的第二種方案。也采用線圓結(jié)構(gòu)，線段和三角形定理，建立模型 如圖6。DI根據(jù)題意，已知從0點出發(fā)到達B點，坐標0(0, 0), B( 100, 700), H

18、(230,60), H1 (220, 410), H2 ( 150, 600)。以 0(x,y )為起點,B(xyQ 為目標 點。路徑經(jīng)過D, E點，以H( %, % )為圓心，r (r10)以半徑為圓拐角小賀 弧的切點，D1,巳以出(X2, y2 )為圓心，r (r10)以半徑為圓拐角小賀弧 的切點，D2, E2以H2 ( X3, y2 )為圓心，r (r10)以半徑為圓拐角小賀弧的切點，令 OH 1=a,OH=b,HH 1=ED=c, HH2=a1,2MH1= H H1 = b1, H2B=c1, H1 B=a2,三角形的角度，/ OHH1= , / OHD= , / H1 HE= =，/

19、 HH1 H2= 1 , / MH1 E1 = 1 ,2/ H H1 D= 1 =, / H1 H2 B= 2 , / B H2 E2 = 2 , / MH2 D2 = 2 ,求2ODED1 + D1 E1 E1 D2 + D2 E2 E2 B 的弧長度。設(shè)弧長 ODd = L1 , D1 E1 E1 M 2 = L2 , MD2EB=I_3 , Lob = L“ + L2 + L3M是圓H1與圓H2公切線與圓心距的交點，設(shè) M點坐標為(X0,y。)即X3 X2X02即方程如下：y。討3 丫2a(X2X)2(y2y)2b(X1X)2(%y)2c(X2X1)2(y2yj2a1(X3X1)2yJ2

20、b1(X3X2)2(y3y2)2C1,(X4X3)2(y4y3)2a2.(X4X2)2(y4y2)2解 得 a=573.8313b=237.6586c=470.1064 a, =545.8938b =98.99495=559.0170 a2 =509.2151,2 2 24?？校篴rCC0S () =76r在 Rt ODH中：arccos- =87b r在 Rt比 HE中：arccos= =rc 22 -=7L. b2 r2 c r 717.5155在HH1H2中：在 Rt ME1H 中:,2 2 2b1 c - a11 arccos2bc441 arccos 78 b1在 Rt HH 1D

21、1 中: 1 arccos r 12121111481b1 22L2. -r r 1 =569.568v 22 2 2在 H1H2B中： 2 arccos1孔 782b1c1r在 Rt BE2 H 2中:2 arccos 89在Rt MD2H2中:2r arccos 78bl12L3 . blr2 g2 r2 r 2 607.5783 2 、通過matlab軟件計算（見附錄八）,1到90余弦函數(shù)值（見附錄四）解得O到目標點B第二種方案的最短距離為607.5783綜上所述，第一種方案得876.6322，第二種方案得。第一種方案小于第二種方 案，比較得到第一種方案為最優(yōu)最短距離， 同理，其它方案也

22、沒有第一種方案最 短，所以0到目標點B的最短距離為607.5783三、根據(jù)題意，從O起點到C點的最短距離有四條路徑，如圖1的平面圖形，在 平面圖形中的障礙物和線段比較，直線的速度是最快最短的路徑，我們排除上面 三條。路徑采用最下一條，機器人要經(jīng)過幾個障礙物拐角點，拐角點用小圓表示， 通過附錄一、附錄二的坐示，算出每一條線段的值，運用線畫結(jié)構(gòu)畫出簡單明了 圖7,用解析幾何建立此模型。由O (x, y)為起點，經(jīng)過以H1(x1, y1), H (x2, y2), H 3(x3, y3) H 4(x4, y4)為圓心的小圓，指定C (x5,y5)為目標點，D,E經(jīng)過以半徑為r (r 10), Hr%

23、圓心的拐角圓上的切 點D1E1是以半徑為r(r 10)H2為圓心的小圓弧上的切 點，D2,E2是以H3為圓心，半徑為r (r 10)上的切點，D3,E3是以H 4為圓心，半徑為r(r 10)的圓上的切點。圓心 的坐標為 Hi 410,100，H 2 500,200，H 3 720,520，H 4 720,600令OH2a,OH1b,h1h22H1MC,H1H3a1, H 2 H 32M1H2 c1,H1H4a2 ,H2Ca3,H3H4E2 D3bnH4CC2, H 3Ca4.OH1H2 ,OH1D,MH1E,EH 1D,H1H2H31,MH 2D11,M1H2E11, D1H2E1,H1H3H

24、 42,M1H3D22 ,H1H3H22,D2H 3E22 ,H2H3C3， H3H4C 3, CH4E33, EH4D33, E2H3H4D3H4H3.2設(shè)ODEM L1, MO1E1M1 L2,M 1D2E2D3 L3,CE3E2D L4.設(shè)O點到 C點的最短距離為 Lc， 求LOC的長度。方程如下：M點是圓H1與圓H2的公切線與圓心距的交點，所以點 M (X0,y。),即X。y。X2X12y2 %2同理可得X6y2y32M1( X6, y6),即M點是圓H2與圓H3的公切線與圓心距的交點，所以點a、:(X2X)2(y2y)2bjr,(X1X)2(y1y)2c(X2X1)2(y2y )2a

25、1.(X3X1)2(y3yj2b1.(X4X3)2(y4y3)2.(X3X2)2(y3y2)2a2/(X4X1)2(y4y2C2.(X5X4)2(y5y4)2a3.(X5X2)2(y5y2)2a4,(X5X3)2(y5y3)2解得 a=538.5165b=422.0190c=134.5362a1 =522.0153b1 =80c1 =388.3298a2 =588.3026 C2 =44.7214 a3 =483.3218 a4 =121.6553在0比出中： 2 2 2b c -aarccos1462bc在 Rt ODH1 中：r “ arccos 77b在Rt MH1E中：2r “ arc

26、cos82c2 -55Lir =498.0156在 H,H2H3 中:在 Rt MDiH 2中:在 Rt M1E1H2 中:2 2 2c C1 - a11-1722c&2r arccos一 81c2r “arccos 87carccos4L2H1H3H4 中:r 11 -1 - 1261.1257在 Rt M1D2H3中:H1H2H3中 : 2L3H3H4C 中:arccos2a1b12r ”arccos82c222a1c1carccos2a1c1-422r 2281.2339b222c - a4arccos2b1c222b132 a2a/ b2144在 Rt CE3H4中:arccos-77

27、C23 2 - 33 2 312L4. C2 -r403r50.5668Loc Li L2 L3 L 498.0156 261.1257 281.2339 50.5668 1090.9424通過matlab軟件計算(見附錄九),1到90余弦函數(shù)值(見附錄四)，解得O 到目標點B的最短距離為1090.942。模型二、根據(jù)題意的分析和以上模型的結(jié)論。從 OB CO 的最短路 徑?？偟淖疃搪窂綖?OA+AB+BC+CO , OB的距離等于OA+AB , SO=OB+BC+CO 從圖1中不難看出，B到 C距離最短路徑，經(jīng)過的障礙物的拐角點用線性圓表示， 通過附錄一、附錄二的坐標，算出每一條線段的值，采

28、用解析幾何解出B到C的距 離。建立以下模型。以B(x, y)為起點，C (X6,y6)為目標點，D, E經(jīng)過半徑為r (r 10)，圓心為H)的的拐角小圓弧的切點，D1E1為經(jīng)過半徑為r(r 10),圓心為的拐角小圓弧的切點，D2 E2為經(jīng)過半徑為r(r 10),圓心為H2(X3,y3)的拐角小圓弧切點，D3, E3為經(jīng)過半徑為r (r 10),圓心為H3(X4,y4)的拐角小圓弧的切點，D4E4為經(jīng)過半徑為r (r 10)，圓心為H3&4,yj的拐角小圓弧的切點。H 270,680，H 1 370,680，H 2 430,680，H 3 540,730，H 4 670,730令 BH1 a,

29、BH2 b, HH1 c, HH231,H1H 2 E1D1C1, H1 H 3b1, H2H3b2,H2H432, H3H4E3 D3C2, H 3 C33, 1H4Cb, BHH1,BHE ,MHD ,DHEHH1H21, MH1D11, EH1H21 匚，DiH1E121, H1H2H 32,M1H2 E22, DH2 H 1 2 ,D2 H 2 E222 ,H2H3H43,M1H 3 D33, E3H3H 43,D3H3E33, H3H4C4, CH4E44,D4 H 4H 34,D4 h4 e44,設(shè) L122BEDM,L2MD1E1D2, L3 D2E2E2M1 , L4M1D3E

30、3D4, L5D4E4E4C,求 B到 C的最短距離。M點是圓H與圓Hi的公切線與圓心距的交點，所以點 M （Xo,y。）,即xX1X22 同理可得Md%,%)y1y2X7y7X3X42y3y42a.(X2X)2(y2y)2b匚（X1X)2(y1y)2cJ(X2X1)2(y2yj2a1.(X3X1)2(y3yj2b1(X4X2)2(y4y2)2c1.(X3X2)2(y3y2)2a2.(X5X3)(y5y3)2b2(X4X3)2(y4y3)2C2.(X5X4)2(y5y4)2a3.(X6X4)2(y6y4)2b3.(X6X5)2(y6y5)2y。a=270.7397b=117.1724c=100

31、.解得a1 =220d =177.2005 =120a2=186.8154b2 =70.7107 C2=130 a3 =183.5756 b3 =94.8683BHH1 中:2 2 2b c a “c arccos1222bc在Rt BEH中:在D1DH中:r arccos b2r arccos c878550L1.b2 r2351.6439在HHM2中:2carccos2cc2 2埜 105在Rt MD1H1 中:arccos2185ceh1h2L2Gr 190.4667在HM2H3中:arccos1352b2&在Rt M1E2H2中:2r arccosb274Di H 2H i906144

32、.552832 222在 H2H3H4中:arccos22空土 1352b2c2在Rt M1D3H2中:arccos 弐 74b2E3H3H4L461C2174.5528在H3H4中:2C24 arccos.22b3 -a3712c?b3在Rt CE4H4中:rarccos 84b3D4H4H34115223 -r114.4009L1L2L3L4 L5351.6429 190.4667 44.5528 174.5528 114.4009875.6171通過matlab軟件計算（見附錄十），1到90余弦函數(shù)值（見附錄四）,解得B到目標點C的最短距離為114.4009。綜合上述，經(jīng)過網(wǎng)上查資料得到

33、此模型，從復(fù)雜的障礙物拐角點，轉(zhuǎn)換成線圓和 點，采用最短路徑，解析幾何，障礙路徑解得每條最短路徑，從CKL4CO最短距離，SO =OB+BC+COSo = Lob + Lbc + Lco =876.6322+875.6171+1090.942=2843.1693從OL 4CO 最短距離為2843.1693。模型三、根據(jù)已知分析，模型一、模型二的結(jié)論基礎(chǔ)上，我們對問題三進行 分析與求解，機器人從O(0, 0)出發(fā)，到達A的最短時間路徑，從平面圖形分析， 采用線段定理和三角形定理進行建立模型，如圖7,有二種方案，第一種方案是OMA第二種方案是ONA在圖形周圍也有障礙物，根據(jù)已知提供的坐標數(shù)據(jù)， A

34、(300,300)、M(80, 210)、N(230、60)，第6障礙物的左下角的坐標為 (60, 300)， 第4障礙物的左下角的坐標為(280,100),距M點上的障礙物(見附錄一)的距離70, N到第4障礙物的距離為50,機器人在O點出發(fā)到達A點的過程與時間和速度，機器 人轉(zhuǎn)彎半徑有關(guān)。所以建立以下模型：但是機器人直線行走的最大速度為v05個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為 v v()盤嚴，其中 是轉(zhuǎn)彎 半徑。如果超過該速度，機器人將發(fā)生1 e側(cè)翻，無法完成行走。M點與第6障礙物時，機器人的轉(zhuǎn)彎半徑最大取 35個單位，最小取10個單位 根據(jù)最大轉(zhuǎn)變公式：V v( ),=35 時，V

35、。51 ev v（35） -r10 0.1*351 eV= -331.9893所以Vm的速度小于Vo個單位，機器人轉(zhuǎn)變半徑可以取 35個單位.機器人將不會發(fā)生側(cè)翻。N點與第4障礙物時，機器人的轉(zhuǎn)彎半徑最大取 25個單位，最小取10個單位。 根據(jù)最大轉(zhuǎn)變公式：/ V。V V（）贏廠，=25 時，Vo 51 e5v v（2J）亍10 0.1*2g1 eVn= -0.0353 （見附錄三）所以Vm的速度小于V。個單位，機器人轉(zhuǎn)變半徑可以取 25個單位.機器人將不會發(fā)生側(cè)翻。此模型采用長線短的距離大于短線段的距離， 在三角形中，兩邊之和大于第三邊， 兩邊差小于第三邊。機器人經(jīng)過二條不同的路徑到達同一個

36、 A點時，用相同的時 間，直線速度相同，轉(zhuǎn)彎時，半徑越大，速度越快。 VmVr半徑。設(shè)機器人的速 度為平均速度。根據(jù)已知各個點的坐標為 A（300,300）、M（80, 210）、N（230、60）、T（80, 60）、 W（230，60）、Z（300，60）障礙物的坐標見附錄二。算出 OM MA ON NA在圖10中可以看出，OTMR MJAV OWNKNZAS是一個矩形，對邊相等， OT=80 MT=210 MJ=220 AJ=90, OW=230 WN=60 NZ=7Q AZ=24QOM= MT2 OT2，2102802 =224.7221MA= MJ 2AJ22202902 =237.

37、6973ON= OW2WN22302602 =237.6973NA= NZ2AZ2,7022402 =250計算出四條線段的值。我們采用 Dijkstra算法進行比較。采用了 MATLAB軟件 進行計算。計算過程見附錄十一，得到以下模型。依據(jù)題目的分析，如圖 11；1、給起始點Oi標以（0，s）,表示從Oi到Oi的距離h為0，Oi炎起始點。2、 這時已標定點集合匸Oi，未標定點的集合 J=M2,N3,A4，弧集合 （ Oi,Oj ）| Oi I,Oj J= （ Q，M2 ），（ Oi，N3） ，G2=OM,Ci3=ON,C32=MA, C34=NA.并有SM2l1 c12 0 224.7221

38、 224.7221Sn3 l1 c13 0 237.6973 237.6973Min( S1M 2，S 1N3 )= SiM 2 =224.7221得到一個向量集合的比較，S1M2 =224.7221路徑最短。3、已標定點集合I= N3，未標定點的集合J=M2，N3，A4，弧集合 ( Ni,Nj)I Ni I,Nj J= ( N3，M2 )，( N3，A) ，并有SN3M 2l1c320237.6973237.6973SN 3A4l1C340250250Min( SN 3M 2,N 3A4)= SN3M2=237.6973所以 min=OM+MA= 224.7221+237.6973=462.

39、4194 min=ON+OA= 237.6973+250=487.6937 OA=OM+MA= 462.4194O為最短時間路徑。六、模型檢驗根據(jù)題目的分析， 我們得到最短路徑模型， 在若干個不規(guī)則的障礙物的區(qū)域 中，按照線圓結(jié)構(gòu)畫出從起始點到目標點的路徑圖 1 轉(zhuǎn)換成流程圖 12，按節(jié)點 均是出發(fā)點和目標點到圓弧的切線和圓弧與圓弧之間的切線轉(zhuǎn)化而成。 路徑幾量 （見附錄十二）1、檢驗切線兩個端點是否在障礙物內(nèi)部。2、檢驗切線是否障礙物的對角線相交。3、檢驗圓弧所對應(yīng)的圓心，即障礙物的頂點到切線的距離是否小于10。如果以上三種情況滿足其一， 我們規(guī)定對應(yīng)這段切線的頂點為無窮大。 此模型有 一定

40、的局限，圖形較復(fù)雜，數(shù)據(jù)較復(fù)雜。最后依據(jù)解析幾何和 Dijkstra 算法求 得最短路徑。在這個模型中， 還可以運用管理運籌學(xué)中的動態(tài)規(guī)劃中多級決策變 量算出最短路徑，也可以網(wǎng)絡(luò)圖論算出最短路徑。七、模型評價模型優(yōu)點：1 、運用多個方案對路徑進行比較，在相對比較中得最優(yōu)解。2、此模型運用解析幾何，障礙路徑。進行解決。3、模型簡單易懂，便于實際應(yīng)用以生活中。模型缺點： 1、障礙物較多，且形狀不規(guī)則，路徑較多，計算量大。精確度不高。2 、此模型只作參考。具體的根據(jù)實際情況算。3、圖形復(fù)雜，字母較多。八、模型推廣本文是根據(jù)機器人的轉(zhuǎn)彎和最短路徑問題， 建立最短路徑模型。 此模型在生 活中運用廣泛，如

41、生活中開車，要達到某一個目的地時，遇到了障礙物，如何在 轉(zhuǎn)彎中走得最快、 又走最短路徑， 而且不出事故。 此模型可以推廣到任何一個開 車司機，運用到抬東西過轉(zhuǎn)角，不碰障礙物。生活中賽車比賽。參考文獻1 、ISBN978-7-04-028387-7/ 韓伯棠/ 管理運籌學(xué) / 北京市西城區(qū)德外大街4 號 / 北京高等教育出版社 /2010 年 1 月第三版、ISBN7-302-04088-5/ 劉滿鳳、傅波、聶高輝 / 運籌學(xué)模型與方法教程 / 清華大學(xué)/清華大學(xué)出版社 /2001 年 2月第一次出版、ISBN7-04-008703-0/ 侯風(fēng)波/ 高等數(shù)學(xué) /北京市東城區(qū)沙灘后街 55號/ 北

42、京高等教育出版社 /2000 年 8 月第一版、ISBN978-7-04-011944-2/ 姜啟源、謝金星、葉俊 / 數(shù)學(xué)模型 / 北京市西 城區(qū)德外大街 4號/北京高等教育出版社 /2003 年 8月第三版、 ISBN 7-302-05545-9/TP ?3268/D.Hanselman,B.Littlefield/MATLAB6/ 清華大學(xué) / 清華大學(xué)出版社 /2002 年 6 月第一版、百度文庫 /機器人行走問題 /2012 年 9月 7日、張昊、羅文廣、臧慶凱 /基于動態(tài)規(guī)劃算法的機器人避障路徑研究 /2011 年 04期/ 廣西工學(xué)院學(xué)報 /附錄附錄附錄二、編號障礙物名稱左下頂點

43、坐標其它特性描述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)上頂點坐標(150, 435)，右下頂點坐標(235, 300)7長方形(0, 470)長220，寬608平行四邊形(150, 600)底邊長90,左上頂點坐標(180, 680)9長方形(370, 680)長60，寬12010正方形(540, 600)邊長13011正方

44、形(640, 520)邊長8012長方形(500, 140)長300，寬60坐標附錄三、Dijkstra算法是用于每條弧的賦權(quán)數(shù)Cij都大于等于零的情況，也是雙標號法。是對圖中的點Uj賦予兩個標號(Lj,Kj),第一個標號Lj表示從起點Us到Uj的最短路的長度，第二個標號 Kj 表示在 Us 到 Uj 的最短路上 Uj 前面一個鄰點 的下標，從而找到Us到Uj的最短路及Us到Uj的距離。附錄四、 余 玄 函 數(shù) 表430.731354860.069756510.999848440.71934870.05233620.999391450.707107880.034899530.99863460.

45、694658890.017452440.997564470.681998900.50.996195480.66913160.994522490.65605970.992546500.64278880.990268510.6293290.987688520.615661100.984808530.601815110.981627540.587785120.978148550.573576130.97437560.559193140.970296570.544639150.965926580.529919160.961262590.515038170.956305600.5180.95105761

46、0.48481190.945519620.469472200.939693630.45399210.93358640.438371220.927184650.422618230.920505660.406737240.913545670.390731250.906308680.374607260.898794690.358368270.891007700.34202280.882948710.325568290.87462720.309017300.866025730.292372310.857167740.275637320.848048750.258819330.838671760.241

47、922340.829038770.224951350.819152780.207912360.809017790.190809370.798636800.173648380.788011810.156434390.777146820.139173400.766044830.12186941 0.7547142 0.74314584 0.10452885 0.0871557附錄五、 matlab 軟件計算 x1=300;x2=0;x3=0;x4=80;x5=80;x6=300;y1=300;y2=0;y3=0;y4=210;y5=210;y6=300;a=sqrt(x1-x2)A2+(y1-y2

48、)A2)b=sqrt(x4-x3F2+(y4-y3F2) c=sqrt(x6-x5)A2+(y6-y5)A2) a =424.2641b =224.7221c =237.6973 x=acos(bA2+cA2-aA2)/2*b*c)x =-22.0841i r=10; s=acos(r/b);s =1.5263 s1=acos(r/c)s1 =1.5287 a1=2*pi-x-s1a1 =1.6129 +22.0841i a2=sqrt(bA2-rA2)+sqrt(cA2-rA2)+r*a1 a2 =4.7812e+002 +2.2084e+002i 附錄六、 matlab 軟件計算 x=0;

49、x1=230;x2=300;y=0; y1=60; y2=300; a=sqrt(x2-x)A2+(y2-y)A2)a =424.2641 b=sqrt(x1-x)A2+(y1-y)A2)b =237.6973 c=sqrt(x2-x1)A2+(y2-y1)A2)c =250 x=(bA2+cA2-aA2)/(2*b*c)x =-0.5 b=237.6973; c=250; q=0.5735;r=10; L=sqrt(bA2-rA2)+sqrt(cA2-rA2)+r*qL =493.0218133附錄七、 matlab 軟件計算 x5=300; x6=220; x9=150; x12=100;

50、 y5=300; y6=530; y9=600; y12=700; a=sqrt(x9-x5)A2+(y9-y5)A2) a =335.4102 b=sqrt(x9-x6)A2+(y9-y6)A2) b =98.9949 c=sqrt(x6-x5)A2+(y6-y5)A2) c =243.5159 d=sqrt(x12-x6)A2+(y12-y6)A2)d =208.0865 e=sqrt(x9-x12F2+(y9-y12F2)e =111.8034x=(bA2+cA2-aA2)/(2*b*c)x =-0.8993 r=10;x=(r/c)x =0.0833f=sqrt(x5+x9)/2)-x

51、6)A2+(y5+y9)/2)-y6)A2) f =80.1561 x=r/fx =0.1248 x=(bA2+eA2-dA2)/(2*b*e)x =-0.9487 x=r/ex =0.0894 x=r/fx =0.1248 x=sqrt(eA2-rA2)x =111.3553 附錄八 、 matlab 軟件計算 x1=230; x2=220; x3=150; x4=100; y1=60; y2=530; y3=600; y4=700; a=sqrt(x2-x)A2+(y2-y)A2) a =573.8313 b=sqrt(x1-x)A2+(y1-y)A2) b =237.6586c=sqrt

52、(x2-x1)A2+(y2-y1)A2)c =470.1064sa1=sqrt(x3-x1)A2+(y3-y1)A2)a1 =545.8938b1=sqrt(x3-x2)A2+(y3-y2)A2)b1 =98.9949c1=sqrt(y4-x3)A2+(y4-y3)A2)c1 =559.0170 a2=sqrt(y4-x2)A2+(y4-y2)A2) a2 =509.2151a =573.8313;b =237.6586;c = 470.1064;r=10;c =470.1064;b1 =98.9949;c1 =559.0170;a2 =509.2151;x=(bA2+cA2-aA2)/(2*

53、b*c)x =-0.2318 e=r/be =0.0421L=sqrt(bA2-rA2)+c+r*dL =717.5155L1=(cA2+b1A2-a1A2)/(2*c*b1)L1 =-0.7220L2=sqrt(b1/2)A2-rA2)+r*dL2 =569.568x=(b1A2+c1A2-a2A2)/2*b1*c1)x =0.21P=r/c1P=0.0179 r2=2*r/b1 r2 =0.2020a2=sqrt(b1/2)A2-rA2)+sqrt(c1A2-rA2)+r*d a2 =607.5783附錄九、 matlab 軟件計算 x=0; x1=410; x2=500; x3=720; x4=720; x5=700; y=0; y1=100; y2=200; y3=520; y4=600; y5=640; a=sqrt(x2-x)A2+(y2-y)A2)a =538.5165 b=sqrt(x1-x)A2+(y1