機(jī)器人繞過障礙物的數(shù)理性研究

吳生根

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

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

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

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

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

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

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

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

1）切點(diǎn)坐標(biāo)求解：在求弧的切點(diǎn)過程中將各頂點(diǎn)上的弧當(dāng)做整個(gè)圓求解點(diǎn)到弧的切點(diǎn)坐標(biāo).如圖1.2設(shè)A（x，y）為起點(diǎn)，點(diǎn)B（x，y）為線段AB與圓O的切點(diǎn)，O（x，y）為圓O的圓心，作過A點(diǎn)與x軸的平行線與過O點(diǎn)垂直x軸的線交于C（x，y），過B點(diǎn)與x軸的平行線與過O點(diǎn)垂直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上兩點(diǎn)A（x，y），B（x，y）所形成的弦AB長為a，與半徑為ρ的圓O形成的圓心角∠AOB為α，弧AB長為l.則a=，α=2×arcsin，l=×2πρ.

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

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