陳倩，張奇松，侯麗

（大連東軟信息學(xué)院信息管理系，遼寧大連116026）

基于位置服務(wù)的系統(tǒng)（LBS），一般是指運(yùn)營商利用GPS或無線通訊網(wǎng)絡(luò)獲取移動(dòng)終端用戶的位置信息，在一定平臺(tái)的支持下，為用戶提供服務(wù)的增值業(yè)務(wù)，其中，而路徑規(guī)劃和人員跟蹤是LBS系統(tǒng)的主要業(yè)務(wù)和功能[1-4]。

本文針對(duì)LBS系統(tǒng)中的路徑規(guī)劃進(jìn)行了研究，由于人工勢(shì)場(chǎng)法原理簡(jiǎn)單，計(jì)算速度快，在路徑規(guī)劃中廣泛應(yīng)用，因此對(duì)人工勢(shì)場(chǎng)法進(jìn)行了深入研究和討論[5-6]。文獻(xiàn)[7-8]指出傳統(tǒng)人工勢(shì)場(chǎng)法存在一些缺陷：無法利用全局環(huán)境信息，算法缺乏自身調(diào)節(jié)能力，在尋址過程中易陷入局部最優(yōu)解，不易躲避動(dòng)態(tài)障礙物，也無法追蹤動(dòng)態(tài)目標(biāo)等問題。針對(duì)以上問題，本文提出一種改進(jìn)式人工勢(shì)場(chǎng)算法，在模型構(gòu)建和搜索算法兩方面進(jìn)行改進(jìn)，首先針對(duì)環(huán)境中的障礙物的連通性進(jìn)行分析[9-10]，借助幾何拓?fù)鋵W(xué)獲取可行解域，其次在可行解域中進(jìn)行路徑預(yù)規(guī)劃，解決其人工勢(shì)場(chǎng)法易陷入局部最優(yōu)解而不能找到可行路徑的問題，同時(shí)在人工勢(shì)場(chǎng)中加入速度因子，使用戶可以躲避動(dòng)態(tài)障礙物以及追蹤動(dòng)態(tài)目標(biāo)，最后進(jìn)行曲率檢查獲得相對(duì)平滑的可行性路徑。

1 障礙物建模及連通性分析

在LBS系統(tǒng)中，所處環(huán)境中靜態(tài)障礙物的建模是路徑規(guī)劃的研究前提，靜態(tài)障礙物建模的優(yōu)劣直接會(huì)影響路徑規(guī)劃的效果，但真實(shí)環(huán)境中靜態(tài)障礙物多樣且未知，為簡(jiǎn)化分析，本文將障礙物全部化為圓形形狀，障礙物中心為原點(diǎn)，影響范圍為半徑，同時(shí)將障礙物投影到二維平面，以此構(gòu)建所處環(huán)境，環(huán)境中障礙物影響的范圍隨著障礙物離用戶的距離的增加而減少，如圖1所示，圓形表示障礙物，圓形及其內(nèi)部為不可通行區(qū)域；其余部分表示可通行區(qū)域。針對(duì)實(shí)際復(fù)雜環(huán)境，單個(gè)圓形難以簡(jiǎn)單明了地描述障礙物信息，因此本文借助幾何拓?fù)鋵W(xué)原理，以距離相近圓形的包絡(luò)弧近似表示障礙物，將路徑規(guī)劃問題簡(jiǎn)化為尋找能躲避圓形區(qū)域的路線問題，即將復(fù)雜的問題簡(jiǎn)單化，具體化。

連通性分析是為了進(jìn)一步對(duì)靜態(tài)障礙物分布及障礙物相互之間的關(guān)系影響進(jìn)行分析，利用靜態(tài)障礙物中心坐標(biāo)及影響半徑大小，分析出用戶路徑規(guī)劃中的可行性解域，進(jìn)而排除非可行性解，使搜索空間縮小，提高后續(xù)智能算法的效率。

分析步驟如下：設(shè)用戶所處環(huán)境障礙物數(shù)量為，障礙物的中心坐標(biāo)表示為，創(chuàng)建維數(shù)為下三角相交信息矩陣，判斷任意與的大小，如果前者大，則設(shè)為1，反之設(shè)為0；隨后根據(jù)信息矩陣中的值分析靜態(tài)障礙物中起作用的相交區(qū)域，利用直線將起作用的區(qū)域中心連接起來，并將該類障礙物中心合并成一個(gè)集合。

分析結(jié)果如圖1所示，在上述集合中所有障礙物中心都被直線連接，通過上述步驟，路徑規(guī)劃問題由避開圓形區(qū)域變?yōu)檎覍て鹗键c(diǎn)和終止點(diǎn)之間與相連線段幾何問題，簡(jiǎn)化了求解問題，同時(shí)使搜索空間進(jìn)一步減小，有利于提高后續(xù)智能算法的可行性和實(shí)時(shí)性。

圖1 障礙物建模及連通性分析圖

2 路徑點(diǎn)預(yù)規(guī)劃

路徑點(diǎn)預(yù)規(guī)劃是在對(duì)障礙物進(jìn)行連通性分析基礎(chǔ)之上進(jìn)行的，預(yù)先在起始點(diǎn)和終止點(diǎn)之間找尋一條連接路徑。障礙物的中心點(diǎn)構(gòu)成了該該連接路徑的中間節(jié)點(diǎn)，既滿足了全劇規(guī)劃的眼球，又可以防止后續(xù)算法—改進(jìn)人工勢(shì)場(chǎng)法陷入局部最優(yōu)解，提高了后續(xù)智能算法的尋找全局最優(yōu)解的能力。

具體步驟如下所示：

1）連接起始點(diǎn)和終止點(diǎn)。

2）判斷有無障礙物集合與1）中連線相交，若沒有相交，則結(jié)束預(yù)規(guī)劃；若有相交，選定離起始點(diǎn)最近的障礙物集合。

3）從該集合中選出新的路徑起始點(diǎn)

4）將新選出的起始點(diǎn)與終止點(diǎn)相連，轉(zhuǎn)到2）步驟

上述2）的具體操作：描繪出所處環(huán)境中所有靜態(tài)障礙物的中心集合，對(duì)于中心集合中的任意中心點(diǎn)，表示為x，如果滿足ax＜aref或ax＞aref（a為角度），則表示連線與障礙物中心集合沒有相交；否則表示兩者相交。

如連線與多個(gè)障礙物中心集合有交集，對(duì)于離起始點(diǎn)最近集合的選擇需要利用障礙物中心點(diǎn)在連線上的投影，然后比較連線上的投影，距離起始點(diǎn)最近的投影所在的障礙物中心集合即為應(yīng)選取得集合。

新起始點(diǎn)最近的障礙物中心的選取是計(jì)算該集合中所有點(diǎn)x的|ax-aref|，將此值最小的點(diǎn)作為新的起始點(diǎn)。其中，ax表示障礙物中心點(diǎn)x與新起始點(diǎn)連線和坐標(biāo)系的夾角，aref為終點(diǎn)和新起始點(diǎn)連線與坐標(biāo)系的夾角。

3 改進(jìn)人工勢(shì)場(chǎng)法

傳統(tǒng)人工勢(shì)場(chǎng)法的基本思想是將用戶所在的已知環(huán)境，構(gòu)造一種抽象的人造勢(shì)場(chǎng)，目標(biāo)點(diǎn)對(duì)用戶產(chǎn)生虛擬“引力場(chǎng)”，進(jìn)而產(chǎn)生“引力”，吸引用戶向其運(yùn)動(dòng)；障礙物對(duì)用戶產(chǎn)生虛擬“斥力場(chǎng)”，進(jìn)而產(chǎn)生“斥力”。在“引力”和“斥力”的共同作用下，用戶可以順利避開障礙物，并達(dá)到目標(biāo)點(diǎn)。通過這種虛擬勢(shì)場(chǎng)的構(gòu)建，能夠規(guī)劃出起始點(diǎn)到終止點(diǎn)之間比較平滑的無障礙路徑[11-13]。

傳統(tǒng)的人工勢(shì)場(chǎng)并不適定位、追蹤動(dòng)態(tài)目標(biāo)以及躲避動(dòng)態(tài)障礙物，其引力場(chǎng)函數(shù)和斥力場(chǎng)函數(shù)，如（1），（2）所示：

其中，ρ(q,qgoal)=‖q-qgoal‖ 是配送車輛當(dāng)前位置q與目標(biāo)位置qgoal之間的距離，ξ為正比例系數(shù)，m=1或 2；ρ(q,qobs)=‖q-qobs‖為當(dāng)前配送車輛位置q與障礙物表面位置qobs的最短距離，ε為正比例系數(shù)，ρ0為斥力場(chǎng)斥力所能影響到的最大距離，超出該值，斥力場(chǎng)斥力不會(huì)對(duì)用戶產(chǎn)生影響。

不難看出傳統(tǒng)人工勢(shì)場(chǎng)法中的引力場(chǎng)函數(shù)只與用戶和目標(biāo)點(diǎn)的位置有關(guān)，因此用戶無法很好的躲避動(dòng)態(tài)障礙物并追蹤動(dòng)態(tài)目標(biāo)。

因此本文在傳統(tǒng)人工勢(shì)場(chǎng)法的基礎(chǔ)上提出了一種新的引力場(chǎng)函數(shù)和斥力場(chǎng)函數(shù)。在函數(shù)中添加速度因子，由于速度因子是矢量，既有大小，又有方向，因此可以使用戶追蹤動(dòng)態(tài)目標(biāo)，同時(shí)在運(yùn)動(dòng)過程中能有效躲避靜態(tài)障礙物和動(dòng)態(tài)障礙物。為便于分析說明，做以下假設(shè)：

假設(shè)1：用戶的位置q和速度v已知；

假設(shè)2：動(dòng)態(tài)目標(biāo)的位置qtar和速度vtar已知，動(dòng)態(tài)障礙物的位置qobs和速度vobs亦已知。

本文將速度因子引入傳統(tǒng)人工勢(shì)場(chǎng)法中，提出一種改進(jìn)的引力場(chǎng)函數(shù)和斥力場(chǎng)函數(shù)，表達(dá)式如公式（3），（4）所示：

其中，q(t)和qtar(t)為t時(shí)刻配送車輛和動(dòng)態(tài)目標(biāo)的位置，v(t)和vtar(t)為t時(shí)刻配送車輛和動(dòng)態(tài)目標(biāo)的速度矢量，‖qtar(t)-q(t)‖是t時(shí)刻配送車輛與動(dòng)態(tài)接收實(shí)體的相對(duì)距離，‖vtar(t)-v(t)‖ 是t時(shí)刻配送車輛與動(dòng)態(tài)接收實(shí)體速度的相對(duì)值，αq和αv是正比例系數(shù)，m和n是兩個(gè)正的常量；q(t)和qobs(t)為t時(shí)刻配送車輛和動(dòng)態(tài)障礙物的位置，v(t)和vobs(t)為t時(shí)刻配送車輛和動(dòng)態(tài)障礙物的速度矢量，‖q(t)-qobs(t)‖是t時(shí)刻配送車輛與動(dòng)態(tài)障礙物的相對(duì)距離，‖vobs(t)-v(t)‖ 是t時(shí)刻配送車輛與動(dòng)態(tài)障礙物速度的相對(duì)值，和是正比例系數(shù)，k和S是兩個(gè)正的常量。

從公式（3）可以得出，當(dāng)速度因子被引入到引力場(chǎng)函數(shù)Uatt(q,v)中后，當(dāng)且僅當(dāng)用戶與動(dòng)態(tài)目標(biāo)的相對(duì)距離和相對(duì)速度都為零時(shí)，函數(shù)值為0。新引力場(chǎng)函數(shù)Uatt(q,v)隨著用戶和動(dòng)態(tài)或靜態(tài)目標(biāo)的相對(duì)距離或者相對(duì)速度增加而增加，可以有效定位和追蹤物流中的動(dòng)態(tài)目標(biāo)；由公式（4）可以看出，當(dāng)斥力場(chǎng)函數(shù)Urep(q,v)引入速度矢量后，當(dāng)配送車輛距離障礙物在其影響范圍之內(nèi)，并且朝向障礙物（包括靜態(tài)和動(dòng)態(tài)障礙物）時(shí)，斥力場(chǎng)函數(shù)起作用，當(dāng)配送車輛在障礙物影響范圍之外或者兩者速度相反時(shí)，障礙物斥力場(chǎng)不起作用，可以有效躲避環(huán)境中靜態(tài)和動(dòng)態(tài)障礙物。

生成路徑后，為保證路徑的平滑性，設(shè)定配送車輛的最大轉(zhuǎn)彎角度θ，規(guī)定生成路徑只能在不大于預(yù)訂的角度范圍內(nèi)轉(zhuǎn)彎，最大角度限制為±90°。

4 算法流程

文中在對(duì)障礙物建模，進(jìn)行連通性分析，其次將速度因子引進(jìn)傳統(tǒng)人工勢(shì)場(chǎng)法中，改進(jìn)引力場(chǎng)函數(shù)和斥力場(chǎng)函數(shù)，使之能夠適應(yīng)動(dòng)態(tài)環(huán)境。整體算法如下：

1）生成障礙物模型；

2）對(duì)障礙物進(jìn)行連通性分析；

3）進(jìn)行路徑點(diǎn)規(guī)劃；

4）通過改進(jìn)人工勢(shì)場(chǎng)法計(jì)算生成路徑；

5）判斷生成路徑是否在障礙物區(qū)域外；

6）如果是，根據(jù)最帶轉(zhuǎn)彎角度，調(diào)整生成路徑，保證其平滑性；如果不是，返回第4）步，重新生成路徑。

5 基于LBS系統(tǒng)的算法實(shí)現(xiàn)

文中所提算法可以基于LBS系統(tǒng)實(shí)現(xiàn)的，LBS系統(tǒng)不是單一系統(tǒng)，而是一種集成性系統(tǒng)[14-16]。該系統(tǒng)有兩部分組成—移動(dòng)終端和服務(wù)器端，組成部分之間通過互聯(lián)網(wǎng)以及無線網(wǎng)絡(luò)進(jìn)行數(shù)據(jù)傳輸，如圖2所示。

圖2 基于LBS系統(tǒng)的算法實(shí)現(xiàn)

LBS系統(tǒng)中，用戶可以利用所持移動(dòng)終端設(shè)備將自己的需求，即需要追蹤的動(dòng)態(tài)目標(biāo)，通過互聯(lián)網(wǎng)或無限網(wǎng)絡(luò)傳送到服務(wù)器端，服務(wù)器端根據(jù)用戶需求調(diào)用安裝在動(dòng)態(tài)目標(biāo)上的配套裝置—GPS裝置或傳感器裝置，配套裝置根據(jù)需求將自身以及周邊障礙物的位置和速度等信息實(shí)時(shí)不斷地返回給服務(wù)器端，服務(wù)器端根據(jù)本文提供的算法，實(shí)時(shí)規(guī)劃相應(yīng)無障礙路徑，并將其結(jié)果傳送到用戶移動(dòng)終端設(shè)備，供其使用。

6 仿真實(shí)驗(yàn)

為了驗(yàn)證本文所提算法的有效性和優(yōu)越性，本文利用Matlab和Visual C++進(jìn)行聯(lián)合編程，構(gòu)建仿真實(shí)驗(yàn)。為簡(jiǎn)明實(shí)驗(yàn)，在仿真實(shí)驗(yàn)中，障礙物和目標(biāo)點(diǎn)的位置人為設(shè)定，配送車輛的步長為0.5 cm，每步間隔時(shí)間為100 ms，同時(shí)為了簡(jiǎn)化研究，實(shí)驗(yàn)中設(shè)定配送車輛和接收實(shí)體均為勻速運(yùn)動(dòng)，同時(shí)參數(shù)設(shè)置如下：引力場(chǎng)系數(shù)αq=2，αv=1.5，斥力場(chǎng)系數(shù)，m=1,n=2，k=1,s=2。為驗(yàn)證基于連通性分析的改進(jìn)人工勢(shì)場(chǎng)在LBS系統(tǒng)中的路徑規(guī)劃有效性和優(yōu)越性，本文進(jìn)行首先對(duì)本文所提算法進(jìn)行仿真試驗(yàn)，圖3，圖4，圖5表示基于連通性分析的改進(jìn)人工勢(shì)場(chǎng)算法，證明本文所提算法的有效性性；其次，進(jìn)行對(duì)比實(shí)驗(yàn)，僅針對(duì)改進(jìn)人工勢(shì)場(chǎng)算法進(jìn)行仿真實(shí)驗(yàn)，如圖5所示，證明本文所提算法的優(yōu)越性。在仿真實(shí)驗(yàn)中，左下方移動(dòng)原點(diǎn)表示用戶，圖中左上位置黑色圓點(diǎn)表示動(dòng)態(tài)目標(biāo)，為體現(xiàn)對(duì)比實(shí)驗(yàn)的準(zhǔn)確性，用戶和動(dòng)態(tài)目標(biāo)的出發(fā)位置相同，同時(shí)為簡(jiǎn)化實(shí)驗(yàn)，動(dòng)態(tài)目標(biāo)設(shè)定為勻速直線運(yùn)動(dòng)，中間靜止圓點(diǎn)為人為設(shè)置的相同靜態(tài)障礙物，中間黑色移動(dòng)圓點(diǎn)表示移動(dòng)障礙物，仿真實(shí)驗(yàn)如下。

圖3 改進(jìn)算法中用戶遇到障礙物

圖4 基于聯(lián)通性分析的改進(jìn)人工勢(shì)場(chǎng)法

通過以上實(shí)驗(yàn)，首先證明了基于連通性分析的改進(jìn)人工勢(shì)場(chǎng)法的有效性，在引入速度因子后，新的引力場(chǎng)函數(shù)和斥力場(chǎng)函數(shù)所產(chǎn)生的合力可以產(chǎn)生一條無障礙路徑，并順利追蹤到動(dòng)態(tài)目標(biāo)，圖3表示用戶進(jìn)入動(dòng)態(tài)障礙物影響范圍，圖4表示用戶成功追蹤到動(dòng)態(tài)目標(biāo)。其次通過對(duì)比實(shí)驗(yàn)，如圖5所示，單純改進(jìn)人工勢(shì)場(chǎng)同樣可以躲避動(dòng)靜態(tài)障礙物，并追蹤到動(dòng)態(tài)目標(biāo)，但明顯在路徑長度上要長于本文所提算法，證明了本文所提算法的優(yōu)越性。為了進(jìn)一步說明本算法的高效性，本文在相同環(huán)境下將基于連通性分析的人工勢(shì)場(chǎng)與單純改進(jìn)人工勢(shì)場(chǎng)算法進(jìn)行數(shù)值比較。其數(shù)值對(duì)比實(shí)驗(yàn)數(shù)據(jù)如表1所示。

圖5 單純改進(jìn)人工勢(shì)場(chǎng)法

表1 對(duì)比實(shí)驗(yàn)具體數(shù)據(jù)

通過實(shí)驗(yàn)表明，在相同實(shí)驗(yàn)環(huán)境下，基于連通性分析的改進(jìn)人工勢(shì)場(chǎng)算法和單純改進(jìn)人工勢(shì)場(chǎng)算法均能追蹤到動(dòng)態(tài)目標(biāo)，但基于連通性分析的改進(jìn)人工勢(shì)場(chǎng)算法到達(dá)時(shí)間和運(yùn)動(dòng)步數(shù)均優(yōu)于單純改進(jìn)人工勢(shì)場(chǎng)算法。說明本文所提出的算法是有效的，同時(shí)明顯提高了算法的搜索效率。

7 結(jié)論

文中提出了一種基于連通性分析改進(jìn)式人工勢(shì)場(chǎng)法，并將其應(yīng)用于LBS系統(tǒng)[17]中路徑規(guī)劃問題。本文在連通性分析基礎(chǔ)上，將速度因子加入到傳統(tǒng)人工勢(shì)場(chǎng)算法中，構(gòu)造新的引力場(chǎng)函數(shù)和斥力場(chǎng)函數(shù)，進(jìn)而使用戶可以躲避動(dòng)態(tài)障礙物及追蹤動(dòng)態(tài)目標(biāo)，并獲取最優(yōu)路徑。最后通過對(duì)比仿真實(shí)驗(yàn)表明本文所提算法的具有很高的實(shí)用性和有效性。

參考文獻(xiàn)：

[1]陳廷斌，張奇松.基于改進(jìn)人工蟻群算法的LBS最短路徑研究[J].計(jì)算機(jī)仿真，2013，30（5）：349-353.

[2]彭紅.基于云計(jì)算的LBS應(yīng)用研究[J].軟件工程，2016，19（10）：27-29.

[3]馬春來，單洪，馬濤，等.一種基于隨機(jī)森林的LBS用戶社會(huì)關(guān)系判斷方法[J].計(jì)算機(jī)科學(xué)，2016，43（12）：218-222.

[4]周傲英，楊彬，金澈清.基于位置的服務(wù)架構(gòu)與進(jìn)展[J].計(jì)算機(jī)學(xué)報(bào)，2011，34（7）：1155-1171.

[5]翟紅生，王佳欣.基于人工勢(shì)場(chǎng)的機(jī)器人動(dòng)態(tài)路徑規(guī)劃新方法[J].重慶郵電大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，27（6）：814-818.

[6]于振中，閆繼宏，趙杰，等.改進(jìn)人工勢(shì)場(chǎng)的移動(dòng)機(jī)器人路徑規(guī)劃[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2011，43（1）：50-55.

[7]陳廷斌，張奇松，楊曉光.基于改進(jìn)人工勢(shì)場(chǎng)-魚群算法的LBS最短路徑修正研究[J].計(jì)算機(jī)應(yīng)用與軟件，2015（6）：259-262.

[8]溫素芳，郭光耀.基于改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)工程與設(shè)計(jì)，2015（10）：2818-2822.

[9]黃玉強(qiáng).移動(dòng)機(jī)器人在未知環(huán)境下的基于視覺系統(tǒng)的地圖創(chuàng)建[D].南京：南京大學(xué)，2012.

[10]王梅，王葉婷，屠大維，等.基于混合勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)應(yīng)用研究，2012，29（7）：2447-2449.

[11]歐陽鑫玉，楊曙光.基于勢(shì)場(chǎng)柵格法的移動(dòng)機(jī)器人避障路徑規(guī)劃[J].控制工程，2014，21（1）：134-137.

[12]崔金琦，陶先平.基于RFID的校園導(dǎo)航系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)科學(xué)，2015，12：92-94，119.

[13]吳晉，張國良，湯文俊，等.基于改進(jìn)人工協(xié)調(diào)場(chǎng)的多機(jī)器人避碰算法[J].計(jì)算機(jī)應(yīng)用，2013，33（11）：3123-3128.

[14]譚鈞.基于LBS技術(shù)與O2O模式的城市共同配送研究[J].物流技術(shù)，2015（22）：126-129.

[15]袁國泉，陶先平.基于云計(jì)算平臺(tái)的LBS服務(wù)管理[J].計(jì)算機(jī)科學(xué)，2011（10）：18-22.

[16]彭紅.基于云計(jì)算的LBS應(yīng)用研究[J].軟件工程師，2016，19（10）：27-29.

[17]劉秋連.O2M全渠道視角下零售企業(yè)會(huì)員營銷模式的構(gòu)建[J].西安工程大學(xué)學(xué)報(bào)，2016（5）：669-674.