機(jī)器人避障問題模型(畢業(yè)論文)(可編輯)

1、機(jī)器人避障問題模型(畢業(yè)論文) 機(jī)器人避障問題模型 摘要 本文研究的是機(jī)器人在給定的區(qū)域中避障最短路徑和最短時間路徑的問題。 問題一:主要研究了在一個存在著12個障礙物的區(qū)域中,機(jī)器人由出發(fā)點(diǎn)到達(dá)目標(biāo)點(diǎn)以及由出發(fā)點(diǎn)經(jīng)過途中的若干目標(biāo)點(diǎn)到達(dá)最終目標(biāo)點(diǎn)的兩類情形。 一類情形是機(jī)器人從定點(diǎn)安全繞過障礙物直達(dá)目標(biāo)點(diǎn)(、或)的最短路徑。首先我們在平面圖形中用包絡(luò)線畫出了機(jī)器人行走的危險區(qū)域,這樣的話,拐角處就是一個以頂點(diǎn)為圓心,半徑為10的圓弧,然后采用拉繩子的方法尋找可能的最短路徑。并且我們通過證明具有圓形限定區(qū)域的最短路徑是由兩部分組成的:一部分是平面上的自然最短路徑(即直線段),另一部分是限定區(qū)域

2、的部分邊界,這兩部分是相切的,互相連接的。因此我們建立了線圓結(jié)構(gòu),這樣無論路徑多么復(fù)雜,我們都可以將路徑劃分為若干個這種線圓結(jié)構(gòu)來求解。我們主要采用窮舉法列出到目標(biāo)點(diǎn)的所有可能的最短路徑,比較其大小便可得出到目標(biāo)點(diǎn)的最短路徑。 另一類情形是機(jī)器人從指定點(diǎn)經(jīng)過若干個中間點(diǎn)(、及)繞過障礙物到達(dá)最終目標(biāo)點(diǎn)的最短路徑.經(jīng)討論分析,我們在拐點(diǎn)和中間點(diǎn)處都采用的是最小轉(zhuǎn)彎半徑的形式,然后建立優(yōu)化模型,最終求解出的結(jié)果為: 最短路徑:通過障礙物正方形5與三角形6之間的那條路徑,其總長為:471.04 最短路徑:通過障礙物三角形6與矩形7以及矩形7與平行四邊形8之間的路徑,其總長為:853.70 最短路徑:

3、通過障礙物5,4,3,11下方的路徑,其總長為:1093.70 最短路徑長為:2754.1 路徑中每段直線段或圓弧的起點(diǎn)與終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及總時間見表1,表2,表3。 問題二:研究的是機(jī)器人從O(0,0)出發(fā),到達(dá)A的最短時間路徑。 關(guān)鍵詞:最短路徑 最短時間 最優(yōu)化問題 1.問題重述1.1問題的背景 在一個800×800的平面場景內(nèi),原點(diǎn)O0, 0點(diǎn)處有一個機(jī)器人,它只能在該平面場景范圍內(nèi)活動。其中有12個不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物,障礙物的數(shù)學(xué)描述如下表:編號障礙物名稱左下頂點(diǎn)坐標(biāo)其它特性描述1正方形300, 400邊長2002圓形圓心坐標(biāo)550,

4、450,半徑703平行四邊形360, 240底邊長140,左上頂點(diǎn)坐標(biāo)400, 3304三角形280, 100上頂點(diǎn)坐標(biāo)345, 210,右下頂點(diǎn)坐標(biāo)410, 1005正方形80, 60邊長1506三角形60, 300上頂點(diǎn)坐標(biāo)150, 435,右下頂點(diǎn)坐標(biāo)235, 3007長方形0, 470長220,寬608平行四邊形150, 600底邊長90,左上頂點(diǎn)坐標(biāo)180, 6809長方形370, 680長60,寬12010正方形540, 600邊長13011正方形640, 520邊長8012長方形500, 140長300,寬60 在該平面場景中,障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)(要求目標(biāo)點(diǎn)與

5、障礙物的距離至少超過10個單位)。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成,其中圓弧是機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎,轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成,也可以由兩個或多個相切的圓弧路徑組成,但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞,同時要求機(jī)器人行走線路與障礙物間的最近距離為10個單位,否則將發(fā)生碰撞,若碰撞發(fā)生,則機(jī)器人無法完成行走。 機(jī)器人直線行走的最大速度為個單位/秒。機(jī)器人轉(zhuǎn)彎時,最大轉(zhuǎn)彎速度為,其中是轉(zhuǎn)彎半徑。如果超過該速度,機(jī)器人將發(fā)生側(cè)翻,無法完成行走。1.2問題的提出 請建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時間路徑的數(shù)學(xué)模型。對場景圖中4

6、個點(diǎn)O0, 0,A300, 300,B100, 700,C700, 640,具體計(jì)算: 1 機(jī)器人從O0, 0出發(fā),OA、OB、OC和OABCO的最短路徑。 2 機(jī)器人從O 0, 0出發(fā),到達(dá)A的最短時間路徑。 2.問題分析 由于機(jī)器人不能折線轉(zhuǎn)彎,轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成,也可以由兩個或多個相切的圓弧路徑組成,但每個圓弧的半徑最小為10個單位;并且機(jī)器人行走路線與障礙物間的最近距離為10個單位,否則將發(fā)生碰撞,則機(jī)器人將無法完成行走。所以我們得到機(jī)器人的路徑必由直線段和圓弧組成。于是我們可采用線圓或圓圓相切結(jié)構(gòu)進(jìn)行求解。 我們可以先用包絡(luò)線畫出機(jī)器人行走的危險區(qū)域?yàn)?將障礙物的

7、所有邊向外平移10個單位,以及以頂點(diǎn)為圓心,10為半徑的圓弧所圍成的光滑曲線。這樣的話,拐角處就是一個半徑為10的圓弧,然后采用拉繩子(無彈性)的方法尋找可能的最短路徑(比如求和之間的最短路徑,我們就可以連接和之間的一段繩子,以拐角處的圓弧為支撐拉緊,那么這段繩子的長度便是到的一條可能的最短路徑), 問題一:主要研究了在一個存在著12個障礙物的區(qū)域中,機(jī)器人由出發(fā)點(diǎn)到達(dá)目標(biāo)點(diǎn)以及由出發(fā)點(diǎn)經(jīng)過途中的若干目標(biāo)點(diǎn)到達(dá)最終目標(biāo)點(diǎn)的兩類情形。 一類情形是求定點(diǎn)按照一定的行走規(guī)則繞過障礙物直達(dá)目標(biāo)點(diǎn)(、或)的最短路徑。我們主要采用窮舉法列出到目標(biāo)點(diǎn)的所有可能的最短路徑,比較其大小便可得出到目標(biāo)點(diǎn)的最短路徑

8、。 另一類情形是求機(jī)器人從指定點(diǎn)經(jīng)過若干個中間點(diǎn)(、及)繞過障礙物到達(dá)最終目標(biāo)點(diǎn)的最短路徑,這時我們需要考慮的不僅僅是安全繞過障礙物的問題,還應(yīng)該考慮路徑中中間點(diǎn)處銜接的問題,由題意可知,相鄰兩段不能為折線,我們在中間點(diǎn)處設(shè)置的均為線圓結(jié)構(gòu), 建立起優(yōu)化模型,并求得最短路徑。 問題二: 3.模型假設(shè)及符號說明 3.1模型假設(shè): 假設(shè)1:機(jī)器人能夠抽象成點(diǎn)來處理; 假設(shè)2:問題二不考慮機(jī)器人在路線銜接處的速度變化; 假設(shè)3:問題二中機(jī)器人在行走過程中不會出現(xiàn)故障; 3.2符號說明: L:表示總距離; T:表示總時間; :轉(zhuǎn)彎半徑; 4.建模準(zhǔn)備4.1 先來證明一個猜想: 猜想一:具有圓形限定區(qū)域

9、的最短路徑是由兩部分組成的:一部分是平面上的自然最短路徑(即直線段),另一部分是限定區(qū)域的部分邊界,這兩部分是相切的,互相連接的。(即問題分析中的拉繩子拉到最緊時的狀況) 證明:假設(shè)在平面中有和兩點(diǎn),中間有一個半圓形的障礙物,證明從A到的最路徑為. 如圖折線的長度:當(dāng)減少時,的值減小.當(dāng)點(diǎn)移動到點(diǎn)時,線段和,與圓分別相切于、兩點(diǎn),則此時的值最小為:.機(jī)器人轉(zhuǎn)彎路徑由直線和與直線路徑相切的一段圓弧組成,也可以由兩個或多個相切的圓弧路徑組成。所以當(dāng)圓與線段AC、CB相切時,路徑最短。最短路徑為:. 當(dāng)路線不在障礙物邊界上,顯然比大.故繞過圓形障礙物最短的方式為. 預(yù)備一:如下圖,已知直線與圓相切于

10、點(diǎn),其中,圓的半徑為,求的坐標(biāo)。 求解如下: 在中,;于是可列方程組: 從而可求得切點(diǎn)的坐標(biāo)。4.2 模型準(zhǔn)備一 由猜想一,我們可以這樣認(rèn)為,兩點(diǎn)之間無論中間繞過幾個拐角為圓弧的障礙物,最短路徑都應(yīng)該是由若干個線圓或圓圓相切銜接而成。在本題中存在障礙物的狀況,且障礙物在頂點(diǎn)處的危險區(qū)域是一個以頂點(diǎn)為圓心,半徑為10的圓弧,所以結(jié)合猜想一,我們易知,求兩點(diǎn)之間的最短路徑中的轉(zhuǎn)彎半徑我們應(yīng)該按照最小的轉(zhuǎn)彎半徑來算才能達(dá)到最優(yōu)。解法如下: 如上圖可得有以下關(guān)系: 在中, 在中: 在中: 所以:從而可得:而對于下圖兩種情況,需要做簡單的變化后,同樣可用線圓結(jié)構(gòu)來解決。 情況一如圖: 我們假設(shè)兩圓心坐標(biāo)

11、分別為和,半徑均為r,G點(diǎn)坐標(biāo)為,那么我們很容易求得: 這樣我們就可以利用1)中的方法,先求A到G,再求G到B,這樣分兩段就可以求解。同理如果有更多的銜接,我們可以按照此種方法處理。 情況二如圖: 我們假設(shè)為起點(diǎn),為目標(biāo)點(diǎn),、均為切點(diǎn),則四邊形為矩形,即,圓心分別為、,圓的半徑為,角度, .求A到B的總長度,由圖形知,將圖形分割成兩部分:設(shè)的長度為,的長度為,A到B的總長度為L,所以A到B的總長度為:.直線的方程為: 四邊形為矩形,則,那么直線DE的方程可表示成:由于點(diǎn)到直線DE的距離等于半徑r,顯然可得: 將公切線和圓的方程聯(lián)立,可以求得切點(diǎn)和的坐標(biāo),、的長度的求解方法同上面的1).同理多個

12、這樣的轉(zhuǎn)彎時,用同樣的方法可以進(jìn)行分割。 4.3 模型準(zhǔn)備二 對于從起點(diǎn)經(jīng)過若干給定的中間點(diǎn)后到達(dá)目標(biāo)點(diǎn)的情況,因?yàn)椴荒茏哒劬€路徑,我們就必須考慮在經(jīng)過路徑中的一個目標(biāo)點(diǎn)時轉(zhuǎn)彎的狀況。為了研究這個問題的方便,我們先來證明一個猜想: 猜想二:如果一個圓環(huán)可以繞著環(huán)上一個定點(diǎn)轉(zhuǎn)動,那么過圓環(huán)外兩定點(diǎn)連接一根繩子,并以該圓環(huán)為支撐拉緊繩子,達(dá)到平衡狀態(tài)時,圓心與該定點(diǎn)以及兩條切線的延長線的交點(diǎn)共線。證明猜想: 我們可以用力學(xué)的知識進(jìn)行證明,因?yàn)槭抢o的繩子,所以兩邊的繩子拉力相等,設(shè)為,它們的合力設(shè)為,定點(diǎn)對圓環(huán)的作用力設(shè)為。 那么由幾何學(xué)的知識我們可以知道一定與共線,而又由力的平衡條件可知: -

13、即與共線。 綜上所述、和三點(diǎn)一定共線。 二、有了以上這個定理我們可以建立以下模型: 如圖4.32,要求求出機(jī)器人從A繞過障礙物經(jīng)過M點(diǎn)到達(dá)目標(biāo)點(diǎn)B的最短路徑,我們采用以下方法: 用一根釘子使一個圓環(huán)定在M點(diǎn),使這個圓環(huán)能夠繞M點(diǎn)轉(zhuǎn)動。然后連接A和B的繩子并以這些轉(zhuǎn)彎處的圓弧為支撐(這里轉(zhuǎn)彎處圓弧的半徑均按照最小轉(zhuǎn)彎半徑來計(jì)算),拉緊繩子,那么繩子的長度就是A到B的最短距離。我們可以把路徑圖抽象為以下的幾何圖形。下面我們對這段路徑求解: 圖5.32 如圖,是起點(diǎn),是終點(diǎn),和是兩個固定的圓,是一個可以繞點(diǎn)轉(zhuǎn)動的圓環(huán),三個圓的半徑均為,、均為切點(diǎn).、分別是、的長度.、均是已知點(diǎn),是未知點(diǎn)。那么最短路

14、徑就可以表示為: +因?yàn)辄c(diǎn)的坐標(biāo)未知,所以我們就不能用模型一中的線圓結(jié)構(gòu)對其進(jìn)行求解。故得先求出點(diǎn)的坐標(biāo)。設(shè),、分別為(,),、分別為、。這樣便有以下關(guān)系:在中: 在中:;在中:在中:,則: 又因?yàn)橐欢〞诘慕瞧椒志€上,所以滿足:我們采用向量的形式來求,易知的一個方向向量:而與垂直,故其一個方向向量:而:,所以 綜合以上式子可以求得的坐標(biāo),從而可以得出路徑的長為: ,這可以采用模型準(zhǔn)備一中的線圓結(jié)構(gòu)來求解。預(yù)備二: 1)如下圖,已知,正方形5的右下頂點(diǎn)的坐標(biāo)為:;三角形4的右下頂點(diǎn)坐標(biāo);與以為圓心,10為半徑的圓切于點(diǎn),求到直線的距離。解法如下: 根據(jù)預(yù)備一,可求出點(diǎn)坐標(biāo),然后求出直線的方程式

15、,最后根據(jù)預(yù)備一求得到直線的距離等于9.429510,所以機(jī)器人按直線段路線行走時,將與障礙物5發(fā)生碰撞,由此之間必有一圓弧路線。 2)如下圖,已知障礙物三角形4的右下角;正方形11的右下角;長方形12的左上角;圓,圓的半徑均為10,求到的距離。5.模型的求解5.1 問題一 1)到目標(biāo)點(diǎn)的可能路徑有兩條,如圖一所示: 機(jī)器人走上面的路徑到達(dá),直接用matlab求得最短路徑為471.04; 機(jī)器人走下面的路徑到達(dá)時,直接用matlab算得的最短路徑長為498.43. 表1起點(diǎn)坐標(biāo)終點(diǎn)坐標(biāo)圓弧圓心坐標(biāo)總距離總時間OA線段一(0,0)(70.51,213.14)471.0496.02圓弧一70.51

16、,213.1476.61,219.4180,210線段二76.61,219.41300,300 2)O到目標(biāo)點(diǎn)B的可能路徑有六條,如圖二所示: 說明:當(dāng)機(jī)器人從O點(diǎn)沿a路徑即將到達(dá)B時,分支為a1、a2兩條路徑;沿b路徑時,途中分支為b1、b2兩條路徑;沿c路徑時,途中也分支為c1、c2兩條路徑。 機(jī)器人走a1路線到達(dá)B時,這條路線由六條線段和五條圓弧組成,我們可以先找出中間四條線段的中點(diǎn)M,N,P,Q.然后利用前面的模型分別求出O到M、M到N、N到P、P到Q、Q到B的長度,然后相加,便可求出O到B的路徑長為853.70. 機(jī)器人走的a2路線實(shí)質(zhì)上就是a1路徑在經(jīng)過第三個圓弧時的分支路線,易得

17、a1和a2的路線在經(jīng)過第三個圓弧之前所走的路線長度相等,并且與第三個圓弧相切的第一個切點(diǎn)相同,此處路徑長為1337.9. 機(jī)器人走b1路線到達(dá)B時,這條路線由五條線段和四條圓弧組成,需要分四部分求解,求得路徑長為873.24. b2路線是b1路線在經(jīng)過第二個圓弧時到達(dá)B的另一個分支路線,同所述,得到路徑長為1345.20. 類似可求出走c1、c2路線時的路徑長分別為945.13,1059.60. 綜上所述,O到目標(biāo)點(diǎn)B的最短路徑長為853.70. 路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的總距離和總時間見下表2:(注:線段或圓弧順序:從下向上,從左向右;坐標(biāo)之間用逗

18、號分隔) 表2起點(diǎn)坐標(biāo)終點(diǎn)坐標(biāo)圓弧圓心坐標(biāo)總距離總時間OB線段一0,050.14,301.64853.70179.08圓弧一50.14,301.6451.68,305.5560,300線段二51.68,305.55141.68,440.55圓弧二141.68,440.55146.71,444.44150,435線段三146.71,444.44222.04,460.21圓弧三222.04,460.21230,470220,470線段四230,470230,530圓弧四230,530225.50,538.35220,530線段五225.50,538.35144.50,591.65圓弧五144.50

19、,591.65140.69,596.35150,600線段六140.69,596.35100,700 3)O到目標(biāo)點(diǎn)C的可能路徑有五條,如圖三所示: 表3起點(diǎn)坐標(biāo)終點(diǎn)坐標(biāo)圓弧圓心坐標(biāo)總距離總時間OC線段一0,0232.12,50.231093.70240.64圓弧一232.12,50.23232.17,50.24230,60線段二232.17,50.24412.17,90.24圓弧二412.17,90.24418.35,94.49410,100線段三418.35,94.49491.66,205.51圓弧三491.66,205.51492.06,206.08500,200線段四492.06,20

20、6.08727.94,513.92圓弧四727.94,513.92730,520720,520線段五730,520730,600圓弧五730,600727.72,606.36720,600線段六727.72,606.36700,6404)(注:線段或圓弧的起點(diǎn)或終點(diǎn)按OABCO依次經(jīng)過的順序)起點(diǎn)坐標(biāo)終點(diǎn)坐標(biāo)圓弧圓心坐標(biāo)總距離總時間OABC圓弧一70.51,213.1476.73,219.4580,210線段二76.73,219.45294.15,294.66圓弧二294.15,294.66300.43,307.11290.89,304.11線段三300.43,307.11229.54,532

21、.99圓弧三229.54,532.99225.49,538.35220,530線段四225.49,538.35144.50,591.65圓弧四144.50,591.65140.91,595.83150,600線段五140.91,595.8398.27,688.90圓弧五98.27,688.90108.12,703.15107.31,693.17線段六108.12,703.15270.81,689.97圓弧六270.81,689.97272,689.80270,680線段七272,689.80368,670.20圓弧七368,670.20370,670370,680線段八370,670430,6

22、70圓弧八430,670435.59,671.71430,680線段九435.59,671.71534.41,738.29圓弧九534.41,738.29540,740540,730線段十540,740670,740圓弧十670,740679.77,732.13670,730線段十一679.77,732.13699.47,641.70圓弧十一699.47,641.70701.59,637.39709.24,643.83線段十二701.59,637.39727.65,606.44圓弧十二727.65,606.44730,600720,600線段十三730,600730,520圓弧十三730,52

23、0727.94,513.92720,520線段十四727.94,513.92492.06,206.08圓弧十四492.06,206.08491.66,205.51500,200線段十五491.66,205.51418.34,94.49圓弧十五418.34,94.49412.17,90.24410,100線段十六412.17,90.24232.17,50.24圓弧十六232.17,50.24232.12,50.23230,60線段十七232.12,50.230,05.2 問題二機(jī)器人從原點(diǎn)出發(fā),到達(dá)A的最短時間路徑。分類1:路線拐一個彎時,求出走的路徑的時間1)如圖1:先按問題一中OA的兩條路線

24、計(jì)算時間對問題一中到的路線進(jìn)行分析,把拐彎處的圓,它圓心帶入編好的程序1中,改變程序中的的即轉(zhuǎn)一次彎圓弧圓心.分別得到兩條路線的時間:路線1:圓心帶入的程序1中得到路線的時間為:96.0176秒路線2:圓心帶入的程序1中得到路線的時間為:101.9136秒2)接著在考慮直線與三角形右頂點(diǎn)的圓相切,切點(diǎn)分別為,直線與圓相切于切點(diǎn)為,求所走路徑時間。設(shè)根據(jù)條件求的坐標(biāo): 解得的坐標(biāo)。在根據(jù),根據(jù)兩點(diǎn)式求直線AW為:根據(jù)直線與圓相切的性質(zhì)求的圓心角為: 路徑的時間為目標(biāo)函數(shù):拐彎的圓不與障礙物相碰約束條件:則 圓心為,時間為109.1998分類2:路線拐兩個彎時,求出走的路徑的時間。3)如圖所示,四

25、分之一的圓與直線和相切,切點(diǎn)分別為,四邊形為矩形,在快到點(diǎn)時拐個半徑為10的四分之一圓到達(dá)點(diǎn),圓心為290,300切點(diǎn)為.求路線的時間.設(shè),路線的時間t,圓的半徑,則圓心,當(dāng)圓與正方形左上頂角的圓相切時時間最短。圓與正方形障礙物左上角的圓相切時,路線用時最短:解得:或當(dāng),時會碰到障礙物舍去.時間的表達(dá)式為:把帶入表達(dá)式,得到秒最短時間為86.107,點(diǎn),點(diǎn),點(diǎn),第一次拐彎的圓心,第二次拐彎圓心。4)如圖所示 圓與直線和相切,切點(diǎn)分別為.直線還與二次拐彎的圓相切切點(diǎn)為,與豎直過點(diǎn)的直線的切點(diǎn)為.該圓半徑為,求路線的時間。則有,。由圖求路線的時間.把路線分成.二次拐彎的半徑1015205080總時間111.1853108.6153108.1853105.6053103.0253當(dāng)取最大80時最小,是103.0253綜上所述,所有情況與路徑時間情況分類1234總時間96.0176101.9136109.199886.107103.0253情況3)路徑時間最短86.107.,點(diǎn),點(diǎn),點(diǎn),第一次拐彎的圓心,第二次拐彎圓心。 6.模型評價6.1 模型的優(yōu)點(diǎn): 1本文運(yùn)用了MATLAB 6.5、LINGO 12等軟件進(jìn)行求解,使結(jié)果更加精確. 2模型中畫出了有關(guān)平面圖形,使得論文更容易理解,增加了論文的可讀性. 3用窮舉法列舉出