具有修正策略的改进NSGA－II 三维路径规划

封建湖，郑宝娟，封 硕，张婷宇

（1.长安大学理学院，陕西 西安 710064；2.长安大学工程机械学院，陕西 西安 710064）

1 引言

路径规划是机器人定位与导航领域研究的热点问题之一，目前的路径规划方法如蚁群算法，粒子群算法，蜂群算法，萤火虫算法及混合算法等[1-3]多用于二维平面空间规划。在复杂环境下三维空间的机器人路径避障问题越来越受到学者们的关注。例如，文献[4]提出了一种结合人工势场思想的改进蚁群算法并用于三维路径规划，并将路径的长度作为优化准则，但是只优化了路径长度，实用性不高。文献[5]提出在偏微分高程建模下蚁群算法的三维路径规划方法，但计算结果容易陷入局部最优。

遗传算法根据生物进化过程的自然遗传理论构造的随机搜索算法，其优点是并行计算能力强，鲁棒性和全局收敛性好，已经成功地应用于机器人的路径规划问题。对多目标的遗传算法，文献[6]改进了非支配排序遗传算法（NSGA），提出了复杂度更低，更能保持种群多样性，具有Pareto 占优的NSGA-II 算法。文献[7]考虑路径长度和难度，加入修正算子减少冗余路径，从而改进NSGA-II 算法并成功应用于二维路径规划，取得了很好的效果。文献[8]在二维空间中优化了路径长度、路径安全性和路径平滑度，在NSGA-II 算法的基础上加入辅助选择算子，并证明了辅助选择算子使算法得到的Pareto 解更优，但对冗余路径情况和路径能耗未做考虑。

针对以上算法的优势和不足，尝试基于NSGA-II 算法研究三维多目标路径规划，首先，构造复杂的三维曲面空间并栅格化；……