趙增遜

（陜西鐵路工程職業(yè)技術(shù)學(xué)院 基礎(chǔ)課部，陜西 渭南 714000）

0 引言

隨著科學(xué)技術(shù)的飛速發(fā)展，機(jī)器人在實(shí)際中的應(yīng)用越來越廣泛；尤其是在一些特殊領(lǐng)域更是得到了大量的應(yīng)用，可以預(yù)見很多科技領(lǐng)域?qū)⑹菣C(jī)器人的舞臺(tái)［1］。雖然機(jī)器人的自動(dòng)化程度在不斷提高，性能在不斷增強(qiáng)，但處理機(jī)器人避障問題仍然是不可忽略的。處理機(jī)器人避障問題可以從多方面去解決，然而從實(shí)際應(yīng)用的角度出發(fā)，解決機(jī)器人避障所采用的方法越簡(jiǎn)單、使用的理論越簡(jiǎn)潔越好，當(dāng)然無論采用何種方法我們都希望達(dá)到的預(yù)期成果較好。本文給出了一種較為方便的方法來解決2012年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽D題機(jī)器人避障問題。

1 命題的證明

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

圖1

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

命題2：機(jī)器人從A行至B，中間需要行走一段圓弧，則圓弧距直線AB的距離越遠(yuǎn)，機(jī)器人的行走路線越長(zhǎng)。

圖2

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

2 尋找機(jī)器人行走最短路徑的問題

2.1 起點(diǎn)與終點(diǎn)之間只有一個(gè)障礙物的情形

當(dāng)起點(diǎn)和終點(diǎn)只有一個(gè)障礙物時(shí)，由上述命題結(jié)論：1）繞過障礙物的圓弧的半徑越小，機(jī)器人所經(jīng)過的路徑就越短；2）所繞過圓弧的位置越靠近起點(diǎn)和終點(diǎn)的連線，機(jī)器人所經(jīng)過的路徑就越短（圓弧在直線兩側(cè)的情況與在一側(cè)的情況結(jié)論不變）。

圖3

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

2.2 起點(diǎn)與終點(diǎn)之間有多個(gè)障礙物的情形

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

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

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

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

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

3 結(jié)語(yǔ)

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

圖4

圖5

［1］ 王東，郭兆正.機(jī)器人避障功能的設(shè)計(jì)［J］.長(zhǎng)春師范學(xué)院學(xué)報(bào)（自然科學(xué)版），2005，24（6）：44-46.

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

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

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