基于多标号修正法的快速最短路算法在智能飞行器航迹快速规划问题中的应用

秦子柔

（上海交通大学船舶海洋与建筑工程学院，上海200240）

1 概述

近年来，随着国民经济的提高以及科学技术尤其是人工智能的飞速发展，无人机已经成为我国物资运输，环境监控，军事侦察，资源勘探等领域不可或缺的一部分。由于信号传输延时，实现无人机的自动导航日显重要。然而由于系统结构及环境多变导致定位系统无法对自身进行精准定位，常常导致任务失败。在2018 年5 月的西安无人机表演中，就有无人机因为环境干扰而无法对自身定位从而打乱编队并引起坠机的先例。

由于无人机发展的重要性与需求，近几年有大量学者从事了无人机自动导航的研究。与他们的方法相比，此文提出了无人机航迹规划的一般模型和算法，有实时性高，计算量小的优势。

2 问题背景及模型建立

2.1 背景描述

假设飞行器的飞行区域业已确定，如图1 所示，出发点为A点，目的地为B 点。其航迹约束要求如2019 年全国研究生数学建模竞赛F 题。

图1 飞行器飞行环境

2.2 模型建立

2.2.1 仅考虑误差积累上限的航迹规划方案

在任意一个误差校正点处，如飞行器满足误差校正要求，则其水平误差或者垂直误差立即被校正。将校正点、出发点A 和终点B 及它们之间的空间路段抽象成简单无向完全图，它们之间的距离用dij表示为目标函数：对一条路段ij，如被选择作为航迹中的路段，则xij=1；否则为0。因此目标函数的第一部分表示的是规划航迹的总长度。如飞行器在此处进行了误差校正，则u1i=0 或u0i=0；否则u1i=1 且u01=1，因此第二部分表示规划航迹中校正的次数。对两部分分别赋予w1和w2的非负参数权重。在建立流量守恒约束、飞行误差控制约束后，建得飞行器误差校正约束。

2.2.2 带转弯约束的航迹规划方案

使用轨迹示意图来展示模型中两点之间飞行器的运动轨迹。

图2 点间运动几何分析图

转弯角度是转弯起始点和转弯结束点之间的连线和原航向间所成的夹角，用β 表示。转弯半径指以原航向与新航向为外切线形成的圆的半径大小，用r1 表示。假设飞行器行驶的第一段圆弧路段是以最小转弯半径行驶。行驶一段距离之后，飞行器将会进入另一个与此最小半径圆相切，同时与速度方向上节点相切的圆的第二段圆弧路段，从而假设了合理的飞行轨迹。如上图所示，红色的两段圆弧为所走轨迹。当飞行器从出发点A出发时，假设它走直线到达第一个校正点。

排除掉一些无法飞达的节点，飞行器飞行轨迹空间长度的模型计算公式如下。

用式(5)获得两点之间的两段弧长运动轨迹总长。

2.2.3 校正点存在失效概率的多目标航迹规划模型

对于给定的可行航迹，飞行器能够成功到达终点的概率符合一种马尔可夫链状态空间概率分布。考虑校正点处校正最坏的状况来找到某个路径的成功概率的下界，来最大化到达终点的概率。所有可能失效的校正点都按失效处理。

增加一个子优化目标作为模型约束：

其含义是对于终点B，尽量使得有流量进入，即飞行器成功到达终点B。

同时需要的流量守恒约束式为：

其中I 为飞行器终止的节点。飞行器成功到达B 点，则I=B。

通过修改约束式来考虑校正点处校正失效。

整理得校正点存在失效概率的多目标航迹规划模型：

3 实验仿真

3.1 考虑飞行器转弯半径约束:

在最短航迹方案和最少检查次数的方案中，航迹大多数情况下会轮流经过垂直/水平校正点来校正误差。两条航迹总体方向始终朝向终点B，最少校正次数方案的航迹会增加路程长度而减少一次校正次数，不分伯仲。

3.2 校正点存在失效概率的多目标航迹规：

最短航迹方案总航迹长度104827.3772m，经过10 个校正点；最少校正次数方案总航迹长度104864.3839m，经过9 个校正点。两种方案航迹总长相差37m，无论从航迹总长度以及校正次数来看都较接近。

图3 数据集1 航迹图

图4 数据集2 轨迹图

数据集2 航迹规划耗时281ms, 最优航迹既是路径最短，且校正次数最少。与数据集1 相比，数据集2 可供选择的校正点较少。

3.3 模型的敏感性分析

随着转弯半径变化，计算得到的航迹长度、校正次数均发生变化，但整体变化不大。数据集2 的计算耗时均远小于数据集1。从两个数据集内部横向比较来看，转弯半径变化对其求解耗时影响很小。随着转弯缩小，两个数据集求解耗时并无一致性变化。

4 结论

本文提出了解决飞行器由于自身定位系统受到限制和误差校正点可能失效情况下最优航迹规划的方法。通过运用基于多标号修正法的快速最短路算法，建立了带转弯约束的双目标航迹规划模型，使用多标号修正法的快速最短路算法求解。算法不依赖于模型的表达式；对于存在多个目标的情况，不需要人为的给定目标间的权重，因为算法能够提供所有的帕累托最优解。

对于点与点之间的飞行轨迹的双圆弧假设，具有创新性和实际操作价值，对飞行器空间轨迹控制提供参考。通过敏感性分析，发现模型、算法求解速度保持稳定，因此适用于飞行器的快速航迹规划。