【《基于轨迹数据的无人机航线再生成方法分析案例》5500字】

基于轨迹数据的无人机航线再生成方法分析案例目录TOC\o"1-3"\h\u20860基于轨迹数据的无人机航线再生成方法分析案例 196911.1引言 116761.2无人机轨迹数据压缩及航线再生成问题建模 154421.3无人机轨迹数据压缩算法设计 3143861.3.13D-Douglas-peucker算法设计 3322171.3.23D-SPM算法设计 936961.4无人机压缩后路径轨迹解聚再生成算法设计 13125961.4.1基于反求控制点的B样条路径平滑算法设计 1381221.4.2基于反求控制点的B样条路径平滑算法仿真分析及改进 1547101.5无人机航线再生成方法仿真分析 16引言大量有关空中交通信息的无人机轨迹数据对无人机作战、环境侦查、远程打击、天基中继、目标跟踪、交通监测、电路巡检、航拍摄影和地理测绘等工程领域具有重要的价值。但是，数据的成本和轨迹处理限制了他们的应用，而且随着无人机数量的快速增多，未来无人机路径数据将非常庞大。为此，本文设计了一种基于轨迹数据的无人机航线再生成方法（包括无人机轨迹压缩、解聚和再生成三个方面），可实现利用已得路径数据完成无人机路径数据压缩、解聚和再生成任务。同时，在轨迹数据基础上采用了3D-Douglas-peucker（DP）/3D-SPM算法对轨迹数据进行压缩以减少存储空间；设计了改进的基于反求控制点B样条路径平滑算法对压缩后的路径进行解聚和平滑处理。仿真试验表明，上述航线再生成算法在保持原有路径重要特征基础上，可以得到更优化的路径（添加数据压缩率、长度损失率、最优化指标和解聚率）。无人机轨迹数据压缩及航线再生成问题建模数据压缩是基于轨迹数据的多无人机航线再生成的关键步骤和关键技术之一。本文采用改进的三维Douglas-peucker算法，选择合适的阈值对轨迹数据进行压缩，从而大大节约存储空间且具有很高的轨迹保真性，并采用改进的基于反求控制点的B样条路径平滑算法对压缩轨迹数据进行解聚和再生成，得到保真度高并继续满足原轨迹任务过程中的约束条件的新路径。多无人机航线再生成问题根据保真性原则继续满足原无人机轨迹满足的障碍约束、最大转弯角约束、最大爬升/俯冲角约束、最小高度约束等，且确保各个无人机的安全。本文基于原轨迹数据进行航线再生成，因此须假设原无人机路径需要满足无人机机动能力、地形、威胁等约束条件，并在航线再生成后仍满足上述约束条件，具体如下：（1）障碍约束：为了确保无人机在飞行过程中的安全，需要与地形、威胁、建筑等障碍保持适当的安全距离。设为无人机与障碍之间的最小安全距离，则障碍约束表示如下： (3-1)（2）最大转弯角约束：受到无人机机动性能的限制，为保证无人机的安全性，无人机需要满足最大转弯角约束。设为最大转弯角，则最大转弯角约束表示如下： (3-2)（3）最大俯冲/爬升角约束：无人机的俯冲/爬升能力受其推力、升力等因素的约束存在一定限制。设无人机最大俯冲角为、最大爬升角为，则最大俯冲/爬升角约束表示如下： (3-3) (3-4)（4）最小高度约束：无人机飞行过程中需要与地面保持一定的距离以确保飞行过程满足安全性要求。设为允许的最低飞行高度，无人机飞行中最低海拔高度为、地形的海拔高度为，则最小高度约束表示如下： (3-5)为证明本文算法的通用性，实现本文提出的算法对较复杂轨迹的应用，本文假设无人机有较高的机动性能，满足、、、、、，本文是对原无人机轨迹的再生成方法，故后文选择的原无人机轨迹满足上述约束条件。无人机轨迹数据压缩算法设计3D-Douglas-peucker算法设计DP算法在二维平面上对轨迹特征点进行提取和化简具有较好的表现，本文将二维DP算法推导并应用于三维空间，实现以空间曲面为参考面来提取和化简轨迹特征点。假设原始轨迹由点集来描述且点集足够密，折线段可以近似代替原始轨迹，在满足精度要求的范围内从上述集合中提取一个反映原始轨迹整体和局部重要特征且所包含的特征点点数足够少的点集，则新得到的轨迹由折线代替。空间三维DP算法的具体计算实现步骤如下：(1)确定原点和首基面：对于一组随机分布的三维离散点集，将所有离散点两两连接获得空间向量并求其矢量积，将矢量积绝对值最大的一对向量选出，并分别将这对向量确定的三个点作为原点、初始锚点和初始漂浮点（分别为图3.1中的O、A、B点），且这三个点确定的平面为首基面。(2)排序点集：上述三维离散点集的起点为初始锚矢量的终点（图3.1中OA向量中的A点），根据三维距离最近的点依次排序点集，整个三维离散点集的末点为初始漂浮矢量的终点（图3.1中OB向量中的B点）。(3)简化数据：构造的基面由O、A、B三点组成，计算得出排序后点列中的锚点及浮动点之间各点到基面的距离。取其最大值为dmax，dmax小于规定的阈值时，删除锚点与浮动点之间其他所有点；dmax大规定的阈值时，则将上述点集分成两段，并重复上述过程。图3.1三维DP算法首基面与点面距假设用三维坐标(x0,y0,z0)表示原点、(xA,yA,zA)表示初始锚点及(xB,yB,zB)表示初始浮动点，则基平面的法向n为(3-6)： (3-6)因此，上述基平面方程ax+by+cz=d的各参数分别有如下解(3-7)、(3-8)、(3-9)、(3-10)： (3-7) (3-8) (3-9) (3-10)定义空间离散点列中任意p点到基平面的距离为dp，则dp计算式为(3-11)： (3-11)定义阈值为δ，按顺序计算，点C为计算中dp最大的点，若dp<δ，则将点列中所有dp都小于该阈值的点删除；若dp>δ，则保留C点，且将初始点列分裂成两段:A~C段和C~B段，分别对两段构建新基面，并递归选取特征点，直到没有特征点满足上述要求为止。根据无人机路径数据点从起始点到终止点依次在光滑路径轨迹上的特点，本文建立O为原点的坐标系，选取轨迹首尾两点为锚点和浮动点，O与轨迹首尾两点确定首基面，原始轨迹点序列分段后，仍以O为原点分别对两段重新构建基平面，从而消除首基面确定造成的时间复杂度。三维坐标原点为(0,0,0)、初始锚点为(xA,yA,zA)及初始浮动点为(xB,yB,zB)，基平面的法向n为(3-12)： (3-12)因此，基平面的函数方程ax+by+cz=d的参数分别有如下解(3-13)、(3-14)、(3-15)、(3-16)： (3-13) (3-14) (3-15) (3-16)设三维离散点序列中任意点p到基平面的距离为dp为(3-17)： (3-17)改进后的三维DP算法与普通三维DP算法对比将不同点列出，结果如表3.1所示。表3.1改进前后3D-DP算法对比结果原点初始锚点初始漂浮点是否排序点集算法复杂度改进前(x0,y0,z0)矢量积最大矢量积最大是改进后(0,0,0)轨迹起点轨迹尾点否本文采用压缩率、长度损失率两个量化指标评估压缩性能，压缩率Cr表示压缩过程中丢弃的轨迹跟踪点数和原轨迹跟踪点数之比如式(3-18)。长度损失率表示损失长度和原始轨迹的总长度之比。原始轨迹可以表示为轨迹跟踪点集T={P1,P2,…,Pi}及其长度T计算如式(3-19)。对j架无人机定义原始轨迹跟踪点集和压缩后轨迹跟踪点集分别为To={T1，…，Tj}和Tc={T1'， (3-18) (3-19) (3-20) (3-21)为综合评价压缩性能，本文定义压缩最优化指标O,为平衡压缩率、长度损失率的数量级，定义平衡系数β。设压缩率、长度损失率重要度分别为ma、mb（ma+mb=1,0<ma<1,0<mb<1），平衡系数和最优化指标计算如式(3-22)、(3-23)。 (3-22) (3-23)无人机路径数据压缩阶段所需的已知信息包括原始路径数据点，环境以及无人机无法进入的其他区域中的障碍物和威胁。将环境中的障碍物设置为一系列大小不同的半球，并将这些障碍物与地图信息结合起来以制作无人机航线生成环境的场景地图，原无人机路径数据与环境要素融合后的地图如图3.2所示：图3.2无人机原始轨迹数据及环境利用本文设计的三维Douglas-peucker算法对场景中的单架无人机路径数据进行压缩说明算法的有效性并确定阈值。本文压缩率、长度损失率重要度分别为ma、mb均取0.5，所得结果的如表3.2和图3.3所示。表3.2无人机原始轨迹数据不同阈值δ压缩结果δNMTT'LlLrCrO0.0011107117166.3547166.33990.014800.008897%89.4%0.9470.0051107108166.3547166.33530.022100.013285%90.2%0.9510.01110798166.3547166.18970.165000.099186%91.1%0.9540.05110760166.3547165.64290.711800.427881%94.6%0.9670.1110741166.3547165.15671.198000.720148%96.3%0.9720.5110716166.3547159.99786.359603.822916%98.6%0.9421110712166.3547154.892811.46196.890037%98.9%0.902511075166.3547104.598861.755937.12303%99.5%0.500δ=0.001δ=0.005δ=0.01δ=0.05δ=0.1δ=0.5δ=1δ=5图3.3无人机原始轨迹数据不同阈值压缩结果由图3.3和表3.2可以看出随着阈值的增加，长度损失率逐渐增大，压缩率也逐渐增大。阈值δ为5时不符合安全性要求，为0.1时有满意的压缩率和损失率，其压缩最优化指标O达到最优值0.972。3D-SPM算法设计SPM算法属于一种扫描式算法，它的基本原理是连接首尾两点以形成一条基线，从起始点开始的第二个路径点依次向上述基线做垂线，得到垂直欧氏距离为ｄ，如果d小于预先设定的阈值δ，则舍弃该点；直至出现轨迹点到基线的距离d大于阈值δ，则将该点设置为新的起点。重复以上步骤，直到所有的路径点都被选取、扫描，则算法结束。算法的原理如图3.4所示。图3.4SPM算法由图3.4知，原始轨迹T={p1,p2,p3,p4,p5,p6,p7}经SPM算法压缩处理后轨迹点p3和p6被去除。压缩后轨迹变为T'={p1,p2,p4,p5,p7}。SPM算法通过连接起点和终点获得基线，对轨迹上的各点依次进行选取、扫描，去除d小于预先设定的阈值δ的点，而把d大于δ的点作为新的起点。该做法实质上就是一种分段策略，不存在递归运算，这使得此算法的时间复杂度较小为O(n)。然而，由于此算法需要把起点和终点连接起来形成第一条基线，且是一种离线算法，因而不适用于在线压缩领域。此外，该算法还可能把能够反映原始轨迹重要特征的轨迹点去除。假设用坐标A(xA,yA)表示基线起点及B(xB,yB)表示基线终点，基线的函数方程和离散点序列中任意点P(xP,yP)到基线的距离dp如下(3-24)、(3-25)： (3-24) (3-25)将二维坐标扩展到三维，基线AB的函数方程和空间离散点序列中任意点P(xP,yP,zP)到基线的距离dp计算式如下(3-26)、(3-27)、(3-28)、(3-29)： (3-26) (3-27) (3-28) (3-29)利用本文设计的三维SPM算法对场景中的单架无人机轨迹数据进行压缩说明算法的有效性并确定阈值δ。本文压缩率、长度损失率重要度分别为ma、mb均取0.5，所得结果的如表3.3和图3.5所示。表3.3无人机原始轨迹数据不同阈值δ压缩结果δNMTT'LlLrCrO0.11107950166.3547166.30510.049600.029816%14.2%0.5700.51107236166.3547165.36520.989500.594813%78.7%0.87711107120166.3547161.66494.689802.819157%89.2%0.8692110763166.3547160.77315.581603.355240%94.3%0.8813110740166.3547154.154312.200407.333968%96.4%0.7834110730166.3547152.071214.283508.586172%97.3%0.7545110724166.3547148.138918.2158010.949976%97.8%0.6936110718166.3547136.113830.2409018.178567%98.4%0.500δ=0.1δ=0.5δ=1δ=2δ=3δ=4δ=5δ=6图3.3无人机原始轨迹数据不同阈值压缩结果由图3.5和表3.3可以看出随着阈值的增加，长度损失率逐渐增大，压缩率也逐渐增大，阈值δ为6时不符合安全性要求，为2时有满意的压缩率和长度损失率，其压缩最优化指标O达到最优值0.881。3D-SPM算法时间复杂度为n，δ=2时，压缩率94.3%，长度损失率3.355240%，最优化指标为0.881。3D-DP算法时间复杂度为nlogn，δ=0.1时，压缩率96.3%，长度损失率0.720148%，最优化指标为0.972，因此后文选择3D-DP算法进行解聚结果分析及阈值确定。无人机压缩后路径轨迹解聚再生成算法设计基于反求控制点的B样条路径平滑算法设计无人机航线再生成的目的是得到适合无人机飞行需要的飞行轨迹，当期望轨迹出现明显的偏折时将难以满足无人机的运动性能。因此，本文采用B样条曲线对期望轨迹进行平滑处理，N次B样条曲线拟合的参数方程如式(3-30)、(3-31)： （3-30） （3-31）其中为曲线的控制顶点，为曲线第个控制顶点的基函数。当n=3时，三次B样条曲线拟合的基函数和参数方程的表达形式如式（3-31、(3-32)： （3-31） （3-32）其中为控制顶点，为分段端点，如图3.3所示。图3.3三次B样条平滑示意图从图中可以看出，通过三次B样条曲线拟合出的路径满足飞行路径平滑的要求，但与原路径点发生偏离可能使无人机不满足安全性要求，因此需要反求其控制顶点。由式图3.3和（3-30）可知第段B样条曲线的起点为(3-43)： （3-43）因此可得方程组(3-44): （3-44）增加边界条件和，将式（3-44）与边界条件联立可得(3-45): （3-45）写成矩阵形式有(3-46): （3-46）最后，将全部控制点代入式（3-30），可以得到通过全部路径点的B样条路径拟合曲线。基于反求控制点的B样条路径平滑算法仿真分析及改进图3.4显示了一组轨迹点分别通过普通B样条路径平滑算法和基于反求控制点的B样条路径平滑算法进行平滑的效果对比。B样条曲线(b)基于反求控制点的B样条曲线图3.4路径平滑效果对比从图3.4(a)可以看出，一般B样条曲线在部分路径点处与原始路径偏离较大可能使无人机在轨迹追踪的过程中发生危险。图3.4(b)为反求控制点后求得的平滑路径，所求得的路径通过了所有原始路径点，可以避免与无人机原始路径偏离较大而发生危险。然而，基于反求控制点的B样条路径平滑算法仍存在缺陷，本文对阈值δ=0.5运用3D-DP算法的压缩路径进行平滑处理，清晰显示了基于反求控制点的B样条路径平滑算法的缺陷如图3.5。图3.5基于反求控制点的B样条路径平滑算法缺陷从图3.5可以看出左侧2、3两路径点间的B样条曲线发生了较大形变而与地形发生碰撞，本文采用插值方法对该算法进行改进，首先找到距离最近的两个轨迹点将距离记录为dmin，对每一段进行插值分段直至分段后相邻点距离dtemp和插值阈值ζ满足dtemp/dmin≤ζ，结果如图3.6、表3.4和表3.5所示。图3.6基于反求控制点的B样条路径平滑算法改进效果示意图表3.4δ=0.1时无人机轨迹数据不同阈值ζ解聚结果ζM'NDepolymerization_rateTime10781110771%1.3513611107123%1.4230811107278%1.5s表3.5δ=0.5时无人机轨迹数据不同阈值ζ解聚结果ζM'NDepolymerization_r