論文 機(jī)器人避障問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

54、t;<p>　　令，由于B點(diǎn)和C點(diǎn)為切點(diǎn)，所以</p><p>　　圖14 最短時(shí)間示意圖</p><p>　　由兩點(diǎn)之間的距離公式得出：</p><p>　　因?yàn)锽點(diǎn)和C點(diǎn)是切點(diǎn)，所以：</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ù)機(jī)器人行走的直線距離和速度以及弧線長(zhǎng)度和對(duì)應(yīng)的弧線速度建立最短時(shí)間的目標(biāo)：</p><p><

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

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

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

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

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

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

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

63、b>　　參考文獻(xiàn)</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)過(guò)多目標(biāo)點(diǎn)最短路徑途中具體情況</p><p><b>　　附圖</b></p><p>　　附圖1 800×800平面場(chǎng)景圖</p><p>　　程序一：基本線圓組合計(jì)算程序（僅以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點(diǎn)所在的圓心坐標(biāo)（以A為例）；</p><p>　　%%%求經(jīng)過(guò)（A）點(diǎn)弧的圓心坐標(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); %直線與弧長(zhǎng)的路程</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>　　程序三：求Ｃ點(diǎn)所在圓的圓心坐標(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>　　程序四：?jiǎn)栴}二求最短時(shí)間路徑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