基于多目标优化方法的无人机复杂场景路径规划方法

本发明涉及了一种无人机路径规划方法，尤其涉及一种基于改进nsga-ⅲ多目标优化方法的无人机复杂场景路径规划方法。

背景技术：

1、随着科技进步与发展，四旋翼无人机在人类生活生产中的应用越发广泛。但是，由不同形状、位置与大小的多个障碍物或是复杂崎岖的地形所形成的复杂障碍场景是影响无人机作业安全的主要障碍。而路径规划作为无人机的关键技术，是其执行各种所需任务、实现自主导航规划的基础，其目的在于面对各种复杂障碍场景下能够快速寻找到一条由起点到终点的路径，该路径在满足无碰撞的同时还能够满足各类任务目标需要。目前在无人机路径规划领域的主流方法包括a-star方法、dijkstra方法、rrt方法、rrt-star方法、prm方法、人工势场法、蚁群方法、粒子群方法等等。其中，a-star方法以及dijkstra方法作为贪婪方法的变种，其运算效率会随着地图尺寸的增加而急速下降。人工势场法、蚁群方法以及粒子群方法等智能方法容易被环境因素所干扰容易陷入局部最小值，且存在计算量大实时性差的问题。rrt方法、rrt-star方法以及prm方法作为基于随机采样点方法，路径随机性过高，需要大量迭代才能得到较优路径，运行时间过长等缺点。同时上述主流方法在无人机路径规划技术领域当中都只考虑了单个或最多两个目标进行优化，面对对如今多种多样的任务需求，存在无法满足多种需求同时优化的缺点。

2、nsga-ⅲ方法是一种基于遗传方法(ga)的改进方法，该方法在多维目标优化方面能力出众，在路径规划方面可以同时对路径长度、路径平滑度以及障碍物躲避等多种目标进行优化。但由于遗传方法本身需要大量的初始种群，因此需要对地图路径点进行随机采样，当环境中存在狭小通道或凹形障碍物时，方法的成功率较低，极易陷入局部最小值，并不适合用作实时路径规划。而hopfiled神经网络路径规划方法，是一种利用hopfiled神经网络能量收敛稳定的特性提出的一种规划方法，该方法克服了其他方法在高维空间当中同样具有良好的收敛特性，具有较高的运算速率，得到空间内无碰撞的最短路径。然而hopfiled方法得到的最短路径优势不能很好的结合无人机的运动学或动力学约束，且只能产生最短路径而不能优化其他目标，在多目标优化领域具有局限性。

技术实现思路

1、针对目前各类主流方法在自身方面以及多目标优化方面存在的各类问题，以及针对nsga-ⅲ多目标优化方法存在的问题，本发明提出了一种基于改进nsga-ⅲ多目标优化方法的无人机复杂场景路径规划方法，克服上述现有技术的缺陷，提高方法在复杂场景中规划成功率，降低路径的随机性，提高多目标优化能力，使得规划出来的路径在无碰撞的同时还能够满足各类任务需要。

2、为了实现上述技术效果，本发明的技术方案如下：

3、步骤1：获取工作环境地图；

4、步骤2：对工作环境地图map1进行地图栅格化处理后，获得初始网格地图，以及获得起点网格和终点网格；

5、步骤3：从起点网格出发至终点网格，采用广度优先方法对初始网格地图中的所有可飞行网格进行编号后，得到网格编号地图；

6、步骤4：利用改进的nsga-ⅲ方法在网格编号地图上生成一条既无碰撞又能够满足多目标优化的路径；

7、步骤5：对步骤4中生成的路径进行优化处理后，获得无人机的规划路径。

8、所述步骤3具体为：

9、步骤31：将初始网格地图中的可飞行网格和障碍物所在的网格以及边界网格的数值进行填充，其中可飞行网格的数值相同，障碍物所在的网格以及边界网格的数值相同，完成初始网格地图的初始化；

10、步骤32：从起点网格开始编号，利用广度优先方法从起点网格出发向八个方向的网格进行顺序编号，直至终点网格，得到网格编号地图。

11、所述步骤4具体为：

12、步骤41：利用hopfiled神经网络向网格编号地图的网格添加能量并进行能量状态迭代更新，获得包含能量状态的网格地图；

13、步骤42：采用回溯法在包含能量状态的网格地图中寻找一条从终点到起点的最大能量梯度的路径，并将该路径作为无碰撞的初始路径pinit；

14、步骤43：以路径长度对无碰撞的初始路径pinit等分后，获得n个路径点坐标；

15、步骤44：分别在n个路径点坐标附近随机得到num个服从二维高斯正态分布的待选路径点，共n×num个待选路径点，从而形成n个待选区域；

16、步骤45：采用nsga-ⅲ方法对n个待选区域中的路径点进行选择并进行多目标的迭代优化后，获得最优的n个路径点，将起点网格、最优的n个路径点以及终点网格相连后得到一条既无碰撞又能够满足多目标优化的路径poptimize。

17、所述步骤41中，利用hopfiled神经网络向网格编号地图的网格添加能量并进行能量状态迭代更新的具体公式如下：

18、

19、

20、其中，xi(k+1)代表第k+1次迭代的网格i的能量状态，xj(k)和xj(k+1)分别为第k次和第k+1次迭代的网格j的能量状态，f(x)代表网格i的能量总输入；di为网格能量系数，障碍物网格与边界网格均为0，其他网格为1；i代表起点网格的初始输入能量，a代表能量衰减系数，ωij代表hopfiled神经网络中网格i和网格j间的权重，k为迭代次数，nei代表是网格i的相邻网格集合。

21、所述步骤45中，nsga-iii方法分别在n个待选区域内随机选择一个待选路径点，得到一条共n个路径点的初始路径，种群pt内共dim条初始路径，在dim条初始路径中遍历寻找后获得最优的n个路径点组成的路径。

22、所述步骤45中，nsga-iii方法采用的适应度函数包括路径长度、障碍物威胁成本以及路径平滑度成本，路径长度、障碍物威胁成本以及路径平滑度成本均作为优化目标，从而形成多优化目标。

23、所述路径长度f1的公式如下：

24、

25、其中，n为路径点数量，pi，j表示第i条路径的第j个路径点，pi，j+1表示第i条路径的第j+1个路径点，||pi，j→pi，j+1||表示相邻路径点pi，j和pi，j+1之间的欧式距离。

26、所述障碍物威胁成本f2的公式如下：

27、

28、

29、其中，n为路径点数量，m为障碍物数量，tk(pi，j→pi，j+1)是关于障碍物和局部路径pi，j→pi，j+1之间的距离dk的分段函数，d为障碍物半径，rk为第k个障碍物的威胁半径，γc()为惩罚系数。

30、所述路径平滑度成本f3的公式如下：

31、

32、其中，n为路径点数量，pi，j表示第i条路径的第j个路径点，pi，j+1表示第i条路径的第j+1个路径点，pi，j-1表示第i条路径的第j-1个路径点，||(pi，j-pi，j+1)+(pi，j-1-pi，j)||2表示在第i条路径的第j个路径点pi，j的合力。

33、所述步骤5具体为：

34、采用三次b样条优化方法对步骤4中生成的路径poptimize进行平滑处理后，得到平面运动曲线，再根据起点和终点高度对平面运动曲线进行高度上的线性插值后，获得无人机的规划路径。

35、本发明的有益效果是：

36、本发明提出一种基于改进nsga-iii多目标优化方法的无人机复杂场景路径规划方法，针对现有主流方法和nsga-iii方法存在的问题从以下四个方面进行了改进：

37、1)针对现有主流方法只能实现单目标优化，无法随着多任务需求变动而进行多目标优化的问题。提出一种改进的nsga-iii多目标优化方法，nsga-iii方法作为目前多目标优化领域的新一代方法，具有极好的多维目标优化特性，优化能力强。

38、2)针对nsga-iii方法初始种群通过随机采样方式选取路径点的导致方法成功率低，运算效率低，极易陷入局部最小值的问题，提出了利用hopfiled神经网络路径规划方法来生成初始路径，避免了方法在面对狭小障碍时路径采用不成功以及陷入局部最小值的问题，减少了方法的运算时间，提高了运算效率。

39、3)针对nsga-ⅲ方法需要大量的初始种群，但hopfiled方法生成的路径在同一场景下只会生成固定的一条的问题，引入了高斯正态随机数分布方法，在hopfiled方法生成的初始路径附近拓展新的路径点，为nsga-ⅲ方法提供了丰富的种群样本，避免了方法陷入局部最佳状态，提高了方法在其他目标方面的优化

40、4)引入路径平滑度作为多目标优化函数之一，提高无人机飞行路径满足轨迹跟踪的要求成功率，提高了下一步三次b样条平滑优化效率。

41、实践证明，本发明提供的方法能够适用在复杂场景下的无人机路径规划。