上傳人：鍵***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：周**（實(shí)名認(rèn)證）

IP屬地：上海

IP屬地：上海 上傳時(shí)間：2022-04-12 格式：DOCX 頁數(shù)：40 大?。?46.67KB 積分：20 舉報(bào) 版權(quán)申訴

1、2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項(xiàng)填寫）： D 我們的參賽報(bào)名號為（如果賽區(qū)設(shè)置

2、報(bào)名號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?參賽隊(duì)員 (打印并簽名) ：1. （此部分內(nèi)容不便公開，見諒） 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 2012 年 9 月 10 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2012高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時(shí)使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）：機(jī)器人避障問題摘要針對機(jī)器人避障問題，本文分別建立了機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障的最短路徑、最短時(shí)間路徑

3、的非線性0-1整數(shù)規(guī)劃模型。同時(shí)，本文為求帶有NP屬性的非線性0-1整數(shù)規(guī)劃模型，構(gòu)建了有效啟發(fā)式算法，利用MATLAB軟件編程，求得了OA、OB、OC、OABAC的最短路徑，同時(shí)得到了OA的最短時(shí)間路徑，求得的各類最短路徑均是全局最優(yōu)。針對區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障的最短路徑問題，首先，本文證明了圓弧位置設(shè)定在需要繞過障礙物的頂角上，且圓弧半徑為10個(gè)單位時(shí)，能夠使得機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的行進(jìn)路徑最短；其次，本文將最短路徑選擇問題轉(zhuǎn)化成了最短路徑的優(yōu)選問題，根據(jù)避障條件，建立了具有較高普適性的避障最短路徑的優(yōu)化模型。為便于求解，本文巧妙地將此優(yōu)化模型轉(zhuǎn)化成了以可行路徑不與障礙物邊界相

4、交、不與圓弧相交為約束條件，以機(jī)器人從區(qū)域中一點(diǎn)達(dá)到另一點(diǎn)避障路徑最短為目標(biāo)的0-1規(guī)劃模型；再次，本文構(gòu)建了兩種有效的啟發(fā)式算法，利用MATLAB軟件編程求得了OA、OB、OC、OABAC的最短路徑，最短路徑長分別為471.0372、853.7001、1088.1952、2725.1596，其中O->A的最短路徑為(0,0)(70.5063,213.1405) (75.975,219.1542)（300,300)，對應(yīng)圓弧的圓心坐標(biāo)為(80,210)，OB的最短路徑，對應(yīng)圓弧的圓心坐標(biāo)：(60,300)、(150,435)、（220、470）、(220,530)、(150,600)，

5、OC經(jīng)過的圓心：(410,100)、(230,60)、(720,520)，（720,600），(500,200)， OABCO經(jīng)過的圓心：(410,100)，(230,60)， (80,210)，(220,530)，(150,600)，(270,680)，(370,680)， (430,680)，(670,730)，(540,730)，(720,520)，(720,600)，(500,200)。針對最短時(shí)間路徑問題，我們建立了從o點(diǎn)出發(fā)到任意目標(biāo)點(diǎn)的0-1非線性整數(shù)規(guī)劃模型，同時(shí)針對題意要求，具體構(gòu)建了從o點(diǎn)出發(fā)到A的最短時(shí)間路徑的0-1非線性整數(shù)規(guī)劃模型，利用LINGO軟件求解，獲得了機(jī)器人

6、從o點(diǎn)出發(fā)，到達(dá)A的最短時(shí)間路徑，求得最短時(shí)間路徑下轉(zhuǎn)彎半徑為12.9885 ，同時(shí)最短時(shí)間路徑時(shí)間長為94.2283個(gè)單位。相應(yīng)圓弧的圓心坐標(biāo)為（82.1414，207.9153），兩切點(diǎn)坐標(biāo)分別為（69.8045，211.9779）、（77.7492,220.1387）。本文確定路線思路循序漸進(jìn)，先建立了有計(jì)算避障約束公式的普適性模型，再建立了以不取相交點(diǎn)來簡化0-1變量取值關(guān)系的簡化模型；給出了二種啟發(fā)式算法，最短路徑即最短時(shí)間路徑具有一定可信度。同時(shí)第一個(gè)啟發(fā)算法可以求得全局最優(yōu)解，第二個(gè)啟發(fā)算法是針對問題的NP屬性減少求解時(shí)間而構(gòu)建的，兩個(gè)算法都具有較重要的意義?！娟P(guān)鍵詞】 機(jī)器人避

7、障 最短路徑 啟發(fā)算法 0-1規(guī)劃模型 一、問題重述在一個(gè)800×800的平面場景圖，在原點(diǎn)O(0, 0)點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面場景范圍內(nèi)活動。圖中有12個(gè)不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：編號障礙物名稱左下頂點(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)上

8、頂點(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在圖1的平面場景中，障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)（要求目標(biāo)點(diǎn)與障礙物的距離至少超過10個(gè)單位）。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧是機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個(gè)或多個(gè)相切

9、的圓弧路徑組成，但每個(gè)圓弧的半徑最小為10個(gè)單位。為了不與障礙物發(fā)生碰撞，同時(shí)要求機(jī)器人行走線路與障礙物間的最近距離為10個(gè)單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機(jī)器人無法完成行走。機(jī)器人直線行走的最大速度為個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如果超過該速度，機(jī)器人將發(fā)生側(cè)翻，無法完成行走。請建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時(shí)間路徑的數(shù)學(xué)模型。對場景圖中4個(gè)點(diǎn)O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計(jì)算：(1) 機(jī)器人從O(0, 0)出發(fā)，OA、OB、OC和OABCO的最短路徑。(2) 機(jī)器人從O (0

10、, 0)出發(fā)，到達(dá)A的最短時(shí)間路徑。注：要給出路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的總距離和總時(shí)間。二、問題分析2.1求取最短路徑的分析本問題要求機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑。機(jī)器人只要做到轉(zhuǎn)彎時(shí)的圓弧半徑最小為10個(gè)單位、與障礙物最近距離單時(shí)刻保持大于10個(gè)單位，那么可行走的路徑就有無數(shù)條，若想求得機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑，則需要建立避障的最短路徑模型，而建立避障的最短路徑模型有一定難度。根據(jù)對問題的分析，我們認(rèn)為可以從簡單做起，先確定小范圍內(nèi)最短路徑條件，如圓弧位置的影響，圓弧半徑的大小，避免與障礙物碰撞條件等，通過確定最短路

11、徑條件來建立避障的最短路徑模型。對于最短路徑的求取，我們可以通過確定窮舉原則，利用窮舉法來求解，當(dāng)然也可以通過構(gòu)建啟發(fā)式算法的進(jìn)行求解。2.2最短時(shí)間路徑的分析對于要建立最短時(shí)間路徑模型來說，我們?nèi)菀字烙绊懙囊蛩赜兄本€行走速度、轉(zhuǎn)彎速度，同時(shí)還需要考慮使得最短時(shí)間路徑條件，如圓弧位置（坐標(biāo)）的影響，圓弧半徑的大小，避免與障礙物碰撞條件等。對于直線行進(jìn)，我們希望行進(jìn)速度越大越好，對于機(jī)器人轉(zhuǎn)彎時(shí)，轉(zhuǎn)彎速度要有約束，要保證機(jī)器人不能發(fā)生側(cè)翻。我們發(fā)現(xiàn)圓弧半徑的大小與轉(zhuǎn)彎速度緊密相連，從轉(zhuǎn)彎速度公式來分析，當(dāng)轉(zhuǎn)彎半徑增大時(shí)，最大轉(zhuǎn)彎速度也增大，為在更短時(shí)間內(nèi)行進(jìn)到目標(biāo)點(diǎn)，我們希望轉(zhuǎn)彎速度為機(jī)器人的

12、最大轉(zhuǎn)彎速度較好，但有很大的可能是行進(jìn)的路徑不是最短的，即行進(jìn)路徑有很大可能在增加。于是，我們需要做的工作是，在滿足最短時(shí)間路徑條件時(shí)，找到一個(gè)圓弧的坐標(biāo)位置，同時(shí)確定半徑的大小，以求得最短時(shí)間路徑。三、模型假設(shè)1.假設(shè)將機(jī)器人看成一個(gè)質(zhì)點(diǎn)；2.假設(shè)半徑不變時(shí)，機(jī)器人在行進(jìn)、轉(zhuǎn)彎過程中能一直保持最大的速度；3.假設(shè)啟發(fā)算法是針對問題的NP屬性減少求解時(shí)間而構(gòu)建的。四、符號說明符號含 義單位備注避障最短路徑圓弧切點(diǎn)到圓弧切點(diǎn)的直線距離，即機(jī)器人從圓弧切點(diǎn)到圓弧切點(diǎn)的直線路徑機(jī)器人從圓弧行進(jìn)至圓弧切點(diǎn)時(shí)的轉(zhuǎn)彎路徑圓弧的橫坐標(biāo)圓弧的縱坐標(biāo)圓弧對應(yīng)圓心角度圓弧的半徑度五、最短路徑模型建立與求解5.1模

13、型準(zhǔn)備確定圓弧位置與轉(zhuǎn)彎半徑在建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑數(shù)學(xué)模型之前，我們需要考慮兩個(gè)問題：問題一：機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)過程中，若中間有障礙物，則需要通過轉(zhuǎn)彎來繞過障礙物，那么，在轉(zhuǎn)彎半徑一定的情況下，怎樣設(shè)定最佳圓弧位置，使得繞行路徑最短？問題二：繞行路徑是最短時(shí)，轉(zhuǎn)彎半徑的大小為多少？針對考慮的問題一，我們?nèi)C(jī)器人從到點(diǎn)的行走過程來說明問題。在行走過程中要求機(jī)器人行走線路與障礙物的最短距離為10個(gè)單位，圓?。ㄞD(zhuǎn)彎）半徑最小為10個(gè)單位。我們先令機(jī)器人轉(zhuǎn)彎半徑為10個(gè)單位，根據(jù)機(jī)器人行走過程中的要求，我們易得兩條極端的行走路徑，如圖1。將路線II中圓弧3兩切點(diǎn)線延

14、長，兩延長交路線I，兩交點(diǎn)處分別作半徑為10個(gè)單位的圓弧，由此我們可得機(jī)器人從到點(diǎn)的行走時(shí)轉(zhuǎn)彎中心坐標(biāo)的范圍，如圖2中四邊形。 圖1 兩條極端路徑 圖2 轉(zhuǎn)彎中心坐標(biāo)的范圍圖1中路線I是理想化路線，機(jī)器人不能沿平面區(qū)域邊界行走，平面區(qū)域邊界也可以看成是一個(gè)障礙物，且有要求機(jī)器人行走線路與障礙物的最短距離為10個(gè)單位，實(shí)際上作這樣的處理并不會影響我們說明問題。我們假設(shè)在平面中有和兩點(diǎn)，中間有一正方形的障礙物，將圖2進(jìn)行轉(zhuǎn)化，如圖3.圖3 最短路徑證明圖圖3中，為切點(diǎn)，為圓弧圓心，四邊形為圓弧中心點(diǎn)的范圍。對于最佳圓弧位置確定，我們采用“覆蓋法”。我們?nèi)菀字溃袈肪€II與構(gòu)成的區(qū)域II能夠完整覆

15、蓋線I與構(gòu)成的區(qū)域I，即區(qū)域I屬于區(qū)域II，那么區(qū)域II的周長一定大于區(qū)域I，否則。圖3中路線I與構(gòu)成的區(qū)域I周長為直線段長度、圓弧長、長之和，區(qū)域I周長為機(jī)器人沿路線I的路徑長可表示為路線II與OA構(gòu)成的區(qū)域II周長為直線段長度、圓弧長、長之和，區(qū)域II周長為機(jī)器人沿路線II的路徑長可表示為顯然我們知道區(qū)域II能夠覆蓋區(qū)域I，即可得，進(jìn)而可得到 同理，在圓弧中心點(diǎn)的范圍任意取一點(diǎn)作為機(jī)器人轉(zhuǎn)彎圓弧中點(diǎn)，并作路線，再將路線與路線I做比較，可得到由此，我們可得出結(jié)論：機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)過程中，當(dāng)圓弧位置設(shè)定障礙物頂角上時(shí)，繞行路徑最短，此時(shí)圓弧中心點(diǎn)坐標(biāo)為障礙物頂角坐標(biāo)。針對考慮的問題

16、二，為了更清晰說明繞行路徑是最短時(shí)，轉(zhuǎn)彎半徑的大小為多少，我們基于最小圓弧半徑條件下使圓弧半徑增大。為了保證機(jī)器人與障礙物不發(fā)生碰撞，所以，需要保證大圓弧能夠覆蓋小圓弧對應(yīng)圓的1/4圓弧。在設(shè)定好最佳圓弧位置情況下，增加圓弧半徑，比較最短路徑的變化。假設(shè)圓弧半徑為（），對應(yīng)最短路線如圖4。（1） （2）圖4 圓弧半徑為R最短路徑圖4（1）中為兩圓弧公共切點(diǎn)，為小圓弧切點(diǎn)（），為大圓弧切點(diǎn)。圖4（2）中、為大圓弧切點(diǎn)，、為小圓弧切點(diǎn)。針對圖4（1）（2），根據(jù)“覆蓋”思想與得出的結(jié)論，我們?nèi)菀装l(fā)現(xiàn)，當(dāng)圓弧半徑為（）時(shí)，行進(jìn)路線與構(gòu)成的區(qū)域顯然是能夠完全覆蓋圓弧半徑為時(shí)構(gòu)成的區(qū)域，由此，可說明在圓

17、弧位置設(shè)定為最佳的條件下，圓弧半徑越小行進(jìn)路徑越短，而圓弧半徑最小為10個(gè)單位，進(jìn)而說明圓弧的半徑為10個(gè)單位時(shí)，繞行路徑最短。根據(jù)考慮的兩個(gè)問題與證明結(jié)果，我們可得出結(jié)論：要使得機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的行進(jìn)路徑最短，應(yīng)使圓弧位置設(shè)定在需要繞過障礙物的頂角上最佳，此時(shí)圓弧中心點(diǎn)坐標(biāo)為障礙物頂角坐標(biāo)，并且此時(shí)圓弧的半徑為10個(gè)單位。問題的轉(zhuǎn)化在模型準(zhǔn)備中我們已得出要使得機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的行進(jìn)路徑最短，應(yīng)使圓弧位置設(shè)定在需要繞過障礙物的頂角上最佳，此時(shí)圓弧中心點(diǎn)坐標(biāo)為障礙物頂角坐標(biāo)，并且此時(shí)圓弧的半徑為10個(gè)單位。因此，我們將的平面場景圖進(jìn)行處理，處理原則有：1. 每個(gè)障礙物的頂

18、角都設(shè)定一個(gè)圓弧；2.圓弧坐標(biāo)為障礙物頂點(diǎn)坐標(biāo)；3.圓弧的半徑設(shè)定為10個(gè)單位；4.給每一段圓弧從2.標(biāo)號，O點(diǎn)標(biāo)記為1、36。根據(jù)處理原則，得圖5。圖5 處理后的平面場景圖在原問題中，若沒進(jìn)行確定圓弧位置與轉(zhuǎn)彎半徑以及平面場景的處理，原問題求解將會很難，并且所有的轉(zhuǎn)彎點(diǎn)均是未知，經(jīng)處理后，我們將問題轉(zhuǎn)化為在已知轉(zhuǎn)彎點(diǎn)，尋找合適的轉(zhuǎn)彎點(diǎn)，使得路徑最短，即我們將問題轉(zhuǎn)化為了最短路徑的優(yōu)化問題。 5.2避障最短路徑模型的建立問題轉(zhuǎn)化為最短路徑的優(yōu)化問題后，我們易知優(yōu)化的目標(biāo)函數(shù)為機(jī)器人在行進(jìn)過程中最短路徑，通過0-1變量來選取經(jīng)過的轉(zhuǎn)彎點(diǎn)，因此可建立0-1規(guī)劃模型。 目標(biāo)函數(shù)目標(biāo)函數(shù)為機(jī)器人出區(qū)域

19、中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑，避障最短路徑為行進(jìn)過程中直線路徑與轉(zhuǎn)彎路徑之和，于是有 （1）其中，為圓弧切點(diǎn)到圓弧切點(diǎn)的直線距離，即機(jī)器人從圓弧切點(diǎn)到圓弧切點(diǎn)的直線路徑；為機(jī)器人從圓弧行進(jìn)至圓弧切點(diǎn)時(shí)的轉(zhuǎn)彎路徑；為0-1變量，表示若選擇行走圓弧后行走圓弧，為1，否則為0，。我們設(shè)為圓弧的切點(diǎn)坐標(biāo)，為各圓弧的編碼，為切點(diǎn)的次序，如表示為圓弧的第一個(gè)切點(diǎn)坐標(biāo)。機(jī)器人從圓弧切點(diǎn)到圓弧切點(diǎn)的直線路徑為 （2）機(jī)器人從圓弧行進(jìn)至圓弧切點(diǎn)時(shí)的為 其中（3）為轉(zhuǎn)彎半徑，。約束條件1.避障條件的約束在本問題中，障礙物邊界可分為直線段與圓弧兩種情況，針對障礙物邊界不同的兩種情況，我們列出避障條件的約束：（1）

20、避障約束條件1任意一條可行路徑與所有障礙物的邊界線段間的最短距離大于10個(gè)單位. 設(shè)平面內(nèi)有兩條線段和，點(diǎn)的坐標(biāo)為 ,點(diǎn)的坐標(biāo)為 ，點(diǎn)的坐標(biāo)為,點(diǎn)的坐標(biāo)為，其中、可視為圓弧的切點(diǎn)坐標(biāo)，、為圓弧的切點(diǎn)坐標(biāo)線段兩圓弧的切點(diǎn)的連線，視為障礙物的某一條邊界線段。 設(shè)是直線上的一點(diǎn)，點(diǎn)的坐標(biāo)可以表示為當(dāng)參數(shù)時(shí)，是線段 上的點(diǎn)；當(dāng)參數(shù)時(shí)，是延長線上的點(diǎn)；當(dāng)參數(shù)時(shí)，是延長線上的點(diǎn)。設(shè)是直線上的一點(diǎn)，點(diǎn)的坐標(biāo) 可以表示為 當(dāng)參數(shù)時(shí)，是線段上的點(diǎn)；當(dāng)參數(shù)時(shí)，是延長線上的點(diǎn)；當(dāng)參數(shù) 時(shí)，是延長線上的點(diǎn)。,兩點(diǎn)之間的距離為 距離的平方為要求直線，之間的最短距離，也就是要求函數(shù)的最小值。對分別求關(guān)于，的偏導(dǎo)數(shù)，并令偏

21、導(dǎo)數(shù)為零：展開并整理后，得到下列方程組：9如果從這個(gè)方程組求出的參數(shù)，的值滿足，說明點(diǎn)落在線段上，點(diǎn)落在線段上，這時(shí)的長度為此時(shí)就是線段與的最短距離。如果從方程組求出的參數(shù)，的值不滿足，說明不可能在線段 內(nèi)部找到一點(diǎn)，在線段內(nèi)部找到一點(diǎn)，使得的長度就是線段與 的最短距離。這時(shí)，還需要進(jìn)行考慮的是：平面中一個(gè)點(diǎn)到一條線段的最短距離。設(shè)編號為的障礙物的圓心坐標(biāo)和一條線段，設(shè)點(diǎn)的坐標(biāo)為，點(diǎn)的坐標(biāo)為，點(diǎn)的坐標(biāo)為。此時(shí)，直線的參數(shù)形式的方程為 直線上的點(diǎn)，當(dāng)參數(shù)時(shí)，是線段上的點(diǎn)；當(dāng)參數(shù)時(shí)，是延長線上的點(diǎn)；當(dāng)參數(shù) 時(shí)，是延長線上的點(diǎn)。 通過點(diǎn)，與直線垂直的平面方程為下面求這個(gè)平面與直線的交點(diǎn)。顯然，所以點(diǎn)

22、也是從點(diǎn)向直線作垂線的垂足點(diǎn)。將代入平面方程，化簡后解得 然后，將上面得到的的值代入直線方程，得到其中，為垂足點(diǎn)的坐標(biāo)。 此時(shí)線段的長度，也就是點(diǎn)到直線的垂直距離為 如果前面求出的參數(shù)的值滿足，說明垂足點(diǎn)落在線段上，這時(shí) 的長度就是點(diǎn)到線段的最短距離。如果前面求出的參數(shù)的值滿足，說明垂足點(diǎn)不落在線段上，而是落在的延長線上，這時(shí)點(diǎn)到線段的最短距離，就是點(diǎn)到點(diǎn)的距離，即 。如果前面求出的參數(shù)的值滿足，說明垂足點(diǎn)不落在線段上，而是落在的延長線上，這時(shí)，點(diǎn)到線段的最短距離，就是點(diǎn)到點(diǎn)的距離，即 。綜上所述，即有平面內(nèi)有兩條線段最短距離為因此，我們可得到任意一條可行路徑與所有障礙物的邊界線段間的最短距離

23、大于10個(gè)單位的約束條件（4）其中，（2）避障約束條件2對于標(biāo)號為2的圓形障礙物，它與機(jī)器人行走路線的最近距離為10個(gè)單位，為使?jié)M足與機(jī)器人行走路線的最近距離為10個(gè)單位要求，我們可以轉(zhuǎn)化為圓形的圓心與障礙物間的最近為80個(gè)單位的問題，即把圓形與直線線段的最短路徑問題轉(zhuǎn)化為點(diǎn)到直線線段的的問題。已知編號為2半徑為（）的圓形障礙物，邊界并不是直線段，且該圓形障礙物的圓形為。根據(jù)平面中一定點(diǎn)到一條線段的最短距離計(jì)算辦法，我們可得 （5）因此，我們可得到圓形障礙物與平面內(nèi)最近約束條件為2.各坐標(biāo)點(diǎn)的約束所有假設(shè)的坐標(biāo)點(diǎn)都應(yīng)在平面場景內(nèi)，于是有3.各圓弧點(diǎn)行進(jìn)先后次序的約束機(jī)器人從某個(gè)圓弧出發(fā)行至下一

24、圓弧，先后次序的約束有 （6）其中，。避障最短路徑模型綜合上述，建立避障最短路徑模型：5.3基于避障條件轉(zhuǎn)化下的最短路徑簡化模型避障條件的轉(zhuǎn)化我們將任意一條可行路徑與所有障礙物的邊界線段間的最短距離大于10個(gè)單位轉(zhuǎn)化為兩直線不相交、與2號障礙物圓周均不相交、切點(diǎn)范圍的的控制。出于簡化避障條件的0-1變量取值關(guān)系，我們進(jìn)行符號補(bǔ)充:為0-1變量，表示為表示圓弧與圓弧的圓心（）所構(gòu)成的線段的縱坐標(biāo)，。表示編號為的區(qū)域內(nèi)一頂點(diǎn)（）與相鄰頂點(diǎn)（），所構(gòu)成的線段的縱坐標(biāo)，。當(dāng)時(shí)，頂點(diǎn)表示以（550,450）為圓點(diǎn)，80個(gè)單位為半徑的圓上的點(diǎn)，相鄰頂點(diǎn)坐標(biāo)則表示為以圓點(diǎn)對稱的點(diǎn)。為0-1變量，表示為， 我

25、們將避障約束條件替換為(7)基于避障條件轉(zhuǎn)化下的最短路徑簡化模型于是，我們可得避障最短路徑簡化模型5.4避障最短路徑簡化模型的求解基于避障條件轉(zhuǎn)化之下的最短路徑的啟發(fā)算法對于避障最短路徑的數(shù)學(xué)模型，是非線性0-1整數(shù)規(guī)劃，具有NP屬性。對于具體的區(qū)域與障礙物，通過巧妙地將避障條件轉(zhuǎn)化為相交約束，同時(shí)結(jié)合任意兩點(diǎn)間最短距離的floyd算法，我們構(gòu)建出了能夠?qū)Υ藛栴}規(guī)模求得全局最優(yōu)解的較好算法。具體算法思想是：針對此模型的NP屬性特征，即此問題搜索可行域的規(guī)模越發(fā)，運(yùn)行時(shí)間倍增的不足，我們采用逐步縮減可行域的辦法，將達(dá)到避障條件要求的所有可行路徑搜索出。同時(shí)，通過用兩切點(diǎn)標(biāo)識圓弧路徑的辦法，將一個(gè)

26、圓弧路徑擴(kuò)充為兩個(gè)切點(diǎn)的表示，建立出具有擴(kuò)充點(diǎn)的鄰接矩陣，于是將問題轉(zhuǎn)化為賦權(quán)圖上兩點(diǎn)的最小距離問題，采用Floyd算法，即可得出避障最短路徑。具體算法步驟為：Setp1：得出所有滿足避障條件的可行路徑，分三步逐步進(jìn)行。(1)對于個(gè)圓弧路徑，任意兩個(gè)圓弧間構(gòu)造切線段及出發(fā)點(diǎn)到各圓弧的切線段，由此形成初始的路徑。判斷每條路徑中的直線段與各障礙物的邊界線段是否相交，判斷方法為將兩線段進(jìn)行矢量跨立。若相交，去除該條路徑中的此直線段。(2)在（1）的基礎(chǔ)上去除各條路徑中的直線段與各圓弧路徑對應(yīng)圓周及2號圓形障礙物邊界相交的部分。判斷各條路徑中的直線段與圓周是否相關(guān)的方法為：判斷圓心到直線段的距離是否小

27、于半徑，若距離小于半徑，則看垂足是否在線段上，垂足在此線段上則相交，否則不相交。若圓心到直線段的距離大于半徑，則不相交。(3)依據(jù)避障條件，選取各切點(diǎn)在圓弧上的可取點(diǎn)范圍，如圖所示。切點(diǎn)只能在上選取判斷條件為：切點(diǎn)與圓心連線的向量與過圓心的兩邊界向量的夾角是否大于等于90度，若是，則在允許的取點(diǎn)范圍?；谝陨希?）（2）（3）的剔除，剩余的路徑即為滿足避障條件的可行路徑，而避障最短路徑必是這些可行路徑中的一條。Step2：構(gòu)造擴(kuò)充的賦權(quán)鄰接矩陣。將每一個(gè)圓弧路徑，轉(zhuǎn)化為由兩個(gè)切點(diǎn)標(biāo)識，給此兩個(gè)切點(diǎn)間賦予邊權(quán)為對應(yīng)圓弧路徑的弧長。對兩切點(diǎn)間的是有直線段相連的，直接將直線段長度賦予給此兩切點(diǎn)間的邊

28、權(quán)。由此對所有可行路徑，構(gòu)造有擴(kuò)充點(diǎn)的賦權(quán)圖的鄰接矩陣。Setp3：利用Floyd算法求擴(kuò)充賦權(quán)圖上任意兩點(diǎn)間的最短路徑，即可轉(zhuǎn)化為任意兩點(diǎn)間的避障最短路徑。避障最短路徑簡化模型的求解過程與結(jié)果根據(jù)構(gòu)建的啟發(fā)式算法步驟，利用MATLAB軟件，我們可求解如下結(jié)果：（1）尋找可行路徑根據(jù)避障約束條件1，任意一條可行路徑與所有障礙物的邊界線段間均不相交，求得只滿足路徑線段與邊界線段不相交時(shí)的可行路徑如圖6。圖6 可行路徑圖只滿足路徑中的各直線段與各障礙物邊界均不相交的可行路徑既滿足各直線段與各障礙物邊界均不相交的要求，又同時(shí)滿足與各圓弧路徑對應(yīng)的圓周及第2號障礙物圓周均不相交的條件的可行路徑如圖7。

29、圖7 滿足三條件的可行路徑圖在滿足算法step1中（1）（2）的基礎(chǔ)上，剔除掉切點(diǎn)不在允許范圍之內(nèi)的路徑線段，得出所有可行路徑示意圖，如圖8。圖8 所有可行路徑示意圖（2）對于每條可行路徑的直線段和圓弧段，構(gòu)造擴(kuò)充點(diǎn)，對任意兩點(diǎn)間按要求賦權(quán)，則問題轉(zhuǎn)化為在賦權(quán)圖上求兩點(diǎn)之間的最短距離。(3)調(diào)用Floyd算法，先后求出O->A的最短路徑及相應(yīng)最短路長，如圖9.圖9 O->A的最短路徑0->A路線序號圓弧起點(diǎn)坐標(biāo)圓弧終點(diǎn)坐標(biāo)圓弧圓心坐標(biāo)最短路長170.5063,213.140575.975,219.154280,210471.0372同理，我們可得到O->B的最短路徑及相

30、應(yīng)最短路長、O->C的最短路徑及相應(yīng)最短路長、O->A->B->C->O的最短路徑及相應(yīng)最短路長.圖10 O->B的最短路徑O->B的最短路徑為：(0,0)->(50.1354,301.6396)->(51.6795,305.547)->(141.6795,440.547)->(147.9621,444.79)->(222.038,460.2096)->(230,470)->(230,530)->(229.9563,530.9242)->(229.5746,532.8954)->(229.25

31、64,533.7791)->(229.1263,534.0782)->(225.4971,538.3544)->(144.5036,591.6465)->(140.6922,596.346)->(100,700)對應(yīng)圓弧的圓心坐標(biāo)：(60,300)，(150,435)， (220,470)，(220,530)，(150,600)最短路長為：853.7001圖11 O->C的最短路徑圖O->C的最短路徑為：(0,0)->(232.1147,50.2273)->(232.1694,50.2377)->(412.1695,90.2373)-

32、>(418.3435,94.4905)->(491.6536,205.5113)->(492.0569,206.0862)->(727.9298,513.924)->(730,520)->(730,600)->(727.7179,606.359)->(700,640)經(jīng)過的圓心：(410,100)， (230,60)， (720,520)， 圓心：(720,600)，半徑：10 圓心：(500,200)，半徑：10 最短路長為：1088.1952圖12 O->A->B->C->O的最短路徑圖O->A->B-&g

33、t;C->O的最短路徑為：(0,0)->(70.5063,213.1405)->(75.975,219.1542)->(76.2776,219.2811)->(76.6064,219.4067)->(300,300)->(229.5746,532.8954)->(229.2564,533.7791)->(229.1263,534.0782)->(225.4971,538.3544)->(144.5036,591.6465)->(140.6922,596.346)->(100,700)->(270.5862,68

34、9.9828)->(272.0002,689.799)->(368.0003,670.2035)->(370,670)->(430,670)->(434.0793,670.8716)->(435.5886,671.7056)->(534.4132,738.2917)->(540,740)->(670,740)->(679.7741,732.1462)->(700,640)->(727.7179,606.359)->(730,600)->(730,520)->(727.9298,513.924)->(

35、492.0569,206.0862)->(491.6536,205.5113)->(418.3435,94.4905)->(412.1695,90.2373)->(232.1694,50.2377)->(232.1147,50.2273)->(0,0)經(jīng)過的圓心：(410,100)， (230,60)， (80,210)， (220,530)， (150,600)， (270,680)， (370,680)， (430,680)， (670,730)， (540,730)， (720,520)， (720,600)， (500,200)最短路長為：2725.

36、1596。本次求解，在搜索可行路徑上程序運(yùn)行時(shí)間為10分鐘左右。5.5基于數(shù)值思想的改進(jìn)算法對每條路徑，直接根據(jù)避障條件，判斷它是否可行路徑的方法基于數(shù)值近似的線段間最短距離判別法。線段間最短距離判別法：給定路徑端點(diǎn)坐標(biāo)，所有障礙物邊界線段的坐標(biāo)，分別在路徑和某一邊界線段上取一系列的點(diǎn)，求得這系列點(diǎn)之間的最短距離即為線段間最短距離的近似值，如果該近似值大于10，則認(rèn)為路徑與該邊界線段的距離滿足要求，否則不滿足。直到該路徑與所有的邊界線段都滿足距離要求，則該路徑為可行路徑并記錄。易知，若線段間的一系列點(diǎn)取值越細(xì)密，結(jié)果越精確。按照該算法，我們編寫MATLAB程序得到的所有可行路徑如下圖： 對此可

37、行路徑集合，仍然使用基于避障條件轉(zhuǎn)化之下的最短路徑的啟發(fā)算法的Step2、Step3步尋找最短路徑，最短路徑結(jié)果完全等同基于避障條件轉(zhuǎn)化之下的最短路徑的啟發(fā)算法的結(jié)果，但是求解時(shí)間卻大大縮減，說明該算法具有一定的有效性。六、最短時(shí)間路徑模型建立與求解6.1到任意目標(biāo)點(diǎn)的避障最短時(shí)間路徑模型的建立基于問題一轉(zhuǎn)化為最短路徑的優(yōu)化問題后，我們易知優(yōu)化的目標(biāo)函數(shù)為機(jī)器人在行進(jìn)過程中最短時(shí)間路徑，通過0-1變量來選取經(jīng)過的轉(zhuǎn)彎點(diǎn)的圓心坐標(biāo)，兩切點(diǎn)坐標(biāo)及轉(zhuǎn)彎半徑，此時(shí)將轉(zhuǎn)彎點(diǎn)的圓心坐標(biāo)，兩切點(diǎn)坐標(biāo)及轉(zhuǎn)彎半徑均作為決策變量。因此，可建立0-1規(guī)劃模型如下。 6.1.1目標(biāo)函數(shù)目標(biāo)函數(shù)為機(jī)器人出區(qū)域中一點(diǎn)到達(dá)

38、另一點(diǎn)的避障最短時(shí)間路徑，避障最短路徑為行進(jìn)過程中直線路徑與轉(zhuǎn)彎路徑的時(shí)間取和，故有 （8）其中，為切點(diǎn)到切點(diǎn)的直線距離；為機(jī)器人從切點(diǎn)行進(jìn)至切點(diǎn)時(shí)的轉(zhuǎn)彎路徑；為0-1變量，表示若選擇行走切點(diǎn)后行走切點(diǎn)，為1，否則為0，。機(jī)器人從切點(diǎn)到切點(diǎn)的直線路徑為 （9）機(jī)器人從切點(diǎn)行進(jìn)至切點(diǎn)時(shí)的為 其中（10）為轉(zhuǎn)彎半徑。 約束條件1.避障條件的約束原理與最短路徑的避障條件的原理保持一致。2.各坐標(biāo)點(diǎn)的約束所有假設(shè)的坐標(biāo)點(diǎn)都應(yīng)在平面場景內(nèi)，于是有3.各圓弧點(diǎn)行進(jìn)先后次序的約束機(jī)器人從某個(gè)圓弧出發(fā)行至下一圓弧，先后次序的約束有 （11） 其中，。4.轉(zhuǎn)彎半徑、圓心、與切點(diǎn)的坐標(biāo)關(guān)系。轉(zhuǎn)彎半徑等于圓心與兩個(gè)

39、切點(diǎn),坐標(biāo)的直線距離。5. 轉(zhuǎn)彎半徑取值為：使?jié)M足的避障最短時(shí)間路徑模型綜合上述，建立避障最短時(shí)間路徑模型是在：6.2求從0->A的最短時(shí)間路徑的簡化模型針對只求0->A的最短時(shí)間路徑，我們具體問題具體分析，建立了相應(yīng)的簡化模型。障礙物5左上角的頂點(diǎn)與圓弧的距離大于等于10的避障約束可以表述如下：于是，我們可得一條路徑時(shí)間最短下的最優(yōu)的簡化模型針對每一條可行路徑，求出各路徑對應(yīng)的最優(yōu)轉(zhuǎn)彎半徑則，最短時(shí)間路徑的優(yōu)化模型為：6.3求從0->A的最短時(shí)間路徑的模型求解根據(jù)0->A的最短時(shí)間路徑的模型，利用LINGO軟件編程，比較兩條可行路徑對應(yīng)的最短時(shí)間，我們求得最短時(shí)間路徑

40、下轉(zhuǎn)彎半徑為12.9885 ，同時(shí)最短時(shí)間路徑時(shí)間長為94.2283個(gè)單位。相應(yīng)圓弧的圓心坐標(biāo)為（82.1414，207.9153），兩切點(diǎn)坐標(biāo)分別為（69.8045，211.9779）、（77.7492,220.1387）。七、模型評價(jià)7.1模型優(yōu)點(diǎn)（1）確定路線思路循序漸進(jìn)，本文先建立了有計(jì)算避障約束公式的普適性模型，再建立了以不取相交點(diǎn)來簡化0-1變量取值關(guān)系的簡化模型；（2）給出了二種啟發(fā)式算法，最短路徑即最短時(shí)間路徑具有一定可信度。同時(shí)第一個(gè)啟發(fā)算法可以求得全局最優(yōu)解，第二個(gè)啟發(fā)算法是針對問題的NP屬性減少求解時(shí)間而構(gòu)建的，兩個(gè)算法都具有較重要的意義。7.2模型缺點(diǎn)（1）本文將機(jī)器人

41、看成一個(gè)質(zhì)點(diǎn)，這將使機(jī)器人出現(xiàn)走區(qū)域邊界的可能，可能會出現(xiàn)與實(shí)際不符合的情況；（2）模型將假設(shè)機(jī)器人在行進(jìn)、轉(zhuǎn)彎過程中能一直保持最大的速度，誠然，現(xiàn)實(shí)并非如此，所以我們得到的問題二的結(jié)果與實(shí)際最短時(shí)間路徑會存在一定的誤差。參考文獻(xiàn)1 吳建國.數(shù)學(xué)建模案例精編M, 北京：中國水電出版社，2006，2102 楊秀月等.系統(tǒng)建模M，北京：國防工業(yè)出版社，2006.53 張志涌等.精通MATLAB6.5版M.北京: 北京航空航天大學(xué)出版社，2003,3附錄題目平面圖MATLAB程序清單：cleardistancebetweenlines.m 計(jì)算兩線段間近似最短路徑function mind=dist

42、ancebetweenlines(A,B,C,D,M)Ax=A(1);Ay=A(2);Bx=B(1);By=B(2);Cx=C(1);Cy=C(2);Dx=D(1);Dy=D(2);if (A(1)-B(1)=0 k=(By-Ay)/(Bx-Ax); b=By-k*Bx; ABXXL=linspace(A(1),B(1),M); ABYXL=k.*ABXXL+b;else ABXXL=linspace(A(1),B(1),M); ABYXL=linspace(A(2),B(2),M);endif (C(1)-D(1)=0 k=(Dy-Cy)/(Dx-Cx); b=Dy-k*Dx; CDXXL=

43、linspace(C(1),D(1),M); CDYXL=k.*CDXXL+b;else CDXXL=linspace(C(1),D(1),M); CDYXL=linspace(C(2),D(2),M);endmind=100000;for i=1:M for j=1:M if sqrt(ABXXL(i)-CDXXL(j)2+(ABYXL(i)-CDYXL(j)2)<=mind mind=sqrt(ABXXL(i)-CDXXL(j)2+(ABYXL(i)-CDYXL(j)2); end endend FLOYD1.m Folyd算法求最短路徑和最短路程function L,R=FLOYD

44、1(w,s,t)n=size(w,1);D=w;path=zeros(n,n);%ÒÔÏÂÊDZê×¼floydËã·¨for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); path(i,j)=path(i,k); end end enden

45、dL=zeros(0,0);R=s;while 1 if s=t L=fliplr(L); L=0,L; return end L=L,D(s,t); R=R,path(s,t); s=path(s,t);endhuchang.m 已知圓心和圓上2點(diǎn)，計(jì)算弧長function z=huchang(A,B,C,r)%CΪԲÐÄ×ø±ê%A,BΪԲ»¡¶Ëµã×ø±

46、;ê,rΪ°ë¾¶D=dot(A-C,B-C)/(norm(A-C)*norm(B-C);%£ä£ï£ôÏòÁ¿µã»ýtheta=acos(D);%»¡¶È±íʾz=theta*r;iscycleIntersect.m 判斷線段是否和圓相交function z=iscycleIntersect(line

47、,A,r)if (line(3)-line(1)=0 k=(line(4)-line(2)/(line(3)-line(1); b=line(2)-k*line(1); d=abs(k*A(1)-A(2)+b)/sqrt(k2+1); x y=solve('x*(' num2str(k) ')-y+(' num2str(b) ')=0',. '(y-(' num2str(A(2) ')*(' num2str(k) ')=(' num2str(A(1) ')-x');else x=li

48、ne(3);y=A(2); d=abs(line(3)-A(1);endx=double(x);y=double(y);if d>=r-0.5 z=0;elseif (y-line(4)*(y-line(2)>0 z=0;else z=1;endislineIntersect.m 判斷兩線段是否相交function z=islineIntersect(A,B,C,D)Ax=A(1);Ay=A(2);Bx=B(1);By=B(2);Cx=C(1);Cy=C(2);Dx=D(1);Dy=D(2);if (Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx)*(Bx-Ax)*(D

49、y-Cy)-(By-Ay)*(Dx-Cx)=0 r=(Ay-Cy)*(Dx-Cx)-(Ax-Cx)*(Dy-Cy)/(Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx); s=(Ay-Cy)*(Bx-Ax)-(Ax-Cx)*(By-Ay)/(Bx-Ax)*(Dy-Cy)-(By-Ay)*(Dx-Cx); if r>0&&r<=1&&s>0&&s<=1 z=1; else z=0; endelse z=0;endlinedistance.m 判斷切點(diǎn)是否位于可行圓弧上function z=linedistance(

50、A,B)a=B(1:2)-B(3:4);b=B(5:6)-B(3:4);c=A-B(3:4);theta1=acos(dot(a,c)/(norm(a)*norm(c)*180/pi;theta2=acos(dot(b,c)/(norm(b)*norm(c)*180/pi;if theta1>=90-0.5&&theta2>=90-0.5 z=0;else z=1;endmethod1.m 啟發(fā)式算法計(jì)算所有可行路徑clearclcclose alltheta=0:pi/100:2*pi;zb1=300 400;500 400;500 600;300 600;zb2

51、=550 450;80 80;zb3=360 240;500 240;540 330;400 330;zb4=280 100;410 100;345 210;zb5=80 60;230 60;230 210;80 210;zb6=60 300;235 300;150 435;zb7=0 470;220 470;220 530;0 530;zb8=150 600;240 600;270 680;180 680;zb9=370 680;430 680;430 800;370 800;zb10=540 600;670 600;670 730;540 730;zb11=640 520;720 520;

52、720 600;640 600;zb12=500 140;800 140;800 200;500 200;zb13=0 0;800 0;800 800;0 800;zb14=0 0 79;zb15=300 300 65;zb16=100 700 66;zb17=700 640 67;%*¼ÆËãÇøÓòÄÚËùÓеÄÖ±Ï߶εķ½

53、³Ì*lines=;kxyh=;for i=1:length(zb) temp=zbi; if size(zbi,1)=2 x=temp(2,1)*cos(theta)+temp(1,1); y=temp(2,2)*sin(theta)+temp(1,2); plot(x,y,'b-');hold on elseif size(temp,1)=3 temp0=temp+-10 -10;10 -10;0 10; for j=1:size(temp,1) if j=size(temp,1) tt=1; else tt=j+1; end lines=lines temp(j,1);temp(j,2);temp(tt,1);temp(tt,2); end plot(temp(:,1);temp(1,1),temp(:,2);temp(1,2),'b-');hold on elseif size(temp,1)=4 if i=13 temp0=temp+10 10;-10 10;-10 -10;10 -10; else temp0=t