機(jī)器人避障問題的解題分析建模集訓(xùn)資料-wenkub
2023-04-10 01:40:09 本頁面
【正文】 短路徑計(jì)算模型 單個(gè)目標(biāo)點(diǎn)的最短路徑根據(jù)前面制定的行走路徑原則，起點(diǎn)到目標(biāo)點(diǎn)無論中間障礙物有多少，最短路徑都應(yīng)該是若干個(gè)線圓結(jié)構(gòu)所組成，圓弧中心為障礙物的頂點(diǎn)，半徑為機(jī)器人轉(zhuǎn)彎最小半徑10個(gè)單位。從頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑就是所求最短路徑，Dijkstra算法就是按路徑的長度遞增次序產(chǎn)生最短路徑的算法[3]。圖4如圖4，已知兩個(gè)固定點(diǎn)，圓心，可以求得兩切點(diǎn)坐標(biāo)，設(shè)半徑為，圓弧所對(duì)的圓心角為，的路徑長度為,則 將路徑函數(shù)對(duì)求導(dǎo)，得因?yàn)?，所以.，則函數(shù)為單調(diào)遞增函數(shù)，因此當(dāng)圓弧半徑逐漸增加時(shí)，機(jī)器人的行走路徑會(huì)增大，逐漸降低時(shí)，機(jī)器人的行走路徑會(huì)減小[2]，本題規(guī)定轉(zhuǎn)彎半徑最小為10個(gè)單位，所以在路徑設(shè)定時(shí)應(yīng)將轉(zhuǎn)彎半徑設(shè)定為最小值10個(gè)單位。圖2 障礙物包絡(luò)圖對(duì)障礙物的一個(gè)角點(diǎn)來說，其禁入?yún)^(qū)的邊界應(yīng)由兩條直線和一條圓弧組成，兩條直線分別平行于角點(diǎn)的兩條邊，間距為10個(gè)單位，圓弧是以障礙物角點(diǎn)為圓心，半徑為10個(gè)單位的四分之一圓弧。場景圖中有4個(gè)目標(biāo)點(diǎn)O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，下面我們將研究機(jī)器人從O(0, 0)出發(fā)，求O→A、O→B、O→C和O→A→B→C→O的最短路徑，以及機(jī)器人從O(0, 0)出發(fā)，到達(dá)A的最短時(shí)間路徑問題。為了不與障礙物發(fā)生碰撞，同時(shí)要求機(jī)器人行走線路與障礙物間的最近距離為10個(gè)單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機(jī)器人無法完成行走。本文以2012年“高教社”杯全國大學(xué)生數(shù)學(xué)建模競賽D題“機(jī)器人避障問題”為例進(jìn)行研究。機(jī)器人避障問題的解題分析摘要：本文對(duì)2012年全國大學(xué)生數(shù)學(xué)建模競賽D題機(jī)器人避障問題進(jìn)行了全面分析，對(duì)最短路的設(shè)計(jì)進(jìn)行了理論分析和證明，建立了機(jī)器人避障最短路徑的幾何模型，對(duì)最短時(shí)間路徑問題通過建立非線性規(guī)劃模型，有效地解決了轉(zhuǎn)彎半徑、圓弧圓心位置和行走時(shí)間等問題。假設(shè)機(jī)器人的工作范圍為800800的平面正方形區(qū)域（如圖1），其中有12個(gè)不同形狀的靜態(tài)障礙物，障礙物的數(shù)學(xué)描述（如表1）：圖1 800800平面場景圖表1編號(hào)障礙物名稱左下頂點(diǎn)坐標(biāo)其它特性描述1正方形(300, 400)邊長2002圓形圓心坐標(biāo)(550, 450)，半徑703平行四邊形(360, 240)底邊長140，左上頂點(diǎn)坐標(biāo)(400, 330)4三角形(280, 100)上頂點(diǎn)坐標(biāo)(345, 210)，右下頂點(diǎn)坐標(biāo)(410, 100)5正方形(80, 60)邊長1506三角形(60, 300)上頂點(diǎn)坐標(biāo)(150, 435)，右下頂點(diǎn)坐標(biāo)(235, 300)7長方形(0, 470)長220，寬608平行四邊形(150, 600)底邊長90，左上頂點(diǎn)坐標(biāo)(180, 680)9長方形(370, 680)長60，寬12010正方形(540, 600)邊長13011正方形(640, 520)邊長8012長方形(500, 140)長300，寬60在原點(diǎn)O(0, 0)點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面場景范圍內(nèi)活動(dòng)，機(jī)器人不能與障礙物發(fā)生碰撞，障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)。機(jī)器人直線行走的最大速度為個(gè)單位/秒。2 靜態(tài)避障問題中機(jī)器人行走最短路徑的分析 行走路徑的設(shè)計(jì)在本例中障礙物有4種不同形狀：矩形、平行四邊形、三角形和圓形?？梢宰C明具有圓形限定區(qū)域的最短路徑由兩部分組成，一部分是平面上的自然最短路徑（直線段），另一部分是限定區(qū)域的部分邊界（即繩子拉到最緊時(shí)的圓弧部分），這兩部分是相切的，互相連接（如圖3所示）。根據(jù)以上分析，對(duì)于靜態(tài)障礙物機(jī)器人的行走路徑應(yīng)遵循以下三個(gè)原則：原則一：機(jī)器人的行走路徑為線圓結(jié)構(gòu)，由兩條切線和一段圓弧組成；原則二：每個(gè)路口至多發(fā)生一次轉(zhuǎn)彎，并以障礙物頂點(diǎn)為轉(zhuǎn)彎圓弧的中心；原則三：機(jī)器人轉(zhuǎn)彎圓弧半徑為最小允許半徑10個(gè)單位。 下面以 為例，確定的最短路徑。觀察這四條路徑，發(fā)現(xiàn)所有行走路徑都可歸結(jié)為以下三種類型：類型一 圖10 線圓結(jié)構(gòu)1如圖10，設(shè)O（）為起點(diǎn)，A（）為目標(biāo)點(diǎn)，C和D分別為直線與轉(zhuǎn)彎圓弧的切點(diǎn)，障礙物的頂點(diǎn)（即轉(zhuǎn)彎圓弧的圓心），圓的半徑為，的長度為，的長度為，的長度為，設(shè)的長度為L，則，由圖10可得以下關(guān)系： 在中： 在中： 在中： 所以： 從而可得： 這個(gè)模型運(yùn)算簡潔，只需將起點(diǎn)、目標(biāo)點(diǎn)和障礙物頂點(diǎn)坐標(biāo)輸入模型，MATLAB就能很快計(jì)算出來[4]，計(jì)算程序見附錄1。 類型三圖12 線圓結(jié)構(gòu)3如圖12，如果兩圓弧的公切線平行于兩圓圓心連線，求的路徑長度。求過A、B、C三點(diǎn)的圓心位置的問題可通過建立非線性規(guī)劃模型求得。解法如下：直線的斜率為，的直線方程為，因?yàn)?所以DE的直線的斜率也為在DE直線上找一點(diǎn)，則DE直線方程為,即，又因?yàn)榍悬c(diǎn)D在圓上，滿足圓的方程，故，建立方程組，解方程可求得D點(diǎn)的坐標(biāo), MATLAB程序見附錄7。 以為例，研究最短時(shí)間路徑問題。（2）運(yùn)用多個(gè)方案進(jìn)行優(yōu)化，在相對(duì)優(yōu)化中能取得最優(yōu)解。非線性變量越來越多會(huì)導(dǎo)致求解時(shí)間越來越長，解的可求性也越來越差。參考文獻(xiàn)[1] :[20120908][2] :[20130228] [3] [M].西安:西安科學(xué)出版社,1984.[4] 章棟恩，[M].北京：電子工業(yè)出版社，2010.[5][J].數(shù)學(xué)建模及其應(yīng)用,2013,2(1):5359
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1