-.zD題：機器人避障問題摘要本文就機器人避障問題，建立了相應(yīng)的優(yōu)化模型。模型一：關(guān)于機器人從區(qū)域中一點到達另一點的避障最短路徑的問題。首先，根據(jù)題意，畫出機器人行走的可行區(qū)域與危險區(qū)域；其次，在證明了具有圓形限定區(qū)域的最短路徑問題為根據(jù)的前提下，可以得出最短路徑一定是由直線和圓弧組成，并依此建立了線圓構(gòu)造，將路徑劃分為假設(shè)干個這種線圓構(gòu)造來求解最短路徑通用模型；最后，根據(jù)最短路徑通用模型，采用窮舉法把可能路徑的最短路徑列舉出來，通過比較最終得出各種最短路徑的坐標(biāo)及總路程如下：〔1〕O→A的最短路程為：471.04個單位〔2〕O→B的最短路程為：853.71個單位〔3〕O→C的最短路程為：1088.20個單位〔4〕O→A→B→C→O的最短路徑為：2730.01個單位模型二：關(guān)于機器人從區(qū)域中一點到達另一點的避障最短時間路徑的問題。首先，根據(jù)題意，找出公共切點，得出轉(zhuǎn)彎時最大圓和最小圓的圓心坐標(biāo)，確定圓心的變化*圍；其次，依據(jù)圓心的變化*圍，得出轉(zhuǎn)彎半徑的變化*圍；然后，利用軟件編程來求解最短時間路徑通用模型；最后，根據(jù)最短時間路徑通用模型，得出所有結(jié)果，通過比較最終得出機器人從O(0,0)出發(fā)，到達A的最短時間路徑的總路程和總時間以及行走路徑如下：O→A最短時間路徑為471.12個單位，最短時間為94.229秒第一條線段起始坐標(biāo)為〔0，0〕終點坐標(biāo)為〔77.66，220.07〕第二條線段起始坐標(biāo)為〔69.82，212.07〕終點坐標(biāo)為〔300，300〕圓弧半徑為12.83個單位圓心坐標(biāo)為〔82，208〕最后，我們對模型進展了改進、檢驗、評價與推廣。關(guān)鍵詞：優(yōu)化模型最短路程線圓構(gòu)造最短時間窮舉法1問題重述1.1背景資料圖1是一個800×800的平面場景圖，在原點O(0,0)點處有一個機器人，它只能在該平面場景*圍內(nèi)活動。圖中有12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：編號障礙物名稱左下頂點坐標(biāo)其它特性描述1正方形(300,400)邊長2002圓形圓心坐標(biāo)(550,450)，半徑703平行四邊形(360,240)底邊長140，左上頂點坐標(biāo)(400,330)4三角形(280,100)上頂點坐標(biāo)(345,210)，右下頂點坐標(biāo)(410,100)5正方形(80,60)邊長1506三角形(60,300)上頂點坐標(biāo)(150,435)，右下頂點坐標(biāo)(235,300)7長方形(0,470)長220，寬608平行四邊形(150,600)底邊長90，左上頂點坐標(biāo)(180,680)9長方形(370,680)長60，寬12010正方形(540,600)邊長13011正方形(640,520)邊長8012長方形(500,140)長300，寬60圖1800×800平面場景圖1.2信息〔1〕在圖1的平面場景中，障礙物外指定一點為機器人要到達的目標(biāo)點。規(guī)定機器人的行走路徑由直線段和圓弧組成，其中圓弧是機器人轉(zhuǎn)彎路徑?！?〕機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位?！?〕機器人直線行走的最大速度為個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如果超過該速度，機器人將發(fā)生側(cè)翻，無法完成行走。1.3問題要求〔1〕機器人不與障礙物發(fā)生碰撞，假設(shè)碰撞發(fā)生，則機器人無法完成行走?！?〕機器人行走線路與障礙物的距離至少超過10個單位，否則將發(fā)生碰撞。1.4問題提出請建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的數(shù)學(xué)模型。對場景圖中4個點O(0，0)，A(300，300)，B(100，700)，C(700，640)，具體計算；問題一：機器人從O(0，0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑。問題二：機器人從O(0,0)出發(fā)，到達A的最短時間路徑。注：要給出路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間。2問題假設(shè)與符號說明2.1問題假設(shè)1.假設(shè)機器人為一個質(zhì)點；2.假設(shè)機器人在轉(zhuǎn)彎時的速度可以瞬間變換；2.2符號說明：轉(zhuǎn)彎半徑：路徑的總長度：機器人行走的速度 ：第段圓弧的長度：第段切線的長度：機器人的最大轉(zhuǎn)彎速度：障礙物上的任意點與行走路徑之間的最短距離3問題分析3.1問題一的分析首先，根據(jù)題意可知，機器人行走線路與障礙物的距離至少超過10個單位，由此條件可畫出機器人的危險區(qū)域與行走區(qū)域。其次，每個拐角處畫一個半徑為10的四分之一圓弧，通過采用拉繩子的方法尋找可能的最短路徑〔比方求和之間的最短路徑，可以連接和之間的一段繩子，以拐角處的圓弧為支撐拉緊，則這段繩子的長度便是到A的一條可能的最短路徑〕。然后,采用窮舉法列出到每個目標(biāo)點的可能路徑的最短路徑，比較其大小便可求得到目標(biāo)點的最短路徑。最后，求定點(0,0)經(jīng)過中間的假設(shè)干點按照一定的規(guī)則繞過障礙物到達目標(biāo)點，這使得不僅要考慮經(jīng)過障礙物拐點的問題，還需考慮經(jīng)過路徑中的目標(biāo)點處轉(zhuǎn)彎的問題，這時簡單的線圓構(gòu)造就不能解決這種問題，可以在拐點及途中目標(biāo)點處都采用最小轉(zhuǎn)彎半徑的形式，最終求得最短路徑。3.2問題二的分析首先，由題意可知，轉(zhuǎn)彎速度與轉(zhuǎn)彎半徑有關(guān)，在一定*圍內(nèi)半徑越大，速度越大。因此到的最短路徑不一定是最短時間路徑。其次，在問題一中以求出，機器人走限定區(qū)域的局部邊界時路徑能到達最小。在機器人不發(fā)生碰撞且路徑盡可能最短的同時，選擇擴大半徑以保證時間最短。通過猜想與證明,計算出圓心的坐標(biāo)*圍與轉(zhuǎn)彎半徑。最后，把所有可能路徑化成問題一中的線圓構(gòu)造，利用軟件進展求解找出最短時間路徑。4模型準(zhǔn)備4.1模型準(zhǔn)備一假設(shè)：具有圓形限定區(qū)域的最短路徑是由兩局部組成的：一局部是最短直線路徑，另一局部是限定區(qū)域的局部邊界，這兩局部是相切的，互相連接的。證明：假設(shè)在平面中有A〔a，0〕和B〔-a，0〕兩點，中間有一個半圓形的障礙物，證明從A到B的最路徑為。圖4-1平面上連接兩點最短的路徑為直線段，但是連接兩點的線段于障礙物相交，所以設(shè)法嘗試折線路徑。在y軸上取一點D〔0，d〕，假設(shè)適當(dāng)大，則折線ADB與障礙物不相交，折線ADB的長度為：顯然隨著的減小而減小，當(dāng)減小時，即,使得BC、CA與障礙物相切，切點分別為E和F,顯然ACB是折線路徑中最短的。由于,所以,因此易知弧度小于的長，即,從而,記線段BE、弧度EF、線段FA為AEFB,則AEFB為折線路中最短路徑。準(zhǔn)備：由假設(shè)可知，起點到目標(biāo)點最短路徑應(yīng)該是假設(shè)干個線圓構(gòu)造所組成。障礙物在拐點處的危險區(qū)域是一個半徑為10的圓弧，求兩點之間的最短路徑中的轉(zhuǎn)彎半徑應(yīng)該按照最小的轉(zhuǎn)彎半徑來算才能到達最優(yōu)。線圓構(gòu)造4-2(1)如上圖，設(shè)A為起點，B為目標(biāo)點，圓心為O，圓的半徑為r，C和D分別為機器人經(jīng)過拐點分別于隔離危險線拐角小圓弧的切點，AB的長度為a，AO的長度為b，BO的長度為c，角度,,，.求的長度，設(shè)為，解法如下：：在：在中：所以：從而可得：〔2〕對于下面兩種情況不能直接采用線圓構(gòu)造來解決，需要做簡單的變換。情況一：對于圓心連線與切點連線穿插的情況。線圓構(gòu)造4-3假設(shè)兩圓心坐標(biāo)分別為和,半徑均為r，P點坐標(biāo)為，可以求得:因此可以利用〔1〕中的方法，先求A到P，再求P到B，這樣分兩段就可以求解。同理如果有更多的轉(zhuǎn)彎，同樣可以按照此種方法分解。情況二：對于圓心連線與切點連線平行的情況。線圓構(gòu)造4-4依然假設(shè)圓心坐標(biāo)分別為和,半徑均為r，可以得到：直線方程為：因為公切線DE與平行，所以DE的直線方程可以表示為：其中：把公切線的方程于圓的方程聯(lián)立，可求得切點D和E的坐標(biāo)。用D和E任意一點作為分割點都可以將上圖分割成兩個4-2所示的線圓構(gòu)造，這樣就可以對其進展求解。同理，多個這樣的轉(zhuǎn)彎時，用同樣的方法可以進展分割。4.2模型準(zhǔn)備二假設(shè):如果一個圓環(huán)可以繞著環(huán)上一個定點轉(zhuǎn)動，則過圓環(huán)外兩定點連接一根繩子，并以該圓環(huán)為支撐拉緊繩子，到達平衡狀態(tài)時，圓心與該頂點以及兩條切線的延長線的交點共線。圖4-5證明：如圖4-5所示，E點就是圓環(huán)上的一個頂點，與圓環(huán)相切的路線，就是切線AC和BD的延長線的交點，證明、E、三點共線。用力學(xué)的知識進展證明，兩邊拉力相等，設(shè)為，它們的合力設(shè)為，定點對圓環(huán)的作用力設(shè)為。由幾何學(xué)的知識可知，與共線，根據(jù)力的平衡條件可得：=-即與共線。綜上所述、和三點一定共線。準(zhǔn)備：根據(jù)假設(shè)的定理可求出機器人從A繞過障礙物經(jīng)過P點到達目標(biāo)點B的最短路徑〔如圖4-6〕，采用以下方法：用一根釘子使一個圓環(huán)定在P點，使這個圓環(huán)能夠繞P點轉(zhuǎn)動。然后連接A和B的繩子并以這些轉(zhuǎn)彎處的圓弧為支撐〔這里轉(zhuǎn)彎處圓弧的半徑均按照最小轉(zhuǎn)彎半徑來計算〕，拉緊繩子，則繩子的長度就是A到B的最短距離。可以把路徑圖抽象為以下的幾何圖形進展求解：圖4-6如圖，A是起點，B是終點，和是兩個固定的圓，是一個可以繞P(p，q)點轉(zhuǎn)動的圓環(huán)，三個圓的半徑均為r，C、D、E、F、G、H均為切點。a、b、c、e，f分別是AM、MO、AO、AN、ON的長度。A、B、M、N均是點，O是未知點。則最短路徑就可以表示為：因為點的坐標(biāo)未知，不能用線圓構(gòu)造對其進展求解。故得先求出點的坐標(biāo)。設(shè)坐標(biāo)為〔m，n〕，、、、、分別為〔=1、2、3、4、5〕，、、分別為、、。得到如下關(guān)系：在中：在中：在中：在中：則：又因為一定會在的角平分線上，所以滿足：采用向量的形式來求，易知的一個方向向量：而與垂直，故其一個方向向量：而：所以：綜合以上式子可以求得的坐標(biāo)，從而可以得出路徑的長為：5模型的建立與求解5.1模型一的建立與求解根據(jù)題意，機器人行走線路與障礙物間的最近距離為10個單位，由此可以畫出機器人行走的可行區(qū)域與危險區(qū)域，如以下圖5-1所示，陰影局部代表可行區(qū)域，白色局部代表危險區(qū)域。圖5-1機器人行走的可行區(qū)域與危險區(qū)域假設(shè)機器人從起點O到目標(biāo)點，由題可知路徑由圓弧和線段組成，設(shè)有m條線段，n條圓弧。則目標(biāo)函數(shù)可以表示為：用此模型就可以對起點到目標(biāo)點之間的路徑進展優(yōu)化求解。如圖5-2解決的是O到目標(biāo)點A的最短路徑問題，圖中給出了可能的兩條路徑的最短路徑〔圖中的藍色所示〕，可以分別計算出兩條可能路徑的最短路徑的長度，然后進展比較，取最小者就是O到目標(biāo)點A的最優(yōu)路徑。圖5-2到達A的可能最短路徑利用編程〔程序見附錄〕對模型進展求解，結(jié)果如下：O從路線1到達目標(biāo)點A，解得最短路徑為498.97個單位。O從路線2到達目標(biāo)點A，解得最短路徑為471.04個單位。綜合①②所述，O到目標(biāo)點A的最短路徑為471.04個單位。如圖5-3解決的是O到目標(biāo)點B的最短路徑問題，圖中給出了可能的六條路徑的最短路徑〔圖中的線條所示〕，可以分別計算出六條可能路徑的最短路徑的長度，然后進展比較，取最小者就是O到目標(biāo)點B的最優(yōu)路徑。圖5-3到達B的可能最短路徑利用編程〔程序見附錄〕對模型進展求解，結(jié)果如下：O從路線1到達目標(biāo)點B，在拐點a處分為兩條路線，即圖中的黃色路線與紅色路線。a1.從路線1走紅色路線：這條路徑是由5條直線和4段圓弧組成，直接用簡單的線圓構(gòu)造無法解出。于是做如下變換：首先，找出兩圓弧的切線段與兩圓心連線的交點M；其次，用線圓構(gòu)造4-2的解法計算，分別求O到M和M到下一個交點，以此類推直到目標(biāo)點B，分四局部求解；最后把這四局部的和相加，便可求出O到B的最短路徑。求得結(jié)果為945.96個單位。b1.從路線1走黃色路線：同理這條路徑是由4條直線和3段圓弧組成，同樣可以采取a1中的變換，分三局部求解，求得結(jié)果為1058.4個單位。綜上：O從路線1到達目標(biāo)點B走紅色路線路徑最短，最短路徑為945.96個單位。O從路線2到達目標(biāo)點B，在拐點b處分為兩條路線，即圖中的黃色路線與紅色路線。a2.從路線2走紅色路線：同理這條路徑是由5條直線和4段圓弧組成，同樣可以采取a1中的變換，分四局部求解，求得結(jié)果為878.05個單位。b2.從路線2走黃色路線：同理這條路徑是由4條直線和3段圓弧組成，同樣可以采取a1中的變換，分三局部求解，求得結(jié)果為990.17個單位。綜上：O從路線2到達目標(biāo)點B走紅色路線路徑最短，最短路徑為878.05個單位。O從路線3到達目標(biāo)點B，在拐點c處分為兩條路線，即圖中的黃色路線與紅色路線。a3.從路線3走紅色路線：同理這條路徑是由6條直線和5段圓弧組成，同樣可以采取a1中的變換，分五局部求解，求得結(jié)果為853.71個單位。b3.從路線3走黃色路線：同理這條路徑是由5條直線和4段圓弧組成，同樣可以采取a1中的變換，分四局部求解，求得結(jié)果為971.23個單位。綜上：O從路線3到達目標(biāo)點B走紅色路線路徑最短，最短路徑為853.71個單位。綜合①②③所述，O到目標(biāo)點B的最短路徑為853.71個單位。如圖5-4解決的是O到目標(biāo)點C的最短路徑問題，圖中給出了可能的三條路徑的最短路徑〔圖中的藍色所示〕，可以分別計算出三條可能路徑的最短路徑的長度，然后進展比較，取最小者就是O到目標(biāo)點C的最優(yōu)路徑。圖5-4到達C的可能最短路徑利用編程〔程序見附錄〕對模型進展求解，結(jié)果如下：O從路線1到達目標(biāo)點C，同理這條路徑是由6條直線和5段圓弧組成，同樣可以采取a1中的變換，分五局部求解，求得結(jié)果為1088.20個單位。O從路線2到達目標(biāo)點C，同理這條路徑是由6條直線和5段圓弧組成，同樣可以采取a1中的變換，分五局部求解，求得結(jié)果為1102.60個單位。O從路線3到達目標(biāo)點C，同理這條路徑是由7條直線和6段圓弧組成，同樣可以采取a1中的變換，分六局部求解，求得結(jié)果為1253.40個單位。O從路線4到達目標(biāo)點C，同理這條路徑是由8條直線和7段圓弧組成，同樣可以采取a1中的變換，分七局部求解，求得結(jié)果為1239.80個單位。綜合①②③④所述，O到目標(biāo)點C的最短路徑為1088.20個單位。(4)如圖5-5解決的是O→A→B→C→O的最短路徑問題，可利用準(zhǔn)備二的理論對其進展計算，得出最短路徑。圖5-5O→A→B→C→O的最短路徑利用編程〔程序見附錄〕對模型進展求解，結(jié)果如下：藍色線為O→A→B→C→O的最短路徑，這條路徑由17條直線和16段圓弧組成，在個目標(biāo)處用準(zhǔn)備二進展計算，同樣采取a1中的變換，分十五局部求解，求得結(jié)果為2730.01個單位。5.2模型二的建立與求解由問題一可知，機器人從O(0,0)出發(fā)，到達A的行走路徑有兩條如以下圖：圖5-6因為線路2比線路1的路程短27.93個單位，所以舍去線路1，選擇線路2。由題可知，機器人最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。所以，在一定*圍內(nèi)，轉(zhuǎn)彎半徑越大，最大轉(zhuǎn)彎速度也就越大，行走時間減小。根據(jù)以上分析，做出以下假設(shè)：假設(shè)：以所走弧線的中點為公共切點，將最小圓的圓心與公共切點連接并延長，所得直線即為以一樣半徑不同圓心所有圓的最優(yōu)路徑〔為所走弧長路徑〕，其中所有最優(yōu)圓的圓心，即為在不與障礙物發(fā)生碰撞的情況下圓心的變化*圍。證明：以任意點、為圓心,其中點、不在公共切點與最小圓的圓心連線的直線上，另外在這條直線上找一點。然后分別以點、、為圓心，作出一樣半徑的圓并都內(nèi)切于公共切點，如以下圖：圖5-7分別求得以點、、為圓心，一樣半徑的圓的不同路徑距離分別為489.61個單位、483.47個單位、472個單位，通過比照可知，當(dāng)半徑一樣時，圓心在公共切點與最小圓的圓心連線的直線上所走的路徑最短。又因為公共切點正好為所走弧線的中點，所以此直線與正方形的對角線重合，因此可得直線為。同時也驗證假設(shè)是正確的。通過上述證明可知，圓心在直線上變化為最優(yōu)。找出圓心在直線上變化時，沒有與障礙物間發(fā)生碰撞的最大圓的圓心位置與最小圓的圓心位置，設(shè)最大圓的圓心坐標(biāo)為，如以下圖所示：圖5-8當(dāng)線段時，以交點為圓心，為半徑畫圓，此時的圓為沒有與障礙物間發(fā)生碰撞的最大圓，又因為點為直線與以點〔80,210〕為圓心半徑為10個單位圓的交點，由此可得；解得點坐標(biāo)為根據(jù)兩點之間的距離公式可知：解得最大圓的圓心坐標(biāo)為同理，可知最小圓的圓心坐標(biāo)為。由上述可知，圓心是在直線直線上移動，因此可推出圓半徑為：根據(jù)題意，機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。所以，當(dāng)一定時，機器人轉(zhuǎn)彎的半徑越大，最大轉(zhuǎn)彎速度也就越大。又因為機器人直線行走的最大速度為個單位/秒，所以當(dāng)趨于無窮大時0〔其中因為不能碰撞障礙物所以不能無限趨于無窮大〕，最大轉(zhuǎn)彎速度也就趨于個單位/秒，所以在轉(zhuǎn)彎時，圓弧的半徑增大，轉(zhuǎn)彎速度加快。如圖5-9解決的是O到目標(biāo)點A的最短時間路徑問題。圓心d從小圓到大圓內(nèi)變化，圖中給出了O→A的所有可能時間路線。計算出所有路線的時間，比較其大小，找出最短時間路徑。圖5-9因為圓心是一個動點，所以可以得到很多條路徑。結(jié)合準(zhǔn)備以中的定理，利用編程〔程序見附錄〕對模型進展求解，找出時間最短的路徑，結(jié)果如下：O→A的最短時間路徑為471.12個單位，最短時間為94.229秒。5.3模型結(jié)果由題意可知，路徑由圓弧和線段組成，設(shè)有m條線段，n條圓弧。機器人直線行走的最大速度為個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為。經(jīng)過推算可知轉(zhuǎn)彎半徑，假設(shè)機器人在直線上一直以5個單位/秒行走，根據(jù)公式可以得到最大轉(zhuǎn)彎速度為個單位/秒。模型一的結(jié)果O→A的最短路徑為471.04個單位，根據(jù)上述公式得到總時間為96.022秒。最短路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間如下表：表5-10O→A每條線段與圓弧的坐標(biāo)及總路程與總時間O→A最短路為471.04個單位，總時間為96.022秒第條線段起始坐標(biāo)076.610219.41終點坐標(biāo)70.5300213.12300第條圓弧圓心坐標(biāo)(80,210)〔2〕O→B的最短路徑為853.71個單位，根據(jù)上述公式得到總時間為179.084秒。最短路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間如下表：表5-11O→B每條線段與圓弧的坐標(biāo)及總路程與總時間O→B最短路徑為853.71個單位，總時間為179.084秒第條線段起始坐標(biāo)052147.96,230225.5,140.690305.55444.79470538.35596.35終點坐標(biāo)50.14141.68222.04230144.5100301.06440.55460.21530591.65700第條圓弧圓心坐標(biāo)60150220220150300435470530600〔3〕O→C的最短路徑為1088.20個單位，根據(jù)上述公式得到總時間為222.046秒。最短路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間如下表：表5-12O→C每條線段與圓弧的坐標(biāo)及總路程與總時間O→C最短路徑為1088.20個單位，總時間為222.046秒第條線段起始坐標(biāo)0232.17418.41492.06730727.72050.2494.59206.08520606.36終點坐標(biāo)232.11412.17491.66728.2373070050.2390.24205.51514.3600640第條圓弧圓心坐標(biāo)23041050072072060100200520600O→A→B→C→O的最短路徑為2730.01個單位，根據(jù)上述公式得到總時間為568.68秒。最短路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間如下表：表5-13O→A→B→C→O每條線段與圓弧的坐標(biāo)及總路程與總時間O→A→B→C→O最短路徑為2730.01個單位，總時間為568.68秒第條線段起始坐標(biāo)076.72300.6225.5140.86108.960219.45307.49538.35595.93704.09終點坐標(biāo)70.51294.35229.54144.598.96270.87213.14295.04533.01591.65690.06689.96第條線段起始坐標(biāo)272370435.59540679.77701.32689.8670671.71740732.12637.96終點坐標(biāo)368430534.41670699.22727.67670.2670738.29740642.26606.41第條線段起始坐標(biāo)730727.94491.66412.17232.11600513.92205.5190.2450.23終點坐標(biāo)730492.06418.41232.170520206.0894.5950.240第條圓弧圓心坐標(biāo)80291.06220150108.09270210304.49530600694.13680第條圓弧圓心坐標(biāo)370430540670708.99720680680730730644.37600第條圓弧圓心坐標(biāo)72050041023052020010060模型二的結(jié)果O→A的最短時間路徑為471.12個單位，根據(jù)上述公式得到總時間為94.229秒。最短路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間如下表：表5-14O→A每條線段與圓弧的坐標(biāo)及總路程與總時間O→A最短時間路徑為471.12個單位，最短時間為94.229秒第條線段起始坐標(biāo)069.820212.07終點坐標(biāo)77.66300220.07300第條圓弧圓心坐標(biāo)(82,208)6模型改進6.1對有多個障礙物的分析在本文解決了機器人避障問題，題中只有四按照線個障礙物，圓構(gòu)造畫出從起點到達目標(biāo)點的路徑是有限的，這完全可以采用窮舉法把這些路徑列出來，然后比較大小取最小者即可。但是我們可以設(shè)想如果這個區(qū)域內(nèi)有n個障礙物，則按照線圓構(gòu)造從起點到達目標(biāo)點的可能路徑就有無數(shù)多條，這時如果再采用窮舉法是不現(xiàn)實的。因此必須尋求新的算法來解決這個問題。由上述分析可以得到這樣一個想法：先求出所有的切線，包括出發(fā)點和目標(biāo)點到所有圓弧的切線以及所有圓弧與圓弧之間的切線，然后把這且曲線看成是圖5-1中的，給這些定點賦一個等于切線長度的權(quán)值，如果*兩條切線有一個公切圓弧，則代表這兩條曲線的頂點是一條直線的兩個端點，邊上的權(quán)值等于這兩條切線之間的劣弧長度。然后在這*圖中加一個原點和終點，則在所有代表出發(fā)點與其它圓弧之間切線的頂點與原點連成一條邊，權(quán)值均為0，同理在所有代表目標(biāo)點到其它圓弧切線的頂點與終點連成一條邊，權(quán)值均為0，這樣題目就轉(zhuǎn)化成了求原點到達終點之間的最短路徑問題了，這里最短路徑就是指經(jīng)過所有頂點與邊的權(quán)值之和最小。6.2進一步求解在有假設(shè)干個障礙物的區(qū)域中，按照線圓構(gòu)造畫出從出發(fā)點到目標(biāo)點的路徑圖，依據(jù)6.1中的想法轉(zhuǎn)換成了下面這*圖，圖中的和點就是添加的原點和終點，其它節(jié)點均是出發(fā)點和目標(biāo)點到圓弧的切線和圓弧與圓弧之間的切線轉(zhuǎn)化而成。圖6-1對于最短路徑的求解，有以下步驟：〔1〕首先，畫出出發(fā)點和目標(biāo)點和各個圓弧的切線，以及圓弧與圓弧之間的切線，但是切線有可能經(jīng)過障礙物的內(nèi)部或危險區(qū)域，也可能出現(xiàn)切線重復(fù)的狀況，既有很多不合法的切線。于是對模型進展以下修正：1.檢驗切線兩個端點是否在障礙物內(nèi)部。2.檢驗切線是否障礙物的對角線相交。3.檢驗圓弧所對應(yīng)的圓心，即障礙物的頂點到切線的距離是否小于1。如果以上三種情況滿足其一，則規(guī)定對應(yīng)這段切線的頂點為M〔M為無窮大〕。另外還有如以下圖所示的一種特殊情況：兩個大小一樣在同一水平或者豎直位置上，不考慮切線滿足1、2、3的狀況它們由2條內(nèi)公切線，8條外公切線，但是有6條外公切線是重復(fù)的。因此作如下規(guī)定:如果*條切線與*段圓弧相切，且切點不在切線的端點上，則該切線為不合法。權(quán)值矩陣中表示它的頂點也為M。圖6-2〔2〕然后把合法的切線與這些切線之間的劣弧轉(zhuǎn)化成如6-1所示的形式。假設(shè)轉(zhuǎn)化過后有m條合法切線，則就有m個頂點，設(shè)這些點的權(quán)值〔〕，即第條合法曲線的長度。為邊的權(quán)值，即第條弧的長度?！?〕然后把路徑圖進展轉(zhuǎn)化，按照求得權(quán)值矩陣給圖中的頂點及邊長賦值。〔4〕最后利用軟件編程求得最短路徑。7模型檢驗 利用較精準(zhǔn)地作出模型一中O點到A、B、C點的可能路徑，并度量出最短路徑的長度，然后與此題運用算出的最短路徑作比照得出下表：結(jié)果結(jié)果絕對誤差相對結(jié)果誤差471.12471.040.080.0170%853.71853.720.010.0012%1088.201088.160.040.0037% 由上表可知誤差很小，最大誤差百分比為0.0170%，所以此題所計算的結(jié)果已較為準(zhǔn)確。8模型的評價與推廣8.1模型的評價優(yōu)點：建立的優(yōu)化模型有成熟的理論根底，又有相應(yīng)的專業(yè)軟件支持，可信度較高.模型優(yōu)化后用解析幾何進展求解，準(zhǔn)確度較高。模型簡單易懂，便于實際檢驗及應(yīng)用。缺點：〔1〕模型建立理論嚴謹，但由于計算機軟件的系統(tǒng)選擇使結(jié)果有一定誤差?！?〕由于本模型是在假設(shè)條件下所建立，其影響因素不可能全部考慮在內(nèi)，因此與實際情況存在一定誤差?！?〕在障礙物較多時，且形狀不規(guī)則時，模型需要進一步改進。8.2模型的推廣本案例建立的二個模型解決了機器人避障的問題，采用了窮舉法列出多條路徑選擇最短路徑，因此，本模型還可以應(yīng)用與其他相類似的最優(yōu)方案設(shè)計，如：輸送電線選擇最短路徑、航海中防止觸碰危險區(qū)域等問題，尤其對機器人的避障是研究者很關(guān)心的問題，此模型的建立更是簡便易行，效果明顯。9參考文獻[1]吳振奎王全文主編?運籌