欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2021105749577
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
专利领域: 测量;测试
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.基于Voronoi图的避障最短路径规划方法,其特征在于,包括以下步骤:步骤一:采集障碍物的信息,包括出发点位置、目的点位置、障碍物的大小及障碍物的中心点位置;

步骤二:根据障碍物的中心点位置,将若干个障碍物的中心点视为一个平面上的点集S,对点集S通过Delaunay三角剖分的方法构造最优三角剖分,构建得到三角剖分的直线对偶图即为点集S、障碍物中心点所对应的Voronoi图;

步骤三:将Voronoi图的每条边向决定该边的两个障碍物所在的方向进行扩展,扩展得到一个简单多边形;

步骤四:求取简单多边形内两点的Euclidean最短路径,得到最终的避障最短路径。

2.根据权利要求1所述基于Voronoi图的避障最短路径规划方法,其特征在于,所述步骤一中障碍物的大小为障碍物中心点到障碍物边缘的最大值A。

3.根据权利要求1所述基于Voronoi图的避障最短路径规划方法,其特征在于,所述步骤三中将Voronoi图的每条边向决定该边的两个障碍物所在的方向进行扩展的距离,由障碍物中心点到障碍物边缘的最大值A和两个障碍物中心点之间的距离所决定。

4.根据权利要求3所述基于Voronoi图的避障最短路径规划方法,其特征在于,所述步骤三中将Voronoi图的每条边向决定该边的两个障碍物所在的方向进行扩展的距离,具体计算为:

将两个障碍物中心点记为点d1和d2,将两个障碍物中心点之间的距离记为l,则对该条Voronoi图的边向d1方向扩展的距离为 ‑(d1对应的障碍物中心点到障碍物边缘的最大值A),向d2方向扩展的距离为 ‑(d2对应的障碍物中心点到障碍物边缘的最大值A)。

5.根据权利要求1所述基于Voronoi图的避障最短路径规划方法,其特征在于,所述步骤四中求取简单多边形内两点的Euclidean最短路径,具体包括:将得到的一个简单多边形分解为若干个Y单调多边形;

对每一个Y单调多边形进行三角剖分,将剖分得到的每一个三角形视为一个顶点,得到三角剖分的对偶图;

判断出发点与目的点是否均处于简单多边形中,若判断是,则找到出发点与目的点所在的三角形,并确认这两个三角形在三角剖分的对偶图中所对应的对偶点,求取这两个对偶点间的最短对偶路径;否则,判断出发点或目的点有不处于简单多边形中的情况,则将不处于简单多边形内的点向距离最近的简单多边形的边作垂线,找到出发点或是目的点与简单多边形的垂点所在的三角形在三角剖分的对偶图中所对应的对偶点,求取该两个对偶点间的最短对偶路径;

通过Rubberband算法求取从出发点到目的点有次序的经过若干线段的最短路径,以得到最终的避障最短路径。

6.根据权利要求5所述基于Voronoi图的避障最短路径规划方法,其特征在于,所述通过Rubberband算法求取得到最终的避障最短路径,包括:选取出发点、目的点以及经过的每条线段的中点的连线作为初始路径;

再不断求取局部最优解得到新的路径,直到求取到的新路径与之前的路径长度差小于某一阈值,并将该求取到的新路径作为最终的避障最短路径。