機器人避障問題

吳元清，廖輝,鄧志揚，郭文靜，凌德梅

(四川職業技術學院，四川 遂寧 629000)

機器人避障問題

吳元清，廖輝,鄧志揚，郭文靜，凌德梅

(四川職業技術學院，四川 遂寧 629000)

本文要解決機器人避障行走的最短路徑和最短時間問題.主要研究了在一個區域中有12個不同形狀的小區域是機器人不能與之發生碰撞的障礙物，機器人從區域中的O點出發避開各種障礙物到達最終目標點的最短路徑和最短時間數學模型.我們對問題1采用初等數學中的解析幾何和三角函數知識，建立基本線圓結構求路徑的數學模型，分內公切線、外公切線和經過定點的動圓三種情形討論，對動圓我們采用將圓形障礙物的半徑增加r，或把切線轉角用由定圓心到定點連線的夾角近似代替，都分解為基本線圓結構數學模型來求解，用窮舉法結合matlab編程算出可能的走法的總路徑的最小值.對問題2我們采用建立時間與行走轉彎半徑的數學模型，用搜索法結合matlab編程，求出最短時間.結果是：O→A的最短路徑為471.0372. O→B的最短路徑為858.6000.O→C的最短路徑為1093.7000.O→A→B→C→O的最短路徑為2783.7000.O→A的最短時間為94.5649.

最短路徑；搜索法；matlab；基本線圓結構；初等數學模型

1 問題重述

機器避障問題是2012年全國大學生學建模竟賽的D題，該問題如：

有一個800*800的平面場景圖（如圖1.1）,有一個機器人在原點O（0，0）處，機器人只能在此平面場景范圍內活動，而圖中有12個不同形狀的區域是障礙物，機器人不能與之發生碰撞，障礙物的數學描述如表1.1：

圖1.1

表1.1

在平面場景中，障礙物外指定一點為機器人要到達的目標點，而目標點與障礙物的距離至少超過10個單位，要想機器人的行走路徑為最優路徑，則它行走的路徑由線圓結構組成.機器人不能折線轉彎，轉彎路徑是與直線路徑相切的一段圓弧組成，也可以由兩個或者多個相切的圓弧路徑組成，要求每個圓弧的半徑和機器人行走線路與障礙物間的最小距離為10個單位，保證機器人在行走過程中不與障礙物發生碰撞;不然就會發生碰撞，如果碰撞發生，機器人行走失敗.

問題1：平面場景圖中有4個點分別為

O(0,0)，A(300,300)，B(100,700)，C(700,640)，機器人從O(0,0)出發,O→A,O→B,O→C和O→A→B→C→O的最短路徑.

問題2：機器人直線行走的最大速度為v0=5個單位∕秒.機器人轉彎的最大速度為v=v(ρ)=其中ρ是轉彎半徑.若超過該速度，機器人將無法完成行走.機器人從O（0，0）出發，到達點A（300，300）的最短時間路徑.

2 問題分析

本題的主要目的是在(如圖1.1)的平面場景圖中求出機器人繞過障礙物到達目標點的最短路徑.在此平面場景圖中機器人行走的路徑有很多種方法，我們通過分析發現每條路徑所經過的障礙物要滿足下面的條件，每條路徑所經過的障礙物都可分解為線圓結構.根據題目要求，機器人行走路徑要滿足這樣的約束條件：

（1）機器人只能在圖1.1的平面場景范圍內活動；

（2）若機器人行走的路徑需要有一定的安全性，則機器人與障礙物的距離至少超過10個單位；

（3）由于機器人的靈活性有限，因此它在轉彎過程中不能是折線，轉彎路徑可以由與直線路徑相切的圓弧組成，也可以由兩個或多個相切的圓弧路徑組成，且轉彎半徑最小為10個單位;

（4）在拐點和節點處都采用最小轉彎半徑，求得的路徑最短.

對問題1，要分別求出機器人行走路徑從O→A,O→B,O→C和O→A→B→C→O四種走法的各段最短的路徑，首先求出所經過路徑中各線段的長以及各段圓弧的弧長.然后各段相加計算總路徑，并求出各種走法的最優解.

對問題2,在解決了問題1的基礎上，要有約束條件：

（1）機器人直線行走以最大速度為v0=5個單位∕秒;

（3）機器人變速和轉身瞬間完成.

3 模型假設

(1)機器人能夠抽象成點來處理；

(2)機器人的性能足夠好，能準確地沿圓弧轉彎；

(3)機器人行走過程中不會意外停止；

(4)機器人行走不小于最小轉彎半徑和最小安全距離；

(5)機器人不會進入兩個相接觸的障礙物的死角.

4 定義與符號說明

r，ρ:轉彎半徑.α，αi：直線傾角或夾角.t:時間. L:最短路徑總長.

5 模型的建立

查閱相關文獻知，具有圓形限定區域的最短路徑是由兩部分組成的，一部分是平面上的自然最短路徑（即直線段），另一部分是限定區域的部分邊界，這兩部分是相切的，這兩條直線段是由圓弧連接的.

對于問題1，我們經過深入分析知，起點到目標點無論中間障礙物有多少，最短路徑都應該是若干個線圓結構所組成.在本題中存在障礙物的狀況，且障礙物在拐點處的危險區域是一個半徑為r的圓弧，而求兩點之間的最短路徑中的轉彎半徑我們應該按照最小的轉彎半徑來算才能達到最優.

5.1 基本線圓結構的數學模型

如圖5.1，設A(x1,y1)為起點，B(x2,y2)為目標點，延長直線O到CD中點交圓弧CD于H,過圓心作OH的垂線分別交AC、CD于F、E，圓心O(x3, y3)，C(x4,y4),和D(x5,y5)為機器人經過拐點分別于脫離危險線拐角小圓弧的切點，圓的半徑為r，∠AOB=α，∠AOC=β，∠BOD=γ，∠COD=θ.設ACDB線圓弧段的長度為L，解法如下：

圖5.1

5.2 三種特殊情形的轉化

下列三種情形我們不能直接采用線圓的結構來解決，需要做簡單的變換.

我們假設兩圓心坐標分別為O1(x1,y1)和O2(x2, y2),半徑分別為r1和r2.

5.2.1 內公切線情形

如圖5.2，設分點M(x3,y3)，由定比分點公式,得

圖5.2

這樣我們就可以利用5.1的方法，先求A到M，再求M到B，分兩段求解.

5.2.2 外公切線情形

如圖5.3，直線O1O2的傾角中點M(x3,y3),求得

圖5.3

我們也可以利用5.1的方法，先求A到M，再求M到B，分兩段求解.

同理如果有更多上述的轉彎，我們同樣可以按照上面方法分解.

5.2.3 從A繞過圓形障礙物經過動點P到達目標點B情形

要求出機器人從A繞過圓形障礙物經營動點P到達目標點B的最短路徑，我們有兩種方法：

方法1，我們把圓形障礙物的半徑增加r,把動態問題轉化為上面兩種情形之一;

方法2，問題1中要求機器人在原約束條件下從O依次經過A,B,C三個點回到O，不能簡單地處理為求各兩點間的最短路徑之和.由于機器人在經過中間目標點后不能直接轉變方向，所以要考慮機器人在到達目標點前的提前轉向.同時整個過程可分為從O到A，從A到B，從B到C，從C到O四個階段.在第一階段，起始點位置確定，出發方向是任意的，而目標點的位置和觸碰時的方向都已經確定了.在第二、三階段，起始點和目標點的位置和方向都是不確定的.在第四個階段，起始點的位置和出發方向確定了，而目標點位置確定，方向不定.

為了使得機器人在目標點處滿足最小轉彎半徑的限制，我們在中間目標點上加一個經過該點的半徑固定、圓心活動的圓環來進行中間目標點弧化處理.圓環圓心的不固定增加了求解的復雜程度.通過分析,我們發現圓環的圓心位置實際上只有有限種情形。排除一切明顯不合理情形后，可以進行窮舉.對于每一種狀態求解最優路徑之后，再將所有狀態的最優路徑進行比較，取全局最優作為本題的結果，同時也可以確定圓心的實際位置.

要求出機器人從A繞過障礙物經過M點到達目標點B的最短路徑，我們采用以下方法：

用一根釘子將一個圓環定在M點，使這個圓環能夠繞M點轉動.然后連接A和B的繩子并以這些轉彎處的圓弧為支撐（這里轉彎處圓弧的半徑均按照最小轉彎半徑來計算），拉緊繩子，那么繩子的長度就是A到B的最短距離.我們可以把路徑圖抽象為圖5.4的幾何圖形.下面我們對這段路徑求解：

圖5.4

如圖，A(x1,y1)是起點，B(x2,y2)是終點，O1(x3, y3)和O3(x4,y4)是兩個固定的圓，O2是一個可以繞點M(p,q)轉動的圓環，三個圓的半徑均為r，C、D、E、F、G、H均為切點.a、b、c、e、f分別是AO1、O1O2、AO2、AO3、O2O3的長度.A、B、O1、O3均是已知點，O2是未知點.那么最短路徑就可以表示為：

因為O2點的坐標未知，所以我們不能直接用模型5.1的線圓結構對其進行求解.故得先求出O2點的坐標.

設O2坐標為(m，n),∠AO1C、∠AO1O2、∠AO2

O1、∠AO2O3、∠AO3O2分別為αi（i=1、2、3、4、5），∠C O1D、∠EO2F、∠EO2M分別為θ1、θ2、θ.這樣便有以下關系:

在Rt△AO1C中，有在△AO1O2中，有在△AO2O3中，有在Rt△NO2F中，有于是有,又因為MO2一定會在∠EO2 F的角平分線上，所以有我們采用向量的形式來求，易知的一個方向向量與垂直，故其一個方向向量又有,=(p-m,q-n) 從 而 有 θ=arccos

綜合以上式子可以求得O2的坐標，從而可以得出路徑的長為

這可以采用模型5.1的線圓結構來求解.

由于動態問題計算太復雜，我們對模型作了進一步處理，為了保證機器人由起點A經過M到B，我們考慮作下面的近似計算，設A(x1,y1)，B(x2,y2)，M (x3,y3)，動點圓心O(a,b)，如圖5.5，則有從而轉化為線圓結構來求解.

表6.1

圖5.5

假設機器人從起點O到目標點P有有限種走法，每種走法由前面分析知路徑一定是由圓弧和線段組成，設有m條線段，n條圓弧，那么目標函數可以表示為：

用此模型就可以對起點到目標點之間的路徑進行優化求解.

對于問題2，設從O經過直線段OP、圓弧段PQ和直線段QA，我們可以建立從O到A所用的時間t與轉彎半徑ρ的函數關系：

建立數學優化模型為

6 模型的求解

對問題1，我們用窮舉法，結合mat lab編程算出可能走法的總路徑的最小值分述如下：

(1)要解決的是O到目標點A的最短路徑，圖中畫出了機器人可能的路線只有兩條（如圖6.1），運用mat lab編程計算（程序見mat lab.m），得出最短路徑為圖6.1標識的粗線條，求得的具體數據見表6.1.

(2)要解決O到目標點B的最短路徑，圖中標出了可能的路徑（如圖6.2），并對每條路徑分析，運用mat lab編程計算（程序見main12.m），得出最短路徑為圖6.2中標識的粗線條，求出的具體數據見表6.2.

圖6.1

圖6.2

表6.2

（3）要解決O到目標點C的最短路徑，圖中標出了可能的幾條路徑（如圖6.3），并對每條路徑分析，從O到C的路徑中要繞過障礙物經過動點P，為了方便求解，我們把圓障礙物的半徑增加r，又把此條路徑轉化為內公切線情形和外公切線的兩種情形，再運用mat lab編程（程序見main13.m）計算出最短路徑為圖6.3中粗線條，求得具體數據見表6.3.

圖6.3

表6.3

（4）解決的是O→A→B→C→O得最短路徑，圖中標出了可能的幾條路徑（如圖6.4），對每條路徑分析，從O→A→B→C→O的路徑中要繞過障礙物經過動點P，為方便求解我們把圓障礙物的半徑增加r，又把此條路徑轉化為模型建立中內公切線和外公切線的兩種情形，再運用mat lab編程（程序見main14.m和main15.m）計算，得出最短路徑為圖6.4中線條，求得具體數據見表6.4.

圖6.4

表6.4

（5）對于問題2，我們用搜索法和mat lab編程（程序見main2.m）,求出結果如表6.5所示.

表6.5

7 模型評價與推廣

7.1 模型的優點

1.用解析幾何計算簡單易懂，精確度高；

2.運用mat lab運算出每個路徑進行比較，得出最短路徑；

3.模型簡單易懂，用實際檢驗相當吻合；4.模型的通用性強，適用范圍廣.

7.2 模型的不足

本題中有12個障礙物，是按照線圓結構和線圓結構的變化從起點到目標點的路徑總是有限的，我們可以依次列舉出這些路徑進行計算和比較大小，得到結果.如果平面場景圖如圖1.1的區域中有n個障礙物，那么按照線圓結構和線圓結構的變化從起點到目標點的路徑就有無限多條，這樣我們用列舉法解決是無法完成的.所以就得找到更好的方法來解決這個問題.窮舉法計算量大，且采用近似算法有一定的誤差.

7.3 模型推廣

由上述分析我們有了這樣一個想法：先求出所有的切線，包括出發點和目標點到所有圓弧的切線以及所有圓弧與圓弧之間的切線，給這些定點賦一個等于切線長度的權值，如果某兩條切線有一個公切圓弧，則代表這兩條曲線的頂點是一條直線的兩個端點，邊上的權值等于這兩條切線之間的劣弧長度.然后在這張圖中加一個源點和終點，那么在所有代表出發點與其它圓弧之間切線的頂點與源點連成一條邊，權值均為0，同理在所有代表目標點到其它圓弧切線的頂點與終點連成一條邊，權值均為0，這樣題目就轉化成了求源點到達終點之間的最短路徑問題了，這里最短路徑就是指經過所有頂點與邊的權值之和最小，我們可以采用Di jkst ra算法進行求解.

注：此文獲2012年全國大學生數學建模競賽國家二等獎.

[1]王正林，龔純，何倩.精通mat lab科學計算[M].北京：電子工業出版社，2009.

[2]全國大學生數學建模競賽組委會.全國大學生建模競賽優秀論文匯編[G].北京：中國物價出版社，2002.

[3]王晶，羅璋，鄧輝.基于切線網絡模型的機[EB/OL].（20 12-09-08）.http://www.docin.com/p-243098224.html.

[4]全國大學生數學建競賽模組委會.機器人行走問題[EB/ OL].（201 2-09-07）.ht tp://wenku.baidu.com/viw/59f d857aa26925c52cc5df4c.html.

[5]王海英，黃強，李傳濤.圖論算法及其mat lab實現[M].北京：北京航空航天大學出版社，2010.

On theProblemsofRobotsAvoidingObstacle

W UYuan q ing,LIAOHui,D EN G Z hiyang,G UO W enj ing,LI N G Demei

(Sichuan V ocational and Technical Col lege,Suining Sichuan 629000)

This paper wants to solve the problems of the shor test path and time for robots avoiding obstacle.There are 12 smal l dif ferent shapes in a region that a robot cannot occur col l ision with them,it mainly researches the shortest path and the shor test time mathematical model for the robot. F or q uestion 1,we use analytic geomet ry and t rigonomet ric knowledge of elementary mathematics,set up a l ine and round st ructure mathematical model,we discuss it f rom three cases the internal common tangent,e x ternal common tangent,and the circle.F or the circle,we wi l l increase the radius of the circular obstacle r,or substitute the tangent angleby centeringangle,break it down into basic l ine and round st ructure to solve a mathematical model,using e x haustive method combined with M ATLA B programming to calculate theminimumvalueof the total pathof possiblemoves.F or q uestion2,we set up a time andwalking radiusmathematicalmodel,using the searchmethod combinedwith M ATLA B programming to calculate the shor test time.The resul ts:the shor test pathof O→Ais 471.0372,O→B is 858.60000, O→Cis 1093.70000,O→A→B→C→Ois 2783.70000,the shortest time of O→Ais 94.5649.

The Shor test Path;Search M ethod;M ATLA B;B asic Line and R ound St ructure;E lementary M athematics M ode

TP242

A

1672-2094(2013)02-0146-08

責任編輯：張隆輝

2013-02-10

吳元清(1964-),男,四川蓬溪人,四川職業技術學院應用數學與經濟系副教授.研究方向:應用數學.

廖 輝(1957-),男,四川蓬溪人,四川職業技術學院應用數學與經濟系副教授,碩士.研究方向:抽象代數,數學分析.