機器人避障問題的解題分析(建模集訓(xùn))

1、機器人避障問題的解題分析摘要：本文對2012年全國大學(xué)生數(shù)學(xué)建模競賽D題機器人避障問題進行了全面分析，對最短路的設(shè)計進行了理論分析和證明，建立了機器人避障最短路徑的幾何模型，對最短時間路徑問題通過建立非線性規(guī)劃模型，有效地解決了轉(zhuǎn)彎半徑、圓弧圓心位置和行走時間等問題。關(guān)鍵詞：機器人避障；最短路徑；Dijkstra算法；幾何模型；非線性規(guī)劃模型1 引言隨著科學(xué)技術(shù)的進步和計算機技術(shù)的發(fā)展，機器人的應(yīng)用越來越廣泛，在機器人的應(yīng)用中如何使機器人在其工作范圍內(nèi)為完成一項特定的任務(wù)尋找一條安全高效的行走路徑，是人工智能領(lǐng)域的一個重要問題。本文主要針對在一個場景中的各種靜態(tài)障礙物，研究機器人繞過障礙物到達

2、指定目的地的最短路徑問題和最短時間問題。本文以2012年“高教社”杯全國大學(xué)生數(shù)學(xué)建模競賽D題“機器人避障問題”為例進行研究。假設(shè)機器人的工作范圍為800800的平面正方形區(qū)域（如圖1），其中有12個不同形狀的靜態(tài)障礙物，障礙物的數(shù)學(xué)描述（如表1）：圖1 800800平面場景圖表1編號障礙物名稱左下頂點坐標其它特性描述1正方形(300, 400)邊長2002圓形圓心坐標(550, 450)，半徑703平行四邊形(360, 240)底邊長140，左上頂點坐標(400, 330)4三角形(280, 100)上頂點坐標(345, 210)，右下頂點坐標(410, 100)5正方形(80, 60)邊長

3、1506三角形(60, 300)上頂點坐標(150, 435)，右下頂點坐標(235, 300)7長方形(0, 470)長220，寬608平行四邊形(150, 600)底邊長90，左上頂點坐標(180, 680)9長方形(370, 680)長60，寬12010正方形(540, 600)邊長13011正方形(640, 520)邊長8012長方形(500, 140)長300，寬60在原點O(0, 0)點處有一個機器人，它只能在該平面場景范圍內(nèi)活動，機器人不能與障礙物發(fā)生碰撞，障礙物外指定一點為機器人要到達的目標點。規(guī)定機器人的行走路徑由直線段和圓弧組成，其中圓弧是機器人轉(zhuǎn)彎路徑。機器人不能折線轉(zhuǎn)彎

4、，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無法完成行走。機器人直線行走的最大速度為個單位/秒。機器人轉(zhuǎn)彎時，最大轉(zhuǎn)彎速度為（是轉(zhuǎn)彎半徑）。如果超過該速度，機器人將發(fā)生側(cè)翻，無法完成行走。場景圖中有4個目標點O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，下面我們將研究機器人從O(0, 0)出發(fā)，求OA、OB、OC和OABCO的最短路徑，以及機器人從O(0, 0)出發(fā)，到

5、達A的最短時間路徑問題。2 靜態(tài)避障問題中機器人行走最短路徑的分析2.1 行走路徑的設(shè)計在本例中障礙物有4種不同形狀：矩形、平行四邊形、三角形和圓形?？紤]到機器人本身的形狀和大小，為研究方便起見，將機器人視為一個點。機器人與障礙物之間的距離至少為10個單位，因此可以先用包絡(luò)線畫出機器人行走的危險區(qū)域（如圖2），包絡(luò)線內(nèi)是機器人的禁入?yún)^(qū)。圖2 障礙物包絡(luò)圖對障礙物的一個角點來說，其禁入?yún)^(qū)的邊界應(yīng)由兩條直線和一條圓弧組成，兩條直線分別平行于角點的兩條邊，間距為10個單位，圓弧是以障礙物角點為圓心，半徑為10個單位的四分之一圓弧。可以證明具有圓形限定區(qū)域的最短路徑由兩部分組成，一部分是平面上的自然最

6、短路徑（直線段），另一部分是限定區(qū)域的部分邊界（即繩子拉到最緊時的圓弧部分），這兩部分是相切的，互相連接（如圖3所示）。由A繞過半圓形障礙物到達B點的路徑有多條，其中最短路徑為(E、F為切點)，其他路徑與AB直線圍成的區(qū)域都覆蓋這一路徑與AB直線圍成的區(qū)域，由此證明1。圖3由此可以確定機器人的行走路徑應(yīng)為線圓結(jié)構(gòu)，那么是否是轉(zhuǎn)彎半徑越小，行走路徑就越短呢？為此需要求在已知兩個固定點和圓弧圓心坐標的情況下，圓弧半徑r為何值，才能使機器人的行走路徑最短。圖4如圖4，已知兩個固定點，圓心，可以求得兩切點坐標，設(shè)半徑為，圓弧所對的圓心角為，的路徑長度為,則 將路徑函數(shù)對求導(dǎo)，得因為,，所以.，則函數(shù)為

7、單調(diào)遞增函數(shù)，因此當(dāng)圓弧半徑逐漸增加時，機器人的行走路徑會增大，逐漸降低時，機器人的行走路徑會減小2，本題規(guī)定轉(zhuǎn)彎半徑最小為10個單位，所以在路徑設(shè)定時應(yīng)將轉(zhuǎn)彎半徑設(shè)定為最小值10個單位。根據(jù)以上分析，對于靜態(tài)障礙物機器人的行走路徑應(yīng)遵循以下三個原則：原則一：機器人的行走路徑為線圓結(jié)構(gòu)，由兩條切線和一段圓弧組成；原則二：每個路口至多發(fā)生一次轉(zhuǎn)彎，并以障礙物頂點為轉(zhuǎn)彎圓弧的中心；原則三：機器人轉(zhuǎn)彎圓弧半徑為最小允許半徑10個單位。2.2 最短路徑的選擇 從起點到達目標點有多條路徑，根據(jù)Dijkstra算法可以找出從起點到達每一個目標點的最短路徑。本文采用帶權(quán)的有向圖表示機器人的行走路徑，途中節(jié)點

8、為障礙物的角點，邊表示障礙物之間的聯(lián)系，權(quán)表示線路的長度（節(jié)點之間的直線距離）。從頂點出發(fā)，沿圖的邊到達另一頂點所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑就是所求最短路徑，Dijkstra算法就是按路徑的長度遞增次序產(chǎn)生最短路徑的算法3。 下面以 為例，確定的最短路徑。如圖5所示，根據(jù)障礙物的形狀和位置，本文給出了機器人從O(0, 0)出發(fā)避過障礙物到達目標B點的4條較優(yōu)路徑。 圖5畫出的非循環(huán)網(wǎng)絡(luò)圖（如圖6）：B621306O230601121712259921647017978162238B5B3B6B2B4B1B9B77B8017111299569237399705159508329圖

9、6運用Dijkstra算法算出的最短路徑，最短路算法如下：1、 起點O記為,終點B記為；2、 從網(wǎng)絡(luò)的終點開始，令它的標號為零，并用方框記錄在圖6中；3、 計算結(jié)點的標號，設(shè)結(jié)點已標號，結(jié)點指向，則的標號可按算式：求出，其中是的標號，是結(jié)點與之間的直線距離；4、 重復(fù)上述計算，直到求得起點的標號為止，此標號即為最短路的長度；5、 確定最短路徑，從起點開始，順網(wǎng)絡(luò)的箭線前進，若有幾條箭線，則選取箭線所指標號最小且滿足條件的結(jié)點為最短路徑所經(jīng)過的結(jié)點。在圖6中，最短路徑為：.應(yīng)用上述算法可得到從點出發(fā)，分別到達各目標點的最短路徑：圖7的最短路徑為： （如圖7）圖8的最短路徑為：（如圖8）圖9的最短

10、路徑為:3 最短路徑計算模型3.1 單個目標點的最短路徑根據(jù)前面制定的行走路徑原則，起點到目標點無論中間障礙物有多少，最短路徑都應(yīng)該是若干個線圓結(jié)構(gòu)所組成，圓弧中心為障礙物的頂點，半徑為機器人轉(zhuǎn)彎最小半徑10個單位。觀察這四條路徑，發(fā)現(xiàn)所有行走路徑都可歸結(jié)為以下三種類型：類型一 圖10 線圓結(jié)構(gòu)1如圖10，設(shè)O（）為起點，A（）為目標點，C和D分別為直線與轉(zhuǎn)彎圓弧的切點，障礙物的頂點（即轉(zhuǎn)彎圓弧的圓心），圓的半徑為，的長度為，的長度為，的長度為，設(shè)的長度為L，則，由圖10可得以下關(guān)系： 在中： 在中： 在中： 所以： 從而可得： 這個模型運算簡潔，只需將起點、目標點和障礙物頂點坐標輸入模型，M

11、ATLAB就能很快計算出來4，計算程序見附錄1。類型二：對于圖11這種線圓結(jié)構(gòu)，需要做簡單的變換，才能求出的路徑長度。 圖11 線圓結(jié)構(gòu)2 假設(shè)兩圓心坐標分別為和,M點為兩圓心連線和兩圓公切線的交點，坐標為，那么很容易可以求得:這樣就可以利用類型一中的方法，先求A到M的長度，再求M到B的長度，分兩段就可以求解。同理如果有更多的轉(zhuǎn)彎，同樣可以按照此種方法分解。 類型三圖12 線圓結(jié)構(gòu)3如圖12，如果兩圓弧的公切線平行于兩圓圓心連線，求的路徑長度。設(shè)各點坐標分別為起點A (,),目標點B(),障礙物頂點,障礙物頂點),半徑為分別是的長度，設(shè)的長度為,則解法如下：由圖12，可以得到以下關(guān)系：a=,b

12、=,c =, , 在中，由余弦定理可得：在中,=arccos所以： 同理：；=arccos；則 運用MATLAB進行計算，MATLAB計算程序見附錄2.3.2 多個目標點的最短路徑 機器人從起點出發(fā)，依次經(jīng)過指定的中間目標點最后到達終點，是多個目標點的最短路徑問題。比如的最短路徑的計算。由于機器人的行走路線為線圓結(jié)構(gòu)，不能折線轉(zhuǎn)彎，因此中間目標點應(yīng)位于某個半徑為的圓周上，這里我們?nèi)园凑兆钚≡试S半徑為10個單位，則只需計算出過A、B、C三點的圓心位置即可，這樣就將多目標點的最短路徑問題轉(zhuǎn)化成了單目標點的最短路徑問題。求過A、B、C三點的圓心位置的問題可通過建立非線性規(guī)劃模型求得。（1） 過A點圓

13、弧的圓心圖13如圖13，障礙物頂點,頂點,，切點，過A的圓弧圓心，最短路徑為,則建立非線性規(guī)劃模型s.t. 運用LINGO13編程計算，計算程序見附錄3.（2） 過B點圓弧的圓心圖14如圖14，障礙物頂點,頂點,，過B的圓弧圓心，最短路徑為,則建立非線性規(guī)劃模型運用LINGO13編程計算，計算程序見附錄4.（3） 過C點圓弧的圓心圖15如圖15，障礙物頂點,頂點,，過C的圓弧圓心，圓與圓的公切線為,切點，圓與圓的公切線為,切點，最短路徑為,則 建立非線性規(guī)劃模型 運用LINGO13編程計算，計算程序見附錄5.運用LINGO對模型求解，過A、B、C的圓弧圓心坐標計算結(jié)果(如表2)：表2 過A、B

14、、C的圓弧圓心坐標經(jīng)過點圓弧的圓心坐標A（290.8854，304.1140）B（107.3884，693.2612）C（709.6622，637.4229） 3.3 切點坐標的計算模型要準確計算出機器人行走路徑的長度，必須要知道每一段圓弧的起點和終點，即切點坐標，通過觀察上述三種線圓結(jié)構(gòu)的切點主要有兩種類型，一種是兩圓圓心連線與公切線相交，另一種是兩圓圓心連線與公切線平行。（1） 第一種類型的切點兩圓圓心連線與公切線相交，則圓心連線的中點在切線上，可由兩圓圓心坐標確定中點坐標，此問題就可以轉(zhuǎn)化為求圓弧外的點與障礙物的轉(zhuǎn)彎圓弧形成的切線的切點（如圖16）圖16設(shè)切點,起點O(,),圓心M(,)

15、，求切點C的坐標在中由勾股定理可得：，即又因為切點C在圓M上，故聯(lián)立方程組運用MATLAB解方程，求出切點的坐標, MATLAB程序見附錄6。 （2） 第二種類型的切點圖17兩圓連線與公切線平行（如圖17），設(shè)切點,圓心,圓心()，半徑為,求切點的坐標。解法如下：直線的斜率為，的直線方程為，因為,所以DE的直線的斜率也為在DE直線上找一點，則DE直線方程為,即，又因為切點D在圓上，滿足圓的方程，故，建立方程組，解方程可求得D點的坐標, MATLAB程序見附錄7。 如果公切線在障礙物中心連線的下方，模型需要做以下變換再計算。根據(jù)以上模型可計算出、以及的所有切點坐標，直線段長度和圓弧長度，計算結(jié)果

16、見附錄8。4 最短時間路徑模型的建立和求解機器人的行走速度與轉(zhuǎn)彎半徑有關(guān)，假設(shè)行走速度與轉(zhuǎn)彎半徑之間滿足（其中為直線行走速度），那么與最短路徑問題不同，轉(zhuǎn)彎半徑不再是越小越好，轉(zhuǎn)彎半徑越小，雖然行走的距離也越短，但是速度會變慢，這樣行走速度反而可能會增加，因此，應(yīng)選擇一個適當(dāng)?shù)霓D(zhuǎn)彎半徑，使得行走時間最短5。 以為例，研究最短時間路徑問題。以機器人從原點出發(fā)到達點的時間最少為目標建立優(yōu)化模型。轉(zhuǎn)彎半徑越大速度越快，走最短距離的時間不一定是最短的到達時間，因此應(yīng)對轉(zhuǎn)彎半徑、轉(zhuǎn)彎所走的圓弧的圓心進行重新搜素，建立非線性規(guī)劃模型6。圖18如圖18，起點，目標點，障礙物5的頂點，切點，轉(zhuǎn)彎圓弧的圓心，圓

17、心角為，半徑為，的路徑為，時間為.則 建立目標函數(shù)編寫LINGO程序，應(yīng)用LINGO13求解，計算程序見附錄9，計算結(jié)果（如表3）：表3 的最短時間路徑路徑起點坐標終點坐標圓弧圓心坐標圓弧半徑總路程總時間0.00000.000069.8049212.7391469.896894.340569.8049212.739176.9877220.117880.9394209.085611.718676.9877220.1178300.0000300.00005 模型的評價與推廣5.1 模型的優(yōu)點（1）將機器人避障行走路線用若干個線圓結(jié)構(gòu)組成建立的模型各點坐標和長度都能直接得出結(jié)果，用解析幾何方法進行計

18、算，精確度較高。（2）運用多個方案進行優(yōu)化，在相對優(yōu)化中能取得最優(yōu)解。（3）模型簡單易懂，便于實際檢驗及應(yīng)用。5.2 模型的缺點（1）此模型需要全局優(yōu)化來求解，求解結(jié)果往往因為迭代產(chǎn)生一定的誤差，但是這個誤差在可允許的范圍內(nèi)。（2）在障礙物較多時，且形狀不規(guī)則時，模型顯得較為繁瑣。非線性變量越來越多會導(dǎo)致求解時間越來越長，解的可求性也越來越差。5.3 模型的改進及推廣本題只涉及12個障礙物，如果障礙物較多，到達目標點的路徑就較多，這時可應(yīng)用網(wǎng)絡(luò)模型計算最短路。如果障礙物形狀較復(fù)雜，單純用解析幾何知識計算較困難，模型需要進一步改進。機器人避障模型可以應(yīng)用于貨物運輸、管道輸送等領(lǐng)域，應(yīng)用此模型能較

19、好地解決運輸線路最短、輸送管道最短等問題。參考文獻1 百度文庫.行走機器人避障問題:2012-09-082 百度文庫.關(guān)于機器人避障行走問題的研究:2013-02-28 3 邦迪.圖論及其應(yīng)用M.西安:西安科學(xué)出版社,1984.4 章棟恩，馬玉蘭.MATLAB高等數(shù)學(xué)實驗M.北京：電子工業(yè)出版社，2010.5蔡志杰.機器人避障問題J.數(shù)學(xué)建模及其應(yīng)用,2013,2(1):53-59.6 王琦.線性-二次雙層規(guī)劃的滿意解與基于LP與NLP過程的算法J.系統(tǒng)工程理論與實踐,2007,27(8).7 周志明.LINGO及其在化工過程優(yōu)化中的應(yīng)用J.計算機與應(yīng)用化學(xué), 2010, 27(7).8 夏伯

20、男.基于最短時間的公交乘車路徑查詢模型J.大連工業(yè)大學(xué)學(xué)報,2011, 30(2).9 譚永基.數(shù)學(xué)模型.上海:復(fù)旦大學(xué)出版社，2011.附錄1、線圓結(jié)構(gòu)類型一的MATLAB程序例如：求圖7中的最短路徑，為，半徑，起點，目標點,障礙物頂點，運用MATLAB計算得的最短距離為471.0372，MATLAB算法如下：在MATLAB中編寫M文件：fun.mfunction L=fun(x1,y1,x2,y2,x3,y3)a=sqrt(x2-x1)2+(y2-y1)2);b=sqrt(x3-x1)2+(y3-y1)2);c=sqrt(x3-x2)2+(y3-y2)2);alpha1=acos(b2+c

21、2-a2)/(2*b*c);alpha2=acos(10/b);alpha3=acos(10/c);theta=2*pi-alpha1-alpha2-alpha3;L=sqrt(b2-102)+sqrt(c2-102)+10*theta;在命令窗口鍵入：fun(0,0,300,300,80,210)ans = 471.03722、線圓結(jié)構(gòu)類型三的MATLAB程序比如圖9中計算從起點繞過障礙物5，障礙物4，到障礙物4與障礙物12的中點的路徑長度，起點,障礙物5的頂點（230，60），障礙物4的頂點（410,100），障礙物4與障礙物12的中點（455,150）。編寫MATLAB程序輸入起點、目標

22、點、兩障礙物頂點坐標及半徑，即可計算出路徑長度為496.8696。 編寫M文件：fun1.mFunction L=fun1(x1,y1,x2,y2,x3,y3,x4,y4) a=sqrt(x4-x1)2+(y4-y1)2); b=sqrt(x4-x3)2+(y4-y3)2); c=sqrt(x3-x1)2+(y3-y1)2); d=sqrt(x3-x2)2+(y3-y2)2); e=sqrt(x4-x2)2+(y4-y2)2); alpha1=acos(b2+c2-a2)/(2*b*c);beta1=acos(10/c);theta1=3*pi/2-alpha1-beta1; alpha2=a

23、cos(b2+e2-d2)/(2*b*e); beta2=acos(10/e);theta2=3*pi/2-alpha2-beta2;L=sqrt(c2-102)+10*theta1+b+10*theta2+sqrt(e2-102);在命令窗口輸入 fun1(0,0,455,150,230,60,410,100)結(jié)果為ans =496.8696 3、過A點圓心編寫LINGO程序5,6model:min=(m-80)2+(n-210)2-400)(1/2)+(m-220)2+(n-530)2)(1/2)+10*(acos(-1)+atan(n-530)/(m-220)-atan(y2-y1)/(

24、x2-x1);(x2-x1)2+(y2-y1)2)(1/2)=(m-80)2+(n-210)2-400)(1/2);(x1-80)2+(y1-210)2=100;(x2-m)2+(y2-n)2=100;(n-y2)/(m-x2)*(y2-y1)/(x2-x1)=-1;(300-m)2+(300-n)2=100;n=y2;y1210;end運行結(jié)果： Objective value: 482.2310 Variable Value Reduced Cost M 290.8854 0.000000 N 304.1140 0.000000 Y2 294.6634 0.000000 Y1 219.45

25、05 0.000000 X2 294.1546 0.000000 X1 76.73080 0.0000004、過B點圓心編寫LINGO程序model:min=(m-150)2+(n-600)2)(1/2)+(m-180)2+(n-680)2)(1/2)+10*(acos(-1)-atan(680-n)/(270-m)-atan(600-n)/(150-m);(m-100)2+(n-700)2=100;end運行結(jié)果: Objective value: 219.9993Variable Value Reduced CostM 107.3884 0.000000N 693.2612 0.00000

26、05、過C點圓心編寫LINGO程序model:min=(m-670)2+(n-730)2-400)(1/2)+(m-720)2+(n-600)2-400)(1/2)+10*(atan(y2-y1)/(x2-x1)-atan(y4-y3)/(x4-x3);(x1-720)2+(y1-600)2=100;(x3-670)2+(y3-730)2=100;(x2-m)2+(y2-n)2=100;(x4-m)2+(y4-n)2=100; (700-m)2+(640-n)2=100;(n-y4)/(m-x4)*(y4-y3)/(x4-x3)=-1;(n-y2)/(m-x2)*(y2-y1)/(x2-x1)

27、=-1;(y2-y1)/(x2-x1)(n-600)/(m-720);(y4-y3)/(x4-x3)700;y4=640;y2670;y1600;end運行結(jié)果： Objective value: 130.7340 Model Class: NLP Variable Value Reduced Cost M 709.6622 0.000000 N 637.4229 0.000000 Y2 634.6639 0.000000 Y1 600.0000 0.000000 X2 700.0503 0.000000 X1 710.0000 0.000000 Y4 641.3609 0.000000 Y3

28、 733.9381 0.000000 X4 718.8542 0.000000 X3 679.1919 0.0000006、 第一種類型的切點例如求起點O繞過障礙物5到達A點的第一個切點坐標.編寫M文件，保存為“切點1.m”:syms x y x1 y1 x2 y2f1=(x2-x)2+(y2-y)2=100); f2=(x2-x1)2+(y2-y1)2-100=(x-x1)2+(y-y1)2);x,y=solve(f1,f2,x,y);在命令窗口輸入 x1=0;y1=0;x2=80;y2=210; eval(x,y)ans = 70.5060 213.1406 89.1772 206.027

29、7根據(jù)題意取障礙物左側(cè)的點，得第一個切點坐標為（70.5060，213.1406）。7、 第二種類型的切點例如求從A點到障礙物7的切點，運用MATLAB求解.編寫M文件，保存為“切點2.m”:syms x y x1 y1 x2 y2f1=(x1-x)2+(y1-y)2=100);f2=(y=y1+10*sqrt(1+(y2-y1)/(x2-x1)2)+(y2-y1)/(x2-x1)*(x-x1);x,y=solve(f1,f2,x,y);在命令窗口輸入： x1=290.8814;y1=304.1051;x2=220;y2=530; eval(x,y)ans = 300.4227 307.099

30、0 公切線的切點的坐標為（300.4227，307.0990），同樣算法，只需交換一下坐標就可得到另一切點的坐標為（229.5413，532.9939）. 8、最短路徑計算結(jié)果匯總：的最短路徑路徑起點坐標終點坐標圓心坐標圓弧半徑直線或圓弧長線段0.00000.000070.5060213.1406224.4995圓弧70.5060213.140676.6064219.406680.0000210.000010.00009.0510線段76.6064219.4066300.0000300.0000237.4868總路程：471.0373 總時間：96.0177的最短路徑路徑起點坐標終點坐標圓心坐

31、標圓弧半徑直線或圓弧長線段0.00000.000050.1353 301.6396305.7776圓弧50.1353301.639651.6795305.547060.0000300.000010.00004.2330線段51.6795305.5470141.6795440.5470162.2498圓弧141.6795440.5470147.9621444.7901150.0000435.000010.00007.7756線段147.9621 444.7901222.0379460.209975.6637圓弧222.0379 460.2099230.0000470.0000220.000047

32、0.000010.000013.6557線段230.0000470.0000230.0000530.000060.0000圓弧230.0000530.0000225.4967538.3538220.0000530.000010.0000.9.8883線段225.4967 538.3538144.5033591.646296.9537圓弧144.5033 591.6462140.6916596.3458150.0000600.000010.00006.1474線段140.6916 596.3458100.0000700.0000111.3553總路程：853.7001 總時間：179.0800的

33、最短路徑路徑起點坐標終點坐標圓心坐標圓弧半徑直線或圓弧長線段0.00000.0000232.1149 50.2262237.4868圓弧232.1149 50.2262232.1693 50.2381230.000060.000010.00000.7860線段232.1693 50.2381412.1693 90.2381184.3909圓弧412.1693 90.2381418.3448 94.4897410.0000100.000010.00007.6852線段418.3448 94.4897491.6552 205.5103133.0413圓弧491.6552 205.5103492.0

34、623 206.0822500.0000200.000010.00003.3127線段492.0623 206.0822727.9377 513.9178387.8144圓弧727.9377 513.9178730.0000520.0000720.0000520.000.10.00006.5381線段730.0000520.0000730.0000600.000080.0000圓弧730.0000600.0000727.7178 606.3589720.0000600.000010.00006.8916線段727.7178 606.3589700.0000640.000043.5889總路程：

35、1091.5359 總時間：223.3499的最短路徑路徑起點坐標終點坐標圓心坐標圓弧半徑直線或圓弧長線段0.00000.000070.5060213.1406224.4995圓弧70.5060,213.140676.7308 219.450580.0000210.000010.00009.1704線段76.7308 219.4505294.1546 294.6635230.9169圓弧294.1546 294.6635300.4266 307.1081290.8854304.114010.000015.4315線段300.4266 307.1081229.5412 532.9941236.7

36、619圓弧229.5412 532.9941225.4967 538.3538220.0000530.000010.00006.8481線段225.498538.3538144.5033 591.646296.9590圓弧144.5033 591.6462140.9044 595.8442150.0000600.000010.00005.6022線段140.9044 595.844298.2928 689.1054102.5349圓弧98.2928 689.1054108.2012 703.2281107.3884693.261210.000020.8073線段108.2012 703.228

37、1270.8128 689.9669163.1514圓弧270.8128 689.9669272.0000 689.7980270.0000680.000010.00005.2668線段272.0000 689.7980368.0000 670.202097.9778圓弧368.0000 670.2020370.0000670.0000370.0000680.000010.00002.0136線段370.0000670.0000430.0000670.000060.0000圓弧430.0000670.0000435.5878 671.7068430.0000680.000010.00005.9291線段435.5878 671.7068534.4122 738.2932119.1638圓弧534.4122 738.2932540.0000740.0000540.0000730.000010.00005.9291線段540.0000740.0000670.0000740.0000130.0000圓弧670.0000740.0000679.7899732.0390670.0000730.000010.000013.6359線