數(shù)學(xué)建模 機器人避障問題.doc

機器人避障問題機器人避障問題一、摘要本文討論了機器人在平面場景中避障行走的問題，已知機器人的行走模式（直線與相切圓弧）以及場景障礙物的分布，計算出到平面各個給定點的最短路徑，以及到A點的最短時間文中，首先，考慮到機器人與障礙物之間有10個單位的碰撞距離，故用CAD軟件將平面場景圖進行改進，再用CAD設(shè)計可能的最短路徑接著，對每條具體路徑進行分解，得到三種基本線圓形模型（點圓模型，雙圓異側(cè)模型，雙圓同側(cè)模型），對這三種模型進行求解，得到各個模型直線長度以及轉(zhuǎn)彎圓弧圓形角的表達公式之后，參照具體的行走路徑，構(gòu)造合適的行走矩陣，用以判斷每段路徑所屬的基本模型路徑總的長度可用如下公式表達：最后，通過計算設(shè)計的集中可能的最短路徑，我們得到每段的最短路徑的長度分別為：O——A路段：471.0372（單位）；O——B路段: 853.7001（單位）；O——C路段: （單位）；O——A——B——C——O路段: （單位）對于問題二，我們在問題一的基礎(chǔ)上分別利用直線最大速度和轉(zhuǎn)彎最大速度計算出時間的表達式為了方便計算，我們將轉(zhuǎn)彎圓弧的圓心定在P（80,210）（場景中正方形5的左上角），這樣得到時間T與轉(zhuǎn)彎半徑的函數(shù)關(guān)系式：通過MATLAB編程，畫出其圖像，求解得出：當半徑=11.435時，時間T最小，其大小為94.5649（秒）。

關(guān)鍵詞：最短路徑 線圓模型 行走矩陣 MATLAB二、問題重述在一個800800的平面場景圖（見附錄一），在原點O(0, 0)點處有一個機器人，它只能在該平面場景范圍內(nèi)活動圖中有12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：編號障礙物名稱左下頂點坐標其它特性描述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正方形(640, 520)邊長8012長方形(500, 140)長300，寬60在圖中的平面場景中，障礙物外指定一點為機器人要到達的目標點（要求目標點與障礙物的距離至少超過10個單位）。

規(guī)定機器人的行走路徑由直線段和圓弧組成，其中圓弧是機器人轉(zhuǎn)彎路徑機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無法完成行走機器人直線行走的最大速度為 個單位/秒機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為 ，其中 是轉(zhuǎn)彎半徑如果超過該速度，機器人將發(fā)生側(cè)翻，無法完成行走現(xiàn)需建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的數(shù)學(xué)模型對場景圖中4個點O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計算：(1) 機器人從O(0, 0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑2) 機器人從O (0, 0)出發(fā)，到達A的最短時間路徑并要求給出路徑中每段直線段或圓弧的起點和終點坐標、圓弧的圓心坐標以及機器人行走的總距離和總時間三、模型假設(shè)1、假設(shè)機器人可看做一個質(zhì)點，不考慮其實際大??；2、假設(shè)機器人能夠準確的按照設(shè)計的路線行走行走，在其行走中不發(fā)生任何突發(fā)事故；3、機器人以最大速度行駛，在轉(zhuǎn)彎過程中沒有發(fā)生側(cè)翻，速度發(fā)生突變，不考慮加速減速。

四、符號說明 ：圓到圓圓心的距離；：機器人經(jīng)過的第i個圓弧的圓心角；：第i段直線多對應(yīng)的圓心角：圓的半徑；：機器人經(jīng)過的第i段直線的長度；S:行走路徑的總的長度；T：機器人行走的總的時間N：機器人行走經(jīng)過的總點數(shù)（包括起點終點以及轉(zhuǎn)彎圓弧的圓心）；A：行走矩陣五、模型建立對于該題建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的數(shù)學(xué)模型的研究，主要是用盡可能短的路徑和時間避開障礙物到達目標點根據(jù)題目中的要求可知，機器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無法完成行走，故可把各障礙物的邊界擴大10單位利用CAD軟件制圖可在距每個障礙物的邊緣10個單位處添加外邊框，形成新的屏障，特別注意的是在障礙物頂點處使用圓弧機器人就可在新屏障外的范圍內(nèi)隨意活動，不用擔(dān)心發(fā)生碰撞，根據(jù)原圖修改后的圖形見下圖1C(700, 640)B(100, 700)A（300,300）圖1機器人行駛路線是由直線段和圓弧組成機器人從O(0, 0)出發(fā)，建立數(shù)學(xué)模型求得O→A、O→B、O→C和O→A→B→C→O的最短路徑現(xiàn)將各個路段的情況進行綜合分析，根據(jù)每個路段所遇到的情況，從起始點到目標點的最短距離應(yīng)該是直線段與圓弧組成，由已知的數(shù)學(xué)知識，兩點之間線段最短，故機器人走的直線越多，路徑越短，也就是說當機器人繞過障礙物的時候，半徑越小，路徑越短，根據(jù)題意，轉(zhuǎn)彎半徑可按最小半徑10來計算，經(jīng)過分析，可建立如下三個線圓模型。

模型一：（點圓模型） 該模型主要求解——的路徑長度，該路徑只有一個轉(zhuǎn)彎，由圖2易知，，C、D均為直線與圓的切點，CD為圓弧，為圓弧對應(yīng)的圓心角的大小，根據(jù)已積累的知識，圓弧的長度為圓弧對應(yīng)的圓心角與圓半徑的乘積，即，同時利用余弦定理，即可求得總距離為： S=；其中 = C圖2D模型二：（雙圓異側(cè)模型） 該模型是為了計算——的距離，從起始點到目標點經(jīng)過圓弧異側(cè)拐彎（如圖3），根據(jù)已知點、、、可求得的長度AB、CD為兩段圓弧，、為其對應(yīng)的圓心角，BC與的交點E是這兩條線段的中點，根據(jù)兩個全等三角形以及勾股定理，可求得BC長度其中，EADCB圖3模型三：（雙圓同側(cè)模型） 該模型是為了計算——的距離，從起始點到目標點經(jīng)過圓弧同側(cè)拐彎（如圖4），添加輔助線，連接、，運用幾何知識輕易能夠證明由圖4易知,可以根據(jù)已知點的坐標求出所需線段的長度，進而求得起始點到目標點的總距離其中，圖4DEFC綜合模型：在實際情況中，機器人所走的路線是以上三種模型的結(jié)合設(shè)計好機器人的行走方案，可根據(jù)設(shè)計好的方案構(gòu)建行走矩陣，構(gòu)建方法如下：i段為模型1i段為模型2i段為模型3i段為模型1i段為模型2i段為模型3則i段的直線長度為：其中i=1,2…N-1;第i段與i+1段之間的轉(zhuǎn)彎圓弧所對應(yīng)的的圓心角為：其中i=1,2…N-2；i段為模型1i段為模型2i段為模型3機器人行走的總的長度為：六、模型求解問題（1）：根據(jù)所建立的數(shù)學(xué)模型，用CAD畫出可能的最短路徑，構(gòu)建每條路線的行走矩陣，通過MATLAB編程計算出每天路線的實際長度，從而得到最短路徑。

1、O——A路段，這是四個路段中最簡單的情況，從O到A經(jīng)過了一個轉(zhuǎn)彎，從圖5中易看出有兩種方案，虛線與實線各代表一個方案A（300,300）（80,60）（0,0）圖5利用MATLAB編程求解，計算結(jié)果如下：機器人從O到A的行走路線長度為471.0372；同理，O從下面繞到目標點A的總的路線長度為498.4259；通過比較兩種方案的結(jié)果易知，機器人在點O從上面繞到目標點A的距離最短，期最短路線長度為471.0372 2、O——B路段，經(jīng)過分析與整理，我們得到四種方案，如圖6所示①②③④，在這四種方案中，三種模型全部都要用到，模型一在O——A路段已詳細說明，模型二就是從起始點到目標點經(jīng)過的圓弧在所走路徑的異側(cè)，而模型三就是從起始點到目標點經(jīng)過的圓弧在所走路徑的同側(cè)，從O——B路段，有多次轉(zhuǎn)彎，具體見圖6B（100,700）O（0,0）④③②①圖6就①路線而言，機器人經(jīng)過了五次轉(zhuǎn)彎，根據(jù)三種模型中的理論公式，需要把各個圓弧與直線長度求得，可利用MATLAB軟件對其進行編程計算結(jié)果如下：①路線機器人行走的總距離為853.7001；②路線機器人行走的總距離為877.3841；③路線機器人行走的總距離為990.1608；④路線機器人行走的總距離為；經(jīng)過比較可得①路線為最短路徑，即機器人在點O從上面繞到目標點B的距離最短，期最短路線長度為853.7001 。

3、O——C路段，經(jīng)過整理分析，我們得到四種方案，具體見圖7， O（0,0）④③②①C（700,640）圖7 每條路線都是由圓弧與直線段，但是該路段與其他路段相比，又有其不同之處，在③路線中有一部分是在兩個不同大小的圓的異側(cè)和同側(cè)（如圖8，圖9所示）圖8AEB就圖8容易看出， ， 圖9EBA就圖9容易得出， ，利用MATLAB軟件對其進行編程計算結(jié)果如下：①路線機器人行走的總距離為；②路線機器人行走的總距離為 ；③路線機器人行走的總距離為；④路線機器人行走的總距離為；顯而易見，經(jīng)過比較可得④路線為最短路徑，即機器人在點O從上面繞到目標點C的距離最短，其最短路線長度為4、O——A——B——C——O路段，這一路段需要結(jié)合之前求得的最短路徑，當機器人在A、B、C轉(zhuǎn)彎時，為確定其路徑最短，既使A點處在機器人的轉(zhuǎn)彎圓弧上，我們設(shè)立了如圖11的路徑，并計算出轉(zhuǎn)彎圓弧的圓心AO圖10由圖易算出轉(zhuǎn)彎圓弧的圓心坐標為：圖11A（300,300）O（0,0）C(700, 640)B(100, 700)需要注意的是，在C點附近，由于其位置的特殊性，原有的線圓模型不能很好的處理，我們采用兩段相切圓弧的線路。

利用MATLAB軟件對其進行編程計算結(jié)果如下：機器人行走的總距離為問題（2）機器人從O (0, 0)出發(fā)，求得到達A的最短時間路徑通過問題（1）中對各個路段最短路徑的求解，我們可以做出合理假設(shè)：機器人轉(zhuǎn)彎圓弧的圓心在點P（80,210）的位置，而半徑我們設(shè)為由問題（1），可以得到機器人從O點到A的時間為（參照模型一）：其中為長度，為長度，為長度，為，由于圓心固定，其值為固定值通過MATLAB編程，得到的函數(shù)圖象如下圖所示：從圖中可以看出，當半徑=11.435時，時間T最小，其大小為94.5649七、模型評價與推廣優(yōu)點：1、該模型設(shè)計了三種基本模型，將實際線路進行簡化，從而降低了計算難度；2、提出行走矩陣的概念，在程序中對不同模型進行判斷，從而簡化了程序，方便了計算，使得程序更具備一般性；3、最終結(jié)果由MATLAB編程計算，計算結(jié)果真實可靠缺點：1、最短路徑的設(shè)計上有一定的主觀性，可能會與實際有所偏差；2、在計算到A點最短時間時，未考慮機器人加速減速的情況，使得計算值與實際值相比偏大3、在計算到A點最短時間時，為了方便計算，將轉(zhuǎn)彎圓弧的圓心確定在點P（80,210），模型過于簡單粗糙，會與實際情況有所偏差。

八、參考文獻[1] 丁緒東編著，AutoCAD2007實用教程[M]，中國電力出版社，2007[2] 曹戈 ， 《MATLAB教程及實訓(xùn)》， 機械工業(yè)出版社 2008年5月1日[3] 孫祥，MATLAB 7.0基礎(chǔ)教程,北京：清華大學(xué)出版社，2005[4] 戴光明.避障路徑規(guī)劃的算法研究[D].華中科技大學(xué)，計算機科學(xué)與技術(shù)學(xué)院,2004[5]薛定宇，陳陽泉，高等應(yīng)用數(shù)學(xué)的Matlab解．清華大學(xué)出版社．2004.183～191[6]馮杰，黃力偉，王琴，尹成義，數(shù)學(xué)建模原理與案例，科學(xué)出版社，2007附錄一場景圖：。