转自：无人机   

作者：张宏宏，甘旭升，毛 亿，杨春林，谢晓伟

运行中的无人机一旦检测到飞行冲突，立即解算避障路径，并驱动机体按照安全路径运行。当前避障技术主要分为三类：基于优化、势场和机器学习的避障方法。

2.1 基于优化的避障方法

基于优化的避障方法思想源于最优控制[6]，是根据已建立的无人机时域数学模型或频域数学模型，选择一个容许的控制律，使无人机按照约束的条件运行，并使某一性能指标达到最优的过程。其特点在于从整个冲突态势的演绎全局来考虑问题，可用各类数值计算与现代优化方法求解规避障碍的路径。

2.1.1 数学优化算法

针对已建立的无人机避障模型，可利用各类数学优化算法将最优控制问题转化为便于求解的模型，从而生成解脱路径。

(1)非线性优化方法

性能指标或约束条件中包含非线性函数的问题称为非线性优化问题，当前用于无人机避障的非线性优化方法有梯度下降法、二次规划法、凸优化法等。陈伟锋等[7]将避障问题转化为最优控制命题形式，提出一种基于析取关系直接变换的动态联立求解方法，并用Radau配置点的拉格朗日插值对最优控制模型进行离散化处理，并通过对比验证了方法的有效性。付其喜等[8]将无人机额外飞行距离作为优化函数，首先基于随机并行梯度下降法(Stochastic Parallel Gradient Descent, SPGD)对初始解脱可行解进行计算，再利用序列二次规划(Sequential Quadratic Programming, SQP)求解最优解脱航向。王祝等[9]将无人机避障非凸问题转化成一系列近似凸优化子问题，利用凸优化法进行求解，得到兼具时效性与最优性的解脱路径。

(2)混合整数线性/非线性规划(Mixed Integer Linear/Nonlinear Programming, MILP/MINLP)

混合整数线性规划方法是用整数约束无人机的控制指令(速度、航向)，进而通过线性规划的方法对最优航路进行计算。Radmanesh等[10] 提出一种有限范围内的动态混合整数线性规划算法，降低了航路规划计算量。Turnbull等[11]提出基于MILP-MPC的避撞航路规划算法，对语言决策树进行训练，训练后的模型被用于实时航路规划。Sarim等[12]在粗略航路规划的前提下，利用MILP对航路进行精细处理，生成最优避障路径。Alonso-Ayuso等[13]利用多次滚动时域方法将消解问题转化为混合整数非线性规划问题，并进一步线性化为MILP模型，实现速度调整进行避障。张启钱等[14]基于序列混合整数线性规划，提出同时可以选择调速、调向与调高的序列混合整数线性优化(Sequential Mixed Integer Linear Optimization-Velocity Change, Turn Change and Altitude Change, SMILO-VTAC)模型，解决了复杂低空多机冲突解脱问题。采俊玲等[15]采用航向-速度解脱策略结合的混合整数非线性规划(MINLP)模型，实现空域内航空器的避障。

(3)动态规划法(Dynamic Programming, DP)

动态规划的核心是基于贝尔曼最优性原理，根据基本递推关系式，不断转移决策过程，将最优化问题转化为多步决策问题。Denton等[16]将动态规划与树形搜索结合，计算出三维最优地形回避航路。Sunberg等[17]将多无人机冲突消解问题转化为近似动态规划问题进行求解。Bousson[18]利用单网格点动态规划，对飞行器避撞问题进行最优化求解。

基于数学优化方法的避障路径求解模型较为直观，易于理解，但当约束条件较为复杂时，求解难度增大，计算量增加，不能满足实时性要求。常见的基于数学优化方法的避障算法适用场景与优缺点如表1所示。

表1 数学优化算法

Table 1 Mathematical optimization algorithm

2.1.2 启发式算法

启发式算法是在可接受的计算成本下，对近似最优解进行搜索的优化算法，在基于路径规划的避障领域应用广泛，主要有群智能算法、A*、D*等。

智能算法是基于仿生学计算原理，模拟群体生物行为协同搜索空间最优解的过程。对于高纬度、非线性、多约束的最优化问题，往往能够收敛到最优值。在无人机路径规划中应用广泛，同时也相应解决了无人机避障问题。常用算法有粒子群算法、遗传算法、蚁群算法、人工蜂群算法、布谷鸟算法等。

(1)粒子群算法(Particle Swarm Optimization, PSO)

粒子群算法是模拟自然界中鸟群觅食现象，通过种群迭代更新粒子位置和速度进行搜索空间最优解[19]。Tang等[20]将多智能粒子滤波器用在未知环境路径规划求解上，降低了计算量。Zhuang等[21]将PSO与勒让德伪谱法结合，寻找更适合无人机运行的轨迹。Yan等[22]将PSO与路径点制导算法结合，生成低功耗、更平滑的避撞路径。Lim等[23]将PSO与量子物理结合，提出量子-粒子群优化算法(Quantum Behavior Particle Swarm Optimization, QPSO)生成光滑的无人机可飞路径，同时降低计算量、提升效率。

(2)遗传算法(Genetic Algorithm, GA)

遗传算法是模拟自然界遗传机理以及生物进化过程，通过基因的选择、交叉、变异等操作，实现对最优值的搜索[24]。余文曌等[25]将GA与弹性网络结合，降低搜索空间，提高搜索效率。Yan等[26]对GA模型进行改进，可以生成满足航空器性能约束的解脱路径，降低运行能耗。何光勤等[27]将GA应用在三维空间内的避障，将惩罚函数代入性能指标中，求解出的解脱路径光滑性较好，适合航空器运行。

(3)蚁群算法(Ant Colony Optimization, ACO)

蚁群算法是模拟自然界中蚂蚁觅食的生物行为而提出来的一种最优化搜索算法，具有并行计算、鲁棒性好的特点，在无人机避障领域应用广泛[28]。Wu等[29]将回退、死亡两种策略加入到ACO中，促使蚂蚁以更大概率达到最优目标位置，优化了算法搜索能力。Jiao等[30]提出了基于自适应状态转移策略和自适应信息素更新策略的改进ACO算法，强化信息素强度、启发信息对算法迭代优化过程的重要作用，提高了算法全局寻优性。Luo等[31]提出将信息素的优劣区分开，除去正常的信息素更新迭代，额外强化效果好的信息素，对提升算法收敛性起到一定作用。张宏宏[28]等基于分割法，以时间换取空间，提高了蚁群算法的搜索能力。

(4)人工蜂群算法(Artificial Bee Colony Algorithm, ABC)

人工蜂群算法是模拟蜜蜂行为而提出的一种优化算法。Kang等[32]在蜂群采蜜阶段加入Rosenbrock旋转方向法，避免了算法早熟收敛，准备率也有一定提升。王渊等[33]在传统ABC算法的基础上，改进了跟随蜂对雇佣蜂的选择概率，用最优解引导迭代方向，保证算法跳出局部最优解。Contreras-Cruz M A等[34]将ABC算法与进化算法结合，先由ABC算法进行局部搜索，再由进化算法得出最优解脱路径。Li等[35]将平衡性策略应用到传统ABC算法中，在局部与全局之间实现平衡。

此外，还有一些智能算法被用在无人机路径规划上，实现避障，如布谷鸟算法(Cuckoo Search, CS)[36]、鲸鱼优化算法(Whale Optimization Algorithm, WOA)[37]、蚁狮算法(Ant Lion Optimizer, ALO)[38]、鸽群算法(Pigeon-Inspired Optimization, PIO)[39]、萤火虫算法(Firefly Algorithm, FA)[40]、乌贼算法[41]等。

(5)A*/D*算法

A*算法是一种图搜索算法，将启发信息因素引入待求解问题目标信息中，使得搜索方向更加精准，降低收敛时间。A*算法支付代价为f(n)=g(n)+h(n)，其中g(n)表示航路代价，h(n)表示预测代价。在搜索过程中，将支付代价最小的节点插入路径链表中，完成对障碍物的规避。马云红等[42]采用变步长策略，提高A*算法搜索效率，同时生成一系列满足UAV俯仰角、偏航角等物理性能约束的可飞航线。祁玄玄等[43]从目标性扩展、目标可见性判断、更换启发函数、改变扩展节点选择策略四个方面对A*算法进行改进，提高了算法的收敛效率，优化了路径长度。宋雪倩等[44]将Dubins结合A*算法，使用“向量共享”原理，对解脱航向改变量进行计算，并进行路径重规划，可在短时间内获取连续飞行安全路径。

针对复杂环境动态变化的问题，传统A*算法难以应用，因此一些学者在A*算法的基础上进行改进，典型的改进算法有D*算法。Ganapathy等[45]提出Enhanced D* Lite算法，解决了穿越尖角障碍物产生的不安全路径问题。Stentz[46]提出分批次局部更新航迹代价图的D*算法，有效解决避障问题。常见的基于启发式典型算法的避障算法的适用场景与优缺点如表2所示。

表2 典型启发式算法优劣比较

Table 2 Comparison of advantages and disadvantages of typical heuristic algorithms

2.1.3 图 论

基于图形的避障方法，首先通过栅格化方法，对环境进行建模，再利用搜索算法生成避障路径，完成全局冲突解脱，常用方法有Dijkstra算法、Voronoi图、随机路标图法(Probabilistic Roadmap, PRM)、Dubins 曲线、轮廓图法(Silhouette)、通视图法(Visibility Graph)等。

Dijkstra算法是图论中经典最短路径求法，顶点代表航路点，边代表可行路径，适用于边权非负的二维静态避障场景。使用该算法的关键在于选取有效航迹点，缩短规划时间[47-48]。Voronoi图根据障碍物分布情况，画出相邻障碍物中垂线，构成围绕障碍物的多边形，再对每条路径进行赋权值，最优搜索出代价最小的避障航路。由于Voronoi图能够在飞行过程中有效降低支付代价，在无人机避障领域应用广泛[49-50]。Dubins 曲线考虑无人机转弯性能约束，生成一条可飞的无人机解脱路径[51-53]。在复杂低空空域中，搜索具有多个自由度的高维避障路径的规划问题往往代价较高，因此，可以放松一下弱约束条件，寻求一种折中的搜索空间，既能代表完备的环境信息，又能有效提高搜索速度。随机路标图法(Probabilistic Roadmap, PRM)基于这一原则，对无人机解脱空间进行搜索[54-55]。常见的基于图论的避障算法的适用场景与优缺点如表3所示。

表3 基于图论的避障方法

Table 3 Obstacle avoidance methods based on graph theory

（关键词：无人机，无人机反制，反制无人机，黑飞无人机，无人机防御，防御无人机，反无人机，无人机管控，无人机黑飞，无人机管理）