吳生根

摘 要： 目前，機器人在我國得到了迅速健康的發(fā)展，并且為我國的科技產(chǎn)業(yè)發(fā)展作出了巨大貢獻(xiàn).本文針對機器人避障問題，根據(jù)選擇不同的行走路線，使用設(shè)立權(quán)值方法，建立線圓結(jié)構(gòu)模型，根據(jù)切點位置不同，做出不同的路線選擇.

關(guān)鍵詞： 障礙 路徑 切點

下圖1.5是一個800×800的平面場景圖，在原點O（0，0）點處有一個機器人，它只能在該平面場景范圍內(nèi)活動.圖中有12個不同形狀的區(qū)域是機器人不能與之發(fā)生碰撞的障礙物，障礙物的數(shù)學(xué)描述如下表：

在平面場景中，障礙物外指定一點為機器人要到達(dá)的目標(biāo)點（要求目標(biāo)點與障礙物的距離至少超過10個單位），為此，需要確定機器人的最優(yōu)行走路線——由直線段和圓弧線段組成的光滑曲線，其中圓弧線段是機器人轉(zhuǎn)彎路線，機器人不能折線轉(zhuǎn)彎，轉(zhuǎn)彎路徑是與直線相切的一條圓形曲線段，也可以是兩條或多條相切的圓弧曲線段組成，但每個圓形路線的半徑都必須大于某個最小轉(zhuǎn)彎半徑，假設(shè)為10個單位.另外，為了不與障礙物發(fā)生碰撞，要求機器人行走線路與障礙物間的最短距離為10個單位，越遠(yuǎn)越安全，否則將發(fā)生碰撞.若碰撞發(fā)生，則機器人無法到達(dá)目標(biāo)點，行走失敗.

建立機器人從區(qū)域中一點到達(dá)另一點的避障最短路徑和最短時間路徑的數(shù)學(xué)模型.對場景圖中4個點O（0，0），A（300，300），B（100，700），C（700，640），具體計算：機器人從O（0，0）出發(fā)，到達(dá)每個點的最短路徑和O→A，O→A→B的最短路徑.

對該問題而言，要求求定點O（0，0）按照一定的行走規(guī)則繞過障礙物到達(dá)目標(biāo)點的最短路徑.機器人的行進線路必定由直線和與此直線相切的圓弧組成，可以先行求出所有的公切線，然后構(gòu)造一個網(wǎng)絡(luò)圖，將這個問題轉(zhuǎn)化為一個無約束的最短路徑問題.若先畫出機器人行走的危險區(qū)域，拐角處就是一個半徑為10的圓弧.此時可采用拉繩子的方法尋找可能的最短路徑（比如：求O點和A點之間的最短路徑，我們就可以連接O點和A點之間的一段繩子，以拐角處的圓弧為支撐拉緊，那么這段繩子的長度便是O點到A點的一條可能的最短路徑），然后采用窮舉法列出O點到每個目標(biāo)點A、B的可能路徑，然后比較其大小便可得出O點到目標(biāo)點的最短路徑.而在計算總路徑時，其關(guān)鍵在于機器人在經(jīng)過A點走向B點的過程中要保證經(jīng)過A點，與此同時，在A點附近轉(zhuǎn)向時轉(zhuǎn)彎半徑及曲率圓心難以確定，B點到C點以此類推.

為了簡化現(xiàn)實問題，現(xiàn)增加如下假設(shè)：（1）機器人能抽象成點來處理；（2）機器人行走過程中不出現(xiàn)故障等問題.我們將目標(biāo)從起點到終點的路徑看成是一條無限長的繩子，將禁區(qū)的圓角矩形看成支點，用繩子繞過禁區(qū)，拉繩子兩端，當(dāng)繩子繃到最緊時，路徑最短.

以障礙物5為例，如圖1.1因為機器人與障礙物間的距離最少為10，所以障礙物5外圈的圓角矩形內(nèi)均為禁區(qū).設(shè)OF、AE切于圓角矩形，點P為線段AE、OF延長線的焦點，如圖所示在禁區(qū)外不管在何處轉(zhuǎn)彎距離最短的肯定是d+l+d，以O(shè)GHPA線為例，線段OP的距離一定小于OGHP因為兩點之間線段最短，而PA的距離一定大于EA，所以線路OGHA的長度一定大于線路OFEA.

1）切點坐標(biāo)求解：在求弧的切點過程中將各頂點上的弧當(dāng)做整個圓求解點到弧的切點坐標(biāo).如圖1.2設(shè)A（x，y）為起點，點B（x，y）為線段AB與圓O的切點，O（x，y）為圓O的圓心，作過A點與x軸的平行線與過O點垂直x軸的線交于C（x，y），過B點與x軸的平行線與過O點垂直x軸的線交于D（x，y）.

設(shè)半徑長為，OA長為a，AB長為b，∠BAO為α，∠AOC為β

則a=，b=，tanα=，α=arctan

tanβ=，β=arctan，cos（α+β）=，x=cos（α+β）×b+x

sin（α+β）=，y=sin（α+β）×b+y.

2）弧長求解：如圖1.3，設(shè)圓O上兩點A（x，y），B（x，y）所形成的弦AB長為a，與半徑為ρ的圓O形成的圓心角∠AOB為α，弧AB長為l.則a=，α=2×arcsin，l=×2πρ.

3）與兩圓圓心形成的線段不相交的切于兩圓的切點坐標(biāo)求解：（兩圓心連成的直線不平行或垂直于x軸）如圖1.4設(shè)圓O的圓心為O（x，y），圓O的圓心為O（x，y），作直線AB與直線OO不相交且切圓O于點A（x，y），切圓O于點B（x，y），過圓O作垂直于x軸的線與過圓O作平行于x軸的線交于C，過圓O作平行于x軸的線與過點A（x，y）作垂直于x軸的線交于點D，設(shè)圓O和圓O的半徑都為ρ.因為直線AB與圓O圓O相切，所以∠OAB=∠ABO=90°，又因為AO與BO都為半徑長度為ρ，所以四邊形ABOO是矩形，所以∠AOO=90°.因為∠DOC=90°，所以∠AOD=∠COO，因為∠ADO=∠OCO=90°，所以△ADO與△OOC為相似三角形，

即=，OC=y-y，OC=x-x，即=

解方程組==ρ可得OD=xAD=y.

則點A的坐標(biāo)為（x+x，y+y），同理可知B點坐標(biāo)為（x+x，y+y）.

接下來我們給出了O到各目標(biāo)點的可能路徑的最短路徑.

1）如圖1.6，解決的就是從O（0，0）到A（300，300）目標(biāo)點的最短路徑問題，從O（0，0）到A（300，300）兩條路徑，經(jīng)計算圖中上面的路線為L=471.04，下面的路線為L=498.43.

2）如圖1.7，解決的就是從O（0，0）到B（100，700）目標(biāo)點的最短路徑問題，從O（0，0）到B（100，700）兩條路徑，圖中上面的路線經(jīng)過計算距離更短為L=471.04.

針對機器人避障問題建立模型的方法有很多種，如：柵格法、精神網(wǎng)格法等，用這幾種方法建立的模型在大多數(shù)情況下只能求出局部最優(yōu)解，且時間和空間復(fù)雜度較大.本文中針對這個問題建立的線圓結(jié)構(gòu)模型，適用性較強，大多情況下均能求出全局最優(yōu)解.在障礙區(qū)間或障礙形狀變化的情況下也適用.線圓結(jié)構(gòu)模型的前提是線圓結(jié)構(gòu)可求，求解速度與障礙區(qū)間的數(shù)量成反比，當(dāng)障礙區(qū)間數(shù)量較大時求解速度會明顯減小，求出的最佳解與實際優(yōu)化解誤差會隨之增大.

參考文獻(xiàn)：

[1]譚永基.數(shù)學(xué)模型.上海：復(fù)旦大學(xué)出版社，2011.

[2]尤承業(yè).解析幾何.北京：北京大學(xué)出版社，2004.

[3]趙靜，但琦，主編.嚴(yán)尚安，等編.數(shù)學(xué)建模與數(shù)學(xué)實驗.北京：高等教育出版社；海德堡：施普林格出版社，2000.11（2002重?。?

[4]算反三角函數(shù)http：//www.ab126.com/geometric/2080.html.