基于沖突檢查模型的機器人避障的最優路徑

何改平

（1.西安外事學院 工學院，陜西 西安710077；2.西安電子科技大學 數學與統計學院，陜西 西安710071）

0 引 言

隨著計算機、微電子技術的不斷發展，智能機器人成為眾多學者研究的熱點.現有文獻針對機器人的路徑規劃研究較多，主要分為全局和局部路徑規劃［1－7］，采用先進的模糊控制理論、神經元控制理論等進行路徑的最優規劃，算法相對復雜［8］.本文主要建立沖突檢查模型，對機器人在限定區域內順利避開障礙物的最優路徑進行分析，結合MATLAB仿真計算工具，分情況進行實例計算驗證了模型的正確性.

圖1 不同形狀障礙物平面圖

1 模型假設

假設機器人在一個800m×800m場景圖的原點O（0，0）處，而且它只能在該區域內活動.其內有12個使機器人不能與之發生碰撞的不同形狀的障礙物，障礙物的數學描述如圖1所示.

在平面場景圖1中，機器人要到達障礙物外指定的目標點O（0，0），A（300，300），B（100，700），C（700，640）（目標點與障礙物之間的距離至少超過10m）.規定機器人的行走路徑由直線段和圓弧組成，其中圓弧是機器人轉彎路徑.因為機器人不能折線轉彎，只能通過圓弧與其相切直線或圓弧與其相切圓弧來完成轉彎，所以機器人的行走路線是由直線和圓弧所構成的.而每個圓弧的半徑最小為10m，且規定機器人與障礙物的最小距離為10m.若無法保證此規定，機器人會因與障礙物發生碰撞而無法完成行走.機器人直線行走最大速度和最大轉彎速度分別為v0＝5m／s；v＝v（ρ）＝v0／（1＋exp（10－0.1ρ2）），其中，ρ為半徑.如超過該速度，機器人將會側翻無法行走.

（1）假設機器人可以用抽象點來說明.

（2）假設問題一中機器人經過障礙物時拐角處均是一個半徑為10m圓弧.

（3）假設機器人行走過程當中均以最大速度行駛且不會出現故障.

（4）假設機器人行走速度突變時沒有緩沖.

2 模型準備

2.1 沖突檢查模型

沖突的檢查過程，即查看路徑距離障礙物的最短距離是否符合機器人距離障礙物的最短距離要求.由于路徑由線段和弧線組成，現分別建立模型.

Step 1：檢查路徑中的所有線段是否滿足距離要求，如果不滿足，直接返回false.

Step 2：檢查路徑中的弧線是否滿足距離要求，如果不滿足，直接返回false.

Step 3：如果Step 1和Step 2都滿足，返回true，說明該路徑是一個有效的路徑.

2.1.1 線段的檢查 （1）線段與多邊形的檢查.①查看該線段的兩個端點到多邊形的各個邊的距離是否滿足安全距離要求，如果不滿足直接返回false；②查看多邊形的各個端點到該線段的距離是否有不滿足的，如果有不滿足的直接返回false；③如果①和②都滿足返回true.

（2）線段與圓之間的檢查.①從圓心向線段所在的直線做垂線，如果垂足落在線段上，看垂線段的長度和圓半徑的差是否滿足距離，如果不滿足返回false；如果垂足落在線段外，計算線段上靠近垂足的點與圓心的距離，以及這段距離和圓半徑的差是否滿足要求，如不滿足返回false；②如果①滿足返回true.

2.1.2 弧線的檢查 （1）弧線和多邊形的檢查.①查看弧線的端點和多邊形的各個端點是否滿足距離要求，如果不滿足返回false；②從多邊形的各個點向圓心做線段，如果該線段和弧線沒有交點，忽略；如果該線段的長度與弧半徑的差不滿足距離要求返回false；③從弧心向多邊形的各個邊做垂線，如果垂線和弧線相交并且垂足落在邊上，計算垂線段與弧半徑的差是否滿足距離要求，否則忽略.

（2）弧線與圓的檢查.假設弧線L的半徑為r1，圓O的半徑為r2.①從弧心到圓心做線段L1，如果弧線L與線段L1相交，檢查L1－r1－r2是否滿足距離要求；②如果L與L1不相交，計算L的端點與圓O的圓心之間的距離S，查看s－r2是否滿足要求.

2.2 幾何模型

2.2.1 點到圓的切點距離 如圖2（a）所示，設點的坐標為（a，b），如果切線斜率存在，則設為k，可得切線方程為y－b＝k（x－a），圓的方程為（x－m）2＋（y－n）2＝r2，根據圓心到切線的距離等于半徑可得

其中，a，b，m，n已知，可求得斜率k，進而求得切線方程y＝k（x－a）＋b，然后將切線方程和圓的方程聯立，即

解方程便可求出切點坐標（x1，x2），由兩點距離公式求得點到圓的切點距離l.

2.2.2 切點到切點間圓弧的距離 用沖突檢查模型準備一中的方法求出2個切點坐標，分別為A（x1，y1），B（x2，y2），若圓的半徑為r，如圖2所示，則弦長d和夾角θ分別為

圖2 切點到切點間的距離示意圖

再根據弧長公式可得弧長c

2.2.3 切點到切點之間線段的距離 （1）內公切線.如圖2（B）所示，EF為內公切線，E，F為切點，設切線方程為y＝kx＋b，圓O的方程為（x－m1）2＋（y－n1）2＝r2，圓O′方程為（x－m2）2＋（y－n2）2＝r2，由圓心到切線的距離等于半徑可得方程組

由方程組（7）即可解得k，b，進而得出切線方程，再與兩個圓分別聯立

求解方程組可解得切點D（x1，y1），E（x2，y2），根據兩點距離公式得到兩切點線段距離

（2）外公切線.如圖2（C）所示，設圓心坐標分別為O（x1，y1）和O′（x2，y2），半徑均為r，這樣可以得到

那么切線方程為

由內切線算法，求出切點、切線方程，進而求得切點坐標和兩切點之間的長度.

3 模型建立與求解

3.1 最短路徑模型

對于任何一條機器人走的線路，其路線都是由線 －弧 －線組成，設X1，X2，…，X2n，X2n＋1分別為路徑上的拐點，即直線和弧線的交點（切點）.其中奇數點和偶數點直接表示直線，偶數點和奇數點直接表示弧線，建立模型如下：

問題變成求一組能通過障礙物檢驗的X使得S最小.

（1）由圖3得出O→A的兩種路線，路徑A和路徑B.通過計算比較得到最短路徑為路徑A.設切線OX1的方程為y＝kx，利用圓心到切線距離等于半徑可得

圖3 O→A的兩種路徑示意圖

其中，x＝80，y＝210，化簡可得k1＝3.023 0，k2＝2.310 3（舍去）.聯立切線方程和圓的方程

可得x＝70.506 0，y＝213.140 6.即切點 X1（70.596 0，213.140 6），同理得出切點 X2（76.606 4，219.406 6），現有兩點 X1（70.596 0，213.140 6），X2（76.606 4，219.406 6）.根據

得c1＝rθ＝9.050 9，所以O→A的最短路徑為

S1＝l1＋c1＋l2，得總長S1＝471.037 2.

（2）O→B的最短路徑：從O到圖形6左下角，到圖形6的頂點，到圖形7的右下角，到圖形7的右上角，到圖形8的左下角，到B.即

3.2 最短時間路徑模型

由問題分析可知最短時間路徑問題是在最短路徑問題的基礎上，考慮到速度因素，得到最短時間路徑，故以拐彎半徑為變量，設為ρ，從O到A由線段OX1，圓弧X1X2，線段X2A組成，設它們的長度分別為l1，c，l2，可得最短時間模型為

圖4 O→B的最短路徑示意圖

圖5 最短時間路徑

（1）l1求解：設切線方程為y＝kx，圓的方程為（x－80）2＋（y－210）2＝ρ2，根據圓心到切線距離等于半徑可得

經化簡，據圖5可得需要斜率稍大的切線，聯立切線方程和圓的方程

由方程組可求得切點坐標為關于ρ的函數，即P1（x（ρ），y（ρ）），進而求得l1

（2）l2求解：設切線方程為y′－300＝k′（x′－300），圓的方程為（x′－80）2＋（y′－210）2＝ρ2，同樣可求得另一個切點坐標P2（x′（ρ）、y′（ρ）），得到l2

（3）弧長c求解：由P1（x（ρ），y（ρ）），P2（x′（ρ），y′（ρ））的坐標及幾何模型，可直接得到

將求得的l1，c，l2代入目標函數，解得ρ＝11.502 5時，時間最短為T＝94.564 9，且最短路徑為O（0，

4 模型算法分析

文中建立的模型算法優點在于將起始點到目標點分解成多個線－弧－線模型，使得復雜問題簡單化，易于實現；利用沖突檢查模型結合解析幾何模型優化后通過程序分別進行求解，精確度較高，便于實際檢驗及應用.缺點是重復計算量大，效率不高；在障礙物較多，且形狀不規則時，模型需要進一步改進.針對模型中有大量重復計算的情況，可以利用MATLAB程序進行模塊化編程.

機器人避障模型可以應用于電子地圖路線查找，電纜及管線的鋪設，交通運輸等，它們都與最短路徑有關，而這些問題用平常方法解決比較困難，所以可用該模型來幫助人們解決生活中的很多實際問題.

［1］李智也.移動機器人路徑規劃問題的解決方案 ［J］.計算機工程，2006，32（1）：189－192.

［2］金秀慧，伊連云，付瑩瑩，等.基于通用運動學模型的移動機器人避障路徑規劃［J］.機械工程師，2005，34（12）：34－35.

［3］董宇欣.移動機器人路徑規劃方法研究［J］.信息技術，2006（6）：108－111.

［4］王強，姚進，王進戈.基于遺傳算法的移動機器人的一種路徑規劃方法［J］.哈爾濱工業大學學報，2004（7）：867－870.

［5］楊晶東，楊敬輝，蔡則蘇.基于多目標優化的移動機器人避障算法［J］.上海交通大學學報，2012，46（2）：213－216.

［6］NUUKAEW Wuttinan，PHRUKSAPHANRAT.A fuzzy multiple objective decision making model for solving a multidepot distribution problem［C］／／Proceedings of the international Multi Conference of Engineers and Computer Scientists.Hong kong：IMECS，2010：17－19.

［7］KRUUSMAA M，WILLEMSON J.Covering the path space：A case base analysis for mobile robot path planning［J］.Knowledge－Based Systems，2003，16（5／6）：235－242.

［8］KIRBY Rachel，SIMMONS Reid，FORLIZZI Jodi.Companion：A constraint optimizing method for person acceptable navigation［C］／／The 18th IEEE International Symposium on robot and Human Interactive Communication（RO－MAN）Toyama，Japan：IEEE，2009：607－612.