一种基于人工势场的无人机航迹规划算法

甄 然，甄士博，吴学礼

(1.河北科技大学电气工程学院，河北石家庄 050018；2.河北省生产过程自动化工程技术研究中心，河北石家庄 050018)

一种基于人工势场的无人机航迹规划算法

甄 然1,2，甄士博1,2，吴学礼1,2

(1.河北科技大学电气工程学院，河北石家庄 050018；2.河北省生产过程自动化工程技术研究中心，河北石家庄 050018)

为了改进传统的人工势场法不能适应复杂环境、容易陷入最小值和在终点附近徘徊的情况，提出一种基于混沌理论的人工势场法的无人机航迹规划算法。在传统人工势场法原理的基础上，将混沌理论的搜索算法引入人工势场法中的斥力场、引力场的函数公式中，改变了各个障碍物斥力系数和目标点的引力系数，将改变后的系数代入计算，搜索出斥力场和引力场的最优系数组。本算法有如下优点:第一，考虑了障碍物对寻优过程的影响，排除了合力为零的情况。第二，通过迭代的方法，具有适应不同地图的能力。第三，适用于无人机的航迹规划。仿真实验结果和理论分析表明，混沌理论的人工势场法不仅解决了无人机在航迹规划中容易陷入最小值和在终点附近徘徊等问题，而且可以实现无人机在复杂环境下的航迹规划，缩短了飞行成本，节约了计算时间，提高了三维空间无人机航迹规划的速度和精度。

机器人控制；无人机；人工势场法；航迹规划；混沌理论

无人机的航迹规划是无人机研究领域的一个重要组成部分[1]，无人机技术的发展，对无人机航迹规划提出了越来越高的要求。无人机航迹规划的任务是在具有障碍物的环境中，按照一定的评价系统，寻找一条从起始位置到达目标位置的无碰撞的路径[2-3]，目前提出的常用算法有A*算法[4]、D*算法[5]、Bug1算法、Bug2算法[6]、人工势场法[7]，还有须满足限制条件的粒子群算法[8]等。其中人工势场法包容性好，方便快捷，可以和很多方法结合，实现无人机的实时控制。但其也有不能适应复杂环境的缺点，比如在狭窄环境中路径摆动，障碍物附近目标不可达，容易陷入最小值等。

针对这些情况，文献[9]提出了按着沿墙走的轨迹来环绕障碍物解决目标点不可达的情况；文献[10]提出了极限环法，通过环绕障碍物的方法让无人机走圆弧状路径，达到避障的目的；文献[11]采用连锁网络方法减小无规则碰撞现象。上述方法虽然在一定程度上避免了算法陷入局部最小值等情况，但仍存在着不能适应复杂环境,在狭窄环境徘徊的缺点。

人工势场算法之所以无法适应复杂的环境，是因为斥力场系数、引力场系数在计算时是固定不变的，本文提出了一种基于混沌理论的人工势场法，将混沌理论全局搜索引入人工势场法，搜索出更优的引力场和斥力场系数，从而发挥出人工势场法的潜力。最近，研究人员将各种混沌优化算法[13-16]应用于路径规划算法中，其基本思想：解空间是从无序空间变换到的，利用混沌变量，发掘共性、随机性和规律性的特点，进行全局搜索。混沌优化方法具有全局渐近收敛、易跳出局部极小点和收敛速度快等特点，与人工势场算法很容易结合。改进的人工势场法的基本思路是：在传统人工势场法无人机航迹规划基础上，通过混沌理论改变障碍物和目标点的斥力和引力，从而搜索出更优路径。

1 人工势场法基本原理

人工势场法的实质是对无人机的飞行区域人为地定义势场[17]，该势场为地图中出现的障碍物斥力场和终点引力场的向量叠加。传统人工势场的定义如下:

假设无人机的位置为X=(x,y,z)，则目标点引力场与无人机电子之间的电势场为

(1)

式中:Katt为势场增益系数;XG为目标点的位置。

定义Fatt(X)为引力势场的引力,

(2)

定义障碍物的斥力势场为

(3)

定义障碍物的斥力为

(4)

式中：Frep为障碍物对无人机的斥力势场系数；X-X0的单位是m，表示移动的无人机到各个障碍物的动态距离；ρ0为障碍物的影响距离。所以移动的无人机像一个电子一样，它的总势场为无人机与障碍物各个势场的和：

(5)

对无人机的作用力Ftotal为

(6)

由式(6)可以算出无人机的下一步运动轨迹。

虽然人工势场法有很多优点，但是在实际飞行中，环境比较复杂的时候，经常出现障碍物在目标位置附近的情况，当无人机向目标点飞行时，Fatt减小Frep增大，此时会出现无人机在终点区域拐弯的情况;当无人机处在障碍物运动时，可能出现无人机处在合力为零点的情况，因而无人机不能到达目标点。

2 改进的人工势场算法

将混沌理论全局搜索引入人工势场法，搜索出更优的引力势场和斥力势场系数，选择出最适合本地图的最优系数组，例如当出现障碍物在目标点附近的时候，此障碍物斥力系数减小，就会减小无人机在目标点徘徊的几率。当无人机处在地图全局势场的零点时，改变各个障碍物的斥力系数，避免了无人机处在全局势场的零点的情况。

2.1 计算期望路线段与障碍物的相对位置关系

图1 障碍物各个势场系数分布Fig.1 Distribution of obstacles potential field coefficients

在多障碍物组合优化求解中，如图1所示，吸引力势场设为K，各个障碍物斥力势场系数分别设为K1，K2，K3，…，Kn。若K过大，算法的全局搜索最优路径的能力就会下降，并且有碰撞到障碍物的危险，若K过小，收敛速度会降低。经过实验可得，K的取值范围在2～4内为最佳。选好K值分布范围后，引入混沌理论logistic映射对K值进行搜索，logistic映射是非线性方程中出现的一个能成功地进行实验数学研究的不寻常的实例,它虽然简单却能体现出所有非线性现象的本质。

假设机器人的位置为X=(x,y,z)，并且设Katth=K+&h，则目标位置与机器人之间的引力场为

(7)

式中:Katth为位置增益系数；XG为目标点的位置；K为增益系数；h为迭代次数；&h为扰动因子。

定义引力Fatt(X)为引力场的负梯度

(8)

式中:|X-XG|为无人机到目标点位置距离；K为引力增益系数的初始值。

&h作为增益系数取值用了混沌算法中的logistic映射[18]，logistic映射就是一个典型的混沌系统,迭代公式如公式(9)所示：

(9)

式中控制参量μ=4，0≤&0≤1时，式(9)完全处于混沌状态。可以用混沌运动特征进行目标优化搜索,其基本思想是利用混沌变量取代优化问题中变量进行搜索,混沌迭代方程可生成一组变量。在fatt(x)公式中加入的混沌扰动因子由式(10)产生,经过式(10)的处理使&h取值为[-1,1]：

(10)

使用混沌算法的logistic映射,经过式(9)、式(10)的处理使&h取值为[-1,1]，确定K的搜索方法。

2.2 改进的人工势场法中吸引力势场系数Kn调节策略

在多障碍物组合优化求解中，在势场模型法中势场参数起着决定性的作用[19],各个障碍物斥力势场中系数分别设为K1,K2,K3,…，Kn。经多次实验可得Kn的取值在1～3内为最佳。综合考虑算法的全局搜索能力和收敛速度，同理将logistic映射引入斥力势场方程中去，即：

(11)

Kori为斥力系数初值，各个禁飞区与无人机之间的引力场为

(12)

(13)

式中：Krepnh为斥力增益系数；X-X0为移动的无人机与禁飞区或者障碍物的路径长度；ρ0为影响距离；h为迭代次数；Frepn(X)为第n个障碍物的斥力负梯度。

将&h代入各个障碍物势场式(3)与斥力式(4)可得：

(14)

(15)

此处再次使用混沌算法的logistic映射,经过式(9)、式(10)的处理使&h取值为[-1,1] ，经过式(11)确定了Kn的搜索方法。

2.3 改进人工势场法流程

首先判断无人机和目标点之间是否有障碍物，有障碍物时，设定n个障碍物斥力系数Kn和引力系数K值，进行计算，由合力公式得出下一步角度和步长，发生碰撞后重新设定新的障碍物斥力系数Kn和引力系数K值，到达目的地后开始新的迭代计算，直到达到设定的迭代次数停止，改进人工势场法的流程如图2所示。

图2 改进人工势场法的流程图Fig.2 Flow chart of the improved algorithm

3 仿真结果与分析

在山地环境中评估和对比新旧人工势场法，并在Matlab环境中实现。

数据设置如下：任务是从起点离开，到达目标点，飞行的空间是一个边长为2 000 m的正方体，在3D的环境中设置大小不同的山峰，山峰的尺寸如表1所示。

设置混沌理论的人工势场法参数Kori=3，进行了对比试验：图3为传统的人工势场法，虽然能到达目的地，但是出现了在狭窄路径中徘徊和绕行半径大的情况；图4为改进后的人工势场法，可以看出，无人机绕行半径减小并且在路径中没有出现徘徊情况。

表1 山峰尺寸表

图3 传统的人工势场法Fig.3 Criteria of the artificial potential field method

图4 改进的人工势场法Fig.4 Improved artificial potential field method

在传统的人工势场法中，K=3用时38.5 s，路径长度2 839 m。在改进的人工势场算法中，迭代7次，K值迭代表如表2所示，迭代结果如表3所示。

K值选取标准为路径长度最短，用时最短的一组K值。从表2中选择第3次迭代结果最优系数组。由图3可以看出，当有障碍物在目标点附近的时候，无人机路径会在目标点附近徘徊，并且绕行障碍物时半径偏大，算出来的路径偏差大，改进后的算法对比原方法提高9%，计算速率提高了46%，并且路径平滑，在目标点附近没有徘徊。经过仿真平台的测试，在无人机飞行壁障无人机航迹规划时，可以找出路径平滑且安全的符合无人机飞行特点的路径，适应复杂环境，比传统算法计算精度和效率高。

表2 势场系数K值迭代数据

表3 迭代结果

4 结 语

本文在传统人工势场法的基础上，采用改变势场系数的方法，引入混沌理论logistic映射，改进了势场公式，建立了混沌理论的人工势场法。将障碍物的Kn值和吸引力的K值都控制在一定的范围内进行搜索，从而选择出最优系数组，改进了人工势场法。通过分析和比较在复杂环境中的路线平滑度以及时间长度，证明了本方法可以更好的完成搜索任务。仿真结果显示，改进后人工势场法不仅提高了路径的精确性和稳定性，缩短了路径长度和时间，而且还可以适应复杂环境，避免无人机在目标点附近徘徊和陷入最小值的情况。通过多次迭代搜索的方法，提高了算法适应复杂地图的能力。因此，该方法能够为无人机在复杂环境中的航迹规划提供有效的计算方法，解决无人机飞行的实际问题，具有重要的科研意义和研究价值。

/References:

[1] 朱庆保,张玉兰.基于栅格法的机器人路径规划蚁群算法[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] 甄然,司超,吴学礼,等.基于改进粒子群算法的飞行器冲突解脱方法研究[J]. 河北科技大学学报,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]程拥强，蒋平，朱劲，等．用势场法改进的极限环导航方法在移动机器人中的应用[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]罗乾又，张华，王姮，等. 改进人工势场法在机器人无人机航迹规划中的应用[J].计算机工程与设计, 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] 胥小波，郑康锋，李丹，等．新的混沌粒子群优化算法[J].通信学报，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].计算机应用,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]周燕,刘培玉,赵静,等.基于自适应惯性权重的混沌粒子群算法[J].山东大学学报,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]黄凯,周永权.带交尾行为的混沌人工萤火虫优化算法[J].计算机科学,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]倪天伟,江红,林金珠.基于改进人工势场法的移动机器人避障无人机航迹规划算法[J].常州大学学报，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]刘晓莹.混沌蚁群算法在多机器人任务规划中的应用研究[D].南京:中南大学,2010. LIU Xiaoying.Chaos Ant Colony Algorithm in The Application of Multi-robot Task Planning Research[D]. Nanjing: Central South University, 2010.

[19]翟红生,王佳欣.基于人工势场的机器人动态路径规划新方法[J].重庆邮电大学学报(自然科版),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] 田子建,高学浩.基于改进人工势场法的救灾机器人路径规划[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；责任编辑：李 穆

河北省自然科学基金(F2015208128，F2014208119)；河北省教育厅青年基金(QN20140157，BJ2016020)

甄 然(1971—)，女，河北安国人，教授，博士，主要从事复杂工业控制方面的研究。

E-mail: 343691960@qq.com

TP273.V19

A

甄 然，甄士博，吴学礼.一种基于人工势场的无人机航迹规划算法 [J].河北科技大学学报,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.