基于seeroavoved法則的蜂窩協(xié)同避障模型

基于seeroavoved法則的蜂窩協(xié)同避障模型

0研究問題的提出作為微電氣、通信和傳感器技術(shù)的結(jié)合，wsa傳感器網(wǎng)絡(luò)已成為計(jì)算機(jī)和通信領(lǐng)域的研究熱點(diǎn)。傳統(tǒng)的無線傳感器網(wǎng)絡(luò)主要采用固定的傳感節(jié)點(diǎn)收集數(shù)據(jù),無法滿足未來微型、高移動(dòng)的應(yīng)用需求,也無法滿足某些需要移動(dòng)節(jié)點(diǎn)的應(yīng)用,比如監(jiān)測(cè)野生動(dòng)物的活動(dòng)、追蹤病人的心跳情況等,節(jié)點(diǎn)總是處于不斷的運(yùn)動(dòng)中。因而通過增設(shè)一些功能更為強(qiáng)大且可移動(dòng)的節(jié)點(diǎn)構(gòu)成的移動(dòng)傳感網(wǎng)絡(luò)已成為當(dāng)前研究領(lǐng)域的一個(gè)熱點(diǎn),并有著廣闊的應(yīng)用前景?；谝苿?dòng)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)性,使其在目標(biāo)跟蹤方面得到廣泛應(yīng)用。在軍事、環(huán)境、醫(yī)療衛(wèi)生、智能家庭等方面有很大的潛在應(yīng)用價(jià)值,尤其在無人監(jiān)測(cè)或環(huán)境惡劣情況下的事件跟蹤中顯示了很大的優(yōu)勢(shì)。同時(shí),在商業(yè)方面也呈現(xiàn)稱出很好的應(yīng)用前景,如辦公建筑的環(huán)境控制、汽車防盜等。用移動(dòng)傳感器來跟蹤監(jiān)測(cè)移動(dòng)目標(biāo)節(jié)點(diǎn)的一個(gè)主要難題在于這些用于跟蹤監(jiān)測(cè)的傳感器必須在移動(dòng)監(jiān)測(cè)過程中無碰撞,這就要求我們采用群體協(xié)同控制方法。蜂擁控制方法是目前最熱點(diǎn)的協(xié)同跟蹤方法之一,蜂擁是如下的一種現(xiàn)象:眾多傳感器節(jié)點(diǎn)群體移動(dòng)并相互通信的同時(shí)還確保無沖突、速度匹配以及向中心匯聚。然而在未知環(huán)境目標(biāo)跟蹤過程中,遇到一些不明障礙物是不可避免的,如何準(zhǔn)確高效地避開障礙物同時(shí)也成了跟蹤問題的一個(gè)關(guān)鍵所在。然而,在移動(dòng)傳感器節(jié)點(diǎn)跟蹤的實(shí)際應(yīng)用中,節(jié)點(diǎn)所處的工作環(huán)境中,有時(shí)障礙物的形狀大小不一,不僅存在凸形障礙物,凹形障礙物也隨處可遇。由于凹形障礙存在各種巢穴,在目標(biāo)跟蹤過程中,移動(dòng)節(jié)點(diǎn)群很容易陷入凹形巢穴,這樣嚴(yán)重影響跟蹤效率,甚至無法繼續(xù)保持跟蹤而脫離目標(biāo)。針對(duì)上述問題,本文從凹形障礙物的特點(diǎn)出發(fā),對(duì)避障中使用到的SteertoAvoid法則做出改進(jìn),提出一種新的避障模型。該模型在SteertoAvoid的避障過程中使節(jié)點(diǎn)能自行判斷自己所處的凹形障礙環(huán)境,取消目標(biāo)對(duì)節(jié)點(diǎn)群的引力,然后沿著障礙的邊緣不斷搜索,最終找到凹形障礙的出口,最后再恢復(fù)節(jié)點(diǎn)群朝向目標(biāo)的引力,使其適應(yīng)于凹形障礙的環(huán)境中。1基于虛擬者的避障控制在移動(dòng)傳感器網(wǎng)絡(luò)目標(biāo)跟蹤問題的研究中,一個(gè)重要的研究?jī)?nèi)容是如何讓群體達(dá)到協(xié)同,即在跟蹤過程中使節(jié)點(diǎn)間既不碰撞又不分離,且速度處于匹配狀態(tài)。在這個(gè)方面,蜂擁控制模型一直是研究的熱點(diǎn),它具有眾多傳感器在一起移動(dòng)并相互通信的同時(shí)且無沖突、速度匹配以及向中心匯聚的優(yōu)點(diǎn)。近年來,群體蜂擁控制理論在國(guó)內(nèi)外得到了廣泛研究。1986年,Reynolds提出了一個(gè)在三維空間上用計(jì)算機(jī)來模擬群體行為的模型——Reynolds模型,該模型包括基本規(guī)則:1)分離,與鄰域內(nèi)的節(jié)點(diǎn)避免相撞;2)聚合,與鄰域內(nèi)的節(jié)點(diǎn)保持緊湊;3)速度匹配,與鄰域內(nèi)的節(jié)點(diǎn)速度保持一致?；赗eynolds模型,Tanner等考慮了一組具有雙積分特性的群體系統(tǒng),實(shí)現(xiàn)了Reynolds模型中的三種行為規(guī)則。在文獻(xiàn)中主要考慮個(gè)體的鄰域始終保持不變的情況。文獻(xiàn)中則討論了個(gè)體的鄰域隨時(shí)間變化的狀況,也就是只有在個(gè)體一定范圍內(nèi)的節(jié)點(diǎn)才能對(duì)個(gè)體有作用,個(gè)體的輸入控制由這個(gè)鄰域內(nèi)的節(jié)點(diǎn)所決定。文獻(xiàn)的主要工作是將前面的結(jié)果推廣到有多個(gè)靜態(tài)障礙物的環(huán)境中。群體在到達(dá)目標(biāo)點(diǎn)的過程中協(xié)同避開障礙,并在某些情況下分成多個(gè)子組,到了目的點(diǎn)之后又重新聚合。文獻(xiàn)在Tanner模型的基礎(chǔ)上進(jìn)一步加入了“虛擬領(lǐng)導(dǎo)者”的概念,可以將虛擬領(lǐng)導(dǎo)者看成一個(gè)新的控制輸入,它使群體能達(dá)到虛擬領(lǐng)導(dǎo)者所決定的速度,虛擬領(lǐng)導(dǎo)者也能夠避免群體的分裂。雖然蜂擁控制模型完成了群體的協(xié)同跟蹤,但群體在目標(biāo)跟蹤過程中需要避開障礙物,所選的避障方法直接影響了群體在空間中運(yùn)動(dòng)的好壞。目前較受關(guān)注的避障方法是虛擬力避障方法,其主要思想是當(dāng)節(jié)點(diǎn)運(yùn)動(dòng)過程中在自己的感應(yīng)范圍內(nèi)感應(yīng)到障礙時(shí),作用一個(gè)與自己到障礙點(diǎn)方向相反的力于節(jié)點(diǎn)上,使得節(jié)點(diǎn)無法靠近障礙物。這個(gè)力當(dāng)節(jié)點(diǎn)靠近障礙時(shí)趨向于無窮大,這保證了節(jié)點(diǎn)不會(huì)和障礙物發(fā)生碰撞。虛擬力的模型建立非常方便,但由于虛擬力與個(gè)體自身的力所抵消,這只能達(dá)到減速的目的,而沒有采取積極措施進(jìn)行轉(zhuǎn)向判斷,避障效率較低且可能陷入死局。與虛擬力避障法相比,Reynolds提到了SteertoAvoid的避障方法更具優(yōu)勢(shì),這個(gè)避障方法有如下特點(diǎn):1)個(gè)體只考慮在他前進(jìn)方向上正對(duì)著的障礙物。2)在個(gè)體自身的坐標(biāo)系工作,檢測(cè)出障礙物離個(gè)體最近的邊緣。3)得出障礙邊緣的切線方向,作為個(gè)體轉(zhuǎn)向的依據(jù)。SteertoAvoid避障方法讓個(gè)體沿著障礙物的邊緣運(yùn)動(dòng),能讓物體避開障礙物的效率得到很大的提高。以上簡(jiǎn)單介紹了蜂擁控制模型和避障方法,那么針對(duì)在跟蹤過程中避開凹形障礙物的方法,相關(guān)學(xué)者也作了一些研究,目前主要方法有人工勢(shì)場(chǎng)法。勢(shì)場(chǎng)法是一種常見的機(jī)器人路徑規(guī)劃方法,其計(jì)算簡(jiǎn)單、易于實(shí)現(xiàn),因而得到了廣泛的應(yīng)用。該方法通過在運(yùn)動(dòng)空間中引入一種虛擬受力場(chǎng)控制機(jī)器人的運(yùn)動(dòng):目標(biāo)點(diǎn)產(chǎn)生引力勢(shì)場(chǎng),障礙物則產(chǎn)生斥力勢(shì)場(chǎng),在合勢(shì)場(chǎng)的作用下,若節(jié)點(diǎn)沿著勢(shì)場(chǎng)的負(fù)梯度方向運(yùn)動(dòng),將進(jìn)入凹形障礙物內(nèi)部,從而困于局部極小點(diǎn)而無法到達(dá)目標(biāo)。針對(duì)上述存在的缺陷,人們?cè)趯ふ覜]有局部極小點(diǎn)的勢(shì)場(chǎng)方面,做了很多有益的嘗試:文獻(xiàn)提出了基于導(dǎo)航的人工勢(shì)場(chǎng)中關(guān)于局部最小恢復(fù)的虛擬障礙概念,它把基于勢(shì)場(chǎng)的方法與虛擬障礙概念結(jié)合起來,在具有凹形障礙的環(huán)境下,有效地克服了局部極小等問題;但由于研究工作不足,設(shè)置虛擬障礙物大都是啟發(fā)式的,缺乏嚴(yán)格的分析,算法驗(yàn)證也往往只基于仿真結(jié)果。文獻(xiàn)提出了進(jìn)化人工勢(shì)場(chǎng)法,它把遺傳算法與人工勢(shì)場(chǎng)法結(jié)合,推導(dǎo)出具有可調(diào)參數(shù)的最優(yōu)勢(shì)場(chǎng)函數(shù),但由于計(jì)算量過大,導(dǎo)致不適合于實(shí)時(shí)應(yīng)用。另外,在人工勢(shì)場(chǎng)法基礎(chǔ)上加入如最佳優(yōu)先、模擬退火、隨即搜索等搜索策略,尋找勢(shì)場(chǎng)值比當(dāng)前局部極小點(diǎn)更低的逃離點(diǎn),然后繼續(xù)沿著勢(shì)場(chǎng)負(fù)梯度方法運(yùn)動(dòng)直到到達(dá)目標(biāo)點(diǎn)或下一個(gè)局部極小點(diǎn);但在缺少啟發(fā)信息的情況下,搜索方法的效率可能很低。因此,在凹形障礙環(huán)境中應(yīng)用人工勢(shì)場(chǎng)法進(jìn)行避障時(shí),常常以失敗告終。目前對(duì)協(xié)同避障模型只是局限于障礙物為凸形的情況,但是在實(shí)際的情況中,障礙物的形狀是無法預(yù)知的,現(xiàn)有協(xié)同避障模型雖然在凸形障礙物環(huán)境下有著較好的避障效率,但SteertoAvoid的判斷是指向目標(biāo)的,在這個(gè)封閉的空間里,節(jié)點(diǎn)群會(huì)做出多次SteertoAvoid轉(zhuǎn)向判斷。再加上目標(biāo)對(duì)節(jié)點(diǎn)的引力,節(jié)點(diǎn)群的平均速率將會(huì)不斷下降,導(dǎo)致了節(jié)點(diǎn)群陷入了無法繞出障礙的僵局。針對(duì)基于凹形障礙物跟蹤避障,在Tanner蜂擁模型與SteertoAvoid法則基礎(chǔ)上進(jìn)行改進(jìn),提出了一個(gè)基于凹形障礙物的協(xié)同避障方法。在此方法中,將協(xié)同避障模型引入凹形障礙的環(huán)境中,對(duì)現(xiàn)有的模型做出適當(dāng)?shù)母倪M(jìn),在SteertoAvoid的避障過程中取消目標(biāo)對(duì)節(jié)點(diǎn)群的引力,讓節(jié)點(diǎn)群在進(jìn)入凹形后能自行地做出判斷并沿著障礙物的邊緣不斷搜索路徑,最終找到凹形障礙的出口,最后再恢復(fù)節(jié)點(diǎn)群朝向目標(biāo)的引力,保持繼續(xù)跟蹤。2合作避障法的改進(jìn)模型2.1節(jié)點(diǎn)群的變化和速度匹配在一個(gè)平面內(nèi)有N個(gè)自治系統(tǒng),每個(gè)自治系統(tǒng)沒有大小(看成點(diǎn))且質(zhì)量為1。每個(gè)自治系統(tǒng)都裝有傳感器,所以可以把每個(gè)自治系統(tǒng)看成一個(gè)傳感器節(jié)點(diǎn),感應(yīng)其他自治系統(tǒng)在平面中的位置、速度等信息,并假設(shè)感應(yīng)角度為360°,感應(yīng)范圍為圓形。節(jié)點(diǎn)i的運(yùn)動(dòng)滿足下面的兩個(gè)方程:{?ri=vi?vi=ui(1){ri?=vivi?=ui(1)其中,i=1,2,…,N。ri=(xi,yi)T是節(jié)點(diǎn)i的位置向量,vi=(˙xi,˙yi)Τvi=(x˙i,y˙i)T是節(jié)點(diǎn)i的速度向量,且節(jié)點(diǎn)i的速度與全局水平坐標(biāo)軸的夾角定義為tanθi=˙xi/˙yi?ui=(¨xi,¨yi)Τ是節(jié)點(diǎn)的控制輸入(加速度)。rij=ri-rj定義為節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離。可以把控制輸入定義為:ui=αi+βi+γi(2)其中:αi是速度匹配項(xiàng),來實(shí)現(xiàn)Reynolds模型中的速度匹配的目標(biāo);βi是協(xié)同項(xiàng),主要完成節(jié)點(diǎn)之間的碰撞避免和聚集,實(shí)現(xiàn)了Reynolds模型中的前兩個(gè)目標(biāo);γi是虛擬領(lǐng)導(dǎo)項(xiàng),在運(yùn)動(dòng)的過程中能夠產(chǎn)生一個(gè)遠(yuǎn)離障礙的斥力,避免節(jié)點(diǎn)與障礙之間的碰撞,同時(shí)使節(jié)點(diǎn)朝著預(yù)先給定的終點(diǎn)rd=(xd,yd)T運(yùn)動(dòng)。筆者曾對(duì)協(xié)同避障模型做了研究,改進(jìn)了Tanner的協(xié)同避障模型。文獻(xiàn)中只研究了障礙物是靜止正方形的情況,文獻(xiàn)將協(xié)同避障的模型推廣到了移動(dòng)障礙物的環(huán)境下。但是在實(shí)際的情況中,障礙物的形狀是無法預(yù)知的,改進(jìn)的模型雖然在凸形的靜止或移動(dòng)的障礙物環(huán)境下有著較好的避障效率,但在凹形障礙的環(huán)境下卻會(huì)陷入僵局,節(jié)點(diǎn)群會(huì)卡在凹形障礙中。本文將協(xié)同避障模型引入凹形障礙的環(huán)境中,對(duì)現(xiàn)有的模型做出適當(dāng)?shù)母倪M(jìn),讓節(jié)點(diǎn)群在進(jìn)入凹形后能自行地做出判斷并沿著障礙物的邊緣不斷搜索路徑,最終繞出障礙到達(dá)目標(biāo)。2.2節(jié)點(diǎn)的虛擬領(lǐng)導(dǎo)控制鄰域(感應(yīng)范圍):由于節(jié)點(diǎn)只能和自己鄰近的節(jié)點(diǎn)通信,控制輸入也主要通過這些信息獲得。令Ni為節(jié)點(diǎn)i的鄰域中的節(jié)點(diǎn)集(不包括i本身)。Ni?{j︱‖rij‖≤R}?{1,2,…,N}(3)其中R是節(jié)點(diǎn)的感應(yīng)半徑。由于節(jié)點(diǎn)是運(yùn)動(dòng)的,每個(gè)節(jié)點(diǎn)之間的距離是不斷變化的,這導(dǎo)致了每個(gè)節(jié)點(diǎn)的鄰域也是不斷變化的。速度匹配項(xiàng)αi:目標(biāo)是使節(jié)點(diǎn)i與鄰域內(nèi)其他節(jié)點(diǎn)的速度不斷接近,直到所有節(jié)點(diǎn)速度相等。節(jié)點(diǎn)i和其鄰域內(nèi)所有速度向量相減,然后將這些差值疊加,得到一個(gè)綜合的控制輸入:αi=-∑j?Νi(vi-vj)(4)協(xié)同項(xiàng)βi:該控制輸入的作用是使節(jié)點(diǎn)間距離太近時(shí)避免碰撞(斥力),節(jié)點(diǎn)間距離太遠(yuǎn)時(shí)又相互吸引(引力),超出感應(yīng)半徑R后不存在任何力的作用。鄰域內(nèi)的所有節(jié)點(diǎn)對(duì)節(jié)點(diǎn)i造成的控制輸入的總和構(gòu)成了控制輸入βi。令i的鄰域內(nèi)的j節(jié)點(diǎn)對(duì)i節(jié)點(diǎn)造成的避障聚合控制輸入為Vij?？啥xVij為:Vij={(rij-r)n,0<∥rij∥≤R0,∥rij∥>R(5)其中n=1,3,5,…,2k+1。在這一項(xiàng)的作用下,節(jié)點(diǎn)和節(jié)點(diǎn)間的距離會(huì)趨向于一個(gè)穩(wěn)定值r。n為一個(gè)正的奇數(shù),可以根據(jù)實(shí)際情況來設(shè)置。則可以得到協(xié)同項(xiàng)βi為:βi=-Ν∑j=1,j≠iVij(6)虛擬領(lǐng)導(dǎo)項(xiàng)γi:該項(xiàng)保證節(jié)點(diǎn)在避開障礙的情況下同時(shí)朝著預(yù)先給定的目標(biāo)點(diǎn)運(yùn)動(dòng)。對(duì)于節(jié)點(diǎn)的運(yùn)動(dòng)分情況討論:當(dāng)節(jié)點(diǎn)在自己的感應(yīng)范圍內(nèi)檢測(cè)不到障礙物時(shí),該項(xiàng)提供一個(gè)恒定的朝向目標(biāo)的引力Ui=Ud,使節(jié)點(diǎn)能夠朝著目標(biāo)運(yùn)動(dòng)。但是節(jié)點(diǎn)的速度不能無限地增加,會(huì)增加碰撞障礙的幾率。當(dāng)節(jié)點(diǎn)速度到達(dá)某個(gè)最大值時(shí)vmax,取消這一項(xiàng)的作用,當(dāng)節(jié)點(diǎn)離目標(biāo)非常近后‖rid‖<rmin,也取消這個(gè)引力,讓節(jié)點(diǎn)能在目標(biāo)處停下來;當(dāng)在感應(yīng)范圍內(nèi)檢測(cè)到障礙物時(shí),先取消這個(gè)引力,取障礙物離節(jié)點(diǎn)最近的一點(diǎn)ro,施加一個(gè)與節(jié)點(diǎn)連線方向上的斥力Ui:Ui=-Uo/(‖rio‖)m(7)其中:Uo為一個(gè)恒值,m是一個(gè)正整數(shù)(按實(shí)際情況設(shè)置)。當(dāng)節(jié)點(diǎn)與障礙離得非常近時(shí),該項(xiàng)提供一個(gè)非常大的斥力,則節(jié)點(diǎn)的虛擬領(lǐng)導(dǎo)控制輸入γi=Ui。綜上所述,節(jié)點(diǎn)i總的控制輸入ui可以確定為:ui={-∑j?Νi(vi-vj)-∑j?ΝiVij-Ui-kvi,∥rid∥<rmin-∑j?Νi(vi-vj)-∑j?ΝiVij-Ui,其他(8)其中:當(dāng)節(jié)點(diǎn)與目標(biāo)點(diǎn)的距離小于一個(gè)定值以后,可以看作節(jié)點(diǎn)已經(jīng)到達(dá)目標(biāo),這時(shí)節(jié)點(diǎn)的速度應(yīng)該下降,最終能在目標(biāo)旁停止下來。所以當(dāng)‖rid‖<rmin時(shí),為ui添加阻尼項(xiàng)-kvi。Tanner的模型雖然實(shí)現(xiàn)了Reynolds的蜂擁控制模型,但是其在避障上的缺陷還比較大,需要引入一種有效的避障方法。SteertoAvoid的避障方法能讓節(jié)點(diǎn)在遇到障礙后沿著障礙的切線方向運(yùn)動(dòng),明顯提高了避障的效率。將SteertoAvoid算法運(yùn)用到避障中,在傳感器節(jié)點(diǎn)檢測(cè)到障礙的同時(shí),計(jì)算節(jié)點(diǎn)速度方向直線與障礙邊緣的交點(diǎn)的切線,作為節(jié)點(diǎn)轉(zhuǎn)向的依據(jù)。切線是有兩個(gè)方向的,必須要選擇其中一個(gè)方向來轉(zhuǎn)向?？梢韵热我膺x擇一個(gè)方向,角度記為σi(角度的大小都是相對(duì)于水平方向的)。將節(jié)點(diǎn)與目標(biāo)點(diǎn)相連接,這條直線的角度記為ξi,這條直線勢(shì)必與該切線相交。ξi=arctan((yi-yd)/(xi-xd))(9)由于切線方向?yàn)檗D(zhuǎn)向后的速度方向,在選擇節(jié)點(diǎn)的轉(zhuǎn)向的方向時(shí),需要選擇能盡快到達(dá)目標(biāo)的方向。若當(dāng)前選擇的方向σi假定為轉(zhuǎn)向后的速度方向,將該速度投影到節(jié)點(diǎn)i與目標(biāo)的連線上,可以得到一個(gè)朝向目標(biāo)的速度分量。將以上兩條直線的角度相減,若得到的結(jié)果小于等于π/2時(shí),該投影的速度分量是指向目標(biāo)的,也就是速度方向是趨向于接近目標(biāo)的,所以取σi為轉(zhuǎn)向方向。如果兩個(gè)角度相減得結(jié)果為鈍角,則將σi減去π,然后將其作為轉(zhuǎn)向角度。最后得到的轉(zhuǎn)向角記為φi。如圖2所示。φi的選擇可以描述為:φi={σi,|σi-ξi|≤π/2σi-π,其他(10)在遇到障礙物的情況下,速度要能很快地改變?yōu)榍芯€方向,否則可能因?yàn)樗俣忍蠖采险系K。所以,在障礙物下的SteertoAvoid避障方法的速度改變應(yīng)該是瞬時(shí)的,速度方向瞬間從θi改變?yōu)棣読。可以把SteertoAvoid引入節(jié)點(diǎn)的跟蹤過程中。在沒有檢測(cè)到障礙物的情況下,現(xiàn)在的模型只單獨(dú)使用一個(gè)朝向目標(biāo)的控制輸入來吸引節(jié)點(diǎn)朝目標(biāo)運(yùn)動(dòng),速度方向的變化非常緩慢,使得追蹤目標(biāo)的效率明顯下降。這里,將SteertoAvoid的避障方法同樣引入節(jié)點(diǎn)的跟蹤過程中,使得節(jié)點(diǎn)能夠更快,走更優(yōu)化路徑到達(dá)目標(biāo)點(diǎn)。當(dāng)節(jié)點(diǎn)在感應(yīng)范圍內(nèi)檢測(cè)不到障礙時(shí)(障礙的最近點(diǎn)在感應(yīng)范圍之外),節(jié)點(diǎn)會(huì)以自身與目標(biāo)點(diǎn)的連線方向作為轉(zhuǎn)向的方向。記為ηi。在跟蹤目標(biāo)的SteertoAvoid中,速度應(yīng)該平滑地改變。這里定義一個(gè)恒定的角速度ω,速度方向以角速ω從θi平滑地轉(zhuǎn)變?yōu)棣莍。這一個(gè)轉(zhuǎn)向法則和虛擬領(lǐng)導(dǎo)控制項(xiàng)共同作用于節(jié)點(diǎn),使得節(jié)點(diǎn)能更優(yōu)化地朝著目標(biāo)運(yùn)動(dòng)。將SteertoAvoid的法則加入?yún)f(xié)同避障模型中,使得節(jié)點(diǎn)群在避開障礙和追蹤節(jié)點(diǎn)中的效率明顯提高。另外,在避障的過程中,可能會(huì)有某些節(jié)點(diǎn)自身沒有檢測(cè)到障礙物,此時(shí)該節(jié)點(diǎn)的轉(zhuǎn)向角度為null,但其鄰域內(nèi)已經(jīng)有節(jié)點(diǎn)做出了轉(zhuǎn)向的決定,那么該節(jié)點(diǎn)可以根據(jù)鄰域內(nèi)其他節(jié)點(diǎn)的轉(zhuǎn)向角做出轉(zhuǎn)向的決定。這可以在沒有遇到障礙前就做出轉(zhuǎn)向的決定,進(jìn)一步提高了群體轉(zhuǎn)向的效率。節(jié)點(diǎn)在做出轉(zhuǎn)向的決定前,首先要看自己是否能檢測(cè)到障礙物,如果能檢測(cè)到障礙物并能根據(jù)SteertoAvoid避障方法來計(jì)算出轉(zhuǎn)向角,則忽略鄰域內(nèi)其他節(jié)點(diǎn)的轉(zhuǎn)向。若節(jié)點(diǎn)不能檢測(cè)到障礙物,則檢查鄰域內(nèi)所有節(jié)點(diǎn)的轉(zhuǎn)向角,并求出所有轉(zhuǎn)向角的平均角度,將該角度作為節(jié)點(diǎn)的轉(zhuǎn)向角?？梢悦枋鰹?φi=∑j∈Νiφj/n;j∈Ni,φi=null,φj≠null(11)其中鄰域內(nèi)有n個(gè)節(jié)點(diǎn)的轉(zhuǎn)向角度不為null。現(xiàn)有的模型在改進(jìn)Tanner的協(xié)同避障模型的基礎(chǔ)上加入SteertoAvoid的避障和追蹤目標(biāo)點(diǎn)的法則,能夠避開環(huán)境中的凸形障礙物,且保證了一個(gè)較高的避障效率。但是在實(shí)際環(huán)境中,傳感器節(jié)點(diǎn)群的運(yùn)動(dòng)環(huán)境總是很復(fù)雜的,不僅僅存在著靜止或者移動(dòng)的凸形障礙,同樣存在著各種凹形障礙。現(xiàn)有的模型在遇到凹形障礙時(shí),由于節(jié)點(diǎn)群感應(yīng)范圍的限制,一開始并不能檢測(cè)出凹形障礙并做出轉(zhuǎn)向判斷。以下的改進(jìn)從凹形障礙物的特點(diǎn)出發(fā),在SteertoAvoid的避障過程中取消目標(biāo)對(duì)節(jié)點(diǎn)群的引力,然后沿著障礙的邊緣不斷搜索,最終找到凹形障礙的出口,最后再恢復(fù)節(jié)點(diǎn)群朝向目標(biāo)的引力。如同2.2節(jié)中提到的,節(jié)點(diǎn)群是沒辦法在走入凹形障礙之前做出轉(zhuǎn)向判斷的。如圖4所示,在節(jié)點(diǎn)群看來,前方并沒有任何障礙,節(jié)點(diǎn)群會(huì)不知情地走入凹形障礙之中。在檢測(cè)到障礙之后,節(jié)點(diǎn)仍然使用SteertoAvoid避障法則來避開障礙,根據(jù)前面的模型,SteertoAvoid的判斷是指向目標(biāo)的,在這個(gè)封閉的空間里,節(jié)點(diǎn)群會(huì)做出多次SteertoAvoid轉(zhuǎn)向判斷。再加上目標(biāo)對(duì)節(jié)點(diǎn)的引力,節(jié)點(diǎn)群的平均速率將會(huì)不斷下降,導(dǎo)致了節(jié)點(diǎn)群陷入了無法繞出障礙的僵局。針對(duì)這種缺陷,我們要對(duì)前文提出來的模型加以改進(jìn)。當(dāng)節(jié)點(diǎn)群遇到一個(gè)障礙物時(shí),局部的信息并不能讓節(jié)點(diǎn)群做出最優(yōu)的判斷。不論是凹形還是凸形的障礙,第一次的SteertoAvoid避障判斷對(duì)于節(jié)點(diǎn)群來講,都是一樣的。對(duì)于凸形的障礙,朝向目標(biāo)的牽引力在SteertoAvoid避障的過程中能使節(jié)點(diǎn)緊貼在障礙旁邊而不至于被障礙彈開(彈開后,節(jié)點(diǎn)群檢測(cè)不到障礙物,運(yùn)動(dòng)會(huì)恢復(fù)到導(dǎo)向的SteertoAvoid);對(duì)于凹形障礙,朝向目標(biāo)的牽引力會(huì)干擾節(jié)點(diǎn)群之后的路徑搜索。所以,在節(jié)點(diǎn)SteertoAvoid避障的過程中,取消這個(gè)對(duì)目標(biāo)的吸引力。為了保證節(jié)點(diǎn)群不會(huì)被障礙彈開,增加一個(gè)朝向障礙的引力Ui′:Ui′={Uo′∥rio∥,0<∥rio∥≤R0,∥rio∥>R(12)其中:Uo′是一個(gè)定值,根據(jù)實(shí)際情況設(shè)置。rio是障礙O上離節(jié)點(diǎn)i最近的點(diǎn)距離,這一項(xiàng)和式(7)共同作用在節(jié)點(diǎn)避障的過程中,保證了節(jié)點(diǎn)能夠沿著障礙的邊緣運(yùn)動(dòng),并能在感應(yīng)范圍中檢測(cè)到障礙物。雖然節(jié)點(diǎn)群能組成一個(gè)較大的感應(yīng)范圍,但是畢竟節(jié)點(diǎn)群也只能接收到障礙物的局部信息。所以,在SteertoAvoid判斷之后,要能使節(jié)點(diǎn)沿著障礙的邊緣尋找路徑,而不被目標(biāo)影響。上文在SteertoAvoid避障判斷的過程中,節(jié)點(diǎn)首先計(jì)算出切線的兩個(gè)方向,然后按照與節(jié)點(diǎn)目標(biāo)連線較小的夾角較小的方向來進(jìn)行轉(zhuǎn)向,這種方法在凸形障礙的環(huán)境下有著較好的避障效果。但是,當(dāng)節(jié)點(diǎn)群進(jìn)入凹形障礙以后,仍然使用這種指向目標(biāo)優(yōu)先的方法就會(huì)使節(jié)點(diǎn)陷入凹形之中無法脫身。這里對(duì)避障中使用到的SteertoAvoid法則做出改進(jìn),使其適應(yīng)于凹形障礙的環(huán)境中,沿著障礙的邊緣搜索,并最終繞出障礙。在SteertoAvoid避障法則得到兩個(gè)切線的角度時(shí)(式(10)中為σi與σi-π),此時(shí)要選擇一個(gè)切線方向來避開障礙,根據(jù)節(jié)點(diǎn)能夠感應(yīng)到的障礙的局部信息,可以分為以下3種情況。1條線是否與感應(yīng)范圍內(nèi)的障礙有點(diǎn)基本概念由于切線在感應(yīng)范圍的邊緣,無法方便節(jié)點(diǎn)得到局部信息,這里將切線平移到節(jié)點(diǎn)i和切點(diǎn)o的中點(diǎn)處,來檢測(cè)這條線是否與感應(yīng)范圍內(nèi)的障礙有交點(diǎn)。如圖5所示,由于節(jié)點(diǎn)在此時(shí)沒有辦法判斷這個(gè)障礙物是否為凹形,仍然使用式(10)的優(yōu)先目標(biāo)方向的SteertoAvoid避障法則?？梢杂檬?13)得到這條切線l的方程,其中yo、xo是速度方向與障礙的切點(diǎn)坐標(biāo):Y-(yi-yo)2=σi(X-(xi-xo)2)(13)2不走重復(fù)路徑如圖6所示,節(jié)點(diǎn)就能夠判斷自己是處在了凹形障礙之中了。為了不走重復(fù)路徑,并讓節(jié)點(diǎn)繼續(xù)沿著障礙邊緣的搜索,忽略節(jié)點(diǎn)指向目標(biāo)的SteertoAvoid判斷。這里切線l與感應(yīng)范圍內(nèi)的障礙邊緣只有一個(gè)交點(diǎn),選擇前方?jīng)]有障礙物的切線方向轉(zhuǎn)向。3節(jié)點(diǎn)的指向目標(biāo)引力如圖7所示,不論節(jié)點(diǎn)選擇哪個(gè)方向都不能繞開障礙。同樣忽略指向目標(biāo)的SteertoAvoid判斷。這里切線l與感應(yīng)范圍內(nèi)的障礙物邊緣有兩個(gè)交點(diǎn)。此時(shí)將節(jié)點(diǎn)的速度反向,使節(jié)點(diǎn)退出凹形障礙。最終的轉(zhuǎn)向方向φi可以描述為:φi={σi,切線l僅在σi-π方向與障礙邊緣相交或切線l與障礙邊緣無交點(diǎn)且|σi-ξi|≤π/2σi-π,切線l僅在σi方向與障礙邊緣相交或切線l與障礙邊緣無交點(diǎn)且|σi-ξi|>π/2θi-π,切線l與障礙邊緣有兩個(gè)交點(diǎn)(14)其中θi是節(jié)點(diǎn)在SteertoAvoid前的速度方向。在最后確定了節(jié)點(diǎn)的轉(zhuǎn)向角度后,可以根據(jù)式(15)將速度向量改變?yōu)?{vx=cosφi√(v2x+v2y)vy=sinφi√(v2x+v2y)(15)通過以上的方法,節(jié)點(diǎn)能通過改進(jìn)的SteertoAvoid避障方法不斷沿著凹形障礙的邊緣來搜索出路。而相互作用的障礙物的斥力和引力能讓節(jié)點(diǎn)貼著障礙的邊緣運(yùn)動(dòng)。當(dāng)節(jié)點(diǎn)走出了凹形障礙時(shí)(節(jié)點(diǎn)檢測(cè)不到障礙物),為了不讓節(jié)點(diǎn)再次陷入凹形障礙,記錄離開障礙前最后一刻的Ui′的大小和方向,讓其再作用一個(gè)Δt的時(shí)間,使節(jié)點(diǎn)徹底走出障礙,Δt與節(jié)點(diǎn)的速度有關(guān),可以描述為:Δti=T/|vi|(16)其中T為定值,根據(jù)實(shí)際情況設(shè)置。當(dāng)節(jié)點(diǎn)速度快時(shí),Ui′維持較短的時(shí)間;當(dāng)節(jié)點(diǎn)速度慢,Ui′維持較長(zhǎng)的時(shí)間。在最終繞開凹形障礙后(Δt時(shí)間后),恢復(fù)節(jié)點(diǎn)的朝向目標(biāo)的引力,使用導(dǎo)向中的SteertoAvoid法則繼續(xù)追蹤目標(biāo)。通過以上的模型,傳感器節(jié)點(diǎn)群能夠組成一個(gè)穩(wěn)定的群體朝著目標(biāo)運(yùn)動(dòng)。運(yùn)動(dòng)中有一個(gè)持續(xù)朝著目標(biāo)的引力,同時(shí)使用了轉(zhuǎn)向中的SteertoAvoid來導(dǎo)航節(jié)點(diǎn)群。運(yùn)動(dòng)中碰到障礙物時(shí),取消朝向目標(biāo)的引力,通過SteertoAvoid避障方法讓節(jié)點(diǎn)沿著障礙物切線的方向運(yùn)動(dòng),提高避障效率。而當(dāng)切線方向也檢測(cè)到障礙時(shí),節(jié)點(diǎn)就能判斷自己已經(jīng)陷入了凹形障礙,節(jié)點(diǎn)能將自己的速度調(diào)整到一個(gè)合理的方向上,沿著障礙的邊緣搜索出口,并最終繞出凹形的障礙。3節(jié)點(diǎn)群目標(biāo)的距離變化第2章描述了針對(duì)凹形障礙的協(xié)同避障模型,仿真實(shí)驗(yàn)將對(duì)該模型在凹形障礙下的應(yīng)用進(jìn)行模擬,驗(yàn)證模型的有效性和穩(wěn)定性。并對(duì)Tanner的蜂擁控制模型和筆者曾提出的協(xié)同避障模型進(jìn)行對(duì)比分析。仿真的檢測(cè)范圍為橫軸1800、縱軸900的長(zhǎng)方形區(qū)域。在橫軸0到100,縱軸450到550的范圍內(nèi)初始10個(gè)傳感器節(jié)點(diǎn)。所有節(jié)點(diǎn)的初始速度大小方向?yàn)槿我庵?初始控制輸入為零。環(huán)境中設(shè)置一個(gè)凹形的線形障礙,由三根線段(x=1000,300≤y≤700;y=300,600≤x≤1000;y=700,600≤x≤1000)組成。目標(biāo)點(diǎn)的坐標(biāo)為[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]。環(huán)境中的傳感器節(jié)點(diǎn)群會(huì)協(xié)同地朝著目標(biāo)前進(jìn),并嘗試避開環(huán)境中的凹形障礙物。本文用以下的幾個(gè)指標(biāo)來衡量協(xié)同避障模型在凹形障礙環(huán)境下的優(yōu)劣:1)是否可以繞出凹形障礙:所使用的模型必須要能繞出凹形障礙,從而達(dá)到目標(biāo)追蹤的目的。2)節(jié)點(diǎn)群的平均速率變化曲線:速率變化曲線清晰地記錄了節(jié)點(diǎn)群在運(yùn)動(dòng)過程中的速率變化情況,可以用來衡量模型的避障效率。3)到達(dá)目標(biāo)所需的時(shí)間:若點(diǎn)群最終能夠到達(dá)目標(biāo),所用時(shí)間較短的模型較優(yōu)。4)節(jié)點(diǎn)與目標(biāo)的平均距離變化:該曲線能夠判斷節(jié)點(diǎn)群是否朝向目標(biāo)運(yùn)動(dòng),最終是否能夠到達(dá)目標(biāo)。在使用Tanner的蜂擁控制模型來避開凹形障礙時(shí),可以得到如圖8所示的仿真圖像。從圖8可以看到,Tanner的蜂擁控制模型在節(jié)點(diǎn)群碰到障礙時(shí)只給節(jié)點(diǎn)施加了一個(gè)斥力,使節(jié)點(diǎn)群從障礙旁彈開。節(jié)點(diǎn)群在凹形障礙內(nèi)經(jīng)過了右邊緣和下邊緣的兩次反彈,最后離開了凹形障礙。彈開后使節(jié)點(diǎn)速度方向再次朝向目標(biāo)點(diǎn)是需要一個(gè)過程的,而且很可能再次進(jìn)入凹形障礙中,這樣使節(jié)點(diǎn)群的目標(biāo)追蹤陷入了死循環(huán),永遠(yuǎn)無法到達(dá)目標(biāo)點(diǎn)。節(jié)點(diǎn)群在運(yùn)動(dòng)中的速率變化如圖9所示,圖中橫軸表示的是節(jié)點(diǎn)運(yùn)動(dòng)的時(shí)間,縱軸表示的是10個(gè)節(jié)點(diǎn)的平均速率?？梢钥吹皆谡系K彈開節(jié)點(diǎn)的過程中的速率損耗較大,而使速度方向再次朝向目標(biāo)也需要大幅度地減速,在150s后節(jié)點(diǎn)群仍然沒有到達(dá)目標(biāo)。筆者曾經(jīng)對(duì)Tanner的模型做出了改進(jìn),加入了SteertoAvoid轉(zhuǎn)向判斷,且能在凸型障礙中保證較高的避障效率。將該模型應(yīng)用到凹形障礙的環(huán)境中,可以得到的仿真圖像如圖10所示。從SteertoAvoid的模型得出,所有轉(zhuǎn)向的判斷都是優(yōu)先于目標(biāo)的點(diǎn)方向的。進(jìn)入障礙后,節(jié)點(diǎn)群會(huì)做出多次轉(zhuǎn)向判斷,但是每一次的判斷都不能讓節(jié)點(diǎn)群繞開障礙,節(jié)點(diǎn)最終陷入了僵局。節(jié)點(diǎn)群在運(yùn)動(dòng)中的速率變化如圖11所示,可以看到節(jié)點(diǎn)群在障礙中不斷地做出轉(zhuǎn)向判斷,卻無法繞出凹形障