一种基于完全膨胀图的无人机最优路径规划方法

本发明涉及基于完全膨胀图的无人机最优路径规划方法，本发明属于无人机器人路径规划领域。

背景技术：

1、路径规划问题是机器人领域乃至自动化领域的关键问题。路径规划问题的定义非常简单:“在特定环境中找到初始(起点)和最终配置(目标)之间的无碰撞运动”。最简单的情况是在一个静态和已知的环境中规划路径；然而，更一般地说，路径规划问题可以制定为任何机器人系统受运动学约束，在动态和未知的环境。它在现实生活中有着广泛的应用，包括无人驾驶、物流配送、机器人导航等领域。随着人工智能和计算机技术的发展，路径规划技术也在不断地得到改进和应用。

2、路径规划算法根据生成几何路径的方法可分为：路线图技术(roadmaptechniques)、区域分割(cell decompositionalgorithms)、人工势场(artificialpotential methods)。

3、线路图方法包含两个阶段：构建和查询。在构建阶段，通过在3d环境中定义网络曲线来计算自由位形空间的连通性。构建路线图之后，在查询阶段解决初始和最终位形点。通过曲线的连接，可以解出在这些点之间的路径规划。线路图技术被用来处理uav在静态环境中移动时的路径规划查询。查询的计算时间在处理时间内实时完成，最终路径的平滑是通过路线图算法完成的，比如rrt,a*,rrt*。

4、区域分割首先将自由空间划分成一组不同的单元或区域，以便于计算同一单元或相邻单元中两点之间的安全路径。一旦计算出自由空间的单元分解，就可以按顺序组织单元。对于位形空间中的uav路径规划，可根据单元类型采用不同的方法和算法。

5、人工势场是一种简单轻便的动态路径规划方法。它将设计对象的环境表示为一个粒子，它在位形空间周围的势场控制下运动。uav路径是根据从初始点到目标点的结果场计算出来的。然而，传统的pfm受限于局部最小，导致uav在到达目标点之前卡住。

6、上述路径规划方法均把无人机视为无体积的质点，因此规划出的路径可能在实际执行过程中会导致碰撞。目前的解决方法通常是根据无人机的体积，膨胀障碍物的体积，将膨胀后的障碍物视为地图中的障碍物，之后再将无人机视为质点进行路径规划。此外使用维诺图(voronoi diagram)，可以从原理上实现安全性最优的路径规划，在特定平面上，它根据航点之间的距离来划分不同区域。vd方法定义周围障碍物的所有点与障碍物的距离都相等，由vd生成的路径图安全性很高，因为障碍物距离路径的所有边都很远。

7、voronoi图的计算方法有许多，主要有分而治之算法、扫描线算法、增量算法等，这些算法主要是针对点站点、线段站点、多边形站点，对于三维复杂站点则难以计算。此外维诺图本身并非为无人机路径规划设计，得到的路线图通常十分曲折，不能直接由无人机执行。

技术实现思路

1、本发明的目的是为了解决现有voronoi图难以用于三维场景的路径规划，以及维诺图本身并非为无人机路径规划设计，得到的路线图通常十分曲折，不能直接由无人机执行的问题，而提出一种基于完全膨胀图的无人机最优路径规划方法。

2、一种基于完全膨胀图的无人机最优路径规划方法具体过程为：

3、步骤一：构建初始栅格地图；

4、步骤二：基于初始栅格地图构建代价地图；

5、步骤三：根据代价地图获得地图骨架；

6、步骤四：在代价地图中搜索一条最优的路径。

7、本发明的有益效果为：

8、本发明结合障碍物膨胀修正与维诺图的技术思路，提出了一种基于完全膨胀图的路径规划方法，可以在平方时间复杂度o(n2)内获得二维或三维的与维诺图类似的安全性最优的路线图，结合随机采样或图搜索算法，得到无人机可执行的路径。

9、本发明采用膨胀算法对包含障碍的地图进行预处理，在较低时间复杂度下获得距离障碍物距离最远的路线图，即安全性最优的路线图。

10、本发明提出的完全膨胀地图方法可以用于二维与三维场景，解决了维诺图难以用于三维场景的路径规划的缺陷。

11、本发明将安全性最优的路线图用于指导图搜索的搜索过程，获得平滑路径，解决了维诺图本身并非为无人机路径规划设计，得到的路线图通常十分曲折的问题。

12、对于静态场景，本发明的代价地图可以离线获得，在路径规划时直接使用代价地图，不会增加路径规划的时间；同时代价地图降低了图搜索过程的搜索维度，可以提高图搜索过程的速度。

技术特征：

1.一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述方法具体过程为：

2.根据权利要求1所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤一中构建初始栅格地图；具体过程为：

3.根据权利要求2所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤一二中基于场景的边界、栅格尺寸、栅格地图原点在世界坐标系下的坐标、以及障碍物的顶点列表构建栅格地图；具体过程为：

4.根据权利要求3所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤二中基于初始栅格地图构建代价地图；具体过程为：

5.根据权利要求4所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤二一中令迭代次数k＝1；基于栅格地图初始化代价地图和膨胀增量地图；

6.根据权利要求5所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤二三中更新代价地图；过程为：

7.根据权利要求6所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤三中根据代价地图获得地图骨架；具体过程为：

8.根据权利要求7所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤三一中设计一组算子；

9.根据权利要求8所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤四中在代价地图中搜索一条最优的路径；具体过程为：

10.根据权利要求9所述的一种基于完全膨胀图的无人机最优路径规划方法，其特征在于：所述步骤四三中扩展当前节点的相邻节点，然后将邻居节点加入到开集中；过程为：

技术总结
一种基于完全膨胀图的无人机最优路径规划方法，本发明涉及基于完全膨胀图的无人机最优路径规划方法，本发明属于无人机器人路径规划领域。本发明的目的是为了解决现有Voronoi图难以用于三维场景的路径规划，以及维诺图本身并非为无人机路径规划设计，得到的路线图通常十分曲折，不能直接由无人机执行的问题。一种基于完全膨胀图的无人机最优路径规划方法具体过程为：步骤一：构建初始栅格地图；步骤二：基于初始栅格地图构建代价地图；步骤三：根据代价地图获得地图骨架；步骤四：在代价地图中搜索一条最优的路径。

技术研发人员：姚蔚然,胡家宁,邵翔字,吴立刚,李晓磊,孙光辉
受保护的技术使用者：哈尔滨工业大学
技术研发日：
技术公布日：2024/12/5