LBS中改進人工勢場法的動態目標路徑規劃研究

陳倩，張奇松，侯麗

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

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

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

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

在LBS系統中，所處環境中靜態障礙物的建模是路徑規劃的研究前提，靜態障礙物建模的優劣直接會影響路徑規劃的效果，但真實環境中靜態障礙物多樣且未知，為簡化分析，本文將障礙物全部化為圓形形狀，障礙物中心為原點，影響范圍為半徑，同時將障礙物投影到二維平面，以此構建所處環境，環境中障礙物影響的范圍隨著障礙物離用戶的距離的增加而減少，如圖1所示，圓形表示障礙物，圓形及其內部為不可通行區域；其余部分表示可通行區域。針對實際復雜環境，單個圓形難以簡單明了地描述障礙物信息，因此本文借助幾何拓撲學原理，以距離相近圓形的包絡弧近似表示障礙物，將路徑規劃問題簡化為尋找能躲避圓形區域的路線問題，即將復雜的問題簡單化，具體化。

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

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

分析結果如圖1所示，在上述集合中所有障礙物中心都被直線連接，通過上述步驟，路徑規劃問題由避開圓形區域變為找尋起始點和終止點之間與相連線段幾何問題，簡化了求解問題，同時使搜索空間進一步減小，有利于提高后續智能算法的可行性和實時性。

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

2 路徑點預規劃

路徑點預規劃是在對障礙物進行連通性分析基礎之上進行的，預先在起始點和終止點之間找尋一條連接路徑。障礙物的中心點構成了該該連接路徑的中間節點，既滿足了全劇規劃的眼球，又可以防止后續算法—改進人工勢場法陷入局部最優解，提高了后續智能算法的尋找全局最優解的能力。

具體步驟如下所示：

1）連接起始點和終止點。

2）判斷有無障礙物集合與1）中連線相交，若沒有相交，則結束預規劃；若有相交，選定離起始點最近的障礙物集合。

3）從該集合中選出新的路徑起始點

4）將新選出的起始點與終止點相連，轉到2）步驟

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

如連線與多個障礙物中心集合有交集，對于離起始點最近集合的選擇需要利用障礙物中心點在連線上的投影，然后比較連線上的投影，距離起始點最近的投影所在的障礙物中心集合即為應選取得集合。

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

3 改進人工勢場法

傳統人工勢場法的基本思想是將用戶所在的已知環境，構造一種抽象的人造勢場，目標點對用戶產生虛擬“引力場”，進而產生“引力”，吸引用戶向其運動；障礙物對用戶產生虛擬“斥力場”，進而產生“斥力”。在“引力”和“斥力”的共同作用下，用戶可以順利避開障礙物，并達到目標點。通過這種虛擬勢場的構建，能夠規劃出起始點到終止點之間比較平滑的無障礙路徑[11-13]。

傳統的人工勢場并不適定位、追蹤動態目標以及躲避動態障礙物，其引力場函數和斥力場函數，如（1），（2）所示：

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

不難看出傳統人工勢場法中的引力場函數只與用戶和目標點的位置有關，因此用戶無法很好的躲避動態障礙物并追蹤動態目標。

因此本文在傳統人工勢場法的基礎上提出了一種新的引力場函數和斥力場函數。在函數中添加速度因子，由于速度因子是矢量，既有大小，又有方向，因此可以使用戶追蹤動態目標，同時在運動過程中能有效躲避靜態障礙物和動態障礙物。為便于分析說明，做以下假設：

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

假設2：動態目標的位置qtar和速度vtar已知，動態障礙物的位置qobs和速度vobs亦已知。

本文將速度因子引入傳統人工勢場法中，提出一種改進的引力場函數和斥力場函數，表達式如公式（3），（4）所示：

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

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

生成路徑后，為保證路徑的平滑性，設定配送車輛的最大轉彎角度θ，規定生成路徑只能在不大于預訂的角度范圍內轉彎，最大角度限制為±90°。

4 算法流程

文中在對障礙物建模，進行連通性分析，其次將速度因子引進傳統人工勢場法中，改進引力場函數和斥力場函數，使之能夠適應動態環境。整體算法如下：

1）生成障礙物模型；

2）對障礙物進行連通性分析；

3）進行路徑點規劃；

4）通過改進人工勢場法計算生成路徑；

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

6）如果是，根據最帶轉彎角度，調整生成路徑，保證其平滑性；如果不是，返回第4）步，重新生成路徑。

5 基于LBS系統的算法實現

文中所提算法可以基于LBS系統實現的，LBS系統不是單一系統，而是一種集成性系統[14-16]。該系統有兩部分組成—移動終端和服務器端，組成部分之間通過互聯網以及無線網絡進行數據傳輸，如圖2所示。

圖2 基于LBS系統的算法實現

LBS系統中，用戶可以利用所持移動終端設備將自己的需求，即需要追蹤的動態目標，通過互聯網或無限網絡傳送到服務器端，服務器端根據用戶需求調用安裝在動態目標上的配套裝置—GPS裝置或傳感器裝置，配套裝置根據需求將自身以及周邊障礙物的位置和速度等信息實時不斷地返回給服務器端，服務器端根據本文提供的算法，實時規劃相應無障礙路徑，并將其結果傳送到用戶移動終端設備，供其使用。

6 仿真實驗

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

圖3 改進算法中用戶遇到障礙物

圖4 基于聯通性分析的改進人工勢場法

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

圖5 單純改進人工勢場法

表1 對比實驗具體數據

通過實驗表明，在相同實驗環境下，基于連通性分析的改進人工勢場算法和單純改進人工勢場算法均能追蹤到動態目標，但基于連通性分析的改進人工勢場算法到達時間和運動步數均優于單純改進人工勢場算法。說明本文所提出的算法是有效的，同時明顯提高了算法的搜索效率。

7 結論

文中提出了一種基于連通性分析改進式人工勢場法，并將其應用于LBS系統[17]中路徑規劃問題。本文在連通性分析基礎上，將速度因子加入到傳統人工勢場算法中，構造新的引力場函數和斥力場函數，進而使用戶可以躲避動態障礙物及追蹤動態目標，并獲取最優路徑。最后通過對比仿真實驗表明本文所提算法的具有很高的實用性和有效性。

參考文獻：

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

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

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

[4]周傲英，楊彬，金澈清.基于位置的服務架構與進展[J].計算機學報，2011，34（7）：1155-1171.

[5]翟紅生，王佳欣.基于人工勢場的機器人動態路徑規劃新方法[J].重慶郵電大學學報：自然科學版，2015，27（6）：814-818.

[6]于振中，閆繼宏，趙杰，等.改進人工勢場的移動機器人路徑規劃[J].哈爾濱工業大學學報，2011，43（1）：50-55.

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

[8]溫素芳，郭光耀.基于改進人工勢場法的移動機器人路徑規劃[J].計算機工程與設計，2015（10）：2818-2822.

[9]黃玉強.移動機器人在未知環境下的基于視覺系統的地圖創建[D].南京：南京大學，2012.

[10]王梅，王葉婷，屠大維，等.基于混合勢場法的移動機器人路徑規劃[J].計算機應用研究，2012，29（7）：2447-2449.

[11]歐陽鑫玉，楊曙光.基于勢場柵格法的移動機器人避障路徑規劃[J].控制工程，2014，21（1）：134-137.

[12]崔金琦，陶先平.基于RFID的校園導航系統的設計與實現[J].計算機科學，2015，12：92-94，119.

[13]吳晉，張國良，湯文俊，等.基于改進人工協調場的多機器人避碰算法[J].計算機應用，2013，33（11）：3123-3128.

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

[15]袁國泉，陶先平.基于云計算平臺的LBS服務管理[J].計算機科學，2011（10）：18-22.

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

[17]劉秋連.O2M全渠道視角下零售企業會員營銷模式的構建[J].西安工程大學學報，2016（5）：669-674.