(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211276457.6 (22)申请日 2022.10.19 (71)申请人 睿羿科技 （山 东） 有限公司 地址 255400 山东省淄博市临淄区金岭回 族镇纬三路168号20 3室 (72)发明人 郑勇飞　王维　 (74)专利代理 机构 济南宝宸专利代理事务所 (普通合伙) 37297 专利代理师 荆向勇 (51)Int.Cl. G06Q 10/08(2012.01) G06F 16/901(2019.01) G06F 16/29(2019.01) (54)发明名称 一种静态障碍物下室内多任务点路径规划 方法 (57)摘要 本发明属于物 流机器人领域， 尤其涉及一种 静态障碍物下室内多任务点路径 规划方法， 包括 以下步骤： S1、 采集静态障碍地图， 标注生成兴趣 点集合M； S2、 采用Floyd算法， 生成兴趣 点拓扑连 接序列表； S3、 输入兴趣点拓扑连接序列表； S4、 输入任务点集合F； S5、 查询 兴趣点集合X； S6、 采 用模拟退火算法求解兴趣点集合X中的兴趣点， 得到兴趣点的有效排列Q(X)； S7、 组合求解出的 兴趣点连接关系得到多任务最优组合序列。 本发 明有效解决了静态障碍地图复杂度对规划效率 的影响， 提高了规划效率以及 多任务最优路径稳 定性， 从而提高了 仓库搬运机 器人的运送效率。 权利要求书2页 说明书6页 附图5页 CN 115358681 A 2022.11.18 CN 115358681 A 1.一种静态障碍物下室内多任务 点路径规划方法， 其特 征在于包括以下步骤： S1、 采集静态障碍地图， 标注生成兴趣点集合M={1， 2， ……， m}， 编辑兴趣点集合M中兴 趣点之间的连接关系； S2、 采用Floy d算法， 利用多源最短路径算法计算兴趣点集合M中某一兴趣点i到其余兴 趣点集合K中任一兴趣点可联通的路径距离最优以及次优解， 生成兴趣点拓扑连接序列 表， 以id序列和序列表路径 距离组成， 其中， 兴趣点 集合K是指除兴趣点 i以外的兴趣点的集 合； S3、 输入兴趣点拓扑 连接序列表； S4、 输入任务点集合F={f0， f1， f2， f3 ……fn}， 其中机器人位置为 起点f0； S5、 查询兴趣点集合X={x0， x1， x2， x3 ……xn}， 其中兴趣点集合X为兴趣点集合M中与任 务点集合F中的任务 点一一对应的兴趣点的集 合； S6、 采用模拟退火算法求解兴趣点集合X中的兴趣点， 得到兴趣点的有效排列Q(X)= {v1， v2……vn}； S7、 组合求解出的兴趣点连接关系得到多任务 最优组合序列。 2.根据权利要求1所述的一种静态障碍物下室内多任务点路径规划方法， 其特征在于： 所述的S2中， Fl oyd算法生成兴趣点拓扑 连接序列表的具体步骤为： S21、 通过拓扑地图表， 获取兴趣点的相邻连接点关系， 建立邻接矩阵dist储存路径， 对 相连两点之间的距离进行 标记， 如果两点没有直接相连则标记为无穷大； S22、 将第1个兴趣点到第n个兴趣点依次加入拓扑地图表中， 在每个兴趣点加入时试探 是否有路径长度被更改； S23、 遍历拓扑地图表中每一个兴趣点， 用i， j表示其中两点， 判断i， j两点之间距离是 否因为新加入的点z而发生 最小距离变化， 如果状态发生改变， 则更新 i， j两点之间距离； S24、 重复上述 步骤S21‑S23直到最后加入兴趣点试探 完成； S25、 输出最短路径和次优路径的兴趣点联通序列， 同时最终状态代表点与点之间的最 短路径， 建立兴趣点拓扑 连接序列表。 3.根据权利要求2所述的一种静态障碍物下室内多任务点路径规划方法， 其特征在于： 所述的S23中， 状态发生改变的更新方法的方程 为： dp[i][j]=min(dp[i][j]， dp[i][z]+dp[z][j])， 其中dp[i][j]为i到j的最短路径， dp [i][z]为 i到z的最短路径， dp[z][j]为z 到j的最短路径。 4.根据权利要求1所述的一种静态障碍物下室内多任务点路径规划方法， 其特征在于： 所述的S6中， 模拟退火算法包括以下步骤： S31、 设置的主要控制参数包括： 快速降温速率q1， 快速降温高温阈值G， 二次精准降温 速率q2、 初始温度T0、 当前温度为T， 结束温度Td、 精度值K、 计数值count以及链长L； S32、 查询任务点对应的兴趣点序列， 随机生成序列初始解Y1， 计数值count设置为0， 精 度值K设置为1； S33、 通过对当前解Y1进行变异， 对构成新解的元素进行交换、 位移、 置换、 倒置的多重 方式变异， 并用二 零域变换法产生 新的序列组合 新解Y2； S34、 建立Metropolis准则， 若路径长度函数为f(Y)， 则当前解的路径长度为f(Y1)， 新 解的路径长度为f(Y2)， 路径差为df=f(Y2) ‑f(Y1)， 则接受新 解路径序列概 率准则为：权　利　要　求　书 1/2 页 2 CN 115358681 A 2； S35、 精度值K加1， 判断K 是否大于L， 是则进行降温， 否则返回S3 3继续迭代； S36、 根据当前温度T是否大于快速降温高温阈值G， 判断是否需要快速低精度降温， 是 则采用快速降温速率q1进行降温， 即T=q1*T， 继续迭代执行二次精 准降温； 否则采用二次精 准降温速率q2进行降温， 即T=q2*T， 同时计数值count加1； S37、 若T小于结束温度Td， 则停止迭代输出当前状态， 否则返回S32继续迭代； S38、 得到有效排列Q(X)={v1， v2 ……vn}。 5.根据权利要求1所述的一种静态障碍物下室内多任务点路径规划方法， 其特征在于： 所述的S7中的最优组合序列的具体步骤为： 通过离线兴趣点连接拓扑表查询获取N个任务 点之间的距离， 计算有效排列Q(X)={v1， v2 ……vn}并回到起 点， 使得： 取得最小值， 即全局多任务组合路径最短， 其中 表示兴趣点i到兴趣点i+ 1的路径距离， 表示兴趣点vn到兴趣点v1的 路径距离。权　利　要　求　书 2/2 页 3 CN 115358681 A 3