2019 年数模竞赛——多约束条件下智能飞行器航迹快速规划 问题分析： 复杂环境下航迹快速规划是智能飞行器控制的一个重要课题。由于系统结构限 制， 这类飞行器的定位系统无法对自身进行精准定位， 一旦定位误差积累到一 定程度可能导致任务失败。 因此， 在飞行过程中对定位误差进行校正是智能飞 行器航迹规划中一项重要任务。本题目研究智能飞行器在系统定位精度限制下的 航迹快速规划问题。 约束（1-8）详细见题目 目录 问题一................................................................................................................................................ 2 问题二................................................................................................................................................ 3 问题三................................................................................................................................................ 4 

问题一 在约束 1-7 下，尽可能减少校正次数和路程。 分析： 1、该问题当中的约束一定程度还是挺严格的（需要按一定频率分别进行 X 轴和 Y 轴校正），而且问题规模很大，大规模问题结合严格约束，这对算法提出了 两点要求:1、初始解产生策略必须可以产生大量的随机的有效解；2、新解的 产生策略必须保证可以有一定量的有效解。 2、该问题要求两个目标，减少校正次数和减少路程并不完全正相关，尤其在这 种复杂约束的优化问题中，因此打算采用多目标优化算法，这里考虑从遗传 算法扩展而来的 NSGAii 算法，详细介绍可以百度。 实际实现策略 初始解产生策略：既然题目对解增加了很多约束，那么我们同样可以对初始解产 生过程添加策略，减少无效解，采用逐点 1、根据题目可知，若前后两个校正节点距离超过（最大误差/单位距离误差）时 候解无效，生成下一个节点时候节点间距离必须小于一个定值(alpha*最大误差/ 单位距离误差). 2、根据题目可知，节点达到下一个校正点后才能校正误差，那么当前误差余量 就对下一个解的距离进行了约束，并且 X 轴校正节点与 Y 轴校正节点需要分 开约束。 3、我们最终目的是为了从 A 到 B，那么选定下一个节点的时候就把离 B 近的节 点概率放大一点。 4、每个节点只能用一次 5、节点到 B 附近后尝试直接连 B，若成功就推出。 新解产生策略： 交叉行为：这个过程本质上还是路径规划，那么两条路径解比较优的交叉方式还 是两个解分别取一点将 2 条路径分为 4 条，然后两两交叉组合得到 2 条新解。点 的选择根据距离确定。 变异行为：由于约束存在这里设定了两种优化策略，一种是路径上相近两个节点 进行交换，一种是直接剔除一个节点。 后续部分不公开（代码实现流程+代码文件解释+结果分析）： 

问题二 在约束 1-8 下，尽可能减少校正次数和路程。 分析： 1、该问题当主要区别是多了一个机动限制，就要去对当前规划的路径进行曲率 半径估计，若当前节点曲率半径过小则不满足约束（平面三点-算圆大小）。 2、确定曲率半径满足要求后还要考虑如何进行机动（计算机动引起的距离增加， 和机动轨迹怎么搞）。 实现策略： 1、曲率半径计算这个没啥 2、路径规划 A-B-C，找一个过 B 的 200m 圆，然后圆上找两点 DE，使得 AD 和 CE 分别与圆相切。主要是几何问题 后续部分不公开（代码实现流程+代码文件解释+结果分析）： 

问题三 在约束 1-8 下，当校正节点集合种存在问题节点时候，如何在尽可能保证成功到 达的概率下，尽可能减少校正次数和路程。 分析： 1、 问题节点的特点是校正误差到不了 0，只能降到 5，由于存在两个校正方向，出现问题 哪个方向节点很可能由于这个 5 的误差导致失联，而这个现象可能下一个校正点出现， 也可能过好几个节点才出现，统计其概率相对比较复杂。因此这里提出采用一种与概率 正相关的参数作为优化目标代替实际概率。 2、 实际的概率计算也是一个问题。 实现策略： 1、 采用一下定义的概率作为参数进行三目标优化，设初始失败概率为 0，在每次都为失败 情况，可以得到最恶劣情况下那几次回会倒置无法校正，每次出现失败，失败概率=失 败概率+成功概率*（0.2）(最近的连续遇到问题节点次数)。成功概率=1-失败概率。 （这里的失败概率非真实的失败概率，而是某个正相关的参数）。 2、 同时限定连续出现问题节点的次数，以保证成功概率 3、 通过蒙特卡洛算法计算真实概率。