全身追踪不怕遮挡，CMU两位华人做了个基于WiFi信号的De

　　文刘燕斌，何家皓，李霜琳
　　摘要
　　本文分别从离线航迹规划、在线航迹规划和多飞行器协同等方面，基于鸽群智能算法提出了三种智能航迹规划算法，力图克服传统航迹规划的缺陷，满足火星飞行器航迹规划设计要求。
　　关键字
　　鸽群智能优化算法；航迹规划；火星飞行器
　　0引言
　　火星探测飞行器体积小、质量轻，为实现对火星的科学探测，需要从地球发射，经历轨道转移和再入过程，在低密度低雷诺数的复杂火星大气环境下，完成机翼展开、下滑、拉平，自主飞行等过程，整个运动进程综合了航空航天领域的若干高技术领域；而自主航迹规划技术是确保火星探测飞行器任务完成的保障，对其关键科学问题进行研究十分必要，具有前瞻性和开拓性。采用飞行器来探测火星有可能成为未来深空探测的研究方向之一，在未来它不仅可以用于火星探测，而且还能用于其他行星的科学探测研究上，对未来星际飞行、星际探测都有着重要的研究意义。
　　新型飞行器因其运行在火星复杂动态环境下，应具有自主控制能力。因此，将智能优化技术应用于火星飞行器自主航路规划中，有助于实现火星飞行器自主控制，对其研究具有重要的价值。基于鸽群优化算法的火星飞行器航路规划技术，主要指的是无人机在火星拒止环境下，利用信息处理与在线环境感知，对飞行航迹进行自主规划，有效避开未知障碍物，完成火星探测过程，并且具有快速而有效的任务自适应能力。火星距离地球遥远，传统的导航技术和辅助引导策略无法适用于火星飞行器，要求其应用智能感知与航迹规划技术提升飞行器自主控制能力，即火星飞行器需要通过改进现有航迹规划算法，使其具有自主航路规划和重规划能力。不仅如此，火星飞行器希望最终能实现自主飞行，完成发现、跟踪和识别目标。为适应火星探测过程，需要将不同的无人系统与特定的功能混合搭配，通过组合不同的无人系统，提升探测能力。灵活的组合搭配将大大提高火星飞行器的探测效能和成本效益，拓宽飞行范围。
　　1火星飞行器智能航迹规划算法
　　多飞行器在线协同航迹规划与现有的航迹规划系统相比较，重点突出了两个方面的要求，一是在线快速规划，主要应用于不确定环境中的航迹修正和任务调整后的在线重新规划；二是多飞行器之间的航迹协同性，要求规划出的航迹之间能满足一定的时空协同要求。
　　1。1火星飞行器离线航迹规划
　　融合鸽群优化算法与可视图法的智能离线航迹规划。首先利用可视图法获得一条可行路径；以该路径作为基础路径输入，并通过确定约束条件与性能指标得到适应度函数；最后利用鸽群优化算法得到更符合需求、性能更优的路径。
　　1。1。1适应度函数构造
　　在飞行器航迹规划的过程中，考虑两类成本。一是飞行器的燃料成本。由于所有的飞行器都假设以恒定的速度飞行，因此飞行距离与燃料的消耗成正比。二是与威胁风险相关，这与飞行器与障碍物之间的距离相关。智能离线航迹规划算法中适应度值即为飞行目标函数J1，计算方法如下：
　　1。1。2算法流程
　　智能离线航迹规划流程如图1所示。
　　智能离线航迹规划的具体实现流程如下所述。
　　图1智能离线航迹规划算法流程
　　步骤1将所有非多边形的障碍物都拟合为多边形，其中圆形障碍物拟合为正十二边形，并记录构成各多边形的ng个顶点于集合T。
　　步骤2从出发点start开始寻找下一节点zi。寻找方法为在集合T中随机寻找若干节点，计算节点的适应度值Jzi1，选取适应度值最小的节点作为下一节点添加到当前路径中。
　　步骤3判断zi是否为目标点aim，若不是则将该点从集合T中删除，并重复步骤2；若是，则计算该路径长度Lnow，若当前路径长度为最小，则记录LbestLnow，并记录该航迹。
　　步骤4从步骤1开始多次循环，更新当前寻路次数，直至当前寻路次数等于寻路总次数，选取路径长度最小的航迹作为智能可视图法避障算法的基础路径。
　　步骤5初始化鸽群优化算法的参数包括空间维度、地图罗盘算子R、种群数量Np、最大迭代次数Nc1max、Nc2max，并确定鸽群优化算法的适应度值计算函数。
　　步骤6将基础路径作为前几只鸽子的速度V与路径X，随机初始化其余鸽子的速度与路径。
　　步骤7将基础路径作为现有最优结果，运算地图罗盘算子，多次迭代（直到迭代次数Nc1Nc1max）更新每只鸽子的速度与路径，并根据鸽子的适应度值J1选取局部最优航迹Xp与全局最优路径Xg。
　　步骤8根据适应度值大小对航迹排序，并淘汰20适应度值较大的航迹，根据地标算子模型多次迭代（直到迭代次数Nc2Nc2max）调整每只鸽子的速度V与路径X。
　　步骤9根据火星飞行器模型的约束条件，判断当前得到的Xg是否可适用于火星飞行器模型，若是则以Xg作为规划得到的航迹输出；否则将返回步骤5重新寻找路径。
　　1。2火星飞行器在线航迹规划
　　该算法的基本思想为融合鸽群优化算法与改进版圆形扩张法。利用改进版圆形扩张法实现飞行器的实时避障，并引入判断机制在障碍物分布疏松时利用鸽群优化算法选择下一目标位置，从而实现飞行器航迹的优化。
　　在飞行器航迹规划的过程中，要同样要考虑上述1。1。1适应度函数构造中所述的两类成本外，为了保持轨迹平滑，还需要保持较小的转弯角。智能在线航迹规划算法中适应度值即为飞行目标函数J2，计算方法如下：
　　智能在线航迹规划流程如图2所示。
　　图2智能在线航迹规划算法流程
　　智能在线航迹规划的具体实现流程如下所述。
　　步骤1从起点出发向前膨胀找到障碍物1；沿障碍物1与起点延长线膨胀确定障碍物2，若由障碍物1、2所构成的通道不可通行，即d12emdemw时，调整膨胀方向重新寻找新的障碍物2。确定障碍物1、2后执行步骤2。
　　步骤2从障碍物1、2所构成的通道穿过并膨胀寻找障碍物3。确定由障碍物构成的安全范围A。当SAemStem时进行步骤4；否则进行步骤5。
　　步骤3经过障碍物1、2所围成的通道到达与三个障碍物相切的相切圆的圆心（xc，yc）后，执行步骤7。
　　步骤4初始化鸽群优化算法参数，如空间维度D、地图罗盘算子R、种群数量Np、地图罗盘算子与地标算子的最大迭代次数Nc1max、Nc2max，并确定鸽群优化算法的适应度值计算函数ftc2，随机初始化鸽群的速度与位置。将执行步骤5。
　　步骤5以安全范围重心作为现有最优，运算地图罗盘算子，多次迭代更新（直到迭代次数Nc1Nc1max）鸽群的速度V与路径X。根据适应度值J2的大小确定每只鸽子的最优位置Xp，以及全局最优位置Xg。
　　步骤6根据适应度值淘汰20的鸽子，再利用地标算子进行迭代更新（直到迭代次数Nc2Nc2max），调整鸽群的速度V与路径X，以当前全局最优Xg作为下一位置，并移动到这一位置，而后执行步骤7。
　　步骤7判断是否可直接达到目标位置，并执行步骤11；否则将执行步骤8。
　　步骤8记录当前位置与障碍物信息至搜索树中。
　　步骤9进行转向判断。若可进行转向，选择构成当前通道的两个障碍物作为新的障碍1、2，并进行步骤3；若不可转向，将进行步骤10。
　　步骤10标记当前通道不可行，火星飞行器掉头返回上一层搜索树，选择另一条通道；若仍不可行，则火星飞行器再一次掉头并返回搜索树更上一层再次重新执行步骤10；若可行将进行步骤2。
　　步骤11验证是否满足火星飞行器模型约束条件。
　　1。3火星飞行器协同航迹规划
　　多飞行器协同避障要求在多飞行器于协同执行任务的过程中，须保证每架飞行器可规避环境中的障碍物，并且飞行器之间也不能发生碰撞。
　　采用集中式控制法，在飞行过程中不断获取其他飞行器的相关信息，并通过将其余飞行器均视为障碍物，从而实现机间防撞。以路径长度、与障碍物的距离、飞行器之间的影响程度作为衡量轨迹优劣的指标，利用鸽群优化算法得到综合性能最优轨迹。其中飞行器之间的影响小是指，飞行器不发生碰撞，且在飞行过程中留有一定的安全范围，这样的情况下认为轨迹之间的影响为0；否则认为飞行器间的影响为最大。
　　1。3。1适应度函数构造
　　在多飞行器协同避障的过程中，同样考虑前述1。1。1适应度函数构造中的两类成本。在飞行器协同避障中适应值函数为
　　式中，k3为权重值；Job2为威胁风险相关的适应度值；Jveh为飞行器间威胁相关的适应度值；Jfuel2为考虑路径最短的适应度函数。
　　1。3。2算法流程
　　智能协同航迹规划的具体步骤如图3所示。智能协同航迹规划的具体实现流程如下所述。
　　图3智能协同航迹规划算法流程
　　步骤1初始化鸽群优化算法的参数包括空间维度D、地图罗盘算子R、种群数量Np、地图罗盘算子与地标算子的最大迭代次数Nc1max、Nc2max；确定鸽群优化算法的适应度值计算函数。
　　步骤2随机初始化鸽群的速度V与轨迹X，以第i只鸽、nv个飞行器为例，将轨迹分为n2段，起点与终点与设置相同不进行随机初始化。
　　步骤3将基础轨迹作为现有最优结果，运算地图罗盘算子，多次迭代（直到迭代次数Nc1Nc1max）更新每只鸽子的速度与轨迹，并根据鸽子的适应度值J3选取局部最优轨迹Xp与全局最优轨迹Xg。
　　步骤4根据适应度值大小对轨迹排序，并淘汰20适应度值较大的轨迹，根据地标算子模型多次迭代（直到迭代次数Nc2Nc2max）调整每只鸽子的速度V与轨迹X，得到当前Xg作为运算结果。
　　步骤5验证轨迹是否满足火星飞行器模型约束条件。
　　2结束语
　　本文将鸽群智能算法与传统的航迹规划算法相结合，在火星探测这个复杂的背景下提出了基于鸽群智能算法的离线航迹规划算法、在线航迹规划算法和协同航迹规划算法。所提出的算法可以克服传统航迹规划的缺陷，满足火星飞行器航迹规划设计要求。
　　选自《中国人工智能学会通讯》
　　2021年第11卷第5期
　　群体智能及应用专辑