機器人繞過障礙物的數理性研究

吳生根

摘 要： 目前，機器人在我國得到了迅速健康的發展，并且為我國的科技產業發展作出了巨大貢獻.本文針對機器人避障問題，根據選擇不同的行走路線，使用設立權值方法，建立線圓結構模型，根據切點位置不同，做出不同的路線選擇.

關鍵詞： 障礙 路徑 切點

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

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

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

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

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

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

1）切點坐標求解：在求弧的切點過程中將各頂點上的弧當做整個圓求解點到弧的切點坐標.如圖1.2設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）.

設半徑長為，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，設圓O上兩點A（x，y），B（x，y）所形成的弦AB長為a，與半徑為ρ的圓O形成的圓心角∠AOB為α，弧AB長為l.則a=，α=2×arcsin，l=×2πρ.

3）與兩圓圓心形成的線段不相交的切于兩圓的切點坐標求解：（兩圓心連成的直線不平行或垂直于x軸）如圖1.4設圓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，設圓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的坐標為（x+x，y+y），同理可知B點坐標為（x+x，y+y）.

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

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

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

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

參考文獻：

[1]譚永基.數學模型.上海：復旦大學出版社，2011.

[2]尤承業.解析幾何.北京：北京大學出版社，2004.

[3]趙靜，但琦，主編.嚴尚安，等編.數學建模與數學實驗.北京：高等教育出版社；海德堡：施普林格出版社，2000.11（2002重印）.

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