1、常見避障算法介紹：實(shí)時(shí)避障是反映智能移動(dòng)機(jī)器人自動(dòng)能力的關(guān)鍵問題之一,國內(nèi)外學(xué)者曾做過大量的研究工作，常見的避障算法有如下幾種：（1）可視圖法52可視圖法將機(jī)器人、目標(biāo)點(diǎn)和多邊形障礙物的各頂點(diǎn)進(jìn)行組合連接，連接的直線視為弧，要求機(jī)器人和障礙物各頂點(diǎn)之間、目標(biāo)點(diǎn)和障礙物各頂點(diǎn)之間以及障礙物頂點(diǎn)與頂點(diǎn)之間的連線均不能穿越障礙物，即直線是可視的。機(jī)器人延這些可視線行進(jìn)直至離開該障礙。使用這種方法時(shí)，缺乏靈活性，一般需要機(jī)器人停止在障礙前搜集傳感器數(shù)據(jù)，并且它受傳感器精度影響較大。（2）人工勢(shì)場法53人工勢(shì)場法是由Khatib提出的一種虛擬力法，其基本思想是建立一種虛擬力，將機(jī)器人在未知環(huán)境中的運(yùn)動(dòng)視

2、為在人工虛擬力場中的運(yùn)動(dòng)，即假設(shè)目標(biāo)對(duì)機(jī)器人存在著吸引力F，而障礙物對(duì)機(jī)器人有排斥力F，那么引力和斥力的合tr力作為機(jī)器人運(yùn)動(dòng)的加速力，從而計(jì)算出機(jī)器人的位置和控制機(jī)器人的運(yùn)動(dòng)方向（如圖4-1）。勢(shì)場法結(jié)構(gòu)簡單，便于底層的實(shí)時(shí)控制；但是也存在若干缺陷，比如：在相近障礙物間不能發(fā)現(xiàn)路徑；在狹隘的通道中會(huì)來回?cái)[動(dòng)等。（3）VFH（VectorFieldHistogram）直方圖由于勢(shì)場法的缺陷，J.Borenstein完全放棄了勢(shì)場法，而設(shè)計(jì)了一種稱為VFH的方法，它將機(jī)器人的工作環(huán)境分解為一系列具有二值信息的柵格單元，每個(gè)矩形柵格中有一個(gè)積累值，表示在此處存在障礙物的可信度，高的累計(jì)值表示存在障

3、礙物的可信度高。這是因?yàn)閭鞲衅鞑粩嗫焖俚牟蓸迎h(huán)境，存在障礙物的柵格不斷被檢測(cè)的結(jié)果。柵格大小的選擇直接影響著控制算法的性能。柵格選得小，環(huán)境分辨率就高，但是抗干擾性就比較弱，環(huán)境信息存儲(chǔ)量大，使得決策速度慢；柵格選的大，抗干擾性就比較強(qiáng)，但環(huán)境分辨率下降，在密集障礙物環(huán)境中發(fā)現(xiàn)路徑的能力減弱。另外，柵格大小的選取也與傳感器的性能有關(guān)，若傳感器的精度高而且反應(yīng)速度快，柵格可以選的小些。由VFH控制的移動(dòng)機(jī)器人表現(xiàn)出了良好的性能。本研究中就是采用該方法作為機(jī)器人的避障策略。其算法思想在下文中具體介紹。abfccJe圖5-1勢(shì)場法思想簡圖5.2VFH避障算法介紹CV(CertaintyValue)值

4、的確定在VFH算法中用二維的柵格來表征環(huán)境。將機(jī)器人的工作空間劃分為若干連續(xù)的二維柵格系列。每個(gè)柵格中都包含一個(gè)概率值。這個(gè)概率值體現(xiàn)了在該柵格中存在障礙物的可信度，CV值越高，表示此處存在障礙物的可能性就越大。它通過一個(gè)與所用傳感器特性有關(guān)的概率方程進(jìn)行更新。如圖5-2,對(duì)于聲納傳感器而言，它具有椎形視角，返回的是傳感器到該錐形區(qū)域內(nèi)最近一物體的距離值。在運(yùn)行過程中，當(dāng)機(jī)器人接收到傳感器讀數(shù)后，利用該讀數(shù)值，通過使用概率函數(shù)C更新錐形區(qū)域內(nèi)每個(gè)柵格的概率值，從而獲得對(duì)障礙的最新認(rèn)識(shí)。實(shí)x驗(yàn)表明，離該錐形軸線越近的柵格更新的越快。我們可以這樣認(rèn)為：被檢測(cè)到的障礙物最可能的位置就是在錐形軸線附近

5、。由上述可知，機(jī)器人每接收到一個(gè)傳感數(shù)據(jù)，就要調(diào)用一次概率函數(shù)。顯然這樣會(huì)使計(jì)算復(fù)雜度提高，導(dǎo)致反應(yīng)延時(shí)而不利于數(shù)據(jù)的實(shí)時(shí)處理。這在機(jī)器人運(yùn)動(dòng)速度較快時(shí)表現(xiàn)更為明顯。因此，可以將算法進(jìn)行如下改動(dòng)：由于被檢測(cè)到的障礙物最可能的位置就是在錐形軸線附近，所以我們每次僅僅需要更新位于錐形的軸線上且到傳感器距離等于傳感器讀數(shù)的那個(gè)柵格即可。在機(jī)器人不斷的運(yùn)行、傳感器連續(xù)采樣的過程中，這種方法同樣可以獲得對(duì)障礙物的概率分布。同時(shí)注意到聲納傳感器有其固有的一些缺點(diǎn)：比如方向性較差，抗干擾能力較低，錯(cuò)誤讀數(shù)多等。在這里我們著重考慮的是因其抗干擾能力低而產(chǎn)生較大噪音的問題。D-15伽口Ie15圖5-2聲納數(shù)據(jù)概

6、率為解決這個(gè)問題，可以從硬件和軟件兩方面進(jìn)行處理。比如可以使用由24個(gè)聲納均勻分布而組成的聲納環(huán)。每次只觸發(fā)四個(gè)聲納，且必須保證聲納之間均為90度。這樣可以減少聲納之間聲波的相互干擾。此外，在算法中也對(duì)噪音進(jìn)行處理，削弱其影響。思想如下：不在每個(gè)柵格中分配具體的概率值，而是在其中記錄其被聲納“發(fā)現(xiàn)”的次數(shù)。每檢測(cè)到一次，賦一個(gè)權(quán)值。實(shí)驗(yàn)中取3（初始值均為0）。比如某柵格被檢測(cè)到3次，那么其CV值則為3x3二9。次數(shù)越多，表明該值的可靠性越高。同時(shí)在算法中，采用CV2來加強(qiáng)合理值的影響。比如某一柵格具有合理CV值3x4=12，CV2值則為144；另一柵格具有噪音CV值3x1=3，CV2值則為9。

7、可以看出，通過CV值來區(qū)分噪音似乎不是太明顯，但是通過CV2來判斷的話,效果就好的多。然后可以通過設(shè)定閾值將噪音濾掉。VFH算法闡述VFH算法5構(gòu)架如圖5-3所示:圖5-3VFH算法構(gòu)架任意時(shí)刻機(jī)器人對(duì)外界環(huán)境的感知范圍是有限的，并取決于所用傳感器的有效測(cè)量范圍。定義某一時(shí)刻機(jī)器人所能感知的最大范圍為活動(dòng)窗口（圖5-4）。它實(shí)際上是以機(jī)器人為圓心，聲納傳感器所測(cè)范圍為半徑的圓形區(qū)域。但在本研究中，為方便算法的使用，將其簡化為邊長為w的正方形區(qū)域。其中，w是聲s納傳感器所能測(cè)的最遠(yuǎn)距離的兩倍。（一）柵格向量化將活動(dòng)窗口內(nèi)的柵格向量化。該向量大小由下式確定:-bd）i,j而其方向取決于柵格與機(jī)器人

8、中心點(diǎn)（VCP）的相對(duì)位置:+yyI,j其中：a,二tan-ij0 xxb是正常數(shù)；ci,jdi,j該柵格到機(jī)器人中心點(diǎn)（VCP）的距離值活動(dòng)窗口內(nèi)柵格Cj）的CV值x;y此刻機(jī)器人中心點(diǎn)（VCP）的絕對(duì)位置坐標(biāo)。00 x;y該柵格的絕對(duì)位置坐標(biāo)ij甘.HarkCV(active.u日1)圖5-4活動(dòng)窗口說明（二）活動(dòng)窗口分區(qū)360。對(duì)于任意區(qū)間若選擇角分辨率a,則分區(qū)后得到的區(qū)間總數(shù)（卩/）丿在本研究中a=5。值的離散性，可能導(dǎo)致障礙密度的過于稀散。因此要對(duì)其進(jìn)行平滑k,(k=0,1,2,n-1),有k=intn=a。其障礙密度h可以由下式得出:kh=丫m。ki,j由于CV處理：h=k（三）

9、確定運(yùn)動(dòng)方向0h+2hHFIh+(/-1hH2h+hkl丨1k112kk+1k11121-1(51)通過式5-1可以得到活動(dòng)窗口中每個(gè)分區(qū)的障礙密度。給定某一閾值5，障礙密度低于該值的區(qū)域，稱為“候選區(qū)”當(dāng)有連續(xù)S（實(shí)驗(yàn)中S=18）個(gè)候TOC o 1-5 h zmaxmax選區(qū)存在時(shí)，稱它們?yōu)椤皩捁取狈駝t稱之為“窄道”將這些連續(xù)候選區(qū)中最左邊的一個(gè)區(qū)記為k，最右邊的一個(gè)區(qū)記為k，則運(yùn)動(dòng)方向可以由下式子得出:0=1（k+k）1r21rVFH+算法闡述VFH+算法是在VFH算法基礎(chǔ)上發(fā)展起來的55它充分考慮了機(jī)器人的大小尺寸對(duì)算法結(jié)果的影響。如圖5-5所示，在VFH+中將柵格放大r,r取決于rr機(jī)

10、器人的尺寸。為了進(jìn)一步加強(qiáng)機(jī)器人運(yùn)行的安全性，還要將機(jī)器人與障礙可以保持不碰撞的最短距離d考慮在內(nèi)。所以對(duì)于任意待研究的柵格其實(shí)際上被放s大了r，r=r+d。TOC o 1-5 h zr+sr+srs這樣，擴(kuò)大角y滿足：y二arcsin卄。對(duì)于任意分區(qū)k，其在極坐標(biāo)下的ijijd障礙密度為：Hp=Ym-h。ijkijij1當(dāng)滿足條件k庭4（3-y,P+y時(shí)h=1；否則，h=0。為了使機(jī)器ijijijiji-ji-j人得到平滑的運(yùn)動(dòng)軌跡，像VFH中那樣使用單一閾值工來決定安全區(qū)域是不夠的。在VFH+中，將采用t與t兩個(gè)閾值。具體操作如下：.Enlaigc.dobstaclezell圖5-5障礙擴(kuò)

11、大示意圖lowhigh若Hpt，則Hb=1;k,ihighk,i若Hpt，則Hb=0；k,ilowk,i其他情況則Hb=Hbk,ik,i1在VFH+算法中，為了動(dòng)態(tài)分析機(jī)器人的運(yùn)動(dòng)，將其軌跡分解成運(yùn)動(dòng)方向不變時(shí)的直線與方向改變時(shí)的弧線。該弧線取決于機(jī)器人的轉(zhuǎn)動(dòng)半徑，與機(jī)器人的速度密切相關(guān)，速度越快，其旋轉(zhuǎn)半徑越大。如圖5-6所示，假設(shè)機(jī)器人向左旋轉(zhuǎn)時(shí)的轉(zhuǎn)向半徑為r，右轉(zhuǎn)時(shí)的轉(zhuǎn)向半徑為r。A，B為兩個(gè)障礙柵格。按上leftright述方法將A,B擴(kuò)大，假定A與機(jī)器人的左轉(zhuǎn)向圓有重疊交叉，那么A與左轉(zhuǎn)向圓覆蓋的所有區(qū)域被認(rèn)為是禁止通行區(qū)（blocked）；B與轉(zhuǎn)向圓無交叉現(xiàn)象所以只有其自身覆蓋的區(qū)

12、域?yàn)榻雇ㄐ袇^(qū)。在圖5-6所示情況下，機(jī)器人將右轉(zhuǎn)。具體算法如下:1)確定轉(zhuǎn)向圓的圓心Ax=r-sin0rrAx二一rsin0iiAy=r-cos0rrAy二一r-cos0ii2)3)計(jì)算障礙柵格C.到兩轉(zhuǎn)向圓心的距離d2=(AX一Ax(j汎+(Ay一Ay0)2d2=(Ax一Ax(j)2+(Ay一AyC)2條件判斷1若若d2(r+r)2,rrr+sd2(r+r)2,i機(jī)器人右方被阻;機(jī)器人左方被阻。r+s通過對(duì)上述條件的對(duì)照比較可以得到兩個(gè)極限角度，分布在機(jī)器人左右兩側(cè)。分別記為*及甲。同時(shí)定義甲=0+兀，表示機(jī)器人當(dāng)前運(yùn)動(dòng)方向的反向。TOC o 1-5 h zirb初始時(shí)刻令*=*=*。對(duì)于

13、活動(dòng)窗口中任意柵格C，在其CV值滿足irbi,jCV1的情況下若P位于*左側(cè)、0右側(cè)時(shí)，令*=p；若p位于0左側(cè)、i,jrri,ji,j*右側(cè)時(shí)，令*=P。這樣，根據(jù)*及*可以得到另一形式的柱狀圖Hmiii,jirk(maskedpolarhistogram)。該柱狀圖表明了機(jī)器人在當(dāng)前速度下的可行方向。若Hb=0且(ktt)e|*,0】I0,*，Hm=0表示該區(qū)域可行；其他情況下，krikHm=1表示該區(qū)域內(nèi)不可行。k通常情況下，我們可以得到若干符合Hm=0的G,*)組合。對(duì)于每個(gè)組合,kri記其左右邊界分別為：k和k。若k和k間包含了S以上個(gè)區(qū)間（S為常量,lrlrmaxmax本實(shí)驗(yàn)中取1

14、0）,則稱該區(qū)域?yàn)椤皩捰颉保环駝t稱之為“窄域”。窄域只提供一個(gè)k豐k候選方向c且c=-r卜，轉(zhuǎn)化為角度后為甲c。而寬域可以提供三個(gè)候nn2nn選方向：c，c以及c。ltS+-ma，轉(zhuǎn)化成角度為申=ac；2rrS-ma，轉(zhuǎn)化成角度為甲=a-c2ll此外，當(dāng)目標(biāo)方向k滿足kGlc,c時(shí)有c=k，轉(zhuǎn)化成角度為甲=ac。ttrltttt為選出最合適的運(yùn)動(dòng)方向c，建立以下代價(jià)函數(shù)：（0）|L1Ac,i+|L1-a丿c=kllgC）=|n-A（c,k）+1t2aCk），其中:3n,i-1A（c,c）=min|c-cI,|c-c-n|,|c-c+n121121212|,是用來計(jì)算兩個(gè)區(qū)間c和c12112絕對(duì)角度差的函數(shù)。比如A（c,k）表示的是候選方向與目標(biāo)方向間的差角，其值t越大，機(jī)器人運(yùn)動(dòng)時(shí)偏離目標(biāo)就越遠(yuǎn)，到達(dá)目的地的代價(jià)也就越高。ac,冬表IaJ示的是候選方向與機(jī)器人行進(jìn)方向間的角度差，該值越大，機(jī)器人轉(zhuǎn)向變化越大。A。k）表示的是當(dāng)前候選方向與前次所選方向間的角度變化，值越大，n,i-1車輪轉(zhuǎn)向變化越大，運(yùn)動(dòng)震蕩越大。所以權(quán)衡系數(shù)卩，卩及卩的選擇至關(guān)重要，它們直接決定了算法的優(yōu)越123性。一般情況下應(yīng)滿足：卩