張美燕,蔡文郁,周莉萍

(1.浙江水利水電學(xué)院 電氣工程系,杭州 310018;2.杭州電子科技大學(xué)電子信息學(xué)院,杭州 310018)

項目來源:浙江省自然科學(xué)基金項目(LY18F030006,LY15F030018,Y18F030025);國家自然科學(xué)基金項目(6170060208)

2017-03-27修改日期2017-06-09

基于二次Bezier曲線的無線傳感網(wǎng)避障路徑規(guī)劃研究*

張美燕1,蔡文郁2*,周莉萍1

(1.浙江水利水電學(xué)院 電氣工程系,杭州 310018;2.杭州電子科技大學(xué)電子信息學(xué)院,杭州 310018)

用固定Sink節(jié)點進行無線傳感網(wǎng)內(nèi)數(shù)據(jù)采集的傳統(tǒng)方式會導(dǎo)致熱點區(qū)域(hot spot)問題,而采用移動Sink節(jié)點進行數(shù)據(jù)采集可以克服這個問題,從而達到均衡網(wǎng)絡(luò)能量分布與延長網(wǎng)絡(luò)生命周期的效果。本文針對類車型機器人作為無線傳感網(wǎng)中移動數(shù)據(jù)匯聚節(jié)點的應(yīng)用場景,提出了一種基于Bezier連續(xù)曲線的移動Sink節(jié)點避障路徑規(guī)劃算法。本文構(gòu)建了連續(xù)分段Bezier曲線為巡航軌跡,采用人工勢場中的斥力場理論實現(xiàn)對多個障礙物的智能躲避,動態(tài)調(diào)節(jié)二次Bezier曲線的內(nèi)部控制點位置,將障礙物排斥在二次Bezier曲線之外。仿真結(jié)果驗證本文提出的算法可以實現(xiàn)移動Sink節(jié)點規(guī)劃路徑的避障功能,同時Bezier曲線規(guī)劃算法簡單,計算量較小。

無線傳感器網(wǎng)絡(luò);Bezier曲線;路徑規(guī)劃;障礙避免

通過合理規(guī)劃移動Sink節(jié)點的運動路徑以實現(xiàn)無線傳感器網(wǎng)絡(luò)中多傳感器節(jié)點的數(shù)據(jù)收集是目前的一大研究熱點[1-2]。無線傳感器網(wǎng)絡(luò)的避障路徑規(guī)劃問題是指:在具有多個凸形障礙物的無線傳感器網(wǎng)絡(luò)配置空間(Configuration Space)中,按照設(shè)定的路徑優(yōu)化目標,尋找一條能夠遍歷所有傳感器節(jié)點的無碰撞路徑[3]。傳統(tǒng)的避障路徑規(guī)劃中往往不考慮路徑的曲率連續(xù)性,只考慮了最小時間、最短巡航距離或最少能量消耗等原則,從而找到一條最優(yōu)解或次優(yōu)解,因此獲得的路徑是一連串由直線段構(gòu)成的避障路線。由于非連續(xù)運動曲線對于車型機器人的運動方向造成突變,不利于機器人保持平穩(wěn)的運動速度和能量消耗。為了使車輛型機器人行駛路線平滑,不存在拐點,整體軌跡應(yīng)由分段連續(xù)曲線構(gòu)成[4]。為滿足以上的幾個特征,Bezier曲線[5]利用了曲線的切矢量性,即Bezier曲線的起點和終點處的切線方向和控制點多邊形的第1條邊及最后一條邊的走向一致,這對于類車型機器人,通過Bezier曲線模型構(gòu)造的運動軌跡,非常符合類車型機器人的動力學(xué)特征。

目前已有一些研究采用了Bezier和B-Spline等樣條曲線對避障路徑規(guī)劃問題和連續(xù)性路徑規(guī)劃問題進行了研究。文獻[6]提出了一種基于多段線方式的避障曲線,然后利用三次樣條曲線簡化實現(xiàn);文獻[7-8]提出了一種基于有理三次樣條曲線的避障路徑規(guī)劃技術(shù);文獻[9]提出了一種利用Bezier曲線描述路徑與改進粒子群優(yōu)化算法相結(jié)合的路徑規(guī)劃方法;文獻[10]提出了一種既能使曲線規(guī)避所有障礙物,又能使曲線在整體上保持G2連續(xù)的低次避障代數(shù)樣條曲線;文獻[11]提出通過遺傳算法再結(jié)合B樣條曲線規(guī)劃出平滑的避障路徑的方法。除此之外,文獻[12-14]研究了存在多個移動機器人情況下如何實現(xiàn)路徑規(guī)劃與協(xié)作避障的方法。上述研究成果都對機器人移動路徑規(guī)劃問題的某些方面做了深入研究,但是有些文獻提出的曲線構(gòu)造算法過于復(fù)雜,需要求解高次方程,有些研究采用了遺傳算法等啟發(fā)式優(yōu)化算法,計算復(fù)雜度過高。

除此之外,在實際的無線傳感器網(wǎng)絡(luò)中,移動Sink節(jié)點進行數(shù)據(jù)收集往往需要一段時間,因此一般會在采集傳感器節(jié)點附近停留,完成數(shù)據(jù)采集后再按路徑向下一個傳感器節(jié)點行駛。但是行駛過程中運動方向突變對減速齒輪的傷害和會減速打滑而帶來的位置誤差,因此只需要在分段曲線內(nèi)滿足較高連續(xù)性即可,這樣可以極大地降低路徑計算復(fù)雜度。

本文結(jié)合了分段連續(xù)二次Bezier曲線和人工勢場算法,實現(xiàn)了一種基于連續(xù)二次Bezier曲線的避障路徑規(guī)劃方法,從而避免由于障礙物存在導(dǎo)致移動失效的情況,為無線傳感器網(wǎng)絡(luò)中移動Sink節(jié)點的高效數(shù)據(jù)采集提供了保證。

1 問題描述

假設(shè)無線傳感器網(wǎng)絡(luò)區(qū)域內(nèi)隨機分布了S個傳感器節(jié)點Ni(i=1,2,…,S),其坐標為(xi,yi)(i=1,2,…,S)和Q個凸形障礙物Oj(j=1,2,…,Q),其坐標為(xj,yj)(j=1,2,…,Q),1個移動Sink機器人沿著預(yù)定的軌跡移動,按序采集每個傳感器節(jié)點的傳感數(shù)據(jù),如圖1所示。本文研究的優(yōu)化問題如下:假設(shè)移動Sink節(jié)點沿著預(yù)定的路徑對各個傳感器節(jié)點進行數(shù)據(jù)采集,且該路徑具有避開障礙物的功能。優(yōu)化目標為尋找一條巡航總距離最短的避障閉合曲線來遍歷所有的傳感器節(jié)點,該曲線滿足曲率連續(xù)的約束條件。數(shù)學(xué)模型如下所示:

(1)

(2)

(3)

圖1 避障路徑規(guī)劃示意圖

Bezier曲線的形狀由通過一組多邊折線(控制點多邊形)的各頂點定義,只有第1個頂點和最后一個頂點在曲線上,其余的頂點用于定義曲線的導(dǎo)數(shù)、階次和形狀,第1條邊和最后一條邊則表示了曲線在兩端點處的切線方向。其數(shù)學(xué)表達式由多項式混合函數(shù)推導(dǎo),如下所示:

(4)

式中:Pi為曲線各個控制點的位置向量,順序連接從P0到Pn的折線被稱為Bezier曲線的控制多邊形,Bn,i(u)為伯恩斯坦基多項式,定義如下:

(5)

由于三次Bezier曲線計算量比二次Bezier更多更復(fù)雜,因此本文將只采用二次Bezier曲線作為相鄰傳感器節(jié)點之間巡航的路徑曲線。由于式(1)～(3)所提出的最優(yōu)化模型需要多階曲線來規(guī)劃,計算復(fù)雜度較大,本文采用的Bezier曲線規(guī)劃較為簡單,屬于一種次優(yōu)解。

由于Bezier曲線的長度計算公式如式(6)所示,無法直接進行積分運算,只能粗略獲取Bezier曲線長度的限值。文獻[15]提出了計算曲線長度的近似式(7),為了簡單起見,本文也以此作為Bezier曲線長度計算的公式,所以對于二次Bezier曲線而言,Bezier距離計算可以等價于首位控制點的歐式距離。

(6)

(7)

2 基于二次Bezier曲線的避障路徑規(guī)劃算法

對于一般類車型機器人,滿足C2連續(xù)的移動路徑已經(jīng)足夠滿足巡航速度和動力性需求,關(guān)于Bezier曲線的連續(xù)性如下定義:

定義1C(u)滿足C2連續(xù)的充要條件,C″(u1)=C″(u2) (u1≠u2),即要求曲線二階導(dǎo)數(shù)連續(xù)。

Bezier曲線的導(dǎo)數(shù)定義為:

(8)

定義2f1和f2滿足G0連續(xù)的充要條件:f1(1)=f2(0)。即f1的終點與f2的起點重合,但是曲線在連接點處不能保證是光滑連接。

根據(jù)Bezier曲線的基本性質(zhì),可以推導(dǎo)出以下定理,這些定理可以用于本文的避障路徑規(guī)劃算法:

定理1當且僅當障礙物在控制點多邊形內(nèi)部時,才需要調(diào)節(jié)內(nèi)部控制點的位置實現(xiàn)避障。

證明由Bezier曲線的凸包性可知,Bezier曲線全段位于由控制點構(gòu)成的閉合凸包內(nèi),因此,如果當障礙物在控制點多邊形外部時,Bezier曲線不會與障礙物發(fā)生碰撞。當且僅當障礙物在控制點多邊形內(nèi)部時,才需要調(diào)節(jié)Bezier曲線形態(tài),實現(xiàn)避障。

定理2障礙物是否處于控制點多邊形內(nèi)部的判斷條件必須滿足:

證明控制點三角形ΔP0P1P2內(nèi)部的任意一點P(α,β)都可以表示如下:

選取慢性心力衰竭合并2型糖尿病患者74例作為研究對象，將其隨機分為替米沙坦組和雷米普利組，各37例，比較兩組慢性心力衰竭治療效果、空腹血糖水平、胰島素水平及不良反應(yīng)發(fā)生率。入院時，患者均符合美國心臟病協(xié)會制定的關(guān)于慢性心力衰竭的診斷標準，1999年WHO制定的關(guān)于2型糖尿病的診斷標準，空腹血清C肽平均指數(shù)為（2.61±0.21）nmol/L，排除免疫系統(tǒng)疾病者、血液系統(tǒng)疾病者、精神疾病者等，其中，替米沙坦組女12例，男25例，平均年齡（36.92±2.14）歲；雷米普利組女11例，男26例，平均年齡（37.16±2.09）歲。兩組患者一般資料比較，差異無統(tǒng)計學(xué)意義（P＞0.05）。

P(α,β)=P1+α(P0-P1)+β(P2-P1)
(α+β<1,α>0,β>0)

(9)

當α+β=1時,P(α,β)在P0P2線段上;當α=0時,P(α,β)在P1P2線段上;β=0,P(α,β)在P0P1線段上。由上式可得如下方程組,通過求解方程組可得α和β的值,通過α和β的條件判斷,從而得知障礙物是否在控制點三角形ΔP0P1P2內(nèi)部。

(10)

(11)

C′(1/2)=P2-P0

(12)

圖2 二次Bezier避障曲線示意

基于人工勢場的方法是機器人運動規(guī)劃中一種常用方法,通過對障礙物建立排斥勢場,對目標點建立引力勢場,綜合目標對機器人的吸引力以及障礙物對機器人的排斥力,使機器人繞開障礙物向目標點移動而形成運動規(guī)劃。但是人工勢場法也有其內(nèi)在的局限性,而且也有較為復(fù)雜的計算量。本文利用人工勢場方法中的斥力勢場理論對Bezier避障曲線的內(nèi)部控制點進行調(diào)整,但是本文的避障算法只引入了人工勢場中的斥力場來分析障礙物排斥范圍,即規(guī)劃曲線路徑要避開障礙物的斥力場區(qū)域,其計算公式如下:

(13)

式中:ρi表示物體和障礙物之間的距離,η表示斥力尺度因子,ρ0表示每個障礙物的斥力場半徑。根據(jù)上述定義,本文假設(shè)只要Sink節(jié)點巡航路徑不通過障礙物的斥力場區(qū)域,那么就是安全的;如果Sink節(jié)點巡航路徑通過了障礙物的斥力場區(qū)域,那么就認為與障礙物發(fā)生了碰撞。障礙物斥力場強度與斥力尺度因子之間的關(guān)系如圖3所示。

圖3 障礙物斥力場強度曲線

定理4二次Bezier曲線f1和f2滿足G1連續(xù)的條件是前后兩條Bezier曲線的兩個內(nèi)部控制點與兩條曲線交點成同一直線,并以兩條曲線交點為中點。

圖4 G1分段連續(xù)二次Bezier曲線示意

圖5 仿真場景示意圖

3 仿真結(jié)果

本文采用MATLAB R2010a仿真平臺對所提出的算法進行驗證。仿真環(huán)境的主要參數(shù)為:區(qū)域半徑為100×100×100的立方體型三維空間內(nèi)隨機分布分布著S個傳感器節(jié)點和Q個凸形障礙物,斥力尺度因子η=10,障礙物的斥力場半徑ρ0=1,算法參數(shù)ν=1/η=0.1,仿真場景示意如圖5所示,其中圖5(a)為傳感器節(jié)點和障礙物的空間分布,圖5(b)為障礙物的斥力場分布。仿真采用的AUV能量模型簡化為距離模型,AUV消耗能量與其所巡航的距離成正比。在本文仿真中,傳感器節(jié)點的數(shù)量從5、10、20變化,即S=5/10/20,凸形障礙物數(shù)量從5、10變化,即Q=5/10。如圖6所示,如果采用最小距離旅行商問題的直線方法進行Sink節(jié)點的路徑規(guī)劃,該曲線與5個障礙物中的2個障礙點發(fā)生了碰撞。因此,雖然采用該方法可以獲得最小的總巡航距離,但是最短直線路徑肯定無法避免全部的障礙物。

圖6 無避障功能最短路徑規(guī)劃圖

本文采用的二次Bezier曲線避障,只有一個內(nèi)部控制點需要調(diào)節(jié),控制量較少,算法簡單。如果采用現(xiàn)有研究中的更高階數(shù)樣條曲線作為規(guī)劃路徑,實施避障路徑規(guī)劃可能達到更優(yōu)的路徑長度,但是要滿足路徑的C2連續(xù),需要調(diào)整更多的參數(shù),不適合于計算能力較低的移動Sink節(jié)點。因此本文仿真過程只比較了不同數(shù)量障礙物和待訪問傳感器節(jié)點下的避障性能。

由式(7)可知,本文假設(shè)Bezier曲線長度可簡單等價于首位控制點的歐式距離。因此本文提出的基于二次Bezier曲線的避障礙路徑規(guī)劃算法中,可以借鑒圖6無避障功能最短路徑規(guī)劃圖所用的最小總距離旅行商問題的求解方法。首先根據(jù)最小總距離旅行商問題求解出移動Sink巡航的傳感器節(jié)點次序,以此獲取最小距離路徑規(guī)劃的求解。然后利用本文提出的Bezier避障曲線算法,對兩兩傳感器節(jié)點之間的滿足C2連續(xù)路徑進行計算,最終得到整個無線傳感網(wǎng)移動數(shù)據(jù)收集總路徑曲線。

在5個傳感器節(jié)點和5個障礙物,10個傳感器節(jié)點和5個障礙物,20個傳感器節(jié)點和10個障礙物情況下,有無避障功能的曲線對比分別如圖7、圖8和圖9所示。圖中粉紅色方塊為障礙物,紅色圓圈為傳感器節(jié)點,綠色折線表示控制點多邊形,藍色曲線表示規(guī)劃路徑。從圖7可以發(fā)現(xiàn),只有右下方兩個障礙物存在于控制點三角形內(nèi),所以Bezier曲線的內(nèi)部控制點進行了下移,并且縮短了曲線距離,其余部分曲線與無故障避免曲線相同。從圖8可以發(fā)現(xiàn),本文提出的障礙避免規(guī)劃路徑已經(jīng)避開了所有障礙物。從圖9可以發(fā)現(xiàn),當障礙物數(shù)量較多時,Bezier曲線避障規(guī)劃路徑也能避開障礙物。因此,通過多次仿真曲線可知,應(yīng)用本文提出的基于二次Bezier曲線的避障路徑規(guī)劃算法,可以實現(xiàn)多個障礙物的有效避免。

圖9 Bezier曲線避障路徑(S=20,Q=10)

圖7 Bezier曲線避障路徑(S=5,Q=5)

圖8 Bezier曲線避障路徑(S=10,Q=5)

4 結(jié)語

本文綜合考慮了滿足C2連續(xù)二次Bezier曲線和人工勢場法中斥力場的分析方法,提出了一種滿足分段連續(xù)的二次Bezier避障曲線,保證無線傳感器網(wǎng)絡(luò)中的Sink節(jié)點對多個凸形障礙的有效避障。仿真結(jié)果驗證了本文提出的基于二次Bezier曲線的無線傳感網(wǎng)避障路徑規(guī)劃算法以較低的計算復(fù)雜度來實現(xiàn)高效率避障。后續(xù)工作將考慮無線傳感器網(wǎng)絡(luò)中存在有多個Sink節(jié)點時如何優(yōu)化規(guī)劃路徑,使得多個Sink節(jié)點協(xié)同完成數(shù)據(jù)采集任務(wù),同時避開障礙物以及避免自我碰撞。

[1] 張美燕,蔡文郁,周麗萍. 三維水下移動傳感網(wǎng)多目標有向路徑覆蓋增強研究[J]. 傳感技術(shù)學(xué)報,2014,27(1):100-106.

[2] 蔣富龍,劉昊. 面向批量數(shù)據(jù)采集的無線傳感器網(wǎng)絡(luò)雙路徑采集協(xié)議[J]. 傳感技術(shù)學(xué)報,2013,9(9):1270-1275.

[3] Latombe J C. Robot Motion Planning. Norwood[M]. Kluwer M A. Academic Publishers,1991.

[4] 胡誠,汪蕓,王輝. 無線可充電傳感器網(wǎng)絡(luò)中充電規(guī)劃研究進展[J]. 軟件學(xué)報,2016,27(1):72-95.

[5] 王家潤,趙南松,華文元,等. 分段連續(xù)三次Bezier曲線控制點的構(gòu)造算法[J]. 計算機工程與應(yīng)用,2010,46(22):190-193.

[6] Li Z,Meek D S,Walton D J. A Smooth,Obstacle-Avoiding Curve[J]. Computers and Graphics,2006,30(4):581-587.

[7] Meek D S,Ong B H,Walton D J. A Constrained GuidedG1Continuous Spline Curve[J]. Computer-Aided Design,2003,35(6):591-599.

[8] Meek D S,Ong B H,Walton D J. Constrained Interpolation With Rational Cubics[J]. Computer Aided Geometric Design,2003,20(5):253-275.

[9] 朱東偉,毛曉波,陳鐵軍. 基于改進粒子群三次Bezier曲線優(yōu)化的路徑規(guī)劃[J]. 計算機應(yīng)用研究,2012,29(5):1710-1712.

[10] 陳軍. 連續(xù)的低次避障代數(shù)樣條曲線[J]. 中國圖象圖形學(xué)報,2013,18(6):718-723.

[11] 王憲,盛巍,宋書林,等. 基于遺傳算法和B樣條曲線的平滑避障路徑規(guī)劃[J]. 計算機系統(tǒng)應(yīng)用,2012,21(2):65-71.

[12] Florin S,Vlad-Mihai I,Ionela P. Obstacle Avoidance Via B-Spline Parameterizations of Flat Trajectories[C]//Proceedings of the 24th Mediterranean Conference on Control and Automation,June 21-24,2016,Athens,Greece.

[13] Igor S,Gregor K. Cooperative Collision Avoidance Between Multiple Robots Based on Bezier Curve[C]//Proceedings of the ITI 2007 29th Int. Conf. on Information Technology Interfaces,Cavtat,Croatia,June 25-28,2007:451-456.

[14] 楊冬梅. 基于無線傳感器網(wǎng)絡(luò)的多移動機器人避障方法研究[D]. 哈爾濱:哈爾濱工業(yè)大學(xué),2013.

[15] Press W H,Teukolsky S A,Vetterling W T,et al. Numerical Recipes in C++[M]. 2nd ed. Cambridge,England:Cambridge University Press,2002.

ObstaclesAvoidanceBasedQuadraticBezierCurvePathPlanningforWirelessSensorNetworks*

ZHANGMeiyan1,CAIWenyu2*,ZHOULiping1

(1.School of Electrical Engineering,Zhejiang University of Water Resources and Electric Power,Hangzhou 310018,China; 2.School of Electronics and Information,Hangzhou Dianzi University,Hangzhou 310018,China)

The traditional sensory data collection method with fixed Sink node will lead to hot spot problem. To overcome this problem,mobile data collection by mobile Sink is proposed so as to balance network energy distribution and prolong network lifecycle. Aiming at the application scenario of the vehicle-like robot as a mobile data aggregation node in wireless sensor networks,this paper proposes a continuous quadratic Bezier curves based obstacle avoidance path planning algorithm for mobile Sink node. Firstly,some segmented continuous Bezier curves are constructed as a whole cruise trajectory. Secondly,the repulsive effect of multiple obstacles is analyzed by artificial potential field method. As a result,the position of internal control points of Bezier curve is dynamically adjusted with repulsive potential field,and adjacent obstacles can be excluded from delta-shaped region by quadratic Bezier curve. Simulation results verify that the proposed method can realize multiple obstacles avoidance in the planning path of mobile Sink node with smaller computational complexity.

wireless sensor networks;bezier curve;path planning;obstacles avoidance

TP393

A

1004-1699(2017)10-1596-06

10.3969/j.issn.1004-1699.2017.10.024

張美燕(1983-),女,副教授,從事無線傳感網(wǎng)絡(luò)、新型能源技術(shù)、物聯(lián)網(wǎng)技術(shù)等研究,主持和參與浙江省自然科學(xué)基金2項,浙江省公益性行業(yè)專項3項,浙江省水利廳科技項目2項,參與浙江省廳級項目多項。近年來發(fā)表論文20余篇,被三大索引收錄論文10余篇,申請發(fā)明專利和實用新型專利30余項;

蔡文郁(1979-),男,博士,副教授,主要從事物聯(lián)網(wǎng)、無線傳感網(wǎng)及嵌入式技術(shù)研究。主持和參與國家自然科學(xué)基金2項、浙江省自然科學(xué)基金3項、浙江省公益性行業(yè)專項3項,國家863計劃項目2項、國家海洋局行業(yè)專項1項、浙江省重大科技專項1項,橫向課題10余項。近年來發(fā)表論文40余篇,被SCI/EI收錄20余篇,申請專利及軟著40余項,授權(quán)30余項,dreampp2000@163.com。