一種基于人工勢場的無人機航跡規(guī)劃算法

甄 然，甄士博，吳學(xué)禮

(1.河北科技大學(xué)電氣工程學(xué)院，河北石家莊 050018；2.河北省生產(chǎn)過程自動化工程技術(shù)研究中心，河北石家莊 050018)

一種基于人工勢場的無人機航跡規(guī)劃算法

甄 然1,2，甄士博1,2，吳學(xué)禮1,2

(1.河北科技大學(xué)電氣工程學(xué)院，河北石家莊 050018；2.河北省生產(chǎn)過程自動化工程技術(shù)研究中心，河北石家莊 050018)

為了改進傳統(tǒng)的人工勢場法不能適應(yīng)復(fù)雜環(huán)境、容易陷入最小值和在終點附近徘徊的情況，提出一種基于混沌理論的人工勢場法的無人機航跡規(guī)劃算法。在傳統(tǒng)人工勢場法原理的基礎(chǔ)上，將混沌理論的搜索算法引入人工勢場法中的斥力場、引力場的函數(shù)公式中，改變了各個障礙物斥力系數(shù)和目標點的引力系數(shù)，將改變后的系數(shù)代入計算，搜索出斥力場和引力場的最優(yōu)系數(shù)組。本算法有如下優(yōu)點:第一，考慮了障礙物對尋優(yōu)過程的影響，排除了合力為零的情況。第二，通過迭代的方法，具有適應(yīng)不同地圖的能力。第三，適用于無人機的航跡規(guī)劃。仿真實驗結(jié)果和理論分析表明，混沌理論的人工勢場法不僅解決了無人機在航跡規(guī)劃中容易陷入最小值和在終點附近徘徊等問題，而且可以實現(xiàn)無人機在復(fù)雜環(huán)境下的航跡規(guī)劃，縮短了飛行成本，節(jié)約了計算時間，提高了三維空間無人機航跡規(guī)劃的速度和精度。

機器人控制；無人機；人工勢場法；航跡規(guī)劃；混沌理論

無人機的航跡規(guī)劃是無人機研究領(lǐng)域的一個重要組成部分[1]，無人機技術(shù)的發(fā)展，對無人機航跡規(guī)劃提出了越來越高的要求。無人機航跡規(guī)劃的任務(wù)是在具有障礙物的環(huán)境中，按照一定的評價系統(tǒng)，尋找一條從起始位置到達目標位置的無碰撞的路徑[2-3]，目前提出的常用算法有A*算法[4]、D*算法[5]、Bug1算法、Bug2算法[6]、人工勢場法[7]，還有須滿足限制條件的粒子群算法[8]等。其中人工勢場法包容性好，方便快捷，可以和很多方法結(jié)合，實現(xiàn)無人機的實時控制。但其也有不能適應(yīng)復(fù)雜環(huán)境的缺點，比如在狹窄環(huán)境中路徑擺動，障礙物附近目標不可達，容易陷入最小值等。

針對這些情況，文獻[9]提出了按著沿墻走的軌跡來環(huán)繞障礙物解決目標點不可達的情況；文獻[10]提出了極限環(huán)法，通過環(huán)繞障礙物的方法讓無人機走圓弧狀路徑，達到避障的目的；文獻[11]采用連鎖網(wǎng)絡(luò)方法減小無規(guī)則碰撞現(xiàn)象。上述方法雖然在一定程度上避免了算法陷入局部最小值等情況，但仍存在著不能適應(yīng)復(fù)雜環(huán)境,在狹窄環(huán)境徘徊的缺點。

人工勢場算法之所以無法適應(yīng)復(fù)雜的環(huán)境，是因為斥力場系數(shù)、引力場系數(shù)在計算時是固定不變的，本文提出了一種基于混沌理論的人工勢場法，將混沌理論全局搜索引入人工勢場法，搜索出更優(yōu)的引力場和斥力場系數(shù)，從而發(fā)揮出人工勢場法的潛力。最近，研究人員將各種混沌優(yōu)化算法[13-16]應(yīng)用于路徑規(guī)劃算法中，其基本思想：解空間是從無序空間變換到的，利用混沌變量，發(fā)掘共性、隨機性和規(guī)律性的特點，進行全局搜索?；煦鐑?yōu)化方法具有全局漸近收斂、易跳出局部極小點和收斂速度快等特點，與人工勢場算法很容易結(jié)合。改進的人工勢場法的基本思路是：在傳統(tǒng)人工勢場法無人機航跡規(guī)劃基礎(chǔ)上，通過混沌理論改變障礙物和目標點的斥力和引力，從而搜索出更優(yōu)路徑。

1 人工勢場法基本原理

人工勢場法的實質(zhì)是對無人機的飛行區(qū)域人為地定義勢場[17]，該勢場為地圖中出現(xiàn)的障礙物斥力場和終點引力場的向量疊加。傳統(tǒng)人工勢場的定義如下:

假設(shè)無人機的位置為X=(x,y,z)，則目標點引力場與無人機電子之間的電勢場為

(1)

式中:Katt為勢場增益系數(shù);XG為目標點的位置。

定義Fatt(X)為引力勢場的引力,

(2)

定義障礙物的斥力勢場為

(3)

定義障礙物的斥力為

(4)

式中：Frep為障礙物對無人機的斥力勢場系數(shù)；X-X0的單位是m，表示移動的無人機到各個障礙物的動態(tài)距離；ρ0為障礙物的影響距離。所以移動的無人機像一個電子一樣，它的總勢場為無人機與障礙物各個勢場的和：

(5)

對無人機的作用力Ftotal為

(6)

由式(6)可以算出無人機的下一步運動軌跡。

雖然人工勢場法有很多優(yōu)點，但是在實際飛行中，環(huán)境比較復(fù)雜的時候，經(jīng)常出現(xiàn)障礙物在目標位置附近的情況，當無人機向目標點飛行時，F(xiàn)att減小Frep增大，此時會出現(xiàn)無人機在終點區(qū)域拐彎的情況;當無人機處在障礙物運動時，可能出現(xiàn)無人機處在合力為零點的情況，因而無人機不能到達目標點。

2 改進的人工勢場算法

將混沌理論全局搜索引入人工勢場法，搜索出更優(yōu)的引力勢場和斥力勢場系數(shù)，選擇出最適合本地圖的最優(yōu)系數(shù)組，例如當出現(xiàn)障礙物在目標點附近的時候，此障礙物斥力系數(shù)減小，就會減小無人機在目標點徘徊的幾率。當無人機處在地圖全局勢場的零點時，改變各個障礙物的斥力系數(shù)，避免了無人機處在全局勢場的零點的情況。

2.1 計算期望路線段與障礙物的相對位置關(guān)系

圖1 障礙物各個勢場系數(shù)分布Fig.1 Distribution of obstacles potential field coefficients

在多障礙物組合優(yōu)化求解中，如圖1所示，吸引力勢場設(shè)為K，各個障礙物斥力勢場系數(shù)分別設(shè)為K1，K2，K3，…，Kn。若K過大，算法的全局搜索最優(yōu)路徑的能力就會下降，并且有碰撞到障礙物的危險，若K過小，收斂速度會降低。經(jīng)過實驗可得，K的取值范圍在2～4內(nèi)為最佳。選好K值分布范圍后，引入混沌理論logistic映射對K值進行搜索，logistic映射是非線性方程中出現(xiàn)的一個能成功地進行實驗數(shù)學(xué)研究的不尋常的實例,它雖然簡單卻能體現(xiàn)出所有非線性現(xiàn)象的本質(zhì)。

假設(shè)機器人的位置為X=(x,y,z)，并且設(shè)Katth=K+&h，則目標位置與機器人之間的引力場為

(7)

式中:Katth為位置增益系數(shù)；XG為目標點的位置；K為增益系數(shù)；h為迭代次數(shù)；&h為擾動因子。

定義引力Fatt(X)為引力場的負梯度

(8)

式中:|X-XG|為無人機到目標點位置距離；K為引力增益系數(shù)的初始值。

&h作為增益系數(shù)取值用了混沌算法中的logistic映射[18]，logistic映射就是一個典型的混沌系統(tǒng),迭代公式如公式(9)所示：

(9)

式中控制參量μ=4，0≤&0≤1時，式(9)完全處于混沌狀態(tài)?？梢杂没煦邕\動特征進行目標優(yōu)化搜索,其基本思想是利用混沌變量取代優(yōu)化問題中變量進行搜索,混沌迭代方程可生成一組變量。在fatt(x)公式中加入的混沌擾動因子由式(10)產(chǎn)生,經(jīng)過式(10)的處理使&h取值為[-1,1]：

(10)

使用混沌算法的logistic映射,經(jīng)過式(9)、式(10)的處理使&h取值為[-1,1]，確定K的搜索方法。

2.2 改進的人工勢場法中吸引力勢場系數(shù)Kn調(diào)節(jié)策略

在多障礙物組合優(yōu)化求解中，在勢場模型法中勢場參數(shù)起著決定性的作用[19],各個障礙物斥力勢場中系數(shù)分別設(shè)為K1,K2,K3,…，Kn。經(jīng)多次實驗可得Kn的取值在1～3內(nèi)為最佳。綜合考慮算法的全局搜索能力和收斂速度，同理將logistic映射引入斥力勢場方程中去，即：

(11)

Kori為斥力系數(shù)初值，各個禁飛區(qū)與無人機之間的引力場為

(12)

(13)

式中：Krepnh為斥力增益系數(shù)；X-X0為移動的無人機與禁飛區(qū)或者障礙物的路徑長度；ρ0為影響距離；h為迭代次數(shù)；Frepn(X)為第n個障礙物的斥力負梯度。

將&h代入各個障礙物勢場式(3)與斥力式(4)可得：

(14)

(15)

此處再次使用混沌算法的logistic映射,經(jīng)過式(9)、式(10)的處理使&h取值為[-1,1] ，經(jīng)過式(11)確定了Kn的搜索方法。

2.3 改進人工勢場法流程

首先判斷無人機和目標點之間是否有障礙物，有障礙物時，設(shè)定n個障礙物斥力系數(shù)Kn和引力系數(shù)K值，進行計算，由合力公式得出下一步角度和步長，發(fā)生碰撞后重新設(shè)定新的障礙物斥力系數(shù)Kn和引力系數(shù)K值，到達目的地后開始新的迭代計算，直到達到設(shè)定的迭代次數(shù)停止，改進人工勢場法的流程如圖2所示。

圖2 改進人工勢場法的流程圖Fig.2 Flow chart of the improved algorithm

3 仿真結(jié)果與分析

在山地環(huán)境中評估和對比新舊人工勢場法，并在Matlab環(huán)境中實現(xiàn)。

數(shù)據(jù)設(shè)置如下：任務(wù)是從起點離開，到達目標點，飛行的空間是一個邊長為2 000 m的正方體，在3D的環(huán)境中設(shè)置大小不同的山峰，山峰的尺寸如表1所示。

設(shè)置混沌理論的人工勢場法參數(shù)Kori=3，進行了對比試驗：圖3為傳統(tǒng)的人工勢場法，雖然能到達目的地，但是出現(xiàn)了在狹窄路徑中徘徊和繞行半徑大的情況；圖4為改進后的人工勢場法，可以看出，無人機繞行半徑減小并且在路徑中沒有出現(xiàn)徘徊情況。

表1 山峰尺寸表

圖3 傳統(tǒng)的人工勢場法Fig.3 Criteria of the artificial potential field method

圖4 改進的人工勢場法Fig.4 Improved artificial potential field method

在傳統(tǒng)的人工勢場法中，K=3用時38.5 s，路徑長度2 839 m。在改進的人工勢場算法中，迭代7次，K值迭代表如表2所示，迭代結(jié)果如表3所示。

K值選取標準為路徑長度最短，用時最短的一組K值。從表2中選擇第3次迭代結(jié)果最優(yōu)系數(shù)組。由圖3可以看出，當有障礙物在目標點附近的時候，無人機路徑會在目標點附近徘徊，并且繞行障礙物時半徑偏大，算出來的路徑偏差大，改進后的算法對比原方法提高9%，計算速率提高了46%，并且路徑平滑，在目標點附近沒有徘徊。經(jīng)過仿真平臺的測試，在無人機飛行壁障無人機航跡規(guī)劃時，可以找出路徑平滑且安全的符合無人機飛行特點的路徑，適應(yīng)復(fù)雜環(huán)境，比傳統(tǒng)算法計算精度和效率高。

表2 勢場系數(shù)K值迭代數(shù)據(jù)

表3 迭代結(jié)果

4 結(jié) 語

本文在傳統(tǒng)人工勢場法的基礎(chǔ)上，采用改變勢場系數(shù)的方法，引入混沌理論logistic映射，改進了勢場公式，建立了混沌理論的人工勢場法。將障礙物的Kn值和吸引力的K值都控制在一定的范圍內(nèi)進行搜索，從而選擇出最優(yōu)系數(shù)組，改進了人工勢場法。通過分析和比較在復(fù)雜環(huán)境中的路線平滑度以及時間長度，證明了本方法可以更好的完成搜索任務(wù)。仿真結(jié)果顯示，改進后人工勢場法不僅提高了路徑的精確性和穩(wěn)定性，縮短了路徑長度和時間，而且還可以適應(yīng)復(fù)雜環(huán)境，避免無人機在目標點附近徘徊和陷入最小值的情況。通過多次迭代搜索的方法，提高了算法適應(yīng)復(fù)雜地圖的能力。因此，該方法能夠為無人機在復(fù)雜環(huán)境中的航跡規(guī)劃提供有效的計算方法，解決無人機飛行的實際問題，具有重要的科研意義和研究價值。

/References:

[1] 朱慶保,張玉蘭.基于柵格法的機器人路徑規(guī)劃蟻群算法[J].機器人,2005,27(2):132-136. ZHU Qingbao,ZHANG Yulan.An ant colony algorithm based on grid method for mobile robot path planning[J].Robot,2005,27(2):132-136.

[2] PARK M G, JEON J H, LEE M C. Obstacle avoidance for mobile robots using artificial potential field approach with simulated annealing [C]// IEEE International Symposium on Industrial Electronics. Washington DC： IEEE,2001:1530-1535.

[3] VELAGIC J, LACEVIC B, OSMIC N. Efficient path planning algorithm for mobile robot navigation with a local minima problem Solving[C]// IEEE International Conference on Industrial Technology.Washington DC:IEEE, 2006:2325-2330.

[4] NISSON N J. Principles of Artificial Intelligence[M].Palo Alto: Tioga Press,1980:355-358.

[5] STENTZ A. Optimal and efficient path planning for partially known environments[C]// IEEE International Conference on Robotics & Automation.Poscataway:IEEE,1994:3310-3317.

[6] LUMELSKY V, STEPANOVA. Path-planning strategies for a point mobile automation moving among stun known obstacles of arbitrary shape[J].Algorithmica,1987(2):403-430.

[7] KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[J]. International Journal of Robotics Research(IJRR),1986,5(1):90-98.

[8] 甄然,司超,吳學(xué)禮,等.基于改進粒子群算法的飛行器沖突解脫方法研究[J]. 河北科技大學(xué)學(xué)報,2016,37(5):491-496. ZHEN Ran, SI Chao, WU Xueli,et al.Aircraft conflict relief method based on improved particle swarm algorithm research[J].Journal of Hebei University of Science and Technology, 2016, 37(5):491-496.

[9] PARK M G, JEON J H,LEE M C. Obstacle avoidance for mobile robots using artificial potential fieldapproach with simulated an nealing[C]// IEEE International Symposium on Industrial Electronics. South Korea:IEEE,2001:1530-1535．

[10]FAZLI S,KLEEMAN L. Wall following and obstacle avoidance results from a mulita-DSP sonar ring on a mobile robot[C]// Mechatronics & Automation, IEEE International Conference.Niagara Falls:IEEE,2005:432-437.

[11]程擁強，蔣平，朱勁，等．用勢場法改進的極限環(huán)導(dǎo)航方法在移動機器人中的應(yīng)用[J]．機器人，2004，26(2)：133-138． CHENG Yongqiang, JIANG Ping, ZHU Jin, et al.Improvement of limit cycle by potential field method application in mobile robot navigation method [J].Robot,2004,26(2):133-138．

[12]羅乾又，張華，王姮，等. 改進人工勢場法在機器人無人機航跡規(guī)劃中的應(yīng)用[J].計算機工程與設(shè)計, 2011, 32(4):1411-1418. LUO Qianyou, ZHANG Hua, WANG Yuan, et al. Improved artificial potential field method in the application of robot unmanned aerial vehicle (uav) flight path planning[J].Computer Engineering and Design,2011,32(4:):1411-1418.

[13] 胥小波，鄭康鋒，李丹，等．新的混沌粒子群優(yōu)化算法[J].通信學(xué)報，2012，33(1):24-37. XU Xiaobo, ZHENG Kangfeng, LI Dan, et al.New chaos-particle swarm optimizationalgorithm[J]. Journal on Communications, 2012,33(1):24-37.

[14]王翔，李志勇，許國藝，等.基于混沌局部搜索算子的人工蜂群算法[J].計算機應(yīng)用,2012,32(4):1033-1036. WANG Xiang, LI Zhiyong, XU Guoyi, et al. The artificial colony algorithm based on chaotic local search operator [J]. Journal of Computer Applications, 2012,32(4):1033-1036.

[15]周燕,劉培玉,趙靜,等.基于自適應(yīng)慣性權(quán)重的混沌粒子群算法[J].山東大學(xué)學(xué)報,2012,47(30):1-6. ZHOU Yan, LIU Peiyu, ZHAO Jing, et al. Chaotic particle swarm algorithm based on adaptive inertia weight [J]. Journal of Shandong University, 2012,47(30):1-6.

[16]黃凱,周永權(quán).帶交尾行為的混沌人工螢火蟲優(yōu)化算法[J].計算機科學(xué),2012,39(3):231-234. HUANG Kai, ZHOU Yongquan.With the chaotic artificial firefly mating behavior optimization algorithm [J]. Computer Science, 2012,39(3):231-234.

[17]倪天偉,江紅,林金珠.基于改進人工勢場法的移動機器人避障無人機航跡規(guī)劃算法[J].常州大學(xué)學(xué)報，2016,28(5):74-77. NI Tianwei, JIANG Hong, LIN Jinzhu. Based on improved artificial potential field method of mobile robot obstacle avoidance unmanned aerial vehicle (UAV) route planning algorithm[J]. Journal of Changzhou University, 2016,28(5):74-77.

[18]劉曉瑩.混沌蟻群算法在多機器人任務(wù)規(guī)劃中的應(yīng)用研究[D].南京:中南大學(xué),2010. LIU Xiaoying.Chaos Ant Colony Algorithm in The Application of Multi-robot Task Planning Research[D]. Nanjing: Central South University, 2010.

[19]翟紅生,王佳欣.基于人工勢場的機器人動態(tài)路徑規(guī)劃新方法[J].重慶郵電大學(xué)學(xué)報(自然科版),2015,27(6):814-818. ZHAI Hongsheng, WANG Jiaxin. Dynamic path planning research for mobile robot basedon artificial potential field[J]. Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition), 2015, 27(6):814-818.

[20] 田子建,高學(xué)浩.基于改進人工勢場法的救災(zāi)機器人路徑規(guī)劃[J].工礦自動化，2016,42(9):37-42. TIAN Zijian, GAOXuehao. Path planning of rescuing robot based on improved artificial field method[J]. Industrial Automation, 2016, 42(9):37-42.

An improved route planning algorithm for unmanned aerial vehicle based on artificial potential field

ZHEN Ran1,2, ZHEN Shibo1,2, WU Xueli1,2

(1.School of Electrical Engineering, Hebei University of Science and Technology, Shijiazhuang, Hebei 050018, China;2.Hebei Provincial Research Center for Technologies in Process Engineering Automation, Shijiazhuang, Hebei 050018, China)

In order to improve the precision and accuracy of artificial potential field, and avoid the situation of hovering on the end point and being caught in minimum value, a path planning algorithm based on artificial potential algorithm for unmanned aerial vehicle is presented. The traditional artificial potential field method is improved: chaos theory is used to improve artificial potential field calculation formula, which changes the potential field coefficients of each barrier and target point, resulting in the best screened out route. The simulation experimental analysis and result show that the optimized algorithm considers the influence of obstacles to the optimization process, ruling out the situation of hovering on the end point in unmanned aerial vehicle route planning, and through iterative method, the algorithm has the ability to adapt to different maps. The improved artificial potential field method is better than the traditional artificial potential field method in speed and precision aspects.

robot control; unmanned aerial vehicle; artificial potential field method; route planning; chaos theory

1008-1542(2017)03-0278-07

10.7535/hbkd.2017yx03010

2017-01-10；

2017-04-26；責(zé)任編輯：李 穆

河北省自然科學(xué)基金(F2015208128，F(xiàn)2014208119)；河北省教育廳青年基金(QN20140157，BJ2016020)

甄 然(1971—)，女，河北安國人，教授，博士，主要從事復(fù)雜工業(yè)控制方面的研究。

E-mail: 343691960@qq.com

TP273.V19

A

甄 然，甄士博，吳學(xué)禮.一種基于人工勢場的無人機航跡規(guī)劃算法 [J].河北科技大學(xué)學(xué)報,2017,38(3):278-284. ZHEN Ran,ZHEN Shibo, WU Xueli.An improved route planning algorithm for unmanned aerial vehicle based on artificial potential field[J].Journal of Hebei University of Science and Technology,2017,38(3):278-284.