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

1、機(jī)器人避障問(wèn)題摘 要本文討論的是機(jī)器人避障問(wèn)題，運(yùn)用改良的橡皮筋算法思想，對(duì)最優(yōu)路徑逐步探索，并進(jìn)行了大膽猜想通過(guò)分析，利用幾何關(guān)系證明了猜想的正確性，以此得到判斷最短路徑的三個(gè)原則：一、所走路線應(yīng)盡可能接近兩目標(biāo)點(diǎn)與目的地連線；二、目標(biāo)點(diǎn)轉(zhuǎn)彎半徑越小越好；三、找不到兩圓間的公切線時(shí)，機(jī)器人應(yīng)盡可能沿障礙物邊界運(yùn)動(dòng)對(duì)于問(wèn)題一，依據(jù)路徑最優(yōu)原則，確定轉(zhuǎn)彎半徑為10個(gè)單位，建立了機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑的優(yōu)化模型利用MATLAB求解得到結(jié)果如下：:總時(shí)間為：96.00826秒，總路程為471.0372個(gè)單位；:總時(shí)間為179.09982秒，總長(zhǎng)度為853.7113單位；:總時(shí)間為

2、239.72602秒，總路程為1100.19單位；：總路程：2794.512單位 ，最終總時(shí)間為598.5477秒對(duì)于問(wèn)題二，要使機(jī)器人行走時(shí)間最短，需在盡可能保證最短路徑的基礎(chǔ)上適當(dāng)增加轉(zhuǎn)彎半徑利用幾何知識(shí)推導(dǎo)出機(jī)器人行走時(shí)間與轉(zhuǎn)彎半徑的關(guān)系，時(shí)間對(duì)半徑求導(dǎo)，并令導(dǎo)數(shù)為零，得出最短時(shí)間所對(duì)應(yīng)的半徑，進(jìn)而建立最短時(shí)間路徑的優(yōu)化模型利用MATLAB軟件求解得，當(dāng)機(jī)器人從出發(fā)到達(dá)時(shí)，所用最短時(shí)間為秒，總距離為470.8301個(gè)單位關(guān)鍵詞：導(dǎo)數(shù)；橡皮筋算法；優(yōu)化模型一、問(wèn)題的重述圖1是一個(gè)800800的平面場(chǎng)景圖，在原點(diǎn)點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面場(chǎng)景范圍活動(dòng)圖中有12個(gè)不同形狀的區(qū)域是機(jī)器人不

3、能與之發(fā)生碰撞的障礙物，障礙物單位數(shù)學(xué)描述如下表：表112個(gè)不同形狀區(qū)域的特性編號(hào)障礙物名稱左下頂點(diǎn)坐標(biāo)其它特性描述1正方形（300,400）邊長(zhǎng)2002圓形圓心坐標(biāo)（550,450），半徑703平行四邊形（360,240）底邊長(zhǎng)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）邊長(zhǎng)1506三角形（60,300）上頂點(diǎn)坐標(biāo)（150,435），右下頂點(diǎn)坐標(biāo)（235,300）7長(zhǎng)方形（0,470）長(zhǎng)220，寬608平行四邊形（150,600）底邊長(zhǎng)90，左上頂點(diǎn)坐標(biāo)（180,680）9長(zhǎng)方形（370,6

4、80）長(zhǎng)60，寬12010正方形（540,600）邊長(zhǎng)13011正方形（640,520）邊長(zhǎng)8012長(zhǎng)方形（500,140）長(zhǎng)300，寬60在圖1的平面場(chǎng)景中，障礙物外制定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)點(diǎn)（要求目標(biāo)點(diǎn)與障礙物的距離至少超過(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ú)法完成行走機(jī)器人直線行走的最大速度為個(gè)單位

5、/秒機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑如果超過(guò)該速度，機(jī)器人將發(fā)生側(cè)翻，無(wú)法完成行走請(qǐng)建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時(shí)間路徑的數(shù)學(xué)模型對(duì)場(chǎng)景圖中4個(gè)點(diǎn)，具體計(jì)算：（1）機(jī)器人從出發(fā)，、和的最短路徑（2）機(jī)器人從出發(fā)，到達(dá)的最短時(shí)間路徑注：要給出路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的總距離和總時(shí)間 圖1 800800平面場(chǎng)景圖二、問(wèn)題分析對(duì)題目條件進(jìn)行分析：要求目標(biāo)點(diǎn)與障礙物的距離至少超過(guò)10個(gè)單位，又知O點(diǎn)坐標(biāo)為（0,0），即邊界不視為障礙物，但目標(biāo)點(diǎn)不能超出界限規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧是機(jī)器人轉(zhuǎn)彎路徑，轉(zhuǎn)

6、彎路徑只能由一段圓弧組成也可以由兩個(gè)或多個(gè)相切的圓弧路徑組成，但每個(gè)圓弧的半徑最小為10個(gè)單位，因?yàn)榘霃节呌?的時(shí)候，圓弧長(zhǎng)度趨于0，圓弧趨于折線機(jī)器人行走路徑與障礙物之間的最近距離為10個(gè)單位，否則發(fā)生碰撞，即可將障礙物區(qū)域向外擴(kuò)充10個(gè)單位，余下部分為目標(biāo)點(diǎn)可行走范圍，對(duì)條件中所給最大轉(zhuǎn)彎速度進(jìn)行分析，當(dāng)半徑時(shí)，即可視為直線運(yùn)動(dòng)，個(gè)單位/秒；當(dāng)半徑時(shí)， 最小速度個(gè)單位/秒；半徑越大，機(jī)器人轉(zhuǎn)彎速度越大對(duì)問(wèn)題一分析：機(jī)器人從出發(fā)，、和的最短路徑問(wèn)題首先分析，在沒(méi)有障礙物的情況下，兩點(diǎn)間線段最短，但在兩點(diǎn)之間有正方形障礙物5阻礙，必須繞開障礙物5到達(dá)，要使路徑最短，則實(shí)際路徑越逼近線段越短根據(jù)

7、目標(biāo)點(diǎn)的位置，可以猜想出機(jī)器人的幾種避障路徑同理分析、路段當(dāng)分析路徑時(shí)，采用分段處理的方法，將其分為、；使各分段路徑最短，最后將分段路徑綜合起來(lái)也是最短對(duì)問(wèn)題二分析：機(jī)器人從出發(fā)，到達(dá)的最短時(shí)間路徑在前文條件分析中，半徑越大，機(jī)器人轉(zhuǎn)彎速度越大，速度越大在問(wèn)題一最短路徑基礎(chǔ)上，在轉(zhuǎn)彎路段進(jìn)行優(yōu)化處理，適當(dāng)增大轉(zhuǎn)彎半徑，速度增大，與此同時(shí)轉(zhuǎn)彎路段圓弧長(zhǎng)度必然增加，綜合使得到達(dá)目的地總時(shí)間最短最后將給出路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)以及機(jī)器人行走的總距離和總時(shí)間 三、模型假設(shè)1假設(shè)機(jī)器人在行進(jìn)過(guò)程中為質(zhì)點(diǎn)；2假設(shè)機(jī)器人直線路段以速度個(gè)單位/秒行進(jìn)；3假設(shè)機(jī)器人在各轉(zhuǎn)彎路段勻

8、速行進(jìn)；4假設(shè)機(jī)器人從直線段至圓弧段，速度由直線行進(jìn)速度瞬間降至轉(zhuǎn)彎速度，速度不存在過(guò)度階段；5假設(shè)平面范圍邊界不是障礙物，不要求目標(biāo)點(diǎn)與邊界的距離至少超過(guò)十個(gè)單位，機(jī)器人目標(biāo)點(diǎn)不出界即可四、符號(hào)說(shuō)明表示機(jī)器人每段路徑，；表示轉(zhuǎn)彎半徑； 表示機(jī)器人所用時(shí)間，；表示 第段圓弧對(duì)應(yīng)的圓心角；表示切點(diǎn)坐標(biāo)五、模型的建立與求解問(wèn)題一模型的建立模型準(zhǔn)備： 根據(jù)對(duì)問(wèn)題的分析及兩點(diǎn)之間直線最短的原理，為使機(jī)器人能以最短的路徑避過(guò)障礙達(dá)到目標(biāo)點(diǎn)，應(yīng)使所走的路線盡可能的接近兩目標(biāo)點(diǎn)的連線，對(duì)此，可以猜想出幾種機(jī)器人行走的路徑并對(duì)其進(jìn)行探索首先對(duì)機(jī)器人所能行走的區(qū)域進(jìn)行分析，根據(jù)題意，需要將區(qū)域向外擴(kuò)展10個(gè)單位

9、，區(qū)域邊界角也應(yīng)擴(kuò)展10個(gè)單位，即機(jī)器人能運(yùn)動(dòng)范圍是由圓弧和相應(yīng)的線段圍成的，具體結(jié)果如下圖1所示：圖1：機(jī)器人行走范圍圖假設(shè)機(jī)器人可以看成是一個(gè)支點(diǎn)，則機(jī)器人可以在邊界線上運(yùn)動(dòng)而不會(huì)發(fā)生碰撞為使得機(jī)器人能以最短路徑避過(guò)障礙物，首先進(jìn)行局部分析，考慮段路徑，由圖可知：（1）若無(wú)障礙物，最短路徑為線段；（2）路段被障礙物5阻隔最短路徑探索探索最短路徑原則：實(shí)際路徑越逼近線段越優(yōu)先不考慮弧長(zhǎng)問(wèn)題，探索大致路徑. 圖3（a）.路徑一 圖3（b）路徑二路徑一是機(jī)器人在保證盡量沿邊界線運(yùn)動(dòng)的情況下得到的要從點(diǎn)到達(dá)點(diǎn)，機(jī)器人必須繞過(guò)邊界角，根據(jù)兩點(diǎn)之間直線最短的原理，可以得到圖3（b）的路徑二通過(guò)比較，可

10、以得出：在盡可能沿路徑行走的前提下，不需要轉(zhuǎn)彎就能到達(dá)的路徑盡量選用直線路徑，減少圓弧路徑階段，使路徑得到優(yōu)化轉(zhuǎn)彎圓弧半徑相等時(shí)，目標(biāo)點(diǎn)在不同地點(diǎn)轉(zhuǎn)彎，探索較優(yōu)路徑如圖所示，三段弧、對(duì)應(yīng)圓半徑相等且依次遠(yuǎn)離障礙物,離線段的距離越來(lái)越遠(yuǎn)以為圓心，為半徑畫弧，分別交、;同理以為圓心，為半徑畫??； 即=，=；顯然的距離最大，距離次之，距離最小；所以由最段路徑選擇由此可得出結(jié)論：在確定轉(zhuǎn)彎圓弧半徑的情況下，機(jī)器人轉(zhuǎn)彎越靠近障礙物，行走路線越接近兩目標(biāo)點(diǎn)之間的連線，總路程越小 在距障礙物最近的前提下，考慮圓弧半徑的影響，確定最短路徑自定義：邊界圓弧中點(diǎn)稱為節(jié)點(diǎn)通過(guò)中結(jié)論可知：在確定轉(zhuǎn)彎圓弧長(zhǎng)度的情況下，

11、機(jī)器人轉(zhuǎn)彎越靠近障礙物，行走路線越接近兩目標(biāo)點(diǎn)之間的連線，總路程越小由機(jī)器人所能行走的區(qū)域范圍及轉(zhuǎn)彎半徑至少為10的約束可知，畫出的圓弧邊界是機(jī)器人行走最短路徑的邊界，若需增大轉(zhuǎn)彎半徑，只能在節(jié)點(diǎn)處進(jìn)行變化，否則將超出機(jī)器人行走范圍節(jié)點(diǎn)是邊界圓弧的中點(diǎn)現(xiàn)判斷在節(jié)點(diǎn)處，轉(zhuǎn)彎半徑對(duì)最優(yōu)路徑選擇的影響各圖形頂角所對(duì)應(yīng)的外圍10個(gè)單位區(qū)域?yàn)檫吔鐖A弧，該圓弧為轉(zhuǎn)彎最小圓弧過(guò)最小圓弧節(jié)點(diǎn)做與節(jié)點(diǎn)相切的半徑大于10個(gè)單位的圓及相應(yīng)的路徑，如下圖3（c）中的2號(hào)路徑圖3（c）路徑三 可做如下猜想：圓弧的半徑越小，機(jī)器人從第一個(gè)目標(biāo)點(diǎn)到達(dá)目的地總路程越小下面對(duì)猜想進(jìn)行證明：圖4：證明猜想示意圖如圖4所示，以為圓

12、心，半徑為畫圓，與圓相切，切點(diǎn)為，與與圓相切，切點(diǎn)為；角位置如圖所示設(shè)點(diǎn)坐標(biāo)為,點(diǎn)坐標(biāo)為,圓心點(diǎn)坐標(biāo)為=，=，=,由幾何知識(shí)可得： ，在和中，可得：，由余弦定理得： ，總路程為，,，+，總長(zhǎng)度與轉(zhuǎn)彎半徑的關(guān)系式為： +，為尋求總長(zhǎng)度與轉(zhuǎn)彎半徑的具體關(guān)系，將對(duì)半徑求導(dǎo)，即:化簡(jiǎn)得：，當(dāng)且僅當(dāng)三點(diǎn)共線時(shí)，此種情況下不存在兩個(gè)切點(diǎn)角均在直角三角形內(nèi)，非直角，綜上所述：即：總路程關(guān)于半徑的函數(shù)單調(diào)遞增，機(jī)器人從一個(gè)目標(biāo)點(diǎn)到另一個(gè)目的點(diǎn)行走的總路程隨著轉(zhuǎn)彎圓弧半徑增大而增加故，猜想：圓弧的半徑越小，機(jī)器人從第一個(gè)目標(biāo)點(diǎn)到達(dá)目的地總路程越小，是正確的由于機(jī)器人轉(zhuǎn)彎半徑至少為10個(gè)單位，要使行走路徑最短，轉(zhuǎn)

13、彎半徑.經(jīng)過(guò)上述對(duì)機(jī)器人避障路線的探究，可得為使機(jī)器人行走最短路徑，需遵循以下幾個(gè)原則：1.所走路線應(yīng)盡可能接近兩目標(biāo)點(diǎn)的連線；2.轉(zhuǎn)彎半徑越小越好；3找不到兩圓間的公切線時(shí)，機(jī)器人應(yīng)盡可能的沿障礙物邊界運(yùn)動(dòng)模型的建立：根據(jù)以上原則，可以建立機(jī)器人從一個(gè)目標(biāo)點(diǎn)到達(dá)另一個(gè)目標(biāo)點(diǎn)的最短路徑優(yōu)化模型設(shè)切點(diǎn)坐標(biāo)為，表示第個(gè)障礙物第 個(gè)切點(diǎn)通過(guò)對(duì)路徑的探索，可知機(jī)器人的路徑是由直線和一條或多條圓弧組成的在此模型中，假設(shè)機(jī)器人的路徑是分階段的，每一階段的路徑由一條線段和一段圓弧組成，包括了一條線段和多條圓弧的情況如第段路徑中，線段和圓弧相連，在第段路徑中，線段與第段路徑中的圓弧相連，當(dāng)此線段長(zhǎng)度為時(shí)，機(jī)器

14、人從第段起點(diǎn)到第段末點(diǎn)的路徑就是由一條線段和兩段圓弧組成的線段的長(zhǎng)度可由兩點(diǎn)間的距離公式解得：圓弧的角度為，半徑為，則圓弧弧長(zhǎng)：已知切點(diǎn)時(shí)，圓弧角度為：機(jī)器人從第一個(gè)目標(biāo)點(diǎn)（）到第二個(gè)目標(biāo)點(diǎn)（）過(guò)程中， 此時(shí)要避過(guò)個(gè)障礙點(diǎn)，設(shè)從第一個(gè)目標(biāo)點(diǎn)出發(fā)到達(dá)另一處時(shí)，則線段部分長(zhǎng)度 :,同理，此時(shí)對(duì)應(yīng)的圓弧長(zhǎng)度：.為使機(jī)器人行走路徑最短，即：.綜上，可以建立最優(yōu)規(guī)劃模型：?jiǎn)栴}二的模型建立要使機(jī)器人從一個(gè)目標(biāo)點(diǎn)到達(dá)另一個(gè)目標(biāo)點(diǎn)所用的時(shí)間最短，需考慮行走總路程與速度的影響對(duì)條件中所給最大轉(zhuǎn)彎速度進(jìn)行分析可知，當(dāng)半徑時(shí)，即可視為直線運(yùn)動(dòng)，此時(shí)個(gè)單位/秒；當(dāng)半徑時(shí)， 最小速度個(gè)單位/秒，即機(jī)器人的速度范圍為2.

15、5到5.且半徑越大，機(jī)器人轉(zhuǎn)彎速度越大所以為追求最小時(shí)間，應(yīng)在模型一的基礎(chǔ)上適當(dāng)增大轉(zhuǎn)彎半徑同樣要保證總路程盡可能的短，機(jī)器人轉(zhuǎn)彎時(shí)要接近障礙物，即所走路線應(yīng)盡可能接近兩目標(biāo)點(diǎn)的連線故可以在最小圓弧基礎(chǔ)上增大轉(zhuǎn)彎半徑，以下討論速度與半徑之間的關(guān)系如上述圖4所示，總路程由線段長(zhǎng)度和圓弧長(zhǎng)度組成，,，+， +，則總時(shí)間 ，即總時(shí)間為：對(duì)半徑求導(dǎo):化簡(jiǎn)得：，令導(dǎo)數(shù) ,由模型一可知：,解得當(dāng)時(shí)，且函數(shù)在 區(qū)間內(nèi)是單調(diào)遞減的，在時(shí)是逐漸增大的，故要使時(shí)間最短，滿足模型的建立： 模型二是在模型一的基礎(chǔ)上增大轉(zhuǎn)彎半徑得到的，是追求最短時(shí)間和最短路徑的雙目標(biāo)規(guī)劃問(wèn)題建立模型如下：， ，問(wèn)題一、問(wèn)題二模型的求解

16、： 根據(jù)建立的模型可利用橡皮筋算法探索最短路徑機(jī)器人行走時(shí)，如果不知道確定路線時(shí)，可以先假設(shè)機(jī)器人會(huì)朝著目的地的方向走，如圖3(a)中的；如果中途碰到障礙物，就試圖繞過(guò)障礙物，再重新朝向目的地的方向行走，如圖所示，其中綠色的圓點(diǎn)S 表示出發(fā)點(diǎn)，紅圓點(diǎn)T 表示目的地實(shí)際上，如果視覺(jué)上沒(méi)有障礙，運(yùn)動(dòng)者會(huì)選擇較近的直切障礙物邊沿的行走路線，如圖3(b)所示這種形狀，就像在出發(fā)點(diǎn)和目的地之間拉了根橡皮筋，由于障礙物的存在，橡皮筋不能橫穿過(guò)去，所以沿障礙物邊沿拉伸，而正是因?yàn)橄鹌そ罹哂械膹椥裕沟寐窂节呌谧疃谈鶕?jù)這種思路，提出了自動(dòng)漫游路徑生成的橡皮筋算法 根據(jù)制定的三條原則：1.所走路線應(yīng)盡可能接近兩

17、目標(biāo)點(diǎn)的連線；2.轉(zhuǎn)彎半徑越小越好；3找不到兩圓間的公切線時(shí)，機(jī)器人應(yīng)盡可能的沿障礙物邊界運(yùn)動(dòng)可以得到機(jī)器人從的幾條最優(yōu)路線，如圖5所示：圖5：最短路徑示意圖 從圖中可以看出，從有兩條路線需要比較計(jì)算，利用MATLAB軟件求解得到結(jié)果如下（長(zhǎng)度單位為單位）：最優(yōu)路徑為：總路程分為2條線段和1段圓弧其中，各起終點(diǎn)坐標(biāo)、圓弧圓心坐標(biāo)及相應(yīng)的弧長(zhǎng)、線段長(zhǎng)度分別是：線段：（0，0）(70.4825，213.0686) 長(zhǎng)度224.4237?。?(70.4825，213.0686) （76.4914,219.3643）圓心（80,210）長(zhǎng)度9.0041線段： （76.4914,219.3643）（30

18、0,300） 長(zhǎng)度237.6094總時(shí)間：96.00826秒 總路程471.0372單位同理可以根據(jù)原則得到從到的幾條路線，如圖6所示：圖6：最短路徑示意圖利用MATLAB軟件求解得到結(jié)果如下：從的最優(yōu)路徑為：其中，各起終點(diǎn)坐標(biāo)、圓弧圓心坐標(biāo)及相應(yīng)的弧長(zhǎng)、線段長(zhǎng)度分別是：線段: , 長(zhǎng)度：305.7777弧: ， 弧長(zhǎng)：4.3214 線段: 長(zhǎng)度：162.1731 ?。?弧長(zhǎng)：7.7751 線段： 長(zhǎng)度： 75.6637 ?。?弧長(zhǎng)：13.6556 線段： 長(zhǎng)度：60?。?弧長(zhǎng)： 9.8883 線段： 長(zhǎng)度：96.9537?。?弧長(zhǎng)：6.1474線段： 長(zhǎng)度：111.3553總路程為853.7

19、113 個(gè)單位 總時(shí)間： 811.9235秒 同理可以根據(jù)原則得到從到的幾條路線，如圖7所示圖7：最短路徑示意圖機(jī)器人段路徑有4條，利用MATLAB求解得出結(jié)果如下：最優(yōu)路徑為：其中，各起終點(diǎn)坐標(biāo)、圓弧圓心坐標(biāo)及相應(yīng)的弧長(zhǎng)、線段長(zhǎng)度分別是：線段： 長(zhǎng)度： 237.4868?。?弧長(zhǎng)：8.5850線段： 長(zhǎng)度：318.4336?。?弧長(zhǎng)：8.8448線段： 長(zhǎng)度：169.7056弧： 弧長(zhǎng)：57.2031線段： 長(zhǎng)度：152.5349?。?弧長(zhǎng)：16.9174線段： 長(zhǎng)度：80?。?弧長(zhǎng)6.8916 線段： 長(zhǎng)度：43.5890 總路程：1001.7499+98.4401=1100.19單位總時(shí)

20、間：200.34998+39.37604=239.72602秒同理，找出的最優(yōu)路徑，如圖8所示：圖8：最短路徑示意圖利用MATLAB求解得出各起終點(diǎn)坐標(biāo)、圓弧圓心坐標(biāo)及相應(yīng)的弧長(zhǎng)、線段長(zhǎng)度分別是：?。?(292.7141, 280.3754) (299.3452, 293.5596)圓心（300,300）長(zhǎng)度：16.5989線段：d2(299.3452, 293.5596) （229.7932，532.02307）長(zhǎng)度 248.3995?。海?29.7932，532.02307）（225.4967，538.3538）圓心：（220,530）長(zhǎng)度7.8147線段：（225.4967，538.35

21、38）（140.4000,597.200） 長(zhǎng)度103.4617?。?（144.5033,591.6462）（140.4000,597.200）圓心（150,600）長(zhǎng)度7.0503線段:（140.4000,597.200）(92.000，694.000) 長(zhǎng)度108.2257弧： (92.000，694.000) （102.3208,709.7270） 圓心（100,700）長(zhǎng)度24.4852線段：（102.3208,709.7270）（270,690） 長(zhǎng)度168.8356?。海?70,690）（272，689.7980）圓心（180,770）， 長(zhǎng)度2.0136線段： （272，689.

22、7980）（368,670.2020） 長(zhǎng)度97.9796?。海?68,670.2020）（370,670）圓心（370，680） 長(zhǎng)度2.0136線段： （370,670）（430,670） 長(zhǎng)度60?。?（430,670）（435.5878,671.7068）圓心（430,680）長(zhǎng)度5.9291線段: （435.5878,671.7068）(534.4122,738.2932) 長(zhǎng)度119.1638?。?(534.4122,738.2932) （540,740）圓心（670,600） 長(zhǎng)度5.9291線段：（540,740）（670,740） 長(zhǎng)度130弧： （670,740）（679.

23、7725,732.1211）圓心（670,730）長(zhǎng)度13.5707線段： （679.7725,732.1211）（700.2275,637.8789） 長(zhǎng)度96.4365?。海?00.2275,637.8789）（702.6928,633.1732）圓心（700,640）長(zhǎng)度5.3769最終總路程：2794.512 單位； 最終總時(shí)間：598.5477秒問(wèn)題二的求解問(wèn)題二是在建立最短時(shí)間優(yōu)化模型的基礎(chǔ)上求解出從到的最短時(shí)間根據(jù)建立的模型，可知當(dāng)轉(zhuǎn)彎半徑時(shí)，時(shí)間有最小值因?yàn)?，此時(shí)轉(zhuǎn)彎時(shí)機(jī)器人的速度： 利用問(wèn)題一的方法解得各起終點(diǎn)的坐標(biāo)、圓弧圓心坐標(biāo)如下：線段：；?。?， 圓心為（81.5055

24、,210）；總時(shí)間秒，總距離470.8301單位模型檢驗(yàn)對(duì)于問(wèn)題一的模型檢驗(yàn)，由于軟件CAD在處理圖形、獲取坐標(biāo)方面較方便快捷，利用CAD可以自動(dòng)讀取坐標(biāo)、線段長(zhǎng)度、弧長(zhǎng)的優(yōu)點(diǎn)，粗略的估計(jì)從、和的可能較短路線，由CAD軟件可求得得粗略解將在Autocad中得到的結(jié)果與計(jì)算值相比較得表如下：Cad繪圖所得471.0362852.11941054.09042707.1591計(jì)算值471.0372853.71131100.192794.512相對(duì)誤差0%0.19%4.30%3.22%通過(guò)比較可知，計(jì)算值在允許的誤差范圍內(nèi)即本模型所得的路線為所有可能的較短路線中的最短路徑，因此本模型在解決機(jī)器人避開障

25、礙物探索最短路徑是相對(duì)較客觀合理的模型的評(píng)價(jià)與推廣優(yōu)點(diǎn)：（1）：本模型借鑒“橡皮筋算法”的精華的思想基礎(chǔ)，并改良其不足，利用改良后的“橡皮筋算法”使解決機(jī)器人機(jī)器人避開障礙物探索最短路徑的問(wèn)題變得生動(dòng)形象，化抽象為具體，使本模型在其它類似問(wèn)題方面的遷移性較強(qiáng)（2）：本模型充分體現(xiàn)數(shù)形結(jié)合思想，在處理機(jī)器人行走路線由直線到曲線、由曲線到直線等問(wèn)題時(shí)，巧妙利用解析幾何中，圓的切線、兩圓公切線處理，同時(shí)，采用CAD軟件進(jìn)行圖像上的檢驗(yàn)，使本模型在幾何關(guān)系、數(shù)學(xué)關(guān)系上得出的結(jié)果都是客觀合理的缺點(diǎn)：由于行走路線的限制，且路線的連續(xù)性以及機(jī)器人只能利用圓弧拐彎，因此求出的拐點(diǎn)（直路線線和圓弧切的點(diǎn)）基本上是小數(shù)，而且本模型中只精確到0.0001，可能會(huì)給具體的機(jī)器人實(shí)踐行走時(shí)帶來(lái)誤差模型的推廣： 本模型可用于推廣解決機(jī)器人快速滅火，迷宮路徑探索等相似路徑的探索問(wèn)題，也可推廣至交警疏通堵車問(wèn)題中路徑規(guī)劃問(wèn)題參考文獻(xiàn)1 陳勇，王棟，陳戈，一種三維虛擬