論文 機器人避障問題

1、<p><b>　　機器人避障問題</b></p><p><b>　　【摘要】</b></p><p>　　本文主要是對機器人在一個平面區(qū)域內(nèi)的通過不同障礙物到指定目標(biāo)點進行研究，首先通過機器人與障礙物的最小安全距離對不同障礙物的禁區(qū)進行了劃分見圖1，把障礙物劃分為有頂點和無頂點兩大類。然后證明了機器人在障礙物頂點處轉(zhuǎn)彎路徑最優(yōu)，轉(zhuǎn)彎

2、半徑最小路徑最優(yōu)，轉(zhuǎn)彎圓心在障礙物頂點處（圓行障礙物在圓心）路徑最優(yōu)。</p><p>　　問題一對于起點和目標(biāo)點的的路線先用拉繩子的方法確定了可能的最短路線，然后用窮舉法確定最佳路徑。機器人的行進又分單目標(biāo)點和多目標(biāo)點兩種情況。</p><p>　　針對單目標(biāo)點問題，先對只進行一次轉(zhuǎn)彎的過程建立了基本線圓組合結(jié)構(gòu)的解法即模型一。然后對多次轉(zhuǎn)彎問題中的直線路徑與圓弧路徑的不同的位置關(guān)系推導(dǎo)

3、出了計算模型即模型二。對O-A是基本的線圓組合，直接用模型一求解得到0-A的最短路徑長為471.0372個單位，所用時間為96.0178秒具體情況見文中表1。對O-B和O-C都是先用模型二對路線進行基本分割，然后用模型一進行求解得到O-B最短路徑長為853.7127個單位，所用總時間為179.0851秒，具體見表2。得到O-C最短路徑長為1087.6個單位，所用時間為221.9秒，具體見表3。</p><p>　

4、　針對多目標(biāo)點問題，由于機器人不能直線轉(zhuǎn)向，所以在經(jīng)過目標(biāo)點時，應(yīng)該提前轉(zhuǎn)向，且中間目標(biāo)點應(yīng)該在轉(zhuǎn)彎弧上。因此先建立優(yōu)化模型（模型三）對進行中間目標(biāo)點處轉(zhuǎn)彎圓弧圓心搜索求解。求出中間目標(biāo)點轉(zhuǎn)彎圓心后，用把中間目標(biāo)點的圓心看做“障礙物”的辦法把問題轉(zhuǎn)化為單目標(biāo)點問題。然后利用模型二和模型一進行求解，解得O-A-B-C-O的最短路徑長為2812.52個單位，所用時間為585.6712秒，具體見附表1。</p><p>

5、;　　對于問題二，在問題一求出的最短路的基礎(chǔ)上，根據(jù)轉(zhuǎn)彎半徑和速度的關(guān)系，在問題一求出的最短路徑的模型的基礎(chǔ)上，進行路線優(yōu)化，建立以最短時間為目標(biāo)的非線性規(guī)劃模型，求解得最短時間為94.22825秒，轉(zhuǎn)彎半徑為12.9886個單位，轉(zhuǎn)彎圓心坐標(biāo)為（82.1414，207.1387），具體結(jié)果見表5。</p><p>　　關(guān)鍵詞：基本線圓組合 拉繩子法 窮舉法 非線性規(guī)劃 中間目標(biāo)點轉(zhuǎn)彎圓心</p>

6、<p><b>　　1問題重述</b></p><p>　　附圖1是一個800×800的平面場景圖，在原點O(0, 0)點處有一個機器人，它只能在該平面場景范圍內(nèi)活動。圖中有12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：</p><p>　　在圖1的平面場景中，障礙物外指定一點為機器人要到達的目標(biāo)點（要求目標(biāo)點與

7、障礙物的距離至少超過10個單位）。規(guī)定機器人的行走路徑由直線段和圓弧組成，其中圓弧是機器人轉(zhuǎn)彎路徑。機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無法完成行走。</p><p>　　機器人直線行走的最大速度為個單位

8、/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如果超過該速度，機器人將發(fā)生側(cè)</p><p><b>　　翻，無法完成行走。</b></p><p>　　請建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的數(shù)學(xué)模型。對場景圖中4個點O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計算：</p>

9、<p>　　(1) 機器人從O(0, 0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑。</p><p>　　(2) 機器人從O (0, 0)出發(fā)，到達A的最短時間路徑。</p><p>　　注：要給出路徑中每段直線段或圓弧的起點和終點坐標(biāo)、圓弧的圓心坐標(biāo)以及機器人行走的總距離和總時間。</p><p><b>　　2問題分析&l

10、t;/b></p><p>　　本問題主要是對機器人在一個平面區(qū)域內(nèi)的通過不同障礙物到指定目標(biāo)點進行研究，首先通過觀察發(fā)現(xiàn)障礙物不同，因此我們先要對機器人通過不同的障礙物的情況進行討論。在行進過程中轉(zhuǎn)彎位置，轉(zhuǎn)彎的半徑，轉(zhuǎn)彎圓心的不同都會影響路徑的優(yōu)劣。因此我們要先確定最佳轉(zhuǎn)彎位置、半徑和轉(zhuǎn)彎圓心。</p><p>　　對于問題一，分單目標(biāo)點和多目標(biāo)點兩種情況。針對單目標(biāo)點問題，從已

11、知點到指定點有多條路徑可以選擇，可以先用拉繩子的辦法確定可能的最短路線，然后用窮舉法確定最短路徑。由于機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的圓弧組成，因此可以把路徑看成由多個基本線圓組合而成，然后在對基本線圓結(jié)構(gòu)建立求解模型。針對多目標(biāo)點問題，不能簡單的處理為求解每個兩點之間的最短路徑之和，因為機器人不能直線轉(zhuǎn)向，所以在經(jīng)過目標(biāo)點時，應(yīng)該考慮提前轉(zhuǎn)向，且中間目標(biāo)點應(yīng)該在轉(zhuǎn)彎弧上。因此對于中間目標(biāo)點處轉(zhuǎn)彎圓弧圓心的確定可以建立優(yōu)化

12、模型進行搜索求解。求出中間目標(biāo)點轉(zhuǎn)彎圓心后可以把中間目標(biāo)點的圓心看做“障礙物”進行研究，這樣問題就轉(zhuǎn)化為了單目標(biāo)點問題。</p><p>　　對于問題二，可以根據(jù)轉(zhuǎn)彎半徑和速度的關(guān)系，在問題一求出的最短路徑的模型的基礎(chǔ)上，進行路線優(yōu)化，即建立以最短時間為目標(biāo)的非線性規(guī)劃模型，進行求解最短時間。</p><p><b>　　3模型假設(shè)</b></p>&l

13、t;p>　　為了簡化計算，給出如下模型合理性的假設(shè)：</p><p>　　【1】假設(shè)所有障礙物是固定不動的；</p><p>　　【2】機器人性能足夠好，能準(zhǔn)確地沿圓弧轉(zhuǎn)彎；</p><p>　　【3】假設(shè)機器人在初始時的速度為5個單位每秒；</p><p>　　【4】假設(shè)機器人在直線切入弧線時的速度是瞬間變化完成的；</p>

14、;<p>　　【5】機器人行走過程中不會意外停止；</p><p>　　【6】忽略影響機器人行走非最小轉(zhuǎn)彎半徑以及最小安全距離因素。 </p><p><b>　　4符號說明</b></p><p>　　為了簡化對問題的分析和對數(shù)字的處理，做出如下符號規(guī)定：</p><p><b>　　5模型的建

15、立與求解</b></p><p>　　5.1最短路徑模型（問題一）</p><p>　　從已知點到指定點有多條路徑可以選擇，可以先用拉繩子的辦法確定可能的最短路線，然后用窮舉法確定最短路徑。在行進過程中轉(zhuǎn)彎位置，轉(zhuǎn)彎的半徑，轉(zhuǎn)彎圓心的不同都會影響路徑的優(yōu)劣。因此我們要先確定最佳轉(zhuǎn)彎位置、半徑和轉(zhuǎn)彎圓心。本問題中對于路徑的求解分為單目標(biāo)路徑和多目標(biāo)路徑兩種，因此在本問題中我們分開

16、討論。</p><p>　　5.1.1單目標(biāo)點模型（只有起點和終點）</p><p>　　由于機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的圓弧組成，因此對于本問題可以把路徑看成由多個基本線圓組合而成。</p><p>　　5.1.1.1相關(guān)推論及證明</p><p>　　把機器人的行進路線看成一根有彈性的繩子，根據(jù)實際情況我們推論：禁區(qū)頂點

17、處變向路徑最小，轉(zhuǎn)彎半徑最小路徑最短，轉(zhuǎn)彎弧圓心在頂點路徑最短。</p><p><b>　　【1】禁區(qū)劃分</b></p><p>　　由于機器人行進過程中與障礙物有最小距離的限制，因此我們先畫出包絡(luò)障礙物的禁區(qū)，對于有圓形障礙物來說，禁區(qū)還是一個圓，對于有頂點的障礙物來說禁區(qū)拐角處為一個圓弧，具體如圖1：</p><p><b>

18、　　圖1 禁區(qū)示意圖</b></p><p><b>　　【2】障礙物有頂點</b></p><p>　　（1）禁區(qū)頂點變向路徑最小</p><p>　　如下圖2所示，機器人從指定的A點到C點，需要進行變向，從圖形可以看出來，在禁區(qū)邊緣變向總路徑會最小，下面我們進行證明：</p><p>　　圖2 禁區(qū)頂點處

19、變向圖</p><p>　　假設(shè)D點為禁區(qū)頂點，先不考慮轉(zhuǎn)彎半徑等因素，其中B為禁區(qū)外任意一點，AD變延長線交BC于E點。由三角形的任意兩邊之和大于第三邊可以得到：</p><p><b>　　兩式相加得到：</b></p><p><b>　　化簡得到：</b></p><p>　　即，由A點到B

20、點，選擇在頂點D處轉(zhuǎn)向，總路徑最短。推論得證。</p><p>　?。?）轉(zhuǎn)彎半徑最小路徑最短</p><p>　　機器人從A點到B點需要繞過禁區(qū)，在禁區(qū)頂點附近（前面已證）轉(zhuǎn)彎。選擇的轉(zhuǎn)彎半徑越小，得到的路徑越短。下面從物理學(xué)的角度進行證明：</p><p>　　如下圖3所示，將A到B的路徑看做一條可伸縮的繩子。假設(shè)其兩點相連時，繩子自然伸長。如線段AB。由于機器

21、人要繞過禁區(qū)，因此拉長繩子繞過禁區(qū)，又因為機器人有最小轉(zhuǎn)彎半徑為10，禁區(qū)直徑也為10，因此可以把繩子直接繞過禁區(qū)邊緣。</p><p>　　由于繩子的彈性勢能與伸長量的關(guān)系為：</p><p>　　因此繩子伸長量最小時，路徑最短。</p><p>　　圖3 機器人過障礙轉(zhuǎn)彎半徑</p><p>　　根據(jù)最小勢能原可知，當(dāng)彈性體平衡時，系統(tǒng)勢

22、能最小。即彈性體在自由條件下，有由高勢能向低勢能轉(zhuǎn)化的趨勢?，F(xiàn)在將圓環(huán)看成也有彈性，在如圖所示的條件下為初始狀態(tài)。圓環(huán)受力如圖所示，此時圓環(huán)有縮小的趨勢，隨著圓環(huán)的縮小系統(tǒng)趨于平衡，彈性繩有最小勢能。由能量守恒也可以說明，繩子的彈性勢能轉(zhuǎn)化為彈性圓環(huán)的彈性勢能，于是彈性繩的彈性勢能減小。</p><p>　　因此，隨著圓環(huán)的半徑的減小，繩子的勢能減小，即最短路徑變短。所以最小轉(zhuǎn)彎半徑最小路徑最短得證。</p

23、><p>　?。?）轉(zhuǎn)彎弧圓心在頂點路徑最短</p><p>　　機器人在禁區(qū)頂點附近轉(zhuǎn)彎時，轉(zhuǎn)彎弧的圓心在頂點上，路徑最短。</p><p><b>　　下面進行證明：</b></p><p>　　如下圖4所示，圓O和圓O’均過最遠點D它們的半徑分別為R和R’。其中圓O的圓心在垂線上。分別為過A、B點向圓O和O’所引切線段

24、和所夾圓弧長度。則需證明：</p><p>　　因為兩圓圓心不同在過點 D 所引的垂線上，且兩圓交于點 D，因此它們只能有兩種關(guān)系——相交或相切。若兩圓相切，由幾何定理知切點、圓心 O、圓心 O’三點共線。因點 D 和圓心O均在過D所作直線AB的垂線上，圓心O’在垂線外，故兩圓不會相切，只能相交。要過點D則必有圓O’上點到直線AB的最大距離大于圓 O上點到直線AB的最大距離。運用上文已證得的結(jié)論可得到：</

25、p><p><b>　　因此推論得證。</b></p><p>　　圖4 機器人過障礙轉(zhuǎn)彎圓心位置</p><p><b>　?。?）結(jié)論分析</b></p><p>　　結(jié)合（1）（2）（3）證明得到結(jié)論：</p><p>　　機器人過有頂點的障礙物時，沿以頂點為圓心，最小轉(zhuǎn)彎

26、半徑為半徑的圓弧轉(zhuǎn)彎路徑最短，在本題中機器人的最小轉(zhuǎn)彎半徑和機器人與障礙物的最小安全距離相等。因此對于本題來說，機器人沿禁區(qū)邊緣轉(zhuǎn)彎路徑最短。</p><p>　　【3】障礙物為圓的情況</p><p>　　在前面我們已經(jīng)證明了障礙物有頂點的情況下，機器人過禁區(qū)時沿禁區(qū)邊緣圓弧轉(zhuǎn)彎路徑最小。下面就機器人通過圓形障礙物的情況是否符合以上結(jié)論進行討論。</p><p>

27、　　如圖5，分別是機器人通過圓形禁區(qū)的3種情況，其中a圖為機器人人沿禁區(qū)邊緣進行轉(zhuǎn)彎的。b圖為機器人沿以圓形障礙物邊上一點為圓形，最小轉(zhuǎn)彎半徑為轉(zhuǎn)彎半徑的弧轉(zhuǎn)彎圖，c圖為機器人沿一個剛好繞過禁區(qū)的圓弧轉(zhuǎn)彎的情況。</p><p>　　圖5 機器人通過圓形障礙物</p><p>　　由以上用彈性繩的方法進行證明發(fā)現(xiàn)，b圖轉(zhuǎn)彎路徑最小，但是經(jīng)過了禁區(qū)，因此不可行，另外兩種方案a圖路徑明顯要比c

28、圖小。因此機器人過禁區(qū)時沿禁區(qū)邊緣圓弧轉(zhuǎn)彎路徑最小得結(jié)論同樣適用于障礙物位圓的情況。轉(zhuǎn)彎半徑為：</p><p>　?。ㄆ渲袨檎系K物半徑，為機器人距離障礙物的最小安全距離）</p><p>　　5.1.1.2模型的建立</p><p>　　經(jīng)過以上證明得到，起點到目標(biāo)點中間不管有多少障礙物，最短路徑都是由若干個相切的直線和圓弧構(gòu)成的，前面已經(jīng)證明機器人經(jīng)過所有障礙物

29、時，禁區(qū)邊緣轉(zhuǎn)彎路徑最短，因此轉(zhuǎn)彎圓弧半徑為危險區(qū)域半徑。所以在下面模型中經(jīng)過障礙物轉(zhuǎn)彎時，都以障礙物頂點為轉(zhuǎn)彎弧圓心，最小轉(zhuǎn)彎半徑為轉(zhuǎn)彎半徑。</p><p>　　【1】途中轉(zhuǎn)彎一次的模型（模型一）</p><p>　　如圖6所示，已知機器人要從起點A（）點出發(fā)繞過障礙物到終點B。途中從以障礙物頂點D（）為圓心，為半徑的弧上轉(zhuǎn)彎，切點為C和E。需要求C點和E點坐標(biāo)，以及的長度。</

30、p><p>　　圖6 機器人過障礙物轉(zhuǎn)彎圖</p><p><b>　　根據(jù)兩點距離公式：</b></p><p>　　由于C點和E點是切點，所以</p><p><b>　　根據(jù)勾股定理：</b></p><p><b>　　◆切點坐標(biāo)的確定</b><

31、;/p><p>　　假設(shè)C點坐標(biāo)為（），E點坐標(biāo)為（）。那么根據(jù)兩點距離公式還有：</p><p>　　綜上所述，對于E點坐標(biāo)就有：</p><p><b>　　對于C點坐標(biāo)：</b></p><p>　　解以上方程組即可得到兩個切點C和E的坐標(biāo)。</p><p><b>　　◆轉(zhuǎn)彎弧長的確

32、定</b></p><p>　　在中，根據(jù)余弦定理：</p><p><b>　　在中：</b></p><p><b>　　在中：</b></p><p><b>　　對于就有：</b></p><p><b>　　因此弧的長度就

33、為：</b></p><p>　　◆總路徑和總時間的確定</p><p>　　機器人途中轉(zhuǎn)彎一次路徑長度就為</p><p><b>　　所用時間就為</b></p><p>　　【2】途中轉(zhuǎn)彎多次的模型（模型二）</p><p>　　機器人在從起點到終點的過程中，如果障礙物多的話，機

34、器人需要通過多次轉(zhuǎn)彎才能到達目標(biāo)點，多次轉(zhuǎn)彎可以分解成由多個兩次轉(zhuǎn)彎和一次轉(zhuǎn)彎組成，而在兩次轉(zhuǎn)彎的過程中，兩個轉(zhuǎn)彎弧度的公切線分為內(nèi)公切線和外公切線兩種。</p><p>　　◆沿內(nèi)公切線前進的情況</p><p>　　如圖7所示，機器人從起始點A到目標(biāo)點B要經(jīng)過兩個障礙物，途中從障礙物內(nèi)側(cè)轉(zhuǎn)兩次彎，已知兩個障礙物轉(zhuǎn)彎處的頂點為D，F(xiàn),圓D和圓F的半徑均為。</p><

35、p>　　圖7 內(nèi)公切線路徑圖</p><p>　　兩圓心連線與內(nèi)切線交點為O點。易證：</p><p>　　因此O點為線段DF的中點，根據(jù)中點坐標(biāo)公式：</p><p>　　確定O點坐標(biāo)后，用模型一就可以分別求出和的長度，以及確定C、E、M、N點坐標(biāo)。</p><p>　　◆沿外公切線前進的情況</p><p>

36、　　如圖8所示，機器人從起始點A到目標(biāo)點B要經(jīng)過兩個障礙物，途中從障礙物外側(cè)轉(zhuǎn)兩次彎，已知兩個障礙物轉(zhuǎn)彎處的頂點為M，N,圓M和圓N的半徑均為。</p><p><b>　　圖8 外公切線路徑</b></p><p>　　在兩圓心的的連線上找出中點O，過O點作DF垂線，交DF于H點。</p><p>　　根據(jù)中點坐標(biāo)公式可得O點坐標(biāo)：</

37、p><p>　　由于,所以四變形MNDF為矩形，因此H也為DF的中點,且</p><p><b>　　。</b></p><p><b>　　根據(jù)勾股定理：</b></p><p>　　因此對于H點坐標(biāo)就有：</p><p>　　解上面方程組可以求出H點坐標(biāo)，確定H點坐標(biāo)后，就可

38、以用模型一分別求出路徑和長度，以及切點C、D、E、F坐標(biāo)。以及所用時間。</p><p>　　5.1.1.3模型計算</p><p>　　假設(shè)機器人從起始點到目標(biāo)點經(jīng)過的路徑有條直線，長度分別為，有條弧線，長度分別為，則機器人到達目標(biāo)點的總路為</p><p><b>　　途中所用時間為：</b></p><p><

39、;b>　　其中，是轉(zhuǎn)彎半徑。</b></p><p>　　【1】O-A的最短路徑</p><p>　　如圖9所示，根據(jù)前文證明，O-A點可能的最短路線有兩條，從5號障礙物左上角處拐彎，或從5號障礙物右下角處拐彎。</p><p>　　圖9 O-A可能最佳路線</p><p>　　兩條路線都為基本的線圓組合，用模型一可直接求解

40、，用MATLAB程序解得，兩條路徑分別為，個單位，因此最佳總路程為從障礙物5左上經(jīng)過路線，總路程為個單位；總時間秒，經(jīng)過二條直線段和一以條以為圓心半徑的弧線段，途中具體情況如表1：</p><p>　　表1 O-A最短路徑途中情況</p><p>　　【2】O-B的最短路</p><p>　　如圖10所示，機器人從O到B點有三條可能最短路線，在路徑途中經(jīng)過多次轉(zhuǎn)彎到

41、達目標(biāo)點，因此先用模型二把路徑分為若干個基本線圓組合，然后用模型一對每個線圓組合求解，可得出答案。</p><p>　　圖10 O-B可能最佳路線</p><p>　　經(jīng)MATLAB計算可得到三條路線的路程分別為，,個單位；最佳總路程為路線一，總路程為個單位；總時間秒，經(jīng)過六條直線段和五條分別以，，，，為圓心半徑的弧線段，具體起始點如表2：</p><p>　　表2

42、 O-B 最短路徑途中情況</p><p>　　【2】O-C的最短路徑</p><p>　　如圖11所示，機器人從O到C點有三條可能最短路線，在路徑途中經(jīng)過多次轉(zhuǎn)彎到達目標(biāo)點，因此先用模型二把路徑分為若干個基本線圓組合，然后用模型一對每個線圓組合求解，可得出答案。</p><p>　　特別要說明的是在O-C的第二條路徑中，通過前文的證明，經(jīng)過圓形障礙物的轉(zhuǎn)彎半徑應(yīng)該

43、為。</p><p>　　圖11 O-C可能最佳路線</p><p>　　經(jīng)MATLAB計算得到距離分別為，個單位，最佳總路徑為路線一，總距離為個單位；總時間秒，經(jīng)過五條直線段和四條分別以，，，為圓心半徑的弧線段，途中具體情況如表3：</p><p>　　表3 O-C最短路徑途中情況</p><p>　　5.1.2經(jīng)過多個目標(biāo)點（O-A-B-

44、C-O）</p><p>　　本問題的特點是要經(jīng)過中間若干個目標(biāo)點后在回到起點，不能簡單的處理為求解每個兩點之間的最短路徑之和，因為機器人不能直線轉(zhuǎn)向，所以在經(jīng)過目標(biāo)點時，應(yīng)該考慮提前轉(zhuǎn)向，且中間目標(biāo)點應(yīng)該在轉(zhuǎn)彎弧上。因此對于中間目標(biāo)點處轉(zhuǎn)彎圓弧圓心的確定為本題的一個難點。</p><p>　　◆經(jīng)過中間目標(biāo)點的路徑（模型三）</p><p>　　如圖12所示已知點

45、，分別為兩個障礙物的頂點，且機器人要繞過B點障礙物經(jīng)過中間目標(biāo)點到另一個障礙物頂點轉(zhuǎn)彎。其中為在圓心為半徑為的圓上。由于點，分別引同側(cè)相切于圓心為的圓的切線，因此我們需要用點和點來確定圓心的位置。</p><p>　　圖12 機器人經(jīng)過中途目標(biāo)點圖</p><p>　　由于需要確定的圓心是以為半徑點為圓上一點，所以需要進行搜索求解求出要確定的圓心。這樣就將目標(biāo)轉(zhuǎn)化為距離和弧長最短的目標(biāo)模型

46、。</p><p>　　根據(jù)點是圓上一點的關(guān)系就可以點為圓心為半徑搜索得出圓心，那么得出關(guān)系為：</p><p>　　將上述關(guān)系轉(zhuǎn)化為圓的標(biāo)準(zhǔn)方程可以得到：</p><p>　　根據(jù)兩點直接的距離公式可以得出以下條件：</p><p>　　由于與是兩個圓的同側(cè)公切線，兩圓的半徑相等而與和與是矩形的對邊，所以，。</p><

47、p>　　在中由余弦定理可以得出：</p><p>　　最后我們建立的模型為：</p><p>　　根據(jù)上面模型我們可以求解出和圓心坐標(biāo)，由于點的圓心與其他附近的圓是交錯相切，根據(jù)交錯相切時切線與圓心的連線的交點是兩圓心的的中間點（前文已經(jīng)證明）可以得出與同側(cè)相切時對應(yīng)的點和的坐標(biāo)，所以我們只需套用上面同側(cè)相切的模型求解點的圓心坐標(biāo)。點的圓心與的連線剛好與到圓的切線垂直，即點是與圓相交

48、的切點。</p><p>　　通過本模型可以求出兩個障礙物中間為中途目標(biāo)點的線圓組合，其他情況的線圓組合可用模型一和模型二進行求解。</p><p><b>　　◆模型計算</b></p><p>　　如圖13所示，通過前文證明以及單目標(biāo)點的計算模型，可以得到從O點出發(fā)，經(jīng)過A、B、C三點在回到O點的最短路線只有一條。首先利用模型三算出A、B、

49、C三點處轉(zhuǎn)彎弧度的圓心坐標(biāo)，然后用模型二把路徑轉(zhuǎn)化為若干個基本線圓組合。利用模型一計算。</p><p>　　圖13 O-A-B-C-O最短路徑</p><p>　　利用MATLAB編程計算得到，機器人從最佳總路程為個單位；總時間秒，一共經(jīng)過十六條直線段和十五條分別以,,,,, ,,,,,,,為圓心半徑的弧線段，具體起始點如附表1：</p><p>　　表4 經(jīng)過多

50、目標(biāo)點最短路徑途中部分情況</p><p>　　5.2最短時間路徑模型（問題二）</p><p><b>　　◆模型分析</b></p><p>　　本問題是研究機器人從O點出發(fā)繞過障礙物5到達A的最短時間，根據(jù)問題一所求最短路，可以知道最短時間路線也是從障礙物5的左上通過，機器人所有的時間由直線段和弧線段兩部分時間組成。由于最短時間和最短距離

51、不是同一條路線，因此在求最短時間時先要確定最短時間的路徑。機器人靠近障礙物時距離障礙物的最近距離不能少于10個單位。所以根據(jù)機器人在行走路線中要避免遇到的障礙物和影響其行動的范圍來確定機器人行走的范圍。</p><p>　　機器人轉(zhuǎn)彎時最大轉(zhuǎn)彎速度為:</p><p>　　機器人經(jīng)過圓弧時間為：</p><p>　　由上式可以看出當(dāng)轉(zhuǎn)彎半徑變小時，機器人速度也變小，

52、而機器人通過的圓弧長度也變小。的變化不好確定。</p><p>　　當(dāng)機器人轉(zhuǎn)彎半徑增大時，轉(zhuǎn)彎速度也增大，而機器人通過的圓弧長度也隨著增大。的變化不好確定。</p><p>　　因此對于轉(zhuǎn)彎時間隨轉(zhuǎn)彎半徑的變化關(guān)系，沒有直接的線性關(guān)系。而對于轉(zhuǎn)彎半徑的變化在題目中是有限制的，過大會發(fā)生碰撞。過?。ㄐ∮?0）會發(fā)生側(cè)翻。</p><p>　　所以我們可以根據(jù)的變化范

53、圍，建立最小時間的非線性規(guī)劃模型，對最小時的進行搜索求解。</p><p><b>　　◆模型準(zhǔn)備：</b></p><p>　　如圖14所示，已知是起始點，是終點，是障礙物5的左上頂點。假設(shè)機器人在C處以N為圓心，為半徑轉(zhuǎn)彎，經(jīng)弧,在B點轉(zhuǎn)彎，可以得到最短時間路徑。連結(jié)BC，做ND⊥于BC。ON長度為，AN長度為，切線OC的長度為，切線AB的長度為。</p&g

54、t;<p>　　令，由于B點和C點為切點，所以</p><p>　　圖14 最短時間示意圖</p><p>　　由兩點之間的距離公式得出：</p><p>　　因為B點和C點是切點，所以：</p><p>　　根據(jù)勾股定理可以得到：</p><p><b>　　根據(jù)距離公式：</b>

55、</p><p><b>　　在</b></p><p><b>　　所以</b></p><p><b>　　◆目標(biāo)分析</b></p><p>　　根據(jù)機器人行走的直線距離和速度以及弧線長度和對應(yīng)的弧線速度建立最短時間的目標(biāo)：</p><p><

56、;b>　　◆約束分析</b></p><p>　　根據(jù)機器人與障礙物的距離至少要超過10個單位可以得到半徑的約束條件，即必須使圓弧離障礙物10個以上的單位：</p><p>　　對于兩個切點的范圍：</p><p>　　根據(jù)問題一證明的結(jié)論圓心在障礙物以內(nèi)的距離最短可以得出約束條件為：</p><p>　　因為機器人不能直線

57、轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，因此對于C、B兩點來說，必須保證是切點：</p><p>　　C、B兩點在圓上，與圓心的距離為半徑：</p><p>　　△NOC和△ABN必須是直角三角形，B點和C點為兩直角邊交點。</p><p><b>　　◆模型的建立與求解</b></p><p>　　綜合以上條件，

58、建立時間最短的優(yōu)化模型：</p><p>　　用Lingor軟件編程求得最短時間為94.22825秒，轉(zhuǎn)彎半徑為，具體結(jié)果見表5：</p><p>　　表5 O-A最短時間路徑途中情況</p><p><b>　　◆結(jié)果分析</b></p><p>　　把結(jié)果同問題一比較發(fā)現(xiàn)最短路徑未必所用時間最少，關(guān)鍵在于轉(zhuǎn)彎半徑和轉(zhuǎn)

59、彎圓心的選擇。因此機器人在轉(zhuǎn)彎過程中的轉(zhuǎn)彎半徑和轉(zhuǎn)彎圓心的確定，對路線的優(yōu)劣有著不可避免的影響。</p><p><b>　　6模型推廣與評價</b></p><p><b>　　◆模型改進</b></p><p>　　本題障礙物并不是太多，當(dāng)障礙物多的時候利用本題目所用的窮舉法是不現(xiàn)實的。</p><

60、p>　　我們在做題目的時候有如下一些想法，先劃去障礙物的危險區(qū)，再求出所有的切線，包括出發(fā)點和目標(biāo)點到所有圓弧的切線以及所有圓弧與圓弧之間的切線，然后把這些相交聯(lián)的線看成是最小生成樹，和最短路。</p><p>　　假設(shè)機器人從起點R到到目標(biāo)點，路徑一定是由圓弧和線段組成，設(shè)有m條線段，n條圓弧。那么目標(biāo)函數(shù)可以表示為：</p><p>　　利用matlab或者lingo等計算機軟件

61、，用最編程求最優(yōu)解。此程序可以起到起點到目標(biāo)點之間的路徑進行優(yōu)化求解</p><p><b>　　◆模型評價</b></p><p><b>　　優(yōu)點：</b></p><p>　　本模型簡單易懂，便于實際檢驗及應(yīng)用，可以應(yīng)用到機動車駕駛證考試、城市汽車運輸?shù)纫幌盗袑嶋H生活問題，主要優(yōu)點；</p><p

62、>　　1、運用多個方案對路徑進行優(yōu)化，在相對優(yōu)化之中取得最優(yōu)解。</p><p>　　2、模型優(yōu)化后用解析幾何進行求解，精確度較高。缺點：</p><p>　　1、利用解析幾何進行求解，精確度較高的前提計算時間比較慢，所以此模型利用起來效率比較低。</p><p>　　2、當(dāng)障礙物足夠多的時候本模型并不適合。</p><p><

63、b>　　參考文獻</b></p><p>　　[1]吳家龍《彈性力學(xué)》北京：高等教育出版社，2001</p><p>　　[2] 姜啟源 謝金星，數(shù)學(xué)建模，北京：高等教育出版社，2003年；</p><p>　　[3] 李 濤 賀勇軍，應(yīng)用數(shù)學(xué)篇，北京：電子工業(yè)出版社，2000年。</p><p><b>

64、　　7附錄</b></p><p>　　附表1：經(jīng)過多目標(biāo)點最短路徑途中具體情況</p><p><b>　　附圖</b></p><p>　　附圖1 800×800平面場景圖</p><p>　　程序一：基本線圓組合計算程序（僅以0-A為例，其它類似）</p><p>&

65、lt;b>　　clc</b></p><p><b>　　o=[0,0];</b></p><p>　　c=[80,210];</p><p>　　m=[300,300];</p><p><b>　　r=10;</b></p><p>　　oc=sqrt(

66、(o(1)-c(1))^2+(o(2)-c(2))^2);</p><p>　　om=sqrt((o(1)-m(1))^2+(o(2)-m(2))^2);</p><p>　　cm=sqrt((c(1)-m(1))^2+(c(2)-m(2))^2);</p><p>　　a1=acos((oc^2+cm^2-om^2)/(2*oc*cm));</p>

67、<p>　　a2=acos(r/oc);</p><p>　　a3=acos(r/cm);</p><p>　　a4=2*pi-a1-a2-a3;</p><p>　　d1=sqrt(oc^2-r^2);</p><p>　　d2=sqrt(cm^2-r^2);</p><p><b>　　d3=r

68、*a4;</b></p><p>　　dd=d1+d2+d3</p><p>　　程序二：求A，B點所在的圓心坐標(biāo)（以A為例）；</p><p>　　%%%求經(jīng)過（A）點弧的圓心坐標(biāo)</p><p><b>　　clc</b></p><p><b>　　clear</

69、b></p><p><b>　　%%%坐標(biāo)</b></p><p>　　A=[300,300]; %所求圓弧上的坐標(biāo)</p><p>　　B=[80,210]; %一邊圓心的坐標(biāo)</p><p>　　C=[220,530]; %另一邊圓心的坐標(biāo)</p

70、><p>　　R=10; %圓的半徑</p><p>　　sita=[-pi:0.0001:pi]; %搜索圓心坐標(biāo)的范圍</p><p>　　for i=1:length(sita) </p><p>　　O=[A(1)+R*sin(sita(i)),A(2)-R*cos

71、(sita(i))];</p><p>　　l1=sqrt((O(1)-B(1))^2+(O(2)-B(2))^2);</p><p>　　l2=sqrt((O(1)-C(1))^2+(O(2)-C(2))^2);</p><p>　　l3=sqrt((B(1)-C(1))^2+(B(2)-C(2))^2);</p><p>　　afa=ac

72、os((l1^2+l2^2-l3^2)/(2*l1*l2));</p><p>　　L(i)=l1+l2+R*(pi-afa); %直線與弧長的路程</p><p><b>　　end</b></p><p>　　sita(find(L==min(L))) %最短路程</p><p&g

73、t;　　min(L) </p><p>　　[A(1)+R*sin(sita(find(L==min(L)))),A(2)-R*cos(sita(find(L==min(L))))] %圓心坐標(biāo)</p><p>　　程序三：求Ｃ點所在圓的圓心坐標(biāo)；</p><p><b>　　clc</b></p

74、><p><b>　　clear</b></p><p><b>　　%%%坐標(biāo)</b></p><p>　　A=[700,640];</p><p>　　C=[720,600];</p><p>　　B=[670,730];</p><p><b&

75、gt;　　R=10;</b></p><p>　　sita=[(51/90)*pi/2:0.001:(80/90)*pi/2];</p><p>　　for i=1:length(sita)</p><p>　　O=[A(1)+R*sin(sita(i)),A(2)+R*cos(sita(i))];</p><p>　　l1=sq

76、rt((O(1)-B(1))^2+(O(2)-B(2))^2);</p><p>　　l2=sqrt((O(1)-C(1))^2+(O(2)-C(2))^2);</p><p>　　l3=sqrt((B(1)-C(1))^2+(B(2)-C(2))^2);</p><p>　　afa=acos((l1^2+l2^2-l3^2)/(2*l1*l2))</p>

77、;<p>　　afa1=acos(20/l1)</p><p>　　afa2=acos(20/l2)</p><p>　　L(i)=sqrt(l1^2-400)+sqrt(l2^2-400)+R*(afa-afa1-afa2);</p><p><b>　　end</b></p><p>　　sita(fi

78、nd(L==min(L)))</p><p><b>　　min(L)</b></p><p>　　[A(1)+R*sin(sita(find(L==min(L)))),A(2)+R*cos(sita(find(L==min(L))))]</p><p>　　程序四：問題二求最短時間路徑lingo程序</p><p>　

79、　min=@sqrt((x-300)^2+(y-300)^2-r^2)/5+@sqrt(x^2+y^2-r^2)/5+2*r*@asin(d/(2*r))/5*(1+@exp(10-0.1*r^2));</p><p>　　d=@sqrt((xc-xb)^2+(yc-yb)^2);</p><p>　　@sqrt((xb)^2+(yb)^2+r^2)=@sqrt(x^2+y^2);<

80、/p><p>　　@sqrt((xc-300)^2+(yc-300)^2+r^2)=@sqrt((x-300)^2+(y-300)^2);</p><p><b>　　init:</b></p><p><b>　　x=80;</b></p><p><b>　　y=210;</b>

81、;</p><p><b>　　endinit</b></p><p><b>　　xb<=80;</b></p><p><b>　　yc>210;</b></p><p>　　r=@sqrt((xb-x)^2+(yb-y)^2);</p><

82、p>　　r=@sqrt((xc-x)^2+(yc-y)^2);</p><p>　　r>@sqrt((80-x)^2+(210-y)^2)+10;</p><p><b>　　x>80;</b></p><p><b>　　x<200;</b></p><p><b&g