(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 20221047893 3.6 (22)申请日 2022.04.29 (71)申请人 中山大学 地址 510275 广东省广州市海珠区新港西 路135号 (72)发明人 朱波　陈帝博　朱翔宇　朱国宾　 张清瑞　 (74)专利代理 机构 广州三环 专利商标代理有限 公司 44202 专利代理师 陈旭红 (51)Int.Cl. G06V 20/17(2022.01) G06V 10/44(2022.01) G06Q 10/04(2012.01) G05D 1/12(2006.01) (54)发明名称 一种最短 路径生成方法及装置 (57)摘要 本发明公开了一种最短路径生成方法及装 置， 其中所述方法包括： 对目标地图进行角点检 测， 生成目标地图内的所有目标角点， 基于各个 目标角点生成从路径起点出发、 所有所述目标角 点与所述路径起点 以最短路径距离连接的初始 路径。 所述初始路径实现了各个目标角点间的局 部最优连接关系。 更进一步的， 所述目标地图中 随机生成测试节点， 根据测试节 点对所述初始路 径的连接关系进行优化， 实现目标地图的全局最 优连接关系， 根据优化结果生成最短路径， 进一 步提高路径的生成质量和精度。 权利要求书3页 说明书13页 附图1页 CN 114863300 A 2022.08.05 CN 114863300 A 1.一种最短路径生成方法， 其特 征在于， 包括： 对目标地图进行角点检测， 生成所述目标地图内的所有目标角点； 生成从路径起点出发、 所有所述目标角点与所述路径起点以最短路径距离连接的初始 路径； 在所述目标地图中随机生成测试节点； 当任一所述目标角点通过所述测试节点与所述路径起点连接的路径距离小于该目标 角点与所述路径起 点的最短路径 距离时， 更新所述初始路径的连接关系， 生成最短路径。 2.如权利要求1所述的一种最短路径生成方法， 其特 征在于， 所述角点检测， 具体包括： 获取所述目标地图中第一像素点的灰度值； 将所述第一像素点分别在x方向和y方向移动预设距离； 获取所述第一像素点移动所述预设距离后的灰度变化 值； 根据角点响应函数判断所述第一像素点是否为所述目标角点。 3.如权利要求2所述的一种最短路径生成方法， 其特征在于， 所述生成所述目标地图内 的所有目标角点， 具体包括： 对所述目标地图内的所有像素点进行所述角点检测， 生成所述目标地图内的所有目标 角点； 对所有所述目标角点进行位置检测， 当检测到目标角点位于所述目标地图中的障碍区 域时， 将所述检测目标角点移动至邻近可行区域， 以使所有所述 目标角点位于所述 目标地 图中的可 行区域。 4.如权利要求1所述的一种最短路径生成方法， 其特征在于， 所述生成从路径起点出 发、 所有所述目标角点与所述路径起 点以最短路径 距离连接的初始路径， 具体包括： 将所有所述目标角点、 所述路径起 点和路径终点进行相互直线连接， 生成角点连接集； 提取所述角点连接集中不受所述目标地图中障碍区域阻断的直线连接路径， 生成初始 连接路径集； 对所述初始连接路径集进行优化， 生成所述初始路径。 5.如权利要求4所述的一种最短路径生成方法， 其特征在于， 所述随所述初始连接路径 集进行优化， 生成所述初始路径， 具体包括： 获取所述初始连接路径集中所有与 所述路径起点直接连接的目标角点， 并记录目标角 点与所述路径起 点的连接关系和对应的直连路径 距离， 生成第一连接集； 获取所述初始连接路径集中不可与 所述路径起点直接连接的目标角点， 生成第 一待连 接集； 根据最短路径连接原则将所述第一待连接集中的所有待连接目标角点添加至所述第 一连接集， 更新所述第一连接集中目标角点与所述路径起 点的连接关系； 根据更新后的所述第一连接集， 生成从路径起点出发、 所有所述目标角点与所述路径 起点以最短路径 距离连接的初始路径。 6.如权利要求5所述的一种最短路径生成方法， 其特征在于， 所述根据最短路径连接原 则将所述第一待连接集中的所有待连接目标角点添加至所述第一连接集， 添加所述第一连 接集中目标角点与所述路径起 点的连接关系， 具体包括： 对所述第一待连接集中的第一待连接目标角点执行添加操作； 其中， 所述添加操作具权　利　要　求　书 1/3 页 2 CN 114863300 A 2体包括： 获取所述第一连接集中所有与所述第一待连接目标角点连接的连接目标角点； 将 第一连接目标角点通过所述第一待连接目标角点与所述路径起点连接的路径距离作为第 一路径距离； 将所述第一连接目标角点与所述路径起点的直连路径距离作为第二路径距 离； 当所述第一路径距离小于所述第二路径距离时， 将所述第二路径距离作为所述第一连 接目标角点与所述路径起点连接的最短路径距离； 将所述第二路径距离对应的连接 关系更 新至所述第一连接集； 依次对所有与 所述第一待连接目标角点连接的连接目标角点执行所述添加操作， 生成 第一更新连接集。 7.如权利要求6所述的一种最短路径生成方法， 其特征在于， 所述根据 更新后的所述第 一连接集， 生成从路径起点出发、 所有所述 目标角点与所述路径起点以最短路径距离连接 的初始路径， 还 包括： 根据与所述路径起点的直线距离依次对所述第一待连接集中的所有待连接目标角点 执行所述添加操作； 将待连接目标角点添加至前一待连接目标角点生成的更新连接集， 直至所述第 一待连 接集中的所有 待检测目标角点全部 完成所述添加操作， 生成最终更新连接集； 提取所述最终更新连接集中的路径连接关系， 生成所述初始路径。 8.如权利要求1所述的一种最短路径生成方法， 其特征在于， 所述当任一所述目标角点 通过所述测试节点与所述路径起点连接的路径距离小于该目标角点与所述路径起点的最 短路径距离时， 更新所述初始路径的连接关系， 生成最短路径， 具体包括： 对所述测试节点执行更新操作； 其中， 所述更新操作具体包括： 获取预设范围内所述初 始路径中所有与所述测试节点直连的目标角点； 获取所有与所述测试节点直连的目标角点 与所述路径起点的最短路径距离， 生成第一搜索路径距离集； 获取所有与所述测试节点直 连的目标角点通过所述测试节点与所述路径起点连接的路径距离， 生成第二搜索路径距离 集； 当所述第二搜索路径距离集中有任一第二搜索路径距离小于所述第一搜索路径距离集 中对应的第一搜索路径距离时， 获取该路径距离对应的目标角点； 将所述第二搜索路径作 为所述对应的目标角点与所述路径起 点的最短路径， 并更新所述初始路径的连接关系。 9.如权利要求8所述的一种最短路径生成方法， 其特征在于， 所述当任一所述目标角点 通过所述测试节点与所述路径起点连接的路径距离小于该目标角点与所述路径起点的最 短路径距离时， 更新所述初始路径的连接关系， 生成最短路径， 还 包括： 执行预设次数的测试节点 生成指令； 对每一次生成的测试节点执行所述更新操作， 直至最后一次更新操作完成， 生成所述 最短路径。 10.一种最短路径生成装置， 其特征在于， 包括： 角点生成模块、 路径生成模块和路径优 化模块； 所述角点生成模块用于对目标地图进行角点检测， 生成所述目标地图内的所有目标角 点； 所述路径生成模块用于生成从路径起点出发、 所有所述目标角点与 所述路径起点以最 短路径距离连接的初始路径； 所述路径优化模块用于在所述目标地图中随机生成测试节点； 当任一所述目标角点通权　利　要　求　书 2/3 页 3 CN 114863300 A 3