機(jī)器人避障問題

1、機(jī)器人避障問題 摘要本文研究了機(jī)器人避障最短路徑和最短時(shí)間路徑的問題，主要研究在一個(gè)存在12個(gè)障礙物的區(qū)域中，由出發(fā)點(diǎn)到達(dá)目標(biāo)點(diǎn)以及由出發(fā)點(diǎn)經(jīng)過途中的若干目標(biāo)點(diǎn)到達(dá)最終目標(biāo)點(diǎn)兩種情形，要得出機(jī)器人到達(dá)目標(biāo)點(diǎn)的最短路徑，我們將路徑分為兩個(gè)部分組成：一部分是平面上的自然最短路徑（即直線段），另一部分則是限定區(qū)域（即圓?。?。針對問題一，我們將直線和圓弧組成的路徑作為機(jī)器人行走的最短路徑，因此我們建立了線圓結(jié)構(gòu)并構(gòu)造直角三角形，運(yùn)用勾股定理與兩點(diǎn)之間的距離建立相應(yīng)方程，無論多么復(fù)雜的路徑，我們都可以將路徑劃分為若干個(gè)這種線圓結(jié)構(gòu)來求解。我們利用線圓結(jié)構(gòu)方法對機(jī)器人到達(dá)目標(biāo)點(diǎn)的每一條路徑進(jìn)行分解，然后把

2、幾條最短路徑采用窮舉法列舉出來，通過比較得出最優(yōu)路徑分別為（詳細(xì)的坐標(biāo)路線見模型的建立于求解部分）：針對問題二，要求得機(jī)器人從O(0，0)到達(dá)A點(diǎn)的最短時(shí)間路徑，由題意我們知道機(jī)器人的直線行走速度是一定的，所以我們考慮到增加機(jī)器人轉(zhuǎn)彎時(shí)的轉(zhuǎn)彎半徑，從而增加轉(zhuǎn)彎速度，相應(yīng)的長度也發(fā)生了變化。針對這個(gè)問題我們根據(jù)機(jī)器人的最大轉(zhuǎn)彎速度與問題一的分析，通過Matlab計(jì)算可得當(dāng)時(shí)，機(jī)器人從O點(diǎn)出發(fā)到A的時(shí)間最短為94.6001秒。關(guān)鍵詞：線圓結(jié)構(gòu) 勾股定理 窮舉法 最優(yōu)路徑 機(jī)器人避障 、問題重述1.1 背景分析機(jī)器人是整合控制論、機(jī)械電子、計(jì)算機(jī)、材料和仿生學(xué)的產(chǎn)物。在工業(yè)、醫(yī)學(xué)、農(nóng)業(yè)、建筑工業(yè)甚至

3、軍事領(lǐng)域中均有重要用途?，F(xiàn)在。，國際上對機(jī)器人是靠自身動(dòng)力和控制能力來實(shí)現(xiàn)各種功能的一種機(jī)器。聯(lián)合國標(biāo)準(zhǔn)化組織采納了美國機(jī)器人協(xié)會(huì)給機(jī)器人下的定義：“一種可編程和多功能的操作機(jī)；或是為了執(zhí)行不同的任務(wù)而具有可用電腦改變和可編程動(dòng)作的專門系統(tǒng)。”在科技界，科學(xué)家會(huì)給每一個(gè)科技術(shù)語一個(gè)明確的定義，但機(jī)器人問世已有幾十年，機(jī)器人的定義仍然仁者見仁，智者見智，沒有一個(gè)統(tǒng)一的意見。機(jī)器人是雖然外表不像人，也不以人類的方法操作，但可以代替人力自動(dòng)工作的機(jī)器。后來美國著名科普作家艾薩克.阿西莫夫?yàn)闄C(jī)器人提出了三條原則，即“機(jī)器人三定律”：第一定律機(jī)器人不得傷害人，或任何人受到傷害而無所作；第二定律機(jī)器人應(yīng)服

4、從人的一切命令，但命令與第一定律相抵觸時(shí)例外；第三定律機(jī)器人必須保護(hù)自身的安全，但不得與第一、第二定律相抵觸。這些“定律”構(gòu)成了支配機(jī)器人行為的道德標(biāo)準(zhǔn)，機(jī)器人必須按人的指令行事，為人類生產(chǎn)和生活服務(wù)1.2 問題的提出題中給出的是一個(gè)800×800的平面場景圖，在原點(diǎn)O（0,0）點(diǎn)處有一個(gè)機(jī)器人，它只能在該平面場景活動(dòng)范圍內(nèi)活動(dòng)。圖中有12個(gè)不同形狀的區(qū)域是機(jī)器人不能與之發(fā)生碰撞的障礙物。在圖中的平面場景中，障礙物外指定一點(diǎn)為機(jī)器人要到達(dá)的目標(biāo)（要求目標(biāo)與障礙物的距離至少超過10個(gè)單位）。規(guī)定機(jī)器人的行走路徑由直線段和圓弧組成，其中圓弧式機(jī)器人轉(zhuǎn)彎路徑。機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由

5、與直線路徑相切的一段圓弧組成，也可以由兩個(gè)或多個(gè)相切的圓弧路徑組成，但每個(gè)圓弧的半徑最小為10個(gè)單位。為了不與障礙物發(fā)生碰撞，同時(shí)要求機(jī)器人行走線路與障礙物間的最小距離為10個(gè)單位，否則將發(fā)生碰撞，若碰撞發(fā)生，則機(jī)器人無法完成行走。機(jī)器人直線行走的最大速度為v0=5個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為，其中是轉(zhuǎn)彎半徑。如超過該速度，機(jī)器人將發(fā)生側(cè)翻，無法完成行走?，F(xiàn)要建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短路徑和最短時(shí)間路徑的數(shù)學(xué)模型。對場景圖4個(gè)點(diǎn)O(0，0), A(300，300), B(100，700), C(700，640),具體計(jì)算：（1）機(jī)器人從O(0，0),出發(fā)，OA、OB

6、、OC和OABCO的最短路徑。（2）機(jī)器人從O（0,0）出發(fā)，到達(dá)A的最短時(shí)間路徑。二、問題分析2.1 問題一的分析針對問題一，我們要求定點(diǎn)O（0,0）按照一定的行走規(guī)則繞過障礙物到達(dá)目標(biāo)點(diǎn)的最短路徑。根據(jù)題目我們從OA點(diǎn)考慮到了兩種最短路徑，OB點(diǎn)我們考慮了三條途徑，OC點(diǎn)我們考慮了六條最短路徑，通過計(jì)算每一條路徑我們得出最優(yōu)路徑。由于機(jī)器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑由與直線路徑相切的一段圓弧組成，也可以由兩個(gè)或多個(gè)相切的圓弧路徑組成，但每個(gè)圓弧的半徑最小為10個(gè)單位。為了不與障礙物發(fā)生碰撞，所以我們采用線圓結(jié)構(gòu)方法并對路徑構(gòu)造出一個(gè)直角三角形，再利用勾股定理以兩點(diǎn)之間的距離公式建立相應(yīng)的方程，

7、得到每個(gè)坐標(biāo)的斷點(diǎn)與切點(diǎn)，最終運(yùn)用Matlab得出機(jī)器人到達(dá)目標(biāo)點(diǎn)的最短路徑。2.2 問題二的分析針對問題二，要求機(jī)器人從O（0,0）出發(fā)，到達(dá)A的最短時(shí)間路徑。由題目已知條件我們知道機(jī)器人的轉(zhuǎn)彎速度與直線行走的最大速度，在不能增加直線行走速度的情況下，我們考慮增加機(jī)器人的轉(zhuǎn)彎半徑。當(dāng)圓的半徑從10慢慢增大時(shí)，O到A的時(shí)間會(huì)變化，當(dāng)圓的半徑增加到某個(gè)臨界值時(shí)，即可求得最短時(shí)間，從而得出最短時(shí)間路徑。三、模型的假設(shè)與符號的說明3.1 模型的假設(shè) （1）假設(shè)機(jī)器人在行走過程中不會(huì)出現(xiàn)故障 (2) 假設(shè)機(jī)器人不會(huì)與障礙物發(fā)生碰撞 (3) 機(jī)器人直線行走的最大速度為v0=5個(gè)單位/秒 (4) 機(jī)器人只

8、在限定的平面場景中行走 （5）假設(shè)機(jī)器人能夠抽象成點(diǎn)來處理 （6 ）機(jī)器人在直線段路徑中一直保持最大行走速度（7) 機(jī)器人轉(zhuǎn)彎時(shí)不會(huì)發(fā)生側(cè)翻 (8) 機(jī)器人不會(huì)折線走符號詮釋（x, y）點(diǎn)的坐標(biāo)L路徑的長度第i行段切線的長度第j段圓弧的長度轉(zhuǎn)彎半徑拉力障礙物上的任意點(diǎn)與行走路徑之間的最短距離 表3-1 符號說明表 四、模型的建立及求解4.1 模型I的建立 針對問題一要得出機(jī)器人到達(dá)目標(biāo)點(diǎn)的最短路徑，首先我們要知道每個(gè)點(diǎn)的坐標(biāo)，在有障礙物的情況下，機(jī)器人將沿圓的圓弧行走，即機(jī)器人到達(dá)每一個(gè)目標(biāo)點(diǎn)都是由若干段線段以及若干個(gè)圓弧構(gòu)成的。將機(jī)器人從O（0，0）到達(dá)目標(biāo)點(diǎn)分為幾小段，將每一小段上已知的兩

9、個(gè)坐標(biāo)與圓弧的圓心連接起來，從而構(gòu)造出一個(gè)直角三角形，我們設(shè)兩個(gè)點(diǎn)的坐標(biāo)分別為（a1,b1、（a2,b2）、所以、切點(diǎn)坐標(biāo)為（x,y），兩條變的長度分別為、，如下圖4-1所示。rm() 圖4-1 構(gòu)造直角三角形示意圖 由圖中構(gòu)造的三角形，運(yùn)用勾股定理我們可以得出： 則由此我們可以根據(jù)兩點(diǎn)的距離公式，推導(dǎo)得出以下方程組： 由此圖中各點(diǎn)的坐標(biāo)都是已知的，針對每一條路徑所經(jīng)過的點(diǎn)與障礙物的坐標(biāo)，運(yùn)用Matlab軟件編程把每一組數(shù)據(jù)代入方程組即可計(jì)算出每條路徑相應(yīng)切點(diǎn)的坐標(biāo)（詳見附件）。 模型準(zhǔn)備 1 定理：具有圓形限定區(qū)域的最短路徑是由兩部分組成的：一部分是平面上的自然最短路徑（即直線段），另一部分

10、是限定區(qū)域的部分邊界， 這兩部分是由相切的，互相連接的。 有了上述定理，我們就可以這樣認(rèn)為，起點(diǎn)到終點(diǎn)中間無論障礙物有多少，最短路徑都應(yīng)該是若干個(gè)線圓結(jié)構(gòu)所組成。在本題中存在障礙物的狀況，且障礙物在拐點(diǎn)處的危險(xiǎn)區(qū)域是一個(gè)半徑為10個(gè)單位的圓弧，所以結(jié)合上面定理，我們易知，求兩點(diǎn)之間的最短路徑中的轉(zhuǎn)彎半徑我們應(yīng)該按照最小的轉(zhuǎn)彎半徑來算才能達(dá)到最優(yōu)。下面分析我們在題目中將會(huì)碰到的線圓結(jié)構(gòu)：DACB 圖4-4線圓結(jié)構(gòu) 1）如圖，設(shè)A為起點(diǎn)，B為目標(biāo)點(diǎn)，C和D分為機(jī)器人經(jīng)過拐點(diǎn)分別于隔離危險(xiǎn)線拐角小圓弧的切點(diǎn)，圓心為O(x5,y5),圓的半徑為r,AB的長度為a,AO的長度為b,BO的長度為c,角解法

11、如下：求ACBD的長度，設(shè)為L,如上圖可得以下關(guān)系: （2）而對于下面兩種情況我們不能直接采用線圓的結(jié)構(gòu)來解決，需要做簡單的變換。 情況一圖4-5 線圓結(jié)構(gòu) 我們假設(shè)兩圓心坐標(biāo)分別為 這樣我們就可以利用1）中的方法，先求出A到M,再求M到B, 這樣分兩段就可以求解。同理如果與更多的轉(zhuǎn)彎，我們同樣可以按照此種方法分解。 情況二:CDAOOOOEFBO 圖4-6線圓結(jié)構(gòu)這里我們依然設(shè)圓心坐標(biāo)分別為O,半徑均為r，這樣我們可以的到： 那么OO直線方程為： 因?yàn)楣芯€DE與OO平行，那么DE的直線方程可表示為： 其中： 那么把公切線的方程與圓的方程聯(lián)立，可以求得切點(diǎn)D和E的坐標(biāo)。這樣用D和E的中點(diǎn)分為

12、分割點(diǎn)都可以講上圖分割成兩個(gè)圖所示的線圓結(jié)構(gòu)，這樣就可以對其進(jìn)行求解。用同樣的方法可以進(jìn)行分割。模型準(zhǔn)備2 對于從起點(diǎn)經(jīng)過若干點(diǎn)然后在到達(dá)目標(biāo)點(diǎn)的狀況，因?yàn)椴荒茏哒劬€路徑，我們就必須考慮在經(jīng)過路徑中的一個(gè)目標(biāo)點(diǎn)時(shí)轉(zhuǎn)彎的狀況。為了研究這個(gè)問題的方便，我們先來證明本文中的一個(gè)猜想：猜想、；如果一個(gè)圓環(huán)可以繞著環(huán)上一個(gè)定點(diǎn)轉(zhuǎn)動(dòng)，那么過圓環(huán)外兩定點(diǎn)鏈接一根繩子，并與該圓環(huán)為支撐拉緊繩子，達(dá)到平衡狀態(tài)時(shí)，圓心與該頂點(diǎn)以及兩條切線的延長線的交點(diǎn)共線。 證明：如圖4-7所示，E點(diǎn)就是圓環(huán)上的一個(gè)頂點(diǎn)，ACDB就是拉緊繩子，B 用力學(xué)的知識(shí)進(jìn)行證明，因?yàn)槭抢o的繩子，所以兩邊的繩子拉力相等，設(shè)為,它們的合力設(shè)

13、為。DCAE圖4-7兩切線相交示意圖由幾何的知識(shí)可以知道共線，而又由力的平衡條件可知： 即4.2模型的建立通過以上這個(gè)定理我們可以建立以下模型：如圖4-8，要求出機(jī)器人從O點(diǎn)出發(fā)，OABCO的最短路徑，我們采用以下方法：分別用釘子使圓環(huán)定在A，B、C三點(diǎn)上，使這些圓環(huán)能夠分別繞點(diǎn)A，B、C轉(zhuǎn)動(dòng)。然后連接的繩子并以這些轉(zhuǎn)彎處的圓弧為支撐（這里轉(zhuǎn)彎處圓弧的半徑均按照最小轉(zhuǎn)彎處半徑來計(jì)算），拉緊繩子，那么繩子的長度就是 的最短距離。假設(shè)機(jī)器人從起點(diǎn)O到目標(biāo)點(diǎn),由上面可知路勁一定是由圓弧和線段組成，設(shè)有m條線段，n條圓弧。那么目標(biāo)函數(shù)可表示為： 用此模型就可以對起點(diǎn)到目標(biāo)點(diǎn)之間的路徑進(jìn)行優(yōu)化求解。4.

14、3模型I的求解一、以下給出機(jī)器人從O點(diǎn)到目標(biāo)點(diǎn)的可能路徑的最短路徑：（1）如圖4-9，解決的就是O到目標(biāo)點(diǎn)A的最短路徑問題，很顯然的一個(gè)問題是機(jī)器人可以從5號障礙物的上方走，也可以從5好障礙物的下方走，我們可以分別計(jì)算出這兩條可能為最短路徑的路徑長度，然后進(jìn)行比較，取最小者就是O到目標(biāo)點(diǎn)A的最短路徑。圖4-9 2) 如圖4-10，解決的是O到目標(biāo)點(diǎn)B的最短路徑問題，圖中給出了可能的三條路徑的最短路徑，我們可以分別計(jì)算出三條可能為最短路徑長度，然后進(jìn)行比較，取最小者就是O到目標(biāo)點(diǎn)B的最短路徑。 圖4-10 圖4-113）如圖4-11，解決的是O到目標(biāo)點(diǎn)C的最短路徑問題。OC的可能路徑共有六條，圖

15、中只畫出了其中一條可能路徑的最短路徑，我們同樣可以分別計(jì)算出六條可能的最短路徑，取最小者就是OC的最優(yōu)路徑。4）圖4-12 ，求解的是OABCO的最短路徑問題，這使我們考慮的不僅僅是經(jīng)過障礙物拐點(diǎn)的問題，應(yīng)該考慮經(jīng)過路徑中的目標(biāo)點(diǎn)處轉(zhuǎn)彎的問題，這是簡單的線圓結(jié)構(gòu)就不能解決這種問題，我們在拐點(diǎn)及途中目標(biāo)點(diǎn)處都采用最小轉(zhuǎn)彎半徑的形式，也可以適當(dāng)?shù)淖儞Q拐點(diǎn)半徑，使機(jī)器人能夠沿直線通過途中的目標(biāo)點(diǎn)，最終求得最短途徑。圖4-12 OABCO的路徑示意圖二，然后用Matlab求解結(jié)果如下：（1） O到目標(biāo)點(diǎn)A的可能路徑有兩條，就有兩條可能的最短路徑，如圖，機(jī)器人走上面這條路徑到達(dá)A，運(yùn)用Matlab求得該

16、路徑的總距離為471.0372。而機(jī)器人走上面這條路徑到達(dá)A ，求得該路徑的總距離為498.4259.所以機(jī)器人從O出發(fā)OA的最短路徑的總距離為471.0372，具體坐標(biāo)路線為：（0,0）（70.5059,213.1405） （坐標(biāo)路線1）（2）O到目標(biāo)點(diǎn)B的可能路徑有三條，即就有三條可能的最短路徑。 如圖，機(jī)器人走最上面這條路徑到達(dá)B這條路徑有六條線段和五段圓弧組成，直接用Matlab求得最短路徑為：845.7001。二機(jī)器人經(jīng)過中間一條路徑到達(dá)B，這條路徑也是有六條線段和五段圓弧組成，直接用Matlab求得這條路徑的結(jié)果為877.3949。機(jī)器人經(jīng)過最下邊一條路徑，同理求得這條路徑的結(jié)果為

17、947.825。綜上所述，O到目標(biāo)點(diǎn)B的最短路徑為845.701。具體的坐標(biāo)路線為：（3）O到目標(biāo)點(diǎn)C的可能路徑有六條，和2中的方法一樣，最終求解結(jié)果O到目標(biāo)點(diǎn)C的最短路徑為1076.6094，具體的坐標(biāo)路線為： (4)的最短路徑如圖所示，最終求解結(jié)果為：2602.3058，具體坐標(biāo)路線為：（0,0）4.4 模型II的求解 題目中要求建立機(jī)器人從區(qū)域中一點(diǎn)到達(dá)另一點(diǎn)的避障最短時(shí)間路徑的數(shù)學(xué)模型，在第一問的基礎(chǔ)上，因?yàn)榈谝粏栁覀兪墙⒌谋苷献疃搪窂侥Ｐ停?dāng)路徑最短（固定）的情況下，時(shí)間是隨著速度的變化而變化的，但是機(jī)器人直線行走的最大速度為v0=5個(gè)單位/秒。機(jī)器人轉(zhuǎn)彎時(shí)，最大轉(zhuǎn)彎速度為可知，直

18、線行走，機(jī)器人的速度已經(jīng)不可增加了，但是轉(zhuǎn)彎時(shí)，機(jī)器人的速度是隨著轉(zhuǎn)彎半徑的增大而增大的，但是不可能超過v0, 所以我們要盡量節(jié)省時(shí)間的途徑只有一條，那就是增加機(jī)器人的轉(zhuǎn)彎時(shí)的轉(zhuǎn)彎半徑，但是此時(shí)轉(zhuǎn)彎圓弧的圓心不能還是一開始的（80,120）點(diǎn)了，如果還是在（80,120），而半徑增大時(shí)，會(huì)增大O到A的路徑長度，所以轉(zhuǎn)彎圓弧的圓心要沿圓的切線AT1和AT2組成的角的角平分線往下移動(dòng)（如下圖），但是該圓始終與圓心為（80,120），半徑為10的圓內(nèi)切。當(dāng)圓的半徑從10慢慢增大時(shí)，O到A的時(shí)間會(huì)變化，當(dāng)圓的半徑增加到某個(gè)臨界值時(shí)，即可求得最短時(shí)間，從而得出最短時(shí)間路徑。 圖4-13最短時(shí)間路徑示意圖

19、根據(jù)問題1的分析，可以求得過圓的兩條切線AT1和AT2長，和弧線的長度 坐標(biāo)路線5五、模型的評價(jià)5.1模型優(yōu)點(diǎn)1、巧妙運(yùn)用了Matlab軟件來計(jì)算；2、模型優(yōu)化后用解析幾何進(jìn)行求解，精確度較高；3、假設(shè)符合實(shí)際情況，模型對問題的描述合理準(zhǔn)確，推導(dǎo)嚴(yán)謹(jǐn)，因此結(jié)果比較準(zhǔn)確，模型具有實(shí)用性；4、建立的規(guī)劃模型能與實(shí)際緊密聯(lián)系，結(jié)合實(shí)際情況對問題進(jìn)行求解，使得模型具有很好的通用性和推廣型；5.2模型缺點(diǎn)1、此模型適于全局規(guī)劃，獲得精確卻失去了效率。2、在障礙物較多時(shí)，且形狀不規(guī)則時(shí)，模型需要進(jìn)一步改進(jìn)。六、模型的改進(jìn)及推廣6.1模型的改進(jìn)本文采用了窮舉法來對每一條路徑的數(shù)據(jù)進(jìn)行分析，求出坐標(biāo)點(diǎn)的同時(shí)計(jì)算中存在一些誤差，在以后的論文中，遇到類似模型時(shí)，我們將把誤差減少到最低。6.2模型的推廣本題所應(yīng)有的模型實(shí)用性較高，在本文所研究的機(jī)器人躲避障礙物行走的最短路徑問題，通過對本問題的分析以及建立的模型來看，我們可以將模型推廣到社會(huì)上的一些實(shí)際問題，比如：運(yùn)輸問題，追蹤問題等等。在實(shí)際生活中，我們利用此種模型可以減少許多人力，精力以及財(cái)力，且適合于由于多種因素影響目標(biāo)時(shí)的判斷方法。參考文獻(xiàn)：（1） 譚永基，數(shù)學(xué)建模，上海，復(fù)旦大學(xué)出版社，2011.（2） 邦迪，圖論及其應(yīng)用，西安，縣科學(xué)出版社 1984（3） 胡海星，RPG游戲中精靈的移動(dòng)