【正文】 所有圓弧與圓弧之間的切線，給這些定點(diǎn)賦一個(gè)等于切線長(zhǎng)度的權(quán)值，如果某兩條切線有一個(gè)公切圓弧，則代表這兩條曲線的頂點(diǎn)是一條直線的兩個(gè)端點(diǎn)，邊上的權(quán)值等于這兩條切線之間的劣弧長(zhǎng)度。轉(zhuǎn)過了兩個(gè)圓弧，如圖6：情況一： 圖6假設(shè)兩圓心坐標(biāo)分別為和,半徑均為，O點(diǎn)坐標(biāo)為，則容易求得:這樣我們就可以利用只有一個(gè)圓弧中的方法，先求A到O，再求O到B，于是分兩段就可以求解。(圖中應(yīng)該剔除的切線用虛線表示)。由于機(jī)器人有最小轉(zhuǎn)彎半徑約束，故在A 處加一最小轉(zhuǎn)彎半經(jīng)的圓，即r=10個(gè)單位，使其受力平衡時(shí)，即為路徑的最優(yōu)解。所以轉(zhuǎn)彎時(shí)圓弧的半徑最小時(shí)路徑最短?，F(xiàn)在將圓環(huán)看成也有彈性，在如圖所示的條件下為初始狀態(tài)。直線行走時(shí)就是最大速度，但在轉(zhuǎn)彎圓弧處因?yàn)檗D(zhuǎn)彎半徑越小，行走的速度就越慢，則需在第一問的前提下增大圓弧的半徑，則圓弧的轉(zhuǎn)彎半徑和圓心都不確定，通過建立模型確定OA之間的轉(zhuǎn)彎時(shí)圓弧的半徑和圓心。因此，我們?cè)诮⒛Ｐ颓蠼鈾C(jī)器人到達(dá)目標(biāo)點(diǎn)的最短路徑時(shí)需優(yōu)先考慮這兩個(gè)約束條件。對(duì)場(chǎng)景圖中4個(gè)點(diǎn)O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計(jì)算：(1) 機(jī)器人從O(0, 0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑。機(jī)器人直線行走的最大速度為個(gè)單位/秒。圖中有12個(gè)不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：編號(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, 680)長(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)與障礙物的距離至少超過10個(gè)單位)。針對(duì)問題一，首先，通過分析，建立了靠近障礙物頂點(diǎn)處轉(zhuǎn)彎得到的路徑最短、轉(zhuǎn)彎時(shí)圓弧的半徑最小時(shí)和轉(zhuǎn)彎圓弧的圓心為障礙物的頂點(diǎn)時(shí)路徑最短、轉(zhuǎn)彎在中間目標(biāo)點(diǎn)附近時(shí)，中間目標(biāo)點(diǎn)位于弧段中點(diǎn)有最短路徑的三個(gè)原理，基于三個(gè)原理，其次對(duì)模型進(jìn)行變換，對(duì)障礙物進(jìn)行加工，擴(kuò)充為符合條件的新的區(qū)域并在轉(zhuǎn)彎處圓角化構(gòu)成障礙圖，并通過擴(kuò)充的跨立實(shí)驗(yàn)，得到切線和圓弧是否在可避障區(qū)的算法，第三，計(jì)算起點(diǎn)、中間目標(biāo)點(diǎn)和最終目標(biāo)點(diǎn)和各圓弧及圓弧之間的所有可避障切線和圓弧路徑，最后給這些定點(diǎn)賦一個(gè)等于切線長(zhǎng)度或弧度的權(quán)值構(gòu)成一個(gè)網(wǎng)絡(luò)圖，然后利用Dijkstra算法求出了OA、OB，OC的最短路徑為OA：，OB：，OC：；對(duì)于需要經(jīng)中間目標(biāo)點(diǎn)的路徑，可運(yùn)用啟發(fā)規(guī)則分別以相鄰的目標(biāo)點(diǎn)作為起點(diǎn)和終點(diǎn)計(jì)算，確定路徑的大致情況。針對(duì)問題二，主要研究的是由出發(fā)點(diǎn)到達(dá)目標(biāo)點(diǎn)A點(diǎn)的最短時(shí)間路徑，我們?cè)诘谝粏柕幕A(chǔ)上考慮路徑盡可能短且圓弧轉(zhuǎn)彎時(shí)的圓弧盡量靠近障礙物的頂點(diǎn)，即確定了圓弧半徑最小時(shí)的圓弧內(nèi)切于要確定的圓弧時(shí)存在最小時(shí)間路徑，建立以總時(shí)間最短為目標(biāo)函數(shù)，其中圓弧的圓心坐標(biāo)為。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧是機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。(2) 機(jī)器人從O (0, 0)出發(fā)，到達(dá)A的最短時(shí)間路徑。首先我們可以根據(jù)約束條件將機(jī)器人行走的危險(xiǎn)區(qū)域進(jìn)行擴(kuò)張，即所有的障礙物都向外擴(kuò)張了10個(gè)單位。
三、模型的基本假設(shè)根據(jù)對(duì)該問題的分析，本文對(duì)所建立的模型提出以下基本假設(shè)：，能準(zhǔn)確地沿圓弧轉(zhuǎn)彎四、符號(hào)說明指每段路徑的長(zhǎng)度：機(jī)器人直線行走時(shí)的最大速度：機(jī)器人的最大轉(zhuǎn)彎速度：每段路徑所用的時(shí)間五、模型的建立與求解 模型的準(zhǔn)備一首先給出以下三個(gè)前提及其證明：如圖1所示：圖1設(shè)A為起點(diǎn)，B為終點(diǎn)，矩形的陰影部分是障礙區(qū)，C為障礙物的頂點(diǎn)，D為障礙物外任意一點(diǎn)，連接AD，BD，AC，BC延長(zhǎng)交AD于E點(diǎn)，因?yàn)樵谌切沃袃蛇呏痛笥诘谌叄杂校? BD+DEBE；BE=BC+CE； AE+CEAC；AD=AE+DE；兩個(gè)不等式相加，得：AE+DE+AE+CEBE+AC；即：BD+ADAC+BC.于是，得證由A到B在頂點(diǎn)C處轉(zhuǎn)彎時(shí)為最短路徑。圓環(huán)受力為F，此時(shí)圓環(huán)有縮小的趨勢(shì)，隨著圓環(huán)的縮小系統(tǒng)趨于平衡，彈性繩有最小勢(shì)能。轉(zhuǎn)彎圓弧的圓心為障礙物的頂點(diǎn)時(shí)路徑最短。根據(jù)以上證明作出如下圖形(圖3)： 圖3作法：過A點(diǎn)分別作圓上M,N的切線，作的角平分線，在上距離A點(diǎn)10個(gè)單位處選取一點(diǎn)O，以O(shè)為圓心，10個(gè)單位為半徑，作圓O，再過M,N分別作圓O的切線，即為路徑。模型準(zhǔn)備三由上準(zhǔn)備一和準(zhǔn)備三可知，對(duì)于機(jī)器人轉(zhuǎn)彎的路徑按照一個(gè)圓弧、兩個(gè)圓弧、三個(gè)圓弧等多個(gè)圓弧枚舉出轉(zhuǎn)彎的情況：轉(zhuǎn)過了一個(gè)圓弧,如圖5: 圖5如圖，設(shè)()，O()，()，、的坐標(biāo)分別為和，, 則: ,，又=，可知：，，故B到A的路徑長(zhǎng)度為： 。同理如果有更多的轉(zhuǎn)彎，同樣可按照此種方法分解。那么在所有代表出發(fā)點(diǎn)與其它圓弧之間切線的頂點(diǎn)與源點(diǎn)連成一條邊，權(quán)值均為0，同理在所有代表目標(biāo)點(diǎn)到其它圓弧切線的頂點(diǎn)與終點(diǎn)連成一條邊，權(quán)值均為0，這樣題目就轉(zhuǎn)化成了求源點(diǎn)到達(dá)終點(diǎn)之間的最短路徑問題了，這里最短路徑就是指經(jīng)過所有頂點(diǎn)與邊的權(quán)值之和最小。 圖102）然后將不合理的切線剔除，假設(shè)剔除過后有m條合理切線，那么就有個(gè)頂點(diǎn)，設(shè)這些點(diǎn)的權(quán)值（），即第條合理曲線的長(zhǎng)度。根據(jù)上述的模型通過編程求解和幾何求解求出了最短路徑，并且求出了最短路徑中每段直線段或圓弧的起點(diǎn)和終點(diǎn)坐標(biāo)、圓弧的圓心坐標(biāo)。OABCO: 圓弧圓心的坐標(biāo)：A（,），B（,），C（,）（其他圓心在障礙物的頂點(diǎn)時(shí)未列出，只列出了在A,B,C三個(gè)目標(biāo)點(diǎn)的圓心坐標(biāo)）。
六、模型的評(píng)價(jià)模型的優(yōu)點(diǎn)：1. 模型簡(jiǎn)單易懂，對(duì)一般過路障問題實(shí)用。2. 當(dāng)障礙物為其他極其不規(guī)則的形狀時(shí)，模型需考慮多幾方面的情形，要對(duì)模型進(jìn)行適當(dāng)?shù)男薷?。fontsize39。,39。O=[80 210]。LineWidth39。if an20 an2=an2+2*pi。,2)。LineWidth39。,39。A39。R=10。line([0 ],[0 ,],39。an2=angle(plex(P2(1)O(1),P2(2)O(2)))。LineWidth39。line([dot1(1) dot2(1)],[dot1(2) dot2(2)],39。O39。text(100,700,39。,12)。dot2=[,]。P2=[,]。 P1=[,]。 dott=[150, ,]。 arcc=[, 230,470, 220,470]。arcPic(O1,P1,P2,R)。linePic(dot1,dot2)。O1=arcc(5:6)。dot2=dott(3:4)。P2=arcc(3:4)。dot1=dott(1:2)。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。168。O39。text(700,640,39。,12)。dot2=data{i