數(shù)學(xué)建模 機(jī)器人避障問(wèn)題.doc

《數(shù)學(xué)建模 機(jī)器人避障問(wèn)題.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)學(xué)建模 機(jī)器人避障問(wèn)題.doc（16頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、機(jī)器人避障問(wèn)題 機(jī)器人避障問(wèn)題 一、摘要 本文討論了機(jī)器人在平面場(chǎng)景中避障行走的問(wèn)題，已知機(jī)器人的行走模式（直線與相切圓?。┮约皥?chǎng)景障礙物的分布，計(jì)算出到平面各個(gè)給定點(diǎn)的最短路徑，以及到A點(diǎn)的最短時(shí)間。 文中，首先，考慮到機(jī)器人與障礙物之間有10個(gè)單位的碰撞距離，故用CAD軟件將平面場(chǎng)景圖進(jìn)行改進(jìn)，再用CAD設(shè)計(jì)可能的最短路徑。接著，對(duì)每條具體路徑進(jìn)行分解，得到三種基本線圓形模型（點(diǎn)圓模型，雙圓異側(cè)模型，雙圓同側(cè)模型），對(duì)這三種模型進(jìn)行求解，得到各個(gè)模型直線長(zhǎng)度以及轉(zhuǎn)彎圓弧圓形角的表達(dá)公式。之后，參照具體的行走路徑，構(gòu)造合適的行走矩陣，用以判斷每段路徑所屬的基本模型。路徑總的長(zhǎng)度可用如

2、下公式表達(dá)： 最后，通過(guò)計(jì)算設(shè)計(jì)的集中可能的最短路徑，我們得到每段的最短路徑的長(zhǎng)度分別為： O——A路段：471.0372（單位）； O——B路段: 853.7001（單位）； O——C路段: （單位）； O——A——B——C——O路段: （單位）。 對(duì)于問(wèn)題二，我們?cè)趩?wèn)題一的基礎(chǔ)上分別利用直線最大速度和轉(zhuǎn)彎最大速度計(jì)算出時(shí)間的表達(dá)式。為了方便計(jì)算，我們將轉(zhuǎn)彎圓弧的圓心定在P（80,210）（場(chǎng)景中正方形5的左上角），這樣得到時(shí)間T與轉(zhuǎn)彎半徑的函數(shù)關(guān)系式： 通過(guò)MATLAB編程，畫出其圖像，求解得出：當(dāng)半徑=11.435時(shí)，時(shí)間T最小，其大小為94.5649（秒）。 關(guān)

3、鍵詞：最短路徑 線圓模型 行走矩陣 MATLAB 二、問(wèn)題重述 在一個(gè)800800的平面場(chǎng)景圖（見(jiàn)附錄一），在原點(diǎn)O(0, 0)點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面場(chǎng)景范圍內(nèi)活動(dòng)。圖中有12個(gè)不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表： 編號(hào) 障礙物名稱 左下頂點(diǎn)坐標(biāo) 其它特性描述 1 正方形 (300, 400) 邊長(zhǎng)200 2 圓形 圓心坐標(biāo)(550, 450)，半徑70 3 平行四邊形 (360, 240) 底邊長(zhǎng)140，左上頂點(diǎn)坐標(biāo)(400, 330) 4 三角形 (280, 100) 上頂點(diǎn)坐標(biāo)(345, 2

4、10)，右下頂點(diǎn)坐標(biāo)(410, 100) 5 正方形 (80, 60) 邊長(zhǎng)150 6 三角形 (60, 300) 上頂點(diǎn)坐標(biāo)(150, 435)，右下頂點(diǎn)坐標(biāo)(235, 300) 7 長(zhǎng)方形 (0, 470) 長(zhǎng)220，寬60 8 平行四邊形 (150, 600) 底邊長(zhǎng)90，左上頂點(diǎn)坐標(biāo)(180, 680) 9 長(zhǎng)方形 (370, 680) 長(zhǎng)60，寬120 10 正方形 (540, 600) 邊長(zhǎng)130 11 正方形 (640, 520) 邊長(zhǎng)80 12 長(zhǎng)方形 (500, 140) 長(zhǎng)300，寬60 在圖中的平面場(chǎng)景中，

5、障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)（要求目標(biāo)點(diǎn)與障礙物的距離至少超過(guò)10個(gè)單位）。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧是機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個(gè)或多個(gè)相切的圓弧路徑組成，但每個(gè)圓弧的半徑最小為10個(gè)單位。為了不與障礙物發(fā)生碰撞，同時(shí)要求機(jī)器人行走線路與障礙物間的最近距離為10個(gè)單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機(jī)器人無(wú)法完成行走。 機(jī)器人直線行走的最大速度為 個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為 ，其中 是轉(zhuǎn)彎半徑。如果超過(guò)該速度，機(jī)器人將發(fā)生側(cè)翻，無(wú)法完成行走。 現(xiàn)需建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避

6、障最短路徑和最短時(shí)間路徑的數(shù)學(xué)模型。對(duì)場(chǎng)景圖中4個(gè)點(diǎn)O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計(jì)算： (1) 機(jī)器人從O(0, 0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑。 (2) 機(jī)器人從O (0, 0)出發(fā)，到達(dá)A的最短時(shí)間路徑。 并要求給出路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的總距離和總時(shí)間。 三、模型假設(shè) 1、假設(shè)機(jī)器人可看做一個(gè)質(zhì)點(diǎn)，不考慮其實(shí)際大??； 2、假設(shè)機(jī)器人能夠準(zhǔn)確的按照設(shè)計(jì)的路線行走行走，在其行走中不發(fā)生任何突發(fā)事故； 3、機(jī)器人以最大速度行駛，在轉(zhuǎn)彎過(guò)程中

7、沒(méi)有發(fā)生側(cè)翻，速度發(fā)生突變，不考慮加速減速。 四、符號(hào)說(shuō)明 ：圓到圓圓心的距離； ：機(jī)器人經(jīng)過(guò)的第i個(gè)圓弧的圓心角； ：第i段直線多對(duì)應(yīng)的圓心角 ：圓的半徑； ：機(jī)器人經(jīng)過(guò)的第i段直線的長(zhǎng)度； S:行走路徑的總的長(zhǎng)度； T：機(jī)器人行走的總的時(shí)間 N：機(jī)器人行走經(jīng)過(guò)的總點(diǎn)數(shù)（包括起點(diǎn)終點(diǎn)以及轉(zhuǎn)彎圓弧的圓心）； A：行走矩陣。 五、模型建立 對(duì)于該題建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時(shí)間路徑的數(shù)學(xué)模型的研究，主要是用盡可能短的路徑和時(shí)間避開障礙物到達(dá)目標(biāo)點(diǎn)。根據(jù)題目中的要求可知，機(jī)器人行走線路與障礙物間的最近距離為10個(gè)單位，否則將發(fā)生碰撞，若碰撞

8、發(fā)生，則機(jī)器人無(wú)法完成行走，故可把各障礙物的邊界擴(kuò)大10單位。利用CAD軟件制圖可在距每個(gè)障礙物的邊緣10個(gè)單位處添加外邊框，形成新的屏障，特別注意的是在障礙物頂點(diǎn)處使用圓弧。機(jī)器人就可在新屏障外的范圍內(nèi)隨意活動(dòng)，不用擔(dān)心發(fā)生碰撞，根據(jù)原圖修改后的圖形見(jiàn)下圖1。 C(700, 640) B(100, 700) A（300,300） 圖1 機(jī)器人行駛路線是由直線段和圓弧組成。機(jī)器人從O(0, 0)出發(fā)，建立數(shù)學(xué)模型求得O→A、O→B、O→C和O→A→B→C→O的最短路徑?，F(xiàn)將各個(gè)路段的情況進(jìn)行綜合分析，根據(jù)每個(gè)路段所遇到的情況，從起始點(diǎn)到目標(biāo)點(diǎn)的最短距離應(yīng)該是直線段與圓弧組成，

9、由已知的數(shù)學(xué)知識(shí)，兩點(diǎn)之間線段最短，故機(jī)器人走的直線越多，路徑越短，也就是說(shuō)當(dāng)機(jī)器人繞過(guò)障礙物的時(shí)候，半徑越小，路徑越短，根據(jù)題意，轉(zhuǎn)彎半徑可按最小半徑10來(lái)計(jì)算，經(jīng)過(guò)分析，可建立如下三個(gè)線圓模型。 模型一：（點(diǎn)圓模型） 該模型主要求解——的路徑長(zhǎng)度，該路徑只有一個(gè)轉(zhuǎn)彎，由圖2易知，，C、D均為直線與圓的切點(diǎn)，CD為圓弧，為圓弧對(duì)應(yīng)的圓心角的大小，根據(jù)已積累的知識(shí)，圓弧的長(zhǎng)度為圓弧對(duì)應(yīng)的圓心角與圓半徑的乘積，即，同時(shí)利用余弦定理 ，即可求得總距離為： S=； 其中 = C 圖2 D 模型二：（雙圓異側(cè)模型） 該模型是為了計(jì)算——的距離，從

10、起始點(diǎn)到目標(biāo)點(diǎn)經(jīng)過(guò)圓弧異側(cè)拐彎（如圖3），根據(jù)已知點(diǎn)、、、可求得的長(zhǎng)度。，AB、CD為兩段圓弧，、為其對(duì)應(yīng)的圓心角，BC與的交點(diǎn)E是這兩條線段的中點(diǎn)，根據(jù)兩個(gè)全等三角形以及勾股定理，可求得BC長(zhǎng)度。 其中， E A D C B 圖3 模型三：（雙圓同側(cè)模型） 該模型是為了計(jì)算——的距離，從起始點(diǎn)到目標(biāo)點(diǎn)經(jīng)過(guò)圓弧同側(cè)拐彎（如圖4），添加輔助線，連接、，運(yùn)用幾何知識(shí)輕易能夠證明。由圖4易知,可以根據(jù)已知點(diǎn)的坐標(biāo)求出所需線段的長(zhǎng)度，進(jìn)而求得起始點(diǎn)到目標(biāo)點(diǎn)的總距離。 其中， 圖4 D E F C 綜合模

11、型： 在實(shí)際情況中，機(jī)器人所走的路線是以上三種模型的結(jié)合。設(shè)計(jì)好機(jī)器人的行走方案，可根據(jù)設(shè)計(jì)好的方案構(gòu)建行走矩陣，構(gòu)建方法如下： i段為模型1 i段為模型2 i段為模型3 i段為模型1 i段為模型2 i段為模型3 則i段的直線長(zhǎng)度為： 其中i=1,2…N-1; 第i段與i+1段之間的轉(zhuǎn)彎圓弧所對(duì)應(yīng)的的圓心角為： 其中i=1,2…N-2； i段為模型1 i段為模型2 i段為模型3 機(jī)器人行走的總的長(zhǎng)度為： 六、模型求解 問(wèn)題（1）： 根據(jù)所建立的數(shù)學(xué)模型，用CAD畫出可能的最短路徑，構(gòu)建每條路

12、線的行走矩陣，通過(guò)MATLAB編程計(jì)算出每天路線的實(shí)際長(zhǎng)度，從而得到最短路徑。 1、O——A路段，這是四個(gè)路段中最簡(jiǎn)單的情況，從O到A經(jīng)過(guò)了一個(gè)轉(zhuǎn)彎，從圖5中易看出有兩種方案，虛線與實(shí)線各代表一個(gè)方案。 A（300,300） （80,60） （0,0） 圖5 利用MATLAB編程求解，計(jì)算結(jié)果如下： 機(jī)器人從O到A的行走路線長(zhǎng)度為471.0372； 同理，O從下面繞到目標(biāo)點(diǎn)A的總的路線長(zhǎng)度為498.4259； 通過(guò)比較兩種方案的結(jié)果易知，機(jī)器人在點(diǎn)O從上面繞到目標(biāo)點(diǎn)A的距離最短，期最短路線長(zhǎng)度為471.0372 。 2、O——B路段，經(jīng)過(guò)分析與整理，我們得到四種方案，如

13、圖6所示①②③④，在這四種方案中，三種模型全部都要用到，模型一在O——A路段已詳細(xì)說(shuō)明，模型二就是從起始點(diǎn)到目標(biāo)點(diǎn)經(jīng)過(guò)的圓弧在所走路徑的異側(cè)，而模型三就是從起始點(diǎn)到目標(biāo)點(diǎn)經(jīng)過(guò)的圓弧在所走路徑的同側(cè)，從O——B路段，有多次轉(zhuǎn)彎，具體見(jiàn)圖6。 B（100,700） O（0,0） ④ ③ ② ① 圖6 就①路線而言，機(jī)器人經(jīng)過(guò)了五次轉(zhuǎn)彎，根據(jù)三種模型中的理論公式，需要把各個(gè)圓弧與直線長(zhǎng)度求得，可利用MATLAB軟件對(duì)其進(jìn)行編程。計(jì)算結(jié)果如下： ①路線機(jī)器人行走的總距離為853.7001； ②路線機(jī)器人行走的總距離為877.3841； ③路線機(jī)器人行走的總距離為990

14、.1608； ④路線機(jī)器人行走的總距離為； 經(jīng)過(guò)比較可得①路線為最短路徑，即機(jī)器人在點(diǎn)O從上面繞到目標(biāo)點(diǎn)B的距離最短，期最短路線長(zhǎng)度為853.7001 。 3、O——C路段，經(jīng)過(guò)整理分析，我們得到四種方案，具體見(jiàn)圖7， O（0,0） ④ ③ ② ① C （700,640） 圖7 每條路線都是由圓弧與直線段，但是該路段與其他路段相比，又有其不同之處，在③路線中有一部分是在兩個(gè)不同大小的圓的異側(cè)和同側(cè)（如圖8，圖9所示） 圖8 A E B 就圖8容易看出， ， 圖9 E B A 就圖9容易得出，

15、 ， 利用MATLAB軟件對(duì)其進(jìn)行編程。計(jì)算結(jié)果如下： ①路線機(jī)器人行走的總距離為； ②路線機(jī)器人行走的總距離為 ； ③路線機(jī)器人行走的總距離為； ④路線機(jī)器人行走的總距離為； 顯而易見(jiàn)，經(jīng)過(guò)比較可得④路線為最短路徑，即機(jī)器人在點(diǎn)O從上面繞到目標(biāo)點(diǎn)C的距離最短，其最短路線長(zhǎng)度為。 4、O——A——B——C——O路段，這一路段需要結(jié)合之前求得的最短路徑，當(dāng)機(jī)器人在A、B、C轉(zhuǎn)彎時(shí)，為確定其路徑最短，既使A點(diǎn)處在機(jī)器人的轉(zhuǎn)彎圓弧上，我們?cè)O(shè)立了如圖11的路徑，并計(jì)算出轉(zhuǎn)彎圓弧的圓心。 A O 圖10 由圖易算出轉(zhuǎn)彎圓弧的圓心坐標(biāo)為： 圖1

16、1 A（300,300） O（0,0） C(700, 640) B(100, 700) 需要注意的是，在C點(diǎn)附近，由于其位置的特殊性，原有的線圓模型不能很好的處理，我們采用兩段相切圓弧的線路。 利用MATLAB軟件對(duì)其進(jìn)行編程。計(jì)算結(jié)果如下： 機(jī)器人行走的總距離為 問(wèn)題（2） 機(jī)器人從O (0, 0)出發(fā)，求得到達(dá)A的最短時(shí)間路徑。通過(guò)問(wèn)題（1）中對(duì)各個(gè)路段最短路徑的求解，我們可以做出合理假設(shè)：機(jī)器人轉(zhuǎn)彎圓弧的圓心在點(diǎn)P（80,210）的位置，而半徑我們?cè)O(shè)為。由問(wèn)題（1），可以得到機(jī)器人從O點(diǎn)到A的時(shí)間為（參照模型一）： 其中為長(zhǎng)度，為長(zhǎng)度，為長(zhǎng)度，為，由于圓心

17、固定，其值為固定值。通過(guò)MATLAB編程，得到的函數(shù)圖象如下圖所示： 從圖中可以看出，當(dāng)半徑=11.435時(shí)，時(shí)間T最小，其大小為94.5649。 七、模型評(píng)價(jià)與推廣 優(yōu)點(diǎn)：1、該模型設(shè)計(jì)了三種基本模型，將實(shí)際線路進(jìn)行簡(jiǎn)化，從而降低了計(jì)算難度； 2、提出行走矩陣的概念，在程序中對(duì)不同模型進(jìn)行判斷，從而簡(jiǎn)化了程序，方便了計(jì)算，使得程序更具備一般性； 3、最終結(jié)果由MATLAB編程計(jì)算，計(jì)算結(jié)果真實(shí)可靠。 缺點(diǎn)：1、最短路徑的設(shè)計(jì)上有一定的主觀性，可能會(huì)與實(shí)際有所偏差； 2、在計(jì)算到A點(diǎn)最短時(shí)間時(shí)，未考慮機(jī)器人加速減速的情況，使得計(jì)算值與實(shí)際值相比偏大。 3、在計(jì)算到A點(diǎn)最

18、短時(shí)間時(shí)，為了方便計(jì)算，將轉(zhuǎn)彎圓弧的圓心確定在點(diǎn)P（80,210），模型過(guò)于簡(jiǎn)單粗糙，會(huì)與實(shí)際情況有所偏差。 八、參考文獻(xiàn) [1] 丁緒東編著，AutoCAD2007實(shí)用教程[M]，中國(guó)電力出版社，2007。 [2] 曹戈 ， 《MATLAB教程及實(shí)訓(xùn)》， 機(jī)械工業(yè)出版社 2008年5月1日。 [3] 孫祥，MATLAB 7.0基礎(chǔ)教程,北京：清華大學(xué)出版社，2005。 [4] 戴光明.避障路徑規(guī)劃的算法研究[D].華中科技大學(xué)，計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,2004。 [5]薛定宇，陳陽(yáng)泉，高等應(yīng)用數(shù)學(xué)的Matlab解．清華大學(xué)出版社．2004.183～191。 [6]馮杰，黃力偉，王琴，尹成義，數(shù)學(xué)建模原理與案例，科學(xué)出版社，2007。 附錄一 場(chǎng)景圖：