【正文】 D題 機器人避障問題摘 要本文綜合運用分析法、圖論方法、非線性規(guī)劃方法，討論了機器人避障最短路徑和最短時間路徑求解問題。針對問題一，首先，通過分析，建立了靠近障礙物頂點處轉彎得到的路徑最短、轉彎時圓弧的半徑最小時和轉彎圓弧的圓心為障礙物的頂點時路徑最短、轉彎在中間目標點附近時，中間目標點位于弧段中點有最短路徑的三個原理，基于三個原理，其次對模型進行變換，對障礙物進行加工，擴充為符合條件的新的區(qū)域并在轉彎處圓角化構成障礙圖，并通過擴充的跨立實驗，得到切線和圓弧是否在可避障區(qū)的算法，第三，計算起點、中間目標點和最終目標點和各圓弧及圓弧之間的所有可避障切線和圓弧路徑，最后給這些定點賦一個等于切線長度或弧度的權值構成一個網(wǎng)絡圖，然后利用Dijkstra算法求出了OA、OB，OC的最短路徑為OA：，OB：，OC：；對于需要經(jīng)中間目標點的路徑，可運用啟發(fā)規(guī)則分別以相鄰的目標點作為起點和終點計算，確定路徑的大致情況。針對問題二，主要研究的是由出發(fā)點到達目標點A點的最短時間路徑，我們在第一問的基礎上考慮路徑盡可能短且圓弧轉彎時的圓弧盡量靠近障礙物的頂點，即確定了圓弧半徑最小時的圓弧內切于要確定的圓弧時存在最小時間路徑，建立以總時間最短為目標函數(shù)，其中圓弧的圓心坐標為。圓弧兩切點的坐標分別為（,）、（,）。
關鍵字： Dijkstra算法 跨立實驗 分析法 非線性規(guī)劃模型 圖是一個800800的平面場景圖，在原點O(0, 0)點處有一個機器人，它只能在該平面場景范圍內活動。圖中有12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學描述如下表：編號障礙物名稱左下頂點坐標其它特性描述1正方形(300, 400)邊長2002圓形圓心坐標(550, 450)，半徑703平行四邊形(360, 240)底邊長140，左上頂點坐標(400, 330)4三角形(280, 100)上頂點坐標(345, 210)，右下頂點坐標(410, 100)5正方形(80, 60)邊長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在圖1的平面場景中，障礙物外指定一點為機器人要到達的目標點(要求目標點與障礙物的距離至少超過10個單位)。規(guī)定機器人的行走路徑由直線段和圓弧組成，其中圓弧是機器人轉彎路徑。機器人不能折線轉彎，轉彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，但每個圓弧的半徑最小為10個單位。為了不與障礙物發(fā)生碰撞，同時要求機器人行走線路與障礙物間的最近距離為10個單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機器人無法完成行走。機器人直線行走的最大速度為個單位/秒。機器人轉彎時，最大轉彎速度為，其中是轉彎半徑。如果超過該速度，機器人將發(fā)生側翻，無法完成行走。請建立機器人從區(qū)域中一點到達另一點的避障最短路徑和最短時間路徑的數(shù)學模型。對場景圖中4個點O(0, 0)，A(300, 300)，B(100, 700)，C(700, 640)，具體計算：(1) 機器人從O(0, 0)出發(fā)，O→A、O→B、O→C和O→A→B→C→O的最短路徑。(2) 機器人從O (0, 0)出發(fā)，到達A的最短時間路徑。注：要給出路徑中每段直線段或圓弧的起點和終點坐標、圓弧的圓心坐標以及機器人行走的總距離和總時間。圖 800800平面場景圖本問題的難點在于機器人要到達指定的目標點需要滿足以下兩個約束條件：1. 機器人的行走路徑由直線段和圓弧組成，不能折線轉彎，轉彎路徑由與直線路徑相切的一段圓弧組成，且每個圓弧的半徑最小為10個單位；2. 要求機器人行走線路與障礙物間的最近距離為10個單位。因此，我們在建立模型求解機器人到達目標點的最短路徑時需優(yōu)先考慮這兩個約束條件。首先我們可以根據(jù)約束條件將機器人行走的危險區(qū)域進行擴張，即所有的障礙物都向外擴張了10個單位。機器人所走的路徑都是直線與圓弧的構成，故存在線和弧、弧與弧之間的切線，可以考慮在所有代表出發(fā)點與其它圓弧之間切線的頂點與源點連成一條邊，權值均為0，同理在所有代表目標點到其它圓弧切線的頂點與終點連成一條邊，權值均為0，這樣題目就轉化成了求源點到達終點之間的最短路徑問題了。 對于問題二，要求最短時間路徑，則要考慮的是要以最大速度行走。直線行走時就是最大速度，但在轉彎圓弧處因為轉彎半徑越小，行走的速度就越慢，則需在第一問的前提下增大圓弧的半徑，則圓弧的轉彎半徑和圓心都不確定，通過建立模型確定OA之間的轉彎時圓弧的半徑和圓心。
三、模型的基本假設根據(jù)對該問題的分析，本文對所建立的模型提出以下基本假設：，能準確地沿圓弧轉彎四、符號說明指每段路徑的長度：機器人直線行走時的最大速度：機器人的最大轉彎速度：每段路徑所用的時間五、模型的建立與求解 模型的準備一首先給出以下三個前提及其證明：如圖1所示：圖1設A為起點，B為終點，矩形的陰影部分是障礙區(qū)，C為障礙物的頂點，D為障礙物外任意一點，連接AD，BD，AC，BC延長交AD于E點，因為在三角形中兩邊之和大于第三邊，所以有： BD+DEBE；BE=BC+CE； AE+CEAC；AD=AE+DE；兩個不等式相加，得：AE+DE+AE+CEBE+AC；即：BD+ADAC+BC.于是，得證由A到B在頂點C處轉彎時為最短路徑。要證明機器人轉彎時圓弧的半徑最小時路徑最短，則可以把P到A的路徑比擬成一條彈性繩，由于路徑要繞過障礙物，故要拉長彈性繩以繞過障礙物，由于機器人轉彎時只能是走圓弧路徑且有圓弧半徑約束，即可以在障礙物的頂點處加入圓環(huán)，將其圓心固定在頂點處，由于彈性繩的彈性勢能和伸長量存在如下能量關系：，故彈性繩彈性勢能最小時伸長量最小，此時正是路徑最短的情況：如圖2所示： 圖2 根據(jù)最小勢能原理可知，當彈性體平衡時，系統(tǒng)勢能最小。即彈性體在自由條件下，有由高勢能向低勢能轉化的趨勢?，F(xiàn)在將圓環(huán)看成也有彈性，在如圖所示的條件下為初始狀態(tài)。圓環(huán)受力為F，此時圓環(huán)有縮小的趨勢，隨著圓環(huán)的縮小系統(tǒng)趨于平衡，彈性繩有最小勢能。由能量守恒也可以說明，彈性繩的彈性勢能轉化為彈性圓環(huán)的彈性勢能，于是彈性繩的彈性勢能減小。因此，隨著圓環(huán)的半徑的減小，彈性繩的勢能減小，即最短路徑變短。所以轉彎時圓弧的半徑最小時路徑最短。轉彎圓弧的圓心為障礙物的頂點時路徑最短。，中間目標點位于弧段中點有最短路徑當機器人從O點出發(fā)不能直接到達另一目標點，而需經(jīng)過中間目標點A時，則必須在A點轉彎處形成一個圓弧，中間目標點位于弧段中點時且半徑最小時有最短路徑，下面給予證明：由上述2的證明可仍然采用此證法，設從兩轉向處引出一根彈性繩，要使其經(jīng)過A 點，如圖所示，在其自然伸長的前提下，必定會在A 點出彎折。由于機器人有轉彎時圓弧的半徑最小時路徑最短，從兩轉向處引出一根彈性繩，要使其經(jīng)過A 點，如圖所示，在其自然伸長的前提下，必定會在A 點出彎折。由于機器人有最小轉彎半徑約束，故在A 處加一最小轉彎半經(jīng)的圓，即r=10個單位，使其受力平衡時，即為路徑的最優(yōu)解。根據(jù)以上證明作出如下圖形(圖3)： 圖3作法：過A點分別作圓上M,N的切線，作的角平分線，在上距離A點10個單位處選取一點O，以O為圓心，10個單位為半徑，作圓O，再過M,N分別作圓O的切線，即為路徑。模型準備二：切線的剔除：基于上述準備一的三個前提條件和題中給出的兩約束條件即（1）機器人的行走路徑由直線段和圓弧組成，不能折線轉彎，轉彎路徑由與直線路徑相切的一段圓弧組成，且每個圓弧的半徑最小為10個單位（2）要求機器人行走線路與障礙物間的最