﻿ 融合简化稀疏A<sup>*</sup>算法与模拟退火算法的无人机航迹规划
 计算机系统应用  2019, Vol. 28 Issue (4): 25-31 PDF

1. 中国科学技术大学 微电子学院, 合肥 230026;
2. 中国科学院 半导体研究所, 北京 100083;
3. 中国科学院大学, 北京 100049;
4. 中国科学院 脑科学与智能技术卓越创新中心, 上海 200031;
5. 半导体神经网络智能感知与计算技术北京市重点实验室, 北京 100083

UAV Path Planning Based on Fusion of Simplified Sparse A* Algorithm and Simulated Annealing Algorithm
YANG Yu1,2, JIN Min2, LU Hua-Xiang2,3,4,5
1. School of Microelectronics, University of Science and Technology of China, Hefei 230026, China;
2. Institute of Semiconductors, Chinese Academy of Sciences, Beijing 100083, China;
3. University of Chinese Academy of Sciences, Beijing 100049, China;
4. Center for Excellence in Brain Science and Intelligence Technology, Chinese Academy of Sciences, Shanghai 200031, China;
5. Semiconductor Neural Network Intelligent Perception and Computing Technology Beijing Key Lab, Beijing 100083, China
Foundation item: CAS Strategic Priority Program (Category A) (XDA18040400); National Natural Science Foundation of China (61701473)
Abstract: To solve the UAV path planning problem, a method based on Fusion of Simplified Sparse A* algorithm and Simulated Annealing algorithm (FSSA-SA) is proposed. Firstly, after modeling the threat environment, the simulated annealing idea is combined with the solution of the specific route planning problem, and the concrete design and implementation method of the simulated annealing algorithm is given. Secondly, the simplified sparse A* algorithm is used to search the roundtrip tracks between the start point and the end point, and the better one of the results will be used as the initial solution of the simulated annealing algorithm to realize the fusion of the two algorithms. Then, when annealing proceeds to the low temperature region, the solution quality of the algorithm is further improved by eliminating the redundant track nodes. Finally, in order to verify the superiority of the proposed algorithm, the simulation experiments are carried out with sparse A* algorithm and simulated annealing algorithm. The experimental results show that the proposed FSSA-SA algorithm has less planning time-consuming than the two algorithms mentioned above; compared with the sparse A* algorithm, the memory occupied by the FSSA-SA algorithm is two orders of magnitude less when the synthetic cost of the obtained track is not too different; compared with the simulated annealing algorithm, under the same annealing conditions, the integrated cost of the planned track is reduced by about 35% on average.
Key words: UAV     path planning     fusion     sparse A* algorithm     simulated annealing algorithm

1 航迹规划问题建模 1.1 威胁建模

 $p = \left\{ \begin{array}{l} 1\;\;\;\;\;\;\;\;\;(d \le {R_{\rm{min}}})\\ f(d)\;\;\;({R_{\rm{min}}} < d \le {R_{\rm{max}}})\\ 0\;\;\;\;\;\;\;\;\;({R_{\rm{max}}} < d) \end{array} \right.$ (1)

 ${p_M} = {p_A} = f(d) = 1/d$ (2)
 ${p_R} = f(d) = 1/{d^4}$ (3)
 ${p_T} = f(d) = \frac{{{R_{\rm{max}}} - d}}{{{R_{\rm{max}}} - {R_{\rm{min}}}}}$ (4)

1.2 无人机自身的约束

1.3 综合代价函数

 $E = \int_0^L {{a_1}{e_t} + {a_2}{e_l}ds = {a_1}{E_t} + {a_2}{E_l}}$ (5)

 ${E_l} = {\omega _l}\sum\limits_{i = 1}^{n - 1} {{l_{i,i + 1}}}$ (6)

 ${E_t} = \sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = 1}^5 {{P_{i,i + 1,j}}} }$ (7)

2 基于模拟退火算法的航迹规划 2.1 模拟退火算法基本原理

 ${P_t}({x_i} \to {x_{i + 1}}) = \left\{ \begin{array}{l} 1,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\Delta E < 0\\ \exp ( - \beta \Delta E),\;\;\;\Delta E > 0 \end{array} \right.$ (8)

2.2 模拟退火算法的实现 2.2.1 模拟退火算法

(1) 设置起始温度倒数β0和终止温度倒数β1以及退火温度表长度nsweeps的值, 以 ${\beta _1} - {\beta _0}/nsweeps$ 的值为间距产生退火温度表.

(2) 随机的在规划空间中产生连接起始点和终点的初始航迹, 计算相应的综合代价值, 并将β设置为起始值.

(3) 在当前温度下, 沿着从起点到终点的方向, 依次对除航迹起始点、终点以外的每一个中间节点进行扰动操作, 并计算该次扰动产生的新解对应的ΔE. 如果 $\Delta E < 0$ , 或 $\Delta E > 0$ $u < \exp ( - \beta \Delta E)$ , 则接受此新解; 否则不接受, 并将下一节点作为新的扰动目标.

(4) 如果对所有中间节点都完成了步骤(3)中所述操作, 则转步骤(5), 否则继续对剩余节点进行未完成的操作.

(5) 将温度表中的下一个值赋值给β, 并判断是否到达终止值β1, 若是则终止算法, 输出最终结果. 否则, 转步骤(3).

2.2.2 新解的产生以及ΔE的计算

 图 1 新解产生示意图

 $\begin{array}{l} \left\{ \begin{array}{l} {x_{new}} = {x_{old}} \pm k \times b,\;\;\;\;\mu < 0.5{\text{时为}} + \\ {y_{new}} = {y_{old}} \mp b,\;\;\;\;\;\;\;\;\;\;\mu < 0.5{\text{时为}} - \; \end{array} \right.\\ \left\{ \begin{array}{l} k = \dfrac{{{y_1} - {y_2}}}{{{x_1} - {x_2}}}\\ b = {d_s}\sqrt {\frac{1}{{{k^2} + 1}}} \end{array} \right. \end{array}$

 $\left\{ \begin{array}{l} {x_{new}} = {x_{old}} \pm {d_s},\;\;\;\;\mu < 0.5{\text{时为}}+\\ {y_{new}} = {y_{old}} \end{array} \right.$

 $\Delta E = ({e_3} + {e_4}) - ({e_1} + {e_2})$ (9)

3 模拟退火算法与简化稀疏A*算法的融合 3.1 FSSA-SA算法和简化的稀疏A*算法

 图 2 稀疏A*算法节点扩展示意图

(1) 设置好搜索步长、相应角度参数、代价参数.

(2) 以起始点为当前点, 将终点的方向假定为此时前进的方向, 产生扩展节点.

(3) 分别计算各扩展节点对应的f(n). 选择具有最小f(n)值的节点作为新的当前点.

(4) 判断当前节点距离终点的距离是否小于等于一个步长, 若是, 则将终点加入航迹中, 算法结束. 否则转至步骤(5).

(5) 利用前一航迹节点和当前点以所确定的方向, 产生新的扩展节点, 转至步骤(3).

 图 3 简化稀疏A*算法调换起始点前后的规划结果图

3.2 对FSSA-SA算法中位置冗余节点的剔除

4 仿真结果及分析

 图 4 第一次仿真规划结果示意图

 图 5 第二次仿真规划结果示意图

5 结束语

 [1] Liu LF, Shi RX, Li SD, et al. Path planning for UAVS based on improved artificial potential field method through changing the repulsive potential function. Proceedings of 2016 IEEE Chinese Guidance, Navigation and Control Conference (CGNCC). Nanjing, China. 2016. 2011–2015. [2] 胡中华, 赵敏, 姚敏, 等. 无人机航迹规划技术研究及发展趋势. 航空电子技术, 2009, 40(2): 24-29, 36. DOI:10.3969/j.issn.1006-141X.2009.02.006 [3] Qi Z, Shao ZH, Ping YS, et al. An improved heuristic algorithm for UAV path planning in 3D environment. Proceedings of the Second International Conference on Intelligent Human-Machine Systems and Cybernetics. Nanjing, China. 2010. 258–261. [4] Li H, Fu Y, Elgazzar K, et al. Path planning for multiple Unmanned Aerial Vehicles using genetic algorithms. Proceedings of 2009 Canadian Conference on Electrical and Computer Engineering. St. John’s, NL, Canada. 2009. 1129–1132. [5] 白俊强, 柳长安. 基于蚁群算法的无人机航路规划. 飞行力学, 2005, 23(2): 9-12. [6] Lin MX, Yuan K, Shi CZ, et al. Path planning of mobile robot based on improved A* algorithm. Proceedings of the 29th Chinese Control and Decision Conference. Chongqing, China. 2017. 3570–3576. [7] 王维, 裴东, 冯璋. 改进A*算法的移动机器人最短路径规划 . 计算机应用, 2018, 38(5): 1523-1526. [8] 姚雨, 李庆, 陈曦. 优化的A*算法在航迹规划上的应用 . 微电子学与计算机, 2017, 34(7): 51-55. [9] 何平川, 戴树岭. 一种改进的UAV三维航迹实时规划算法. 北京航空航天大学学报, 2010, 36(10): 1248-1251. [10] 王雷, 李明, 蔡劲草, 等. 改进遗传算法在移动机器人路径规划中的应用研究. 机械科学与技术, 2017, 36(5): 711-716. [11] 赖智铭, 郭躬德. 基于自适应阈值蚁群算法的路径规划算法. 计算机系统应用, 2014, 23(2): 113-118, 59. DOI:10.3969/j.issn.1003-3254.2014.02.019 [12] Aarts E, Korst J. Simulated Annealing and Boltzmann Machines. Chichester: Wiley, 1989. [13] 胡中华. 基于智能优化算法的无人机航迹规划若干关键技术研究[博士学位论文]. 南京: 南京航空航天大学, 2011. [14] 赵毓. 基于群体智能算法的无人机航迹规划研究[硕士学位论文]. 哈尔滨: 哈尔滨工业大学, 2016. [15] Kirkpatrick S, Gelatt CD Jr, Vecchi MP. Optimization by simulated annealing. Science, 1983, 220(4598): 671-680. DOI:10.1126/science.220.4598.671 [16] 耿修堂, 吴勇, 许进. 基于禁忌退火算法的巡航导弹航迹规划. 火力与指挥控制, 2009, 34(11): 43-47. DOI:10.3969/j.issn.1002-0640.2009.11.012 [17] Szczerba RJ, Galkowski P, Glicktein IS, et al. Robust algorithm for real-time route planning. IEEE Transactions on Aerospace and Electronic Systems, 2000, 36(3): 869-878. DOI:10.1109/7.869506 [18] 何雨枫, 曾庆化, 王云舒, 等. 室内微型飞行器实时路径规划算法研究. 电子测量技术, 2014, 37(2): 23-27. DOI:10.3969/j.issn.1002-8978.2014.02.007