基于幾何方法的機器人避障研究

趙增遜

（陜西鐵路工程職業技術學院 基礎課部，陜西 渭南 714000）

0 引言

隨著科學技術的飛速發展，機器人在實際中的應用越來越廣泛；尤其是在一些特殊領域更是得到了大量的應用，可以預見很多科技領域將是機器人的舞臺［1］。雖然機器人的自動化程度在不斷提高，性能在不斷增強，但處理機器人避障問題仍然是不可忽略的。處理機器人避障問題可以從多方面去解決，然而從實際應用的角度出發，解決機器人避障所采用的方法越簡單、使用的理論越簡潔越好，當然無論采用何種方法我們都希望達到的預期成果較好。本文給出了一種較為方便的方法來解決2012年全國大學生數學建模競賽D題機器人避障問題。

1 命題的證明

命題1：假設機器人從A繞過障礙物到達B需要走過一段圓弧（圓弧所對的圓心角為90°），則圓弧所在圓的半徑越小，機器人從A到B所經過的路程就越短。

圖1

因此機器人在經過障礙物轉彎時要盡量縮小其經過圓弧的半徑，最好是達到所要求的距障礙物的最小距離以實現障礙距離最短［2］。設機器人在轉彎時圓弧的半徑為r（r為機器人行走路線與障礙物之間的最小單位），則該圓弧的圓心為障礙物的轉彎頂點（障礙物本身為圓弧時轉彎圓弧與障礙物圓弧同心，半徑為R+r，其中R為障礙物圓弧的半徑）。機器人行走路徑中的直線與轉彎圓弧之間都以相切形式連接。

命題2：機器人從A行至B，中間需要行走一段圓弧，則圓弧距直線AB的距離越遠，機器人的行走路線越長。

圖2

證明：如圖2所示，為了方便證明，假設O1和O2為半徑為r的圓，且圓心在同一豎直直線上。則機器人從A沿兩個圓弧行至B的路徑分別為A→C→D→B和A→E→F→B，其中 AC、BD 與圓 O2相切于 C、D 兩點，AE、BF與圓O！相切于E、F兩點；上述命題的結論即為。證明如下：在△HO1B 中；因為HO2>HO1，所以O2B>O1B。又因為D、F為切點，所以O1F⊥BF。O2D⊥BD在中，因為O1F=O2D=r，所以BD>BF。同理可以得到AC>AE。很明顯。，命題得證。

2 尋找機器人行走最短路徑的問題

2.1 起點與終點之間只有一個障礙物的情形

當起點和終點只有一個障礙物時，由上述命題結論：1）繞過障礙物的圓弧的半徑越小，機器人所經過的路徑就越短；2）所繞過圓弧的位置越靠近起點和終點的連線，機器人所經過的路徑就越短（圓弧在直線兩側的情況與在一側的情況結論不變）。

圖3

若起點O和終點A之間只有一個障礙物（如圖3所示），則很明顯從O到達A可以有兩條有效的路徑（可能為最短路徑）可走：O→P1→A；O→P2→A。兩條路徑在轉彎P1、P2處的轉彎圓弧的半徑都為最小值（距障礙物的最小距離），則由命題2可以得出從O到達A的最短路徑為O→P1→A。

2.2 起點與終點之間有多個障礙物的情形

2.2.1 采用貪心法尋找最短路徑

起點與終點之間有多個障礙物的情況是第一種情況的推廣，不過這時從起點A和終點B的有效路徑是多個A→P1→P2→B，A→P3→P2→B，A→P3→P4→P5→B 等。需要對這些路徑一一求解，以確定最短路徑，這顯然比較麻煩。若障礙物較多時，我們只能采用窮舉法進行一一的計算，才能得到最短的路徑。我們可以采用貪心法［3］，貪心法的意思是將那些明顯不可能是最短路徑的線路直接略去不再考慮，例如圖4中的路徑A→P3→P4→PA→P3→P2→B，該路徑很明顯A→P3→P4→P5→B路徑要長。如此一來對多個障礙物的情況我們需要計算的路徑就不是太多了，我們可以對得到的若干路徑進行計算，最后得到最短路徑。

2.2.2 采用就近原則尋找最小路徑

采用貪心法經過一定量的計算基本上可以找到從A到B的最短路徑，不過在計算量上來講可能還是有些大。我們可以根據命題2提供一種更為簡便的方法——“就近原則”。所謂的就近原則指的是如果從A到B需要通過障礙物O，則靠近AB的路徑即為最短路徑。如2.1節中的O→P1→A。下面我們來分析多個障礙物時如何使用就近原則。

如圖5從A到B需要依次經過3個障礙 物 O1、O2、O3，設 O1的兩個端點的圓弧的頂點為 P1、P3，連接 AB，則很明顯P3距離AB近，故通過O1時路徑為A→P3。然后連接P3B，障礙物O2兩個端點的圓弧的頂點為P4、P6，易得 P6距P3B的距離近，故通過O2的路徑為P3→P6。同理連接P6B，障礙物O3兩個端點圓弧的頂點為P2、P5，則P2距P6B的距離近，因此通過O3的路徑為P6→P2→B。因此我們可以得到從A到B的較短路徑A→P3→P6→P2→B。事實上這并不一定是從A到B的最短路徑，就近原則適用于AB的連線穿越障礙物內部的情況，如圖5中的路徑A→P1→P2→B，從P1到B并不需要經過障礙物O2，所以A→P1→P2→B也可能是最短的路徑，我們只需要將得到的兩條路徑進行比較即可得到最短的路徑。對于有的情況按照上述方法可能得到路徑較多一些，經過計算即可得到最短的路徑。

3 結語

采用幾何的方法處理機器人避障問題是一種較為簡便的方法，通過命題的證明驗證了使用這種方法的正確性；對于求最小障礙路徑問題提供了兩種方法：貪心法和就近原則［4］，從方便性來看就近原則更具有可操作性。

圖4

圖5

［1］ 王東，郭兆正.機器人避障功能的設計［J］.長春師范學院學報（自然科學版），2005，24（6）：44-46.

［2］ 陳智鵬，楊詩琴.帶障礙物情況下兩點最短距離的求解方法［J］.計算機工程，2010，36（16）：171-173.

［3］ 楊忠，鮑明，張阿舟.求解中國旅行商問題的新結果［J］.數據采集與處理，1993，8（3）：177-184.

［4］ 姜啟源，謝金星，葉俊.數學模型［M］.北京：高等教育出版社，2011：58-130.