機 器 人 避 障 問 題

1、D題 機 器 人 避 障 問 題摘 要 本文針對機器人避障問題，建立了相應地優(yōu)化模型，解決了機器人從出發(fā)點到目標點最短路徑和最短時間路徑的問題。模型一:針對問題一的分析，建立了最短路徑和最短時間路徑的通用模型；首先，根據(jù)機器人行走線路與障礙物間的最近距離，確定機器人可行走的區(qū)域；其次，結(jié)合題中給出的信息，根據(jù)機器人直線行走的長度與轉(zhuǎn)彎時的弧長，建立最短路徑的通用模型；最后，根據(jù)機器人直線行走的速度與轉(zhuǎn)彎速度速度建立最小時間路徑的通用模型。模型二：針對問題二的分析，根據(jù)模型一中建立的最短路徑的通用模型計算各路徑的總路程。機器人在可行區(qū)域內(nèi)從、和的路徑不止一條，以所走路程相對較小為原則，畫出各路線

2、相對較小的路徑。求出最短的路徑如下表所示：出發(fā)點到達的目的點最短路徑的線路最短路徑(單位)所用總時間（秒） 471.03796.0176 853.70195.76 1088.1222.60 2733.4570.97模型三：針對問題三的分析，根據(jù)模型一中建立的最短時間路徑模型計算機器人從出發(fā)，到達A的最短時間路徑。機器人在轉(zhuǎn)彎時有兩種方式：一種是在拐點和節(jié)點都采用最小轉(zhuǎn)彎半徑的形式，另一種是適當擴大拐點處的轉(zhuǎn)彎半徑，使得機器人能夠沿直線通過途中的目標點。最短時間路徑具體情況如下表所示：出發(fā)點到達的目的點圓弧的起點圓弧的終點圓心最短時間路徑（單位）所用總時間（秒）(72.33,196.09)(87

3、.89,195.06)(81,209)474.994.98最后，對模型進行了評價與推廣，保證了模型的有效可行。關鍵詞： 避障 優(yōu)化模型 最短路徑 最短時間路徑 直線與轉(zhuǎn)彎的速度1問題重述1.1基本情況（1）有一個800×800的平面場景圖（見附錄A），在原點O(0, 0)點處有一個機器人，只能在該平面場景范圍內(nèi)活動。圖中有12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學描述（見附錄A）。 （2）在平面場景圖中，障礙物外指定一點為機器人要到達的目標點（要求目標點與障礙物的距離至少超過10個單位）。規(guī)定機器人的行走路徑由直線段和圓弧組成，其中圓弧是機器人轉(zhuǎn)彎路徑。 （3

4、）機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無法完成行走。 （4）機器人直線行走的最大速度為個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如果超過該速度，機器人將發(fā)生側(cè)翻，無法完成行走。(5)機器人從原點O(0, 0)出發(fā)所要到達各目標點的坐標如下表所示：1-1各目標點的坐標目標點ABC各目標點的坐標(300, 300)(100, 700)(700, 640)1.2問題提出 問題

5、一：建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的通用數(shù)學模型。 問題二：對場景圖中3個目標點（如上表所示），具體計算機器人從出發(fā)，、和的最短路徑。問題三： 機器人從出發(fā)，到達A的最短時間路徑。注：要給出路徑中每段直線段或圓弧的起點和終點坐標、圓弧的圓心坐標以及機器人行走的總距離和總時間。2模型假設與符號說明2.1 模型假設 （1）在平面場景圖中機器人看成一質(zhì)點； （2）將平面場景圖看成是放在一個平面直角坐標系中； （3）機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度只能無限接近但不能超過機器人直線行走的最大 速度； （4）機器人在直線路段時以最大的速度行走； （5）機器人在行走過程中不會出現(xiàn)故障

6、； （6）機器人在轉(zhuǎn)彎時以所能達到最大的轉(zhuǎn)彎速度行走； （7）機器人經(jīng)過目標點時以圓弧的形式轉(zhuǎn)彎。2.2 符號說明 平面直角坐標系的橫坐標； 平面直角坐標系的縱坐標； 機器人直線行走的最大速度； 機器人轉(zhuǎn)彎時的最大速度； 轉(zhuǎn)彎半徑； 路徑的總長度； 第段切線的長度； 第段圓弧的長度； 機器人在行走過完路徑時的總時間。3問題分析3.1 問題一的分析 首先，將800×800的平面場景圖等效成一個平面直角坐標系； 其次，平面場景圖中有12個障礙物，障礙物外指定一點為機器人要到達的目標點，為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距離為10個單位，我們可以用包絡線畫出機器

7、人行走的危險區(qū)域； 再次，計算機器人在行走的過程中會不會遇到障礙物可分為兩種情況：第一種情況：機器人在行走的過程未遇到障礙物，從起點直接到達終點即為此時最短的路徑，根據(jù)兩點間的距離公式與機器人直線行走的速度以求出最短路程與總時間；第二種情況：機器人在行走的過程遇到障礙物，根據(jù)路徑由直線段和圓弧組成，其中機器人轉(zhuǎn)彎路徑通過圓弧實現(xiàn)，采用拉繩法尋找機器人行走的路徑（比如求O和A之間的最短路徑，我們就可以連接R和A之間的一段繩子，以拐角處的圓弧為支撐拉緊，那么這段繩子的長度便是O到A的一條路徑）可分為兩種方案：方案一：以拐角處為圓心，以機器人行走線路與障礙物間的最近距離不少于10個單位為前提所能達到

8、最大的半徑畫圓，利用拉繩法即可找出一條機器人的行走路徑；方案二：以拐角處為圓心，以滿足在行走過程中不與障礙物碰撞時的最小半徑10為半徑畫圓，同理利用拉繩法即可找出一條機器人的行走路徑；最后，由上述分析結(jié)合實際情況可知，在本模型中機器人行走過程中不會出現(xiàn)第一種情況，要找出機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑，方案一不滿足此要求，所以對上述第二種情況與方案二進行分析，從而建立最優(yōu)的避障短路徑和時間路徑的通用數(shù)學模型。3.2 問題二的分析 首先，根據(jù)對問題一的第二種情況與方案二進行的分析，機器人在可行走的區(qū)域內(nèi)一點到達另一點的路徑不止一條，以所走路程相對較小為原則，分別畫出在滿足

9、上述要求的各條路徑； 其次，具有圓形限定區(qū)域的路徑是由兩部分組成的：一部分是平面上的自然最短路徑（即直線段），另一部分是限定區(qū)域的部分邊界，這兩部分是相切的，互相連接的。（即問題分析中的拉繩子拉到最緊時的狀況）分別計算從原點到各目標點各種路徑的總路程（機器人所走的直線路程與所走圓弧的路程）； 最后，采用窮舉法具體計算出機器人從出發(fā)，、和的最短路徑。分別計算原點O到每個目標點的各路徑的最短路程，然后比較其大小便可得出原點O到目標點的最短路徑。3.3 問題三的分析首先，根據(jù)題意可知，要求最短時間路徑，必須先確定直線段和圓弧的長度，而圓弧的長度與兩條直線段與轉(zhuǎn)彎時圓弧所在圓的切點有關，同過一定點、且

10、半徑相同的圓與直線段相切所得圓弧長度不一樣，即當半徑相同時，需確定圓心的最佳位置，從而可得出圓心的范圍。其次，根據(jù)機器人的可行區(qū)域與圓心的范圍，以確定機器人轉(zhuǎn)彎時半徑的范圍。最后，根據(jù)不同半徑、不同圓心所得的圓弧和直線段長度不同，算出每個路徑所需的時間，再比較得出最小時間，從而得出最小時間路徑，并算出每個切點的坐標。4模型建立與求解4.1模型一的建立與求解針對問題一的分析以下是機器人避障最短路徑和時間路徑的通用數(shù)學模型的建立過程：將800×800的平面場景圖等效成一個平面直角坐標系，該場景圖中有12個障礙物，障礙物外指定一點為機器人要到達的目標點，為了不與障礙物發(fā)生碰撞，同時要求機器

11、人行走線路與障礙物間的最近距離為10個單位，我們可以包絡線畫出機器人行走的危險區(qū)域，這樣的話，拐角處就是一個半徑為10的四分之一圓弧，機器人除去危險區(qū)域的活動范圍如下圖所示： 圖4-1 機器人除去危險區(qū)域的活動范圍 假設機器人從起點O到目標點，由問題一的析可知路徑一定是由圓弧和線段組成，設有m條線段，n條圓弧。那么最短路徑的通用模型可以表示為： 機器人在行走的過程中會不會遇到障礙物可分為兩種情況：第一種情況：機器人在行走的過程未遇到障礙物，從起點直接到達終點即為此時最短的路徑，根據(jù)兩點間的距離公式與機器人直線行走的速度以求出最短路程與總間；設機器人在行走時的起點與所要到達的終點分別為。此時的最

12、短路徑為： 機器人所要行走的路程為： 因為機器人在行走過程總未遇到障礙物，所以機器人是以直線進行行走，根據(jù)它直線行走時的速度，可以求出總的行走時間： 第二種情況：機器人在行走的過程遇到障礙物，根據(jù)路徑由直線段和圓弧組成，其中機器人轉(zhuǎn)彎路徑通過圓弧實現(xiàn)，采用拉繩法尋找機器人行走的路徑（比如求O和N之間的最短路徑，我們就可以連接O和N之間的一段繩子，以拐角處的圓弧為支撐拉緊，那么這段繩子的長度便是O到N的一條路徑）可分為兩種方案：方案一：以拐角處為圓心，以機器人行走線路與障礙物間的最近距離不少于10個單位為前提所能達到最大的半徑R畫圓，利用拉繩法即可找出一條機器人的行走路徑；方案二：以拐角處為圓心

13、，以滿足在行走過程中，不與障礙物碰撞時的最小半徑為半徑畫圓，同理利用拉繩法即可找出一條機器人的行走路徑； 兩種方案中用圖形表示如下圖所示：圖4-2 兩種方案所反映的的情形方案一的求解：并根據(jù)機器人轉(zhuǎn)彎時的半徑與直線行走的速度，建立最短時間路徑的通用模型，用此模型就可以對起點到目標點之間的路徑進行優(yōu)化求解。由上圖可知機器人要想從O點到達目的地N點，在行走的過程中會遇到兩個障礙物，以拐角處為圓心，以機器人行走線路與障礙物間的最近距離不少于10個單位為前提所能達到最大的半徑R畫圓，利用拉繩法即可找出一條機器人的行走路徑: ； 設為起點，為目標點，和分別為機器人經(jīng)過拐點分別于隔離危險線拐角小圓弧的切點

14、，圓心為，圓的半徑為R，MN的長度為a，MO的長度為b，NO的長度為c，,求的長度，設為L.解法如下： 如上圖可得有以下關系： 在中： 在中： 在中： 所以: 從而可得： 即： 機器人直線行走的最大速度為個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。假設機器人從起點O到目標點，由問題一的析可知路徑一定是由圓弧和線段組成，設有m條線段，n條圓弧。最短時間路徑的通用模型可以表示為： 用此模型就可以對起點到目標點之間的時間路徑進行優(yōu)化求解。 所以機器人在轉(zhuǎn)彎時的速度為： 機器人所走的直線段所用的時間為： 機器人所走的弧長所用的時間為： 機器人所走的直線段所用的時間為： 綜上所述，機器人按

15、照的路線行走所花費總的時間為： 同理，方案二中以拐角處為圓心，以滿足在行走過程中不與障礙物碰撞時的最小半徑為半徑畫圓，建立的最小路徑與最短時間路徑數(shù)學模型的過程同上。最后，由上述分析結(jié)合實際情況可知，在本模型中機器人行走過程中不會出現(xiàn)第一種情況，要找出機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑，方案一不滿足此要求，所以對上述第二種情況與方案二進行分析，從而建立最優(yōu)的避障短路徑和時間路徑的通用數(shù)學模型。4.2模型二的建立與求解針對問題二的分析與假設，根據(jù)問題一中建立了最小路徑的通用數(shù)學模型，以下是從原點O到各目標點最小路徑的求解過程：第一步：具有圓形限定區(qū)域的最短路徑是由兩部分組成

16、的：一部分是平面上的自然最短路徑（即直線段），另一部分是限定區(qū)域的部分邊界，這兩部分是相切的，互相連接的。（即問題分析中的拉繩子拉到最緊時的狀況）；證明：假設在平面中有A（a，0）和B（-a，0）兩點，中間有一個半圓形的障礙物，證明從A到B的最路徑為AB。A到B點在圓形障礙物的情況下，各種路徑如下圖所示：圖4-3 點A在圓形障礙物的情況下到B點的各種路徑 平面上連接兩點最短的路徑是通過這兩點的直線段，但是連接兩點的線段于障礙物相交，所以設法嘗試折線路徑。在y軸上取一點，若y適當大，則折線ACB與障礙物不相交，折線ACB的長度為： 顯然隨著y的減小而減小，減小y得，即,使得與與障礙物相切，切點分

17、別為E和F,顯然是這種折線路徑中最短的。由于滿足的角滿足,所以易知弧度EF小于的長， 即,從而 記線段AE、弧度EF、線段FB為AEFB,那么AEFB比任何折線路徑都短。 下面再考察一條不穿過障礙物的任何一條路徑，設其分別于OE和OF的延長線交與P、Q兩點，記A和P之間的路徑長度為，顯然,又由,所以,從而,同理可得。再來比較PQ之間路徑長度和的長度的大小。若PQ之間的路徑可有極坐標方程,則有,可得： 亦即路徑APQB的長度超過路徑AEFB的長度。以上證明足以說明了AEFB是滿足條件A到B的最短路徑。機器人直線行走的最大速度為個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如果超過該速

18、度，機器人將發(fā)生側(cè)翻，無法完成行走。由上述路徑APQB的長度超過路徑AEFB的長度。以上證明足以說明了AEFB是滿足條件A到B的最短路徑。線段AE、弧度EF、線段FB為AEFB,那么AEFB比任何折線路徑都短。結(jié)合實際情況，在本此模型中機器人行走過程中不會出現(xiàn)機器人在行走過程中遇不到障礙物的情況發(fā)生，且機器人在可行走的區(qū)域內(nèi)一點到達另一點的路徑不止一條，以所走路程相對較小為原則，分別畫出在滿足上述要求的各條路徑；1.下圖反映的是點O到目標點A的最短路徑問題，很顯然從原點O出發(fā)有兩條路徑(路徑a,路徑b)可以到達目標點A，機器人在行走的過程中，紅色區(qū)域就為機器人隔出了危險區(qū)域，黑線表示的就是通過

19、點的圓為支撐而拉緊的繩子，這樣計算出繩子的長度就是O到A的最短路徑。點O到目標點A的路徑如下圖所示： 圖4-4點O到目標點A的路徑 具有圓形限定區(qū)域的路徑是由兩部分組成的：一部分是平面上的自然最短路徑（即直線段），另一部分是限定區(qū)域的部分邊界，這兩部分是相切的，互相連接的。（即問題分析中的拉繩子拉到最緊時的狀況）利用編程（見附錄B）分別計算從原點O到目標點A各種路徑的總路程（機器人所走的直線路程與所走圓弧的路程）,各路徑的計算結(jié)果如下表所示： 表4-1從O點到目標點A的路徑從O點到目標點A的路徑 ab最短路徑（單位）471.037498.43 由表中信息可知原點到目標點A的最短路徑為a路徑，為

20、470.83。 最短路徑的具體情況如下表所示：表4-2最短路徑的具體情況路徑a圓弧的起點圓弧的終點圓心坐標總距離（單位）總時間（s）(70.48,213.06) （76.21,219.26）（80,210）471.03796.0176第二步：而對于下圖兩種情況我們不能直接采用線圓的結(jié)構(gòu)來解決，需要做簡單的變換。 情況一：機器人以兩圓交叉的形式進行行走的線圓結(jié)構(gòu)如下圖所示：圖4-5以兩圓交叉形式行走的線圓結(jié)構(gòu) 假設兩圓心坐標分別為和,半徑均為r，M點坐標為，那么我們很容易可以求得:這樣我們就可以利用1）中的方法，先求A到M，再求M到B，這樣分兩段就可以求解。同理如果有更多的轉(zhuǎn)彎，我們同樣可以按照

21、此種方法分解。情況二：機器人以兩圓平行的形式進行行走的線圓結(jié)構(gòu)如下圖所示：圖4-6以兩圓平行形式行走的線圓結(jié)構(gòu) 這里我們依然設圓心坐標分別為和,半徑均為r，這樣我們可以得到： 那么直線方程為： 因為公切線DE與平行，那么DE的直線方程可以表示為： 其中： 那么把公切線的方程于圓的方程聯(lián)立，渴可以求得切點D和E的坐標。這樣用D和E任意一點作為分割點都可以將上圖分割成兩個4.21所示的線圓結(jié)構(gòu)，這樣就可以對其進行求解。同理多個這樣的轉(zhuǎn)彎時，用同樣的方法可以進行分割。2.下圖解決的是原點O到目標點B的最短路徑問題，圖中給出了可能的三條路徑的最短路徑（圖中的黑線所示），我們可以分別計算出三條可能路徑的

22、最短路徑的長度，然后進行比較，取最小者就是O到目標點B的最優(yōu)路徑。點O到目標點A的路徑如下圖所示：圖4-7 點O到目標點A的路徑原點O到目標點B時所走的的路徑出現(xiàn)第二步中的兩種情況,根據(jù)兩種情況的的求解步驟，再利用編程分別計算從原點O到目標點B的各種路徑的總路程（機器人所走的直線路程與所走圓弧的路程）,各路徑的計算結(jié)果如下表所示：表4-3原點O到目標點B的路徑原點O到目標點B的路徑abcd最短路徑（單位）1016.81065.41058.4853.70由表中信息可知原點到目標點B的最短路徑為d路徑，為853.70。3.把路徑圖進行轉(zhuǎn)化，轉(zhuǎn)化后的路徑如下圖所示：圖4-8路徑轉(zhuǎn)化后的路徑由轉(zhuǎn)化后的

23、路徑，分別計算出機器人所走直線段與圓弧的路程為973.5；終上所述只有路徑d的總距離最??；具體情況如下表所示：表4-4從最短路徑d的具體情況路徑d圓弧的起點圓弧的終點圓心坐標總距離（單位）總時間（s）(50.16,301.80)(141.68,440.55)(224.47,461.06)(230,530)(124.79,624.20)(51.68,305.55) (145.53,443.94) (230,470)(212.25,523.68) (141.11,604.58)(60,300)（150,435）（220,470）（220,530）（150,600）853.70195.76 4.下圖

24、解決的是O到目標點C的最短路徑問題。圖中給出了兩條可能路徑的最短路徑（圖中的黑線所示），我們同樣可以分別計算出兩條可能的最短路徑，取最小者就是O到目標點C的最優(yōu)路徑。圖4-9 點O到目標點C的各路徑原點O到目標點C時所走的的路徑出現(xiàn)第二步中的兩種情況,根據(jù)兩種情況的的求解步驟，再利用編程分別計算從原點O到目標點C的各種路徑的總路程（機器人所走的直線路程與所走圓弧的路程）,各路徑的計算結(jié)果如下表所示：表4-5原點O到目標點C的路徑原點O到目標點C的路徑abc最短路徑（單位）1296.71189.21088.1由表中信息可知原點到目標點C的最短路徑為表4-6最短路徑c的具體情況最短路徑c圓心坐標總

25、距離（單位）總時間（s）（230,60）（410,100）（500,200）（720,520）（720,600）1088.1222.60第三步：求解從起點經(jīng)過若干個點再到達目標點的問題，適當擴大障礙物拐點處的拐彎半徑使機器人能夠沿直線通過路徑中的目標點。這樣拐點處拐彎圓弧的半徑和圓心都是個變量，對于該題，那么我們可以首先設定三個圓心、,然后按照以下步驟進行作圖： （1）給定，以為圓心，為半徑，畫圓，然后過R點做圓的切線，切點為D。然后過A點做的切線設為，切點為E。 (2)然后做F垂直于，垂足為F，F(xiàn)的長就是，然后以為圓心，為半徑畫圓。很顯然能由來確定，即。(3)然后過B點做的切線為，切點為G，

26、再過F垂直于，垂足為H，那么H的長度就是，然后以為圓心，為半徑，畫圓。很顯然能由來確定，即。(4)過C做的切線。這就完成了由R經(jīng)過A和B在到達C的路徑。(5)然后再變換、，可得到新的路徑。找出最小者即可。根據(jù)上述的分析方法，機器人行走的此路線，機器人經(jīng)過A點時所走路線同樣是弧形，所走路徑必須要經(jīng)過A，以10個單位的長度為半徑畫圓，要找出圓心在何處時所走的路程最少，其中尋找的的過程大致如下圖所示：圖4-10找過A點的最短路徑的圓心的過程圖圖中反映的是機器人要到一目標點必須要經(jīng)過經(jīng)過目標點A，分別以兩障礙物拐角處的圓心點為圓心，以10個單位為半徑畫圓，將除去機器人在行走時兩障礙物對它的危險區(qū)域；連

27、接，因為點是固定的，則是一定長，以點A為圓心，以10為半徑，畫圓；此時以10為半徑畫圓過A點的最短路徑的圓心在上，分別找出與的中點，分別為M,N點，再分別連接與，若越大，與就越長，即經(jīng)過A點所對應的弧長越長，機器人所走的總路程也會越長。根據(jù)上述角度對應弧長的關系，經(jīng)分析與多次驗證可知：分別找出與的中點M,N，連接MN, 最小，即所對應經(jīng)過A點時的弧長也最短，此時的交點M為過A點的圓的圓心時，過A點時所經(jīng)過的弧長最短，即總路程也最短；同理，機器人所要經(jīng)過目標點同樣以上述方法對圓心進行尋找，計算最終所得最短路徑；5.圖中給出了兩條可能路徑的最短路徑（圖中的黑線所示），分別計算出兩條可能的最短路徑，

28、用從起點經(jīng)過若干個點再到達目標點的方法與步驟進行求解，取最小者就是O到目標點C的最優(yōu)路徑。點OABCO的最短路徑如下圖所示：圖4-11 OABCO的路徑根據(jù)求解從起點經(jīng)過若干個點再到達目標點的問題的步驟進行計算，求解的結(jié)果最短路徑為：表4-7點OABCO的路徑OABCO的路徑ab最短路徑（單位）2797.82733.4由表中信息可知原點OABCO的最短路徑為b路徑，為2733.4。 路徑OABCO圓弧的起點與終點與上述路徑的求法相同，由于點數(shù)較多未列出，最短路徑b的其余具體情況如下表所示：表4-8最短路徑b的具體情況路徑圓心坐標總距離（單位）總時間（s）OABCO（80,210）（290.20

29、,297.97）（220.530）（150,600）（270,680）（370,680）（530,680）（540,600）（670,600）（99.41,690.01）（707.71,646.36）2733.4570.974.3模型三的建立與求解 針對問題三的分析，根據(jù)模型一中建立的最短時間路徑的通用數(shù)學模型，以下是的最短時間路徑的求解過程：如果一個圓環(huán)可以繞著環(huán)上一個定點轉(zhuǎn)動，那么過圓環(huán)外兩定點連接一根繩子，并以該圓環(huán)為支撐拉緊繩子，達到平衡狀態(tài)時，圓心與該頂點以及兩條切線的延長線的交點共線。 圖4-12三點共線圖證明猜想：圖形如上圖所示，E點就是圓環(huán)上的一個頂點，AB就是拉緊的繩子，O就

30、是切線AC和BD的延長線的交點，證明O、E、三點共線。我們可以用力學的知識進行證明，因為是拉緊的繩子，所以兩邊的繩子拉力相等，設為，它們的合力設為，定點對圓環(huán)的作用力設為。那么由幾何學的知識我們可以知道一定與共線，而又由力的平衡條件可知：=-即與共線。綜上所述O、E和三點一定共線。1.確定圓心的范圍 以不在對角線上的一點為圓心、點到點（70,220）的距離R為半徑畫圓B，分別過原點O和終點A作圓B的切線，切點為別為C、E，再連接BC、BE、OB、OA，即得出如下圖： 圖4-13圓心確定圖 根據(jù)已知條件可求的半徑R=76.1557 已知起點、轉(zhuǎn)彎圓心和終點坐標可用MATLAB編程（見附錄C）求解

31、出其所用時間為：96.829秒以在對角線上的一點I為圓心、半徑為76.1577畫出一個經(jīng)過點G的圓I，由此可得圓心坐標為（123.8516,166.1484），分別過原點O和終點A做圓I的切線，切點分別為F、H，連接IF、IH、OI、IA，即得出如下圖：圖4-14圓心確定圖 已知起點、轉(zhuǎn)彎圓心和終點坐標可用編程（見附錄C）求解出其所用時間為：95.44秒。由以上數(shù)據(jù)可以說明圓心應選在對角線上。2.確定半徑的取值范圍 因為圓心的取值在正方形的對角線上，即對角線上的任意一點到Y(jié)軸和外三角形底邊的距離都相等。而要使機器人能安全通過障礙物，則轉(zhuǎn)彎時的半徑最小要為10。當以正方形的右下角的點為圓心畫圓時

32、，得到最大的半徑為230，所以滿足條件圓的半徑取值范圍為。3.確定最短時間路徑并算出切點坐標 由轉(zhuǎn)彎半徑和轉(zhuǎn)彎速度的關系可知，對于轉(zhuǎn)彎速度，當半徑達到15后，我們可以默認其轉(zhuǎn)彎速度為5。每個圓心都能畫出要求的最大圓和最小圓，取對角線的兩端點和中點，利用編程(程序見附錄C)可以分別比較最大圓和最小圓所用時間：最大圓路徑的時間比較：表4-9 最大圓的時間圓心點半徑弧距直線段長度總時間（80,210）80122.0593433.8303111.1779（155,135）155274.4839290.6438113.0255（230,60）230808.5683157.9796193.3096各種情況

33、的最小圓時間路徑比較：表4-10 最小圓的時間圓心點半徑弧距直線段長度總時間（80,210）109.0510461.986396.0176（155,135）107.0047127.2958367.332598.9257（230,60）1011.1391487.2868101.913 由以上數(shù)據(jù)可知，在半徑相同的前提下，最小圓所用時間比最大圓所用時間少，所用在圓心確定的情況下選用最小圓原則求時間。由表4-10可知，最短時間路徑應在點(80,210)和點(155,135)之間，再依次遞推最后可得：表4-11 時間路徑的具體情況圓心點半徑弧距直線段長度總時間（81,209）15.556314.659

34、4460.2594.9819（82,208）16.970616.0150458.943494.9917（83,207）18.384817.3745457.633295.0015（84,206）19.799018.7379456.319195.0114由表4-11可知當圓心點為(81,209)、半徑為15.5563是最小時間為94.9819，此時起點、切點和終點的坐標分別如下表所示： 表4-12最小時間半徑的具體情況點的名稱起點第一個切點第二個切點終點點的坐標(0,0)(72.3255,196.0868)(87.8987,195.057)(300,300)5模型評價與推廣5.1模型的評價優(yōu)點：

35、（1）運用多個方案對路徑進行優(yōu)化，在相對優(yōu)化之中取得最優(yōu)解。 例如模型一中考慮機器人在行走過程中會不會遇到障礙物分為兩種情況；在轉(zhuǎn)彎處，轉(zhuǎn)彎半徑的大小可分為多種方案；再如從一出發(fā)點到一目標點又可有幾種路徑，根據(jù)已知信息與一些運算工具求出各路徑的總路程與總時間；對各種路徑計算出來的結(jié)果進行比較，得出最優(yōu)解； （2）模型優(yōu)化后用解析幾何與計算機數(shù)學軟件進行求解，精確度較高。 根據(jù)機器人可能行走的路徑，用幾何作圖將原點到目標點的各條路徑形象的表現(xiàn)出來，是行走的路線更加清晰明了，為以后的計算做了充分的準備； （3）模型簡單易懂，便于實際檢驗及應用。 （4）建立的模型與實際緊密聯(lián)系，充分考慮現(xiàn)實情況的多

36、樣性，從而使模型更貼近實際，通用性、推廣性較強。缺點： （1）此模型適于全局規(guī)劃，需要考慮的因素較多，機器人從一點到達另一點的路徑較多，且求解過程由于轉(zhuǎn)彎多，以及轉(zhuǎn)彎半徑的確定，直接關系到轉(zhuǎn)彎速度的求解從而影響到總路程與總時間，獲得精確解失去就增加了難度。 （2）本模型中機器人在行走過程中障礙物較多，且形狀不規(guī)則時，模型需要進一 步改進。5.2模型的推廣 在本題中有12個障礙物，按照線圓結(jié)構(gòu)畫出從起點到達目標點的路徑是有限的，我們完全可以采用窮舉法把這些路徑列出來，然后比較大小取最小者即可，但是我們可以設想如果這個區(qū)域內(nèi)有n個障礙物，那么按照線圓結(jié)構(gòu)從起點到達目標點的可能路徑就有無數(shù)多條，這時

37、我們?nèi)绻诓捎酶F舉法是不現(xiàn)實的。所以我們必須尋求新的算法來解決這個問題。由上述分析對模型進行進一步的修改先求出所有的切線，包括出發(fā)點和目標點到所有圓弧的切線以及所有圓弧與圓弧之間的切線，然后給這些定點賦一個等于切線長度的權(quán)值，如果某兩條切線有一個公切圓弧，則代表這兩條曲線的頂點是一條直線的兩個端點，邊上的權(quán)值等于這兩條切線之間的劣弧長度。然后在這張圖中加一個源點和終點，那么在所有代表出發(fā)點與其它圓弧之間切線的頂點與源點連成一條邊，權(quán)值均為0，同理在所有代表目標點到其它圓弧切線的頂點與終點連成一條邊，權(quán)值均為0，這樣題目就轉(zhuǎn)化成了求源點到達終點之間的最短路徑問題了，這里最短路徑就是指經(jīng)過所有頂點

38、與邊的權(quán)值之和最小。從而借助數(shù)學工具進行求解。本模型不僅適用于機器人的避障問題，還廣泛運用于先進的高科技領域中，例如在船舶在大海航行的過程，往往會遇到一些人為難以預測的麻煩，海底會不會有暗礁，水的深度能不能承載自身的重力等，這些問題若處理不當將會有意想不到的后果出現(xiàn)；還有航空航天領域方面；都需要對信息進行精確的處理，使其有更好的安全保障；如雷達探測儀、光敏探測儀等設備都能對障礙物進行探測，當探測到障礙物時，會接收到信號，對數(shù)據(jù)進行處理后，快速傳給各種設備，使其及時有效的實施避障，從而保證各種設備與人員的安全。6.模型的改進根據(jù)對問題的進行更深層次的分析，在機器人行走過程中有若干個障礙物的區(qū)域中

39、，我們把按照線圓結(jié)構(gòu)畫出從出發(fā)點到目標點的路徑圖依據(jù)轉(zhuǎn)換成了下面這張圖，圖中的A和D點就是添加的源點和終點，其它節(jié)點均是出發(fā)點和目標點到圓弧的切線和圓弧與圓弧之間的切線轉(zhuǎn)化而成。圖6-1添加的源點和終點后的改進圖 對于最短路徑的求解，有以下步驟： 我們畫出出發(fā)點和目標點和各個圓弧的切線，以及圓弧與圓弧之間的切線，但是切線有可能經(jīng)過障礙物的內(nèi)部或危險區(qū)域，也可能出現(xiàn)切線重復的狀況，既有很多不合法的切線。于是我們對模型做了以下修正： 第一種情況：檢驗切線兩個端點是否在障礙物內(nèi)部。 第二種情況：檢驗切線是否障礙物的對角線相交。第三種情況：檢驗圓弧所對應的圓心，即障礙物的頂點到切線的距離是否小于1。 如果以上三種情況滿足其一，我們規(guī)定對應這段切線的頂點為M（M為無窮大）。7參考文獻 1 姜啟源 謝金星 葉俊主編數(shù)學模型（第三版）高等教育出版社 2003.2 2 孫祥 徐流美 吳清編著MATLAB7.0基礎教程清華大學出版社 2005.5 3 吳建國主編數(shù)學建模案例精編中國水利水電出版社 2005.5 4 錢小軍主編 數(shù)量方法 高等教育出版社 1999.8 5 吳振奎 王全文 主編運籌學 中國人民大學出版社 2006.28附錄附錄A一個800×800的平面場景如下圖所示：圖1 800×800平面