(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210887855.5 (22)申请日 2022.07.26 (71)申请人 中国科学院自动化研究所 地址 100190 北京市海淀区中关村东路95 号 (72)发明人 熊刚　陈曾华　刘胜　沈震　田星　 方启航　韩云君　吴怀宇　王飞跃　 (74)专利代理 机构 北京路浩知识产权代理有限 公司 11002 专利代理师 李文清 (51)Int.Cl. G05B 19/418(2006.01) G06Q 10/08(2012.01) G06Q 10/04(2012.01) G06N 3/12(2006.01) (54)发明名称 AGV拣货路径规划方法及系统 (57)摘要 本发明涉及路线规划技术领域， 提供一种 AGV拣货路径规划方法及系统， 摒弃了现有AGV 针 对单一种类的货物执行分拣任务的工作模式， 而 是针对一个订单中的多种货物依次进行分拣， 如 此可以提高货物的分拣效率， 缩短AGV的行驶路 程。 而且， AGV在执行完成一个订单后的停放位置 并非是停车区， 而是前一订单中的首次拣货位置 本， 可以提高AGV的工作效率， 节约重回停车区导 致的时间成本和电耗成。 此外， 结合各备选路径 的路径长度、 路径转角以及路径拐点个数， 建立 TSP模型， 并以遗传算 法对TSP模型进行求解的方 式确定各备选路径中的全局规划路径， 相比于 现 有的A*算法， 其搜索效率大大提升， 可以提升路 径规划效率， 提高货物的分拣效率。 权利要求书2页 说明书16页 附图5页 CN 115421448 A 2022.12.02 CN 115421448 A 1.一种AGV拣货路径规划方法， 其特 征在于， 包括： 获取当前订单并确定所述当前订单对应的一个目标AGV， 所述当前订单中包含有多种 货物； 以所述目标AGV的停放位置为起始节点、 各种货物的存放位置为中间节点、 所述当前订 单的目标位置为结束节点， 构建各备选路径； 所述停放位置包括所述当前订单 的前一订单 中的首次拣货位置； 基于所述各备选路径的路径长度、 路径转角以及路径拐点个数， 建立TSP模型， 并采用 遗传算法， 对所述TS P模型进行求 解， 确定所述各 备选路径中的全局规划路径。 2.根据权利要求1所述的AGV拣货路径规划方法， 其特征在于， 所述采用遗传算法， 对所 述TSP模型进行求 解， 确定所述各 备选路径中的全局规划路径， 具体包括： 将所述各备选路径作为个体， 将所述各备选路径的中间节点作为基因， 并基于所述各 备选路径的路径长度、 路径转角以及路径拐点个数， 确定个 体适应度； 采用两个Flink集群， 分别初始化得到第一种群和第二种群， 并对所述第一种群的个体 进行迭代更新得到第三种群， 对所述第二种群的个 体进行迭代更新得到第四种群； 从所述第三种群以及所述第四种群中确定最佳个体适应度对应的第 一个体， 将所述第 一个体确定为所述全局规划路径。 3.根据权利要求2所述的AGV拣货路径规划方法， 其特征在于， 所述采用两个Flink集 群， 分别初始化得到第一种群和第二种群， 具体包括： 采用第一Flink集群， 初始化得到第一备选种群， 并采用第二Flink集群， 初始化得到第 二备选种群； 基于所述第一备选种群的个 体适应度方差， 确定所述第一种群； 基于所述第二备选种群的每个个体与最佳个体适应度对应的第二个体之间的相似度 均值， 确定所述第二种群。 4.根据权利要求2所述的AGV拣货路径规划方法， 其特征在于， 所述对所述第一种群的 个体进行迭代更新得到第三种群， 具体包括： 采用第一Flink集群的主节点， 将所述第一种群划分为多个第一子种群， 并采用所述第 一Flink集群的任务节点分布式并行对每个第一子种群进行第一类基因操作， 得到更新后 的第一子种群； 采用所述主节点， 对所有更新后的第一子种群进行汇合， 得到第一 新种群； 采用所述第一Flink集群对所述第一新种群迭代进行划分、 第一类基因操作以及汇合， 得到所述第三种群。 5.根据权利 要求4所述的AGV拣货路径规划方法， 其特征在于， 所述采用所述第一Flink 集群中的任务节点分布式并行对每 个第一子种群进行第一类 基因操作， 具体包括： 对于所述第一Flink集群 中的任一任务节点， 采用所述任一任务节点， 基于所述第一子 种群中的任一个 体的个体适应度， 确定所述任一个 体对应的激活函数； 基于所述任一个体的激活函数以及所述第 一类基因操作的操作概率范围， 确定所述任 一个体对应的第一类 基因操作的目标操作概 率； 基于所述目标操作概 率， 对所述任一个 体进行所述第一类 基因操作。 6.根据权利要求1 ‑5中任一项所述的AGV拣货路径规划方法， 其特征在于， 所述采用遗权　利　要　求　书 1/2 页 2 CN 115421448 A 2传算法， 对所述TS P模型进行求 解， 确定所述各 备选路径中的全局规划路径， 之后还 包括： 基于动态窗口算法， 对所述全局规划路径进行局部路径规划， 得到所述目标AGV的局部 规划路径。 7.根据权利要求6所述的AGV拣货路径规划方法， 其特征在于， 所述动态窗口算法的动 态窗口评价函数基于所述目标AGV的当前模拟 速度信息的评价函数、 所述目标AGV的模拟轨 迹与所述目标AGV周围的静态障碍物之间的最近距离以及所述模拟 轨迹的终点方向与所述 全局规划路径上的目标点之间的方位角偏差确定， 所述目标点为以所述 目标AGV的当前位 置为圆心、 以目标距离为半径的圆周与所述全局规划路径的交点。 8.根据权利要求6所述的AGV拣货路径规划方法， 其特征在于， 所述基于动态窗口算法， 对所述全局规划路径进行局部路径规划， 得到所述目标AGV的局部规划路径， 具体包括： 在局部路径规划过程中， 若所述目标AGV 的当前位置的第一预设范围内存在多个第一 类AGV， 则控制所述多个第一类AGV停止运行， 并按所述多个第一类AGV的序号由大到小的顺 序依次重新对每个第一类AGV的全局规划路径进行局部路径 规划， 以使每个第一类AGV驶离 所述第一预设范围。 9.根据权利要求8所述的AGV拣货路径规划方法， 其特征在于， 所述基于动态窗口算法， 对所述全局规划路径进行局部路径规划， 得到所述目标AGV的局部规划路径， 具体包括： 在局部路径规划过程中， 若所述目标AGV 的当前位置的第二预设范围内存在多个第二 类AGV， 则控制所述多个第二类AGV以第一加速度进行减速运行； 若所述目标AGV的当前位置的第三预设范围内存在多个第三类AGV， 则控制所述多个第 三类AGV以第二加速度进行减速运行； 其中， 所述第二预设范围中任一点与所述目标AGV的距离均大于所述第一预设范围中 任一点与所述目标AGV的距离， 所述第三预设范围中任一点与所述目标AGV的距离均大于所 述第二预设范围中任一 点与所述目标AGV的距离， 所述第一加速度大于所述第二加速度。 10.一种AGV拣货路径规划系统， 其特 征在于， 包括： 获取模块， 用于获取当前订单并确定所述当前订单对应的一个目标AGV， 所述当前订单 中包含有多种货物； 备选路径构建模块， 用于以所述目标AGV的停放位置为起始节点、 各种货物的存放位置 为中间节点、 所述当前订单的目标位置为结束节 点， 构建各备选路径； 所述停 放位置包括所 述当前订单的前一 订单中的首次拣货位置； 全局路径规划模块， 用于基于所述各备选路径的路径长度、 路径转角以及路径拐点个 数， 建立TSP模型， 并采用遗传算法， 对所述TSP模型进行求解， 确 定所述各备选路径 中的全 局规划路径。权　利　要　求　书 2/2 页 3 CN 115421448 A 3