本发明涉及一种用于四向穿梭车的路径规划方法，以四向穿梭车立体库中可四向行驶的节点为交叉节点，用于放置货物的货位为货位节点，相邻交叉节点的连线为路径段，构建四向穿梭车运行地图；以四向穿梭车当前所在交叉节点/所在路径段可达的最接近交叉节点为初始交叉节点，以目标节点所在交叉节点/货位节点绑定的路径段可达的最接近交叉节点为目标交叉节点，以四向穿梭车的运行时间为成本函数，在成本函数的约束下进行交叉节点之间的路径查找，形成四向穿梭车的规划路径。本发明提出了一种动态树形数据结构来构建地图降低路径算法计算的时间

　　(19)国家知识产权局 (12)发明专利 (10)授权公告号 CN 113359774 B (45)授权公告日 2022.07.15 (21)申请号 6.3 (56)对比文件 CN 112068544 A,2020.12.11 (22)申请日 2021.07.07 CN 110398965 A,2019.11.01 (65)同一申请的已公布的文献号 CN 108469827 A,2018.08.31 申请公布号 CN 113359774 A CN 113075927 A,2021.07.06 (43)申请公布日 2021.09.07 CN 109542098 A,2019.03.29 (73)专利权人 江苏智库智能科技有限公司 CN 107168316 A,2017.09.15 地址 210039 江苏省南京市雨花台区龙藏 审查员 盛艳燕 大道1-1号 (72)发明人 蔡传玉于静楠 (74)专利代理机构 江苏致邦律师事务所 32230 专利代理师 葛胜非 (51)Int.Cl. G05D 1/02 (2020.01) 权利要求书2页 说明书6页 附图2页 (54)发明名称 一种用于四向穿梭车的路径规划方法 (57)摘要 本发明涉及一种用于四向穿梭车的路径规 划方法，以四向穿梭车立体库中可四向行驶的节 点为交叉节点，用于放置货物的货位为货位节 点，相邻交叉节点的连线为路径段，构建四向穿 梭车运行地图；以四向穿梭车当前所在交叉节 点/所在路径段可达的最接近交叉节点为初始交 叉节点，以目标节点所在交叉节点/货位节点绑 定的路径段可达的最接近交叉节点为目标交叉 节点，以四向穿梭车的运行时间为成本函数，在 成本函数的约束下进行交叉节点之间的路径查 找，形成四向穿梭车的规划路径。本发明提出了 一种动态树形数据结构来构建地图降低路径算 B 法计算的时间复杂度，可配置路径可行性与方向 4 性，适用于更多的应用场景，且路径查找的算法 7 7 9 时间复杂度低。 5 3 3 1 1 N C CN 113359774 B 权利要求书 1/2页 1.一种用于四向穿梭车的路径规划方法，其特征在于，包括： 以四向穿梭车立体库中可四向行驶的节点为交叉节点，用于放置货物的货位为货位节 点，相邻交叉节点的连线为路径段，构建四向穿梭车运行地图； 将路径段与货位节点绑定； 对各路径段预设可行驶性及可行驶方向； 以四向穿梭车当前所在交叉节点/所在路径段可达的最接近交叉节点为初始交叉节 点，以目标节点所在交叉节点/货位节点绑定的路径段可达的最接近交叉节点为目标交叉 节点，以四向穿梭车的运行时间为成本函数，在成本函数的约束下进行交叉节点之间的路 径查找，形成四向穿梭车的规划路径； 其中，路径查找的过程包括： a.建立候选路径池和可用路径池，将以初始交叉节点为起点的路径段作为初始路径存 放到候选路径池中； b.判断四向穿梭车的初始交叉节点是否和目标交叉节点相同，如果相同，则按照默认 路径行驶，跳转h；否则跳转c； c.查找初始交叉节点是否有相邻交叉节点，如果没有，跳转d，否则转e； d.从候选路径池中移除该路径，计算候选路径池size是否为0，若size≠0，则跳转g；若 size＝＝0，则判断可用路径池是否为空，如果为空，则无可用路径，跳转h；如果可用路径池 不为空，则在可用路径池中寻找路径成本最小的路径作为四向车的运行路径，跳转h； e.判断相邻交叉节点是否包含目标交叉节点，如果包含，则将生成路径存放至可用路 径池中，跳转f；如果不包含，则将相邻交叉节点与候选路径池中的初始路径组成的路径作 为新的初始路径，替换候选路径池中原有的初始路径，跳转g； f.判断可用路径池size是否大于设定值，若size＞设定值则从可用路径池中选择路径 成本最小的路径作为四向车的行驶路径，跳转h；若size≤设定值则继续遍历路径，跳转g； g.取出候选路径池中路径成本最小的一条路径的最后一位交叉节点作为新的初始交 叉节点，重复步骤b～f； h.结束路径查找。 2.根据权利要求1所述的方法，其特征在于，还包括，将候选路径池和可用路径池中的 路径按路径成本升序排序。 3.根据权利要求1所述的方法，其特征在于，根据四向穿梭车立体库实际布局将路径段 与货位节点绑定。 4.根据权利要求1所述的方法，其特征在于，根据四向穿梭车立体库实际布局确定路径 段的可行驶性及可行驶方向。 5.根据权利要求1所述的方法，所述初始交叉节点的判断方式为： 当四向穿梭车的当前位置为路径段时，判断路径段的可行驶方向： 如果为双向行驶，则路径段两端的交叉节点为最接近交叉节点； 如果为单向行驶，则路径段方向下游节点为最接近交叉节点，即初始交叉节点。 6.根据权利要求1所述的方法，所述目标交叉节点的判断方式为： 当目标节点为货位节点时，判断货位节点绑定的路径段的可行驶方向： 如果为双向行驶，则路径段两端的交叉节点为最接近交叉节点； 2 2 CN 113359774 B 权利要求书 2/2页 如果为单向行驶，则路径段方向下游节点为最接近交叉节点，即目标交叉节点。 7.根据权利要求1所述的方法，其特征在于，所述四向穿梭车的运行时间包括四向穿梭 车执行反应时间及四向穿梭车各动作的运行时间。 8.根据权利要求1所述的方法，其特征在于，所述四向穿梭车各动作的运行时间包括直 行动作、转弯动作、升/降动作的运行时间。 9.根据权利要求1、7或8任一项所述的方法，其特征在于，所述四向穿梭车的运行时间 计算包括： I.将每条路径切分为四向穿梭车动作，分为直行动作、换向动作、顶升动作与下降动 作； II.根据四向穿梭车实际的换向时间配置换向动作成本； III.根据四向穿梭车实际的顶升/下降的时间配置的顶升/下降动作成本； IV.根据PLC程序中的实际速度曲线配置四向穿梭车直线页 一种用于四向穿梭车的路径规划方法 技术领域 [0001] 本发明属于自动化仓储设备及其控制技术领域，具体涉及一种用于四向穿梭车的 路径规划方法。 背景技术 [0002] 物流设备移动机器人是一个集环境信息感知、路径规划、行为控制与执行等多种 功能于一体的综合智能系统。而其中的路径规划技术是机器人研究领域的关键技术之一， 是机器人完成任务的安全保障，是机器人智能化程度的标志之一，同时也是人工智能与机 器人学的一个重要的结合点和研究热点。 [0003] 自上世纪70年代起，路径规划问题就已经受到了国内外众多机构和学者的广泛关 注，尤其是80年代以来，在人工智能、计算机科学、数学和机械工程等领域内的专家学者们 的共同努力下，路经规划技术的研究在理论和实践方面都有了很大的提高。 [0004] 近年来，随着机器人技术越来越多的渗入到我们的生产生活中，具有自主感知决 策和执行功能的智能移动机器人得到了快速的发展，随着人类在生存和工作中对机器人代 为劳动的要求不断增长，自主移动式机器人研究取得了很大发展。随着机器人应用的日益 广泛，及机器人作业效率问题所具有的复杂性、随机性、多约束性、多目标性等特点，如何在 各种不同的环境中具体问题具体地分析，合理有效地选择路径规划方法及策略等问题已经 成为机器人研究中的具有非常实际意义的课题。现有技术中，四向穿梭车在地图构建基本 使用栅格化方法构建一种二位数组计算路径，这样计算路径的时间复杂度会随着地图的增 加成指数增长；同时在评价路径标准为路径的距离的长短，没有考虑四向穿梭车的换向与 顶升的时间，计算出的路径可能耗时不是最短；最后，现有的路径计算方法都以枚举法或迭 代次数作为结束条件，这样影响算法的计算效率。 发明内容 [0005] 为解决现有技术中的地图构建、成本函数定义以及最优路径计算方法的问题，本 发明的目的是提供一种用于四向穿梭车的路径规划方法。 [0006] 为解决上述技术问题，本发明采用的技术方案为： [0007] 一种用于四向穿梭车的路径规划方法，包括： [0008] 以四向穿梭车立体库中可四向行驶的节点为交叉节点，用于放置货物的货位为货 位节点，相邻交叉节点的连线为路径段，构建四向穿梭车运行地图； [0009] 将路径段与货位节点绑定； [0010] 对各路径段预设可行驶性及可行驶方向； [0011] 以四向穿梭车当前所在交叉节点/所在路径段可达的最接近交叉节点为初始交叉 节点，以目标节点所在交叉节点/货位节点绑定的路径段可达的最接近交叉节点为目标交 叉节点，以四向穿梭车的运行时间为成本函数，在成本函数的约束下进行交叉节点之间的 路径查找，形成四向穿梭车的规划路径。 4 4 CN 113359774 B 说明书 2/6页 [0012] 作为一种优选的实施方式，所述路径查找过程包括： [0013] a.建立候选路径池和可用路径池，将以初始交叉节点为起点的路径段作为初始路 径存放到候选路径池中； [0014] b.判断四向穿梭车的初始交叉节点是否和目标交叉节点相同，如果相同，则按照 默认路径行驶，跳转h；否则跳转c； [0015] c.查找初始交叉节点是否有相邻交叉节点，如果没有，跳转d，否则转e； [0016] d.从候选路径池中移除该路径，计算候选路径池size是否为0，若size≠0，则跳转 g；若size＝＝0，则判断可用路径池是否为空，如果为空，则无可用路径，跳转h；如果可用路 径池不为空，则在可用路径池中寻找路径成本最小的路径作为四向车的运行路径，跳转h； [0017] e.判断相邻交叉节点是否包含目标交叉节点，如果包含，则将生成路径存放至可 用路径池中，跳转f；如果不包含，则将相邻交叉节点与候选路径池中的初始路径组成的路 径作为新的初始路径，替换候选路径池中原有的初始路径，跳转g； [0018] f.判断可用路径池size是否大于设定值，若size＞设定值则从可用路径池中选择 路径成本最小的路径作为四向车的行驶路径，跳转h；若size≤设定值则继续遍历路径，跳 转g； [0019] g.取出候选路径池中路径成本最小的一条路径的最后一位交叉节点作为新的初 始交叉节点，重复步骤b～f； [0020] h.结束路径查找。 [0021] 进一步的，还包括，将候选路径池和可用路径池中的路径按路径成本升序排序。 [0022] 作为一种优选的实施方式，根据四向穿梭车立体库实际布局将路径段与货位节点 绑定。 [0023] 作为一种优选的实施方式，根据四向穿梭车立体库实际布局确定路径段的可行驶 性及可行驶方向。 [0024] 作为一种优选的实施方式，所述初始交叉节点的判断方式为： [0025] 当四向穿梭车的当前位置为路径段时，判断路径段的可行驶方向： [0026] 如果为双向行驶，则路径段两端的交叉节点为最接近交叉节点； [0027] 如果为单向行驶，则路径段方向下游节点为最接近交叉节点，即初始交叉节点。 [0028] 作为一种优选的实施方式，所述目标交叉节点的判断方式为： [0029] 当目标节点为货位节点时，判断货位节点绑定的路径段的可行驶方向： [0030] 如果为双向行驶，则路径段两端的交叉节点为最接近交叉节点； [0031] 如果为单向行驶，则路径段方向下游节点为最接近交叉节点，即目标交叉节点。 [0032] 作为一种优选的实施方式，所述四向穿梭车的运行时间包括四向穿梭车执行反应 时间及四向穿梭车各动作的运行时间。 [0033] 作为一种优选的实施方式，所述四向穿梭车各动作的运行时间包括直行动作、转 弯动作、升/降动作的运行时间。 [0034] 作为一种优选的实施方式，所述四向穿梭车的运行时间计算包括： [0035] I.将每条路径切分为四向穿梭车动作，分为直行动作、换向动作、顶升动作与下降 动作； [0036] II.根据四向穿梭车实际的换向时间配置换向动作成本； 5 5 CN 113359774 B 说明书 3/6页 [0037] III.根据四向穿梭车实际的顶升/下降的时间配置的顶升/下降动作成本； [0038] IV.根据PLC程序中的实际速度曲线配置四向穿梭车直线] 现有四向穿梭车路径规划方法中，传统的地图构建采取的是栅格化方法，将四向 穿梭车运行的地图构建为一个点矩阵，并且在程序中数据结构表达形式为二维数组，影响 路径算法计算的时间复杂度，因此本发明提出一种动态树形数据结构来构建地图降低路径 算法计算的时间复杂度，可配置路径可行性与方向性，适用于更多的应用场景；传统的方法 成本函数是以路径的长度为衡量标准，本发明提出的成本函数以四向穿梭车运行时间为成 本函数，实现可配置的路径成本计算方法，寻找出的路径更符合实际的运行路径；同时本发 明提出了一种路径算法，在计算路径算法时进行树的深度遍历，与传统的进化算法对比，本 发明的算法时间复杂度更低。 附图说明 [0040] 图1为本发明构建的四向穿梭车运行地图示例。 [0041] 图2为初始交叉节点确认方法流程图。 [0042] 图3为目标交叉节点确认方法流程图。 具体实施方式 [0043] 下面结合附图对本发明作进一步的描述，以下实例仅用于更加清楚的说明本发明 的技术方案，而不能以此来限制本发明的保护范围。 [0044] 本发明主要包括四向穿梭车运行的地图构建方案，成本函数的设置方案与四向穿 梭车路径规划方案。 [0045] 如图1所示，是本发明构建四向穿梭车运行的地图示例，地图有三个部分组成，第 一部分是可以换向的交叉节点，如1,2,3,5,6号节点为交叉节点，在该节点，四向穿梭车在 该节点可以进行上下左右四个方向行走；第二部分是四向穿梭车运行的路径段，路径段是 由相邻的交叉节点组成，如图中的1→2,1→3，2→4,3→4，3→5,4→6,6→5都为地图中得到 路径段，考虑路径的方向性，路径可以设置为双向与单向，四向穿梭车在路径段1→2上可以 从1行走到2节点也可以从2行走至1节点，四向穿梭车在路径段3→4上时只能从3节点移动 至4节点不能从节点4移动至节点3，在路径段6→5上时只能从节点6移动至节点5，不能逆向 行走；第三部分为可以存放货物的货位节点，如图中的1001,1002,1003,1004,1005,1006号 节点，货位节点需与路径段绑定，如节点1001与1002号节点属于路径段1→2。通过本发明的 地图构建方案，地图有传统的栅格型转换成点线，数据结构由二维数组转换成动态树结构， 减少算法后续的遍历次数，提升路径规划算法的计算效率；同时，本发明的地图构建方式提 供了单双向配置，适用的业务场景更加广泛。 [0046] 本发明提出的成本函数构建方案，与以前以距离为衡量标准相比，本发明提出以 时间作为成本的适度函数构建方案。由于四向穿梭车的作业路径由三个部分组成：直行移 动，转弯换向、顶升/下降；因此本发明将三种动作的运行时间作为成本函数的计算标准；本 发明的顶升换向的两种动作时间标准是以四向穿梭车实际运行的时间统计出来的结果；对 于目前公司现有的几种四向穿梭车进行多次执行顶升与换向操作计算出每款四向穿梭车 的运行平均时间作为标准；直行的运行时间则是以PLC程序中的速度曲线页 时间；目前算法中的这些标准都开放一些配置接口，可提供不同的种类四向穿梭车来配置 顶升换向的时间，不同的速度曲线因素，从而使算法更加通用化。路径查找时还应考虑四向 穿梭车的负载状态以筛选路线，有负载时则预先排除有货货位通道的路径段，负载状态判 断属于常识部分，本发明在下述流程表述中不再列入这一判断逻辑。 [0047] 本发明提出的路径计算方案基于上述的地图与成本函数方案，在计算效率上有了 很大的提升。本发明的路径规划方案包括以下步骤： [0048] 步骤一、构建四向穿梭车的运行地图，初始化候选路径池与可用路径池； [0049] 步骤二、获取当前四向穿梭车的当前位置； [0050] 步骤三、根据当前四向穿梭车的当前位置确定初始交叉节点与目标交叉节点，将 以初始交叉节点为起点的路径段作为初始路径存放到候选路径池中； [0051] 步骤四、判断初始交叉节点与目标交叉节点是否相同； [0052] 步骤五、若初始交叉节点与目标交叉节点相同，则可确定四向穿梭车目标节点与 当前位置处于相同的路径段中，则根据两点之间直线距离最短原则，并且该路径中无需转 换换向操作，则默认寻找到最优路径并移除候选路径池中的初始路径，跳转步骤十六； [0053] 步骤六、若初始交叉节点与目标交叉节点不同，寻找初始交叉节点的相邻交叉节 点； [0054] 所述相邻交叉节点为以初始交叉节点为起点可抵达的相邻交叉节点，需预先判断 初始交叉节点和相邻交叉节点组成的路径段的可方向性，并剔除已走过的相邻交叉节点； [0055] 步骤七、判断是否有相邻交叉节点，若有相邻交叉节点则跳至步骤十一；否则从候 选路径池中移除该路径； [0056] 步骤八、判断候选路径池size是否为0，若size＝＝0，则判断可用路径池是否为 空；否则跳转步骤十五； [0057] 步骤九、若可用路径池为空，则没有可用路径，跳转步骤十六； [0058] 步骤十、若可用路径池不为空，则在可用路径池中寻找路径成本最小的路径作为 四向车的运行路径，跳转至步骤十六； [0059] 步骤十一、判断相邻交叉节点是否包含目标交叉节点； [0060] 步骤十二、若相邻交叉节点包含目标交叉节点，则将生成路径存放至可用路径池 中，按成本函数从小到大排序，并移除候选路径池中的初始路径；否则跳转步骤十四； [0061] 步骤十三、判断可用路径池size是否大于设定值，若大于设定值则跳出遍历，确定 最短路径，跳转至步骤十六；若size小于等于设定值则继续遍历路径，跳转至步骤十五； [0062] 步骤十四、将相邻交叉点与候选路径池中的初始路径组成的路径作为新的初始路 径，替换候选路径池中原有的初始路径，并将新的初始路径按成本函数从小到大排序； [0063] 步骤十五、取出候选路径池中路径成本最小的一条路径的最后一位交叉节点作为 新的初始交叉节点，重复步骤六； [0064] 步骤十六、结束路径查找。 [0065] 本发明所述的路径寻找方案是基于交叉节点之间的路径寻找，但路径寻找的过程 中还需考虑的货位节点到交叉节点的成本，货位节点与交叉节点的绑定，因此本发明提出 确定初始与结束交叉节点的确认方法，若四向穿梭车的位置或目标节点位置不在交叉节点 上，在上述的寻找路径方法中需将四向车当前位置(目标节点位置)到交叉节点的路径段包 7 7 CN 113359774 B 说明书 5/6页 含进去。如图2所示，初始交叉节点初始方式步骤如下： [0066] 步骤一、获取四向穿梭车的当前位置； [0067] 步骤二、判断当前位置是否为某交叉节点的坐标； [0068] 步骤三、若当前位置为某个交叉节点坐标，则该节点为初始交叉节点； [0069] 步骤四、若当前位置不为某交叉节点坐标，则寻找当前位置所在的路径段； [0070] 步骤五、判断当前路径的方向性； [0071] 步骤六、若当前路径段为双向可行时，路径段两端的交叉节点为初始交叉节点； [0072] 步骤七、若当前路径段为单向行驶时，路径段的下游交叉节点为初始交叉节点； [0073] 如图3所示，与初始交叉节点确定相比，四向穿梭车作业的目标点基本处于货位节 点或者交叉节点，不会处于两个节点中间，因此目标交叉节点位置确定方式比较简单，具体 步骤如下： [0074] 步骤一、确定四向穿梭车运行的目标节点； [0075] 步骤二、判断目标节点为交叉节点还是货位节点； [0076] 步骤三、若目标节点为交叉节点，则该节点为目标交叉节点； [0077] 步骤四、若目标节点为货位节点，则先寻找货位节点所在的路径段； [0078] 步骤五、判断路径段的方向性； [0079] 步骤六、若当前路径段为双向可行时，路径段两端的交叉节点为目标交叉节点； [0080] 步骤七、若当前路径段为单向行驶时，路径段的上游交叉节点为目标交叉节点。 [0081] 以图1的地图为例，假设初始交叉节点1，目标节点1006。 [0082] 目标节点1006为货位节点，所在路段6→5为单向可行，因此路径段的上游交叉节 点6为目标交叉节点。 [0083] 则初始候选路径池是1和相邻交叉节点2、3组成的路径段1→3，1→2； [0084] 首先判断1是否为目标交叉节点，1≠6，因此寻找九游智能体育科技其相邻交叉节点2、3；在另一种情 景中，例如目标节点为1001，则1、2为目标交叉节点，此时可以直接按照1→2的路径继续行 驶，终止循环； [0085] 对比相邻交叉节点2、3均不是目标交叉节点，则将1→3，1→2都存入候选路径池， 此时相邻交叉节点和初始路径组成的路径并没有变化，因此候选路径池仍是1→3，1→2；将 1→3，1→2按照成本函数排序，1→3成本较低，因此选择3作为新的初始交叉节点，继续循 环； [0086] 初始交叉节点3和目标交叉节点6不同，因此寻找其相邻交叉节点，为1、4和5，其中 1为已途径交叉节点，因此剔除；3→4单向可行，因此可选的相邻交叉节点为5、4，相邻交叉 节点仍不是目标交叉节点，因此将4、5放入候选路径与当前路径组成新的路径1→3→5，1→ 3→4，1→2→4，并按照成本函数排序；此处相邻交叉节点与候选路径中的一个端点交叉节 点形成一个路径段，例如相邻交叉节点5与路径1→2中的任一端点交叉节点1、2都无法形成 一个路径段，因此组成路径中不包括1→2→5； [0087] 1→3→5成本最低，因此选择5为新的初始交叉节点； [0088] 初始交叉节点5≠6，因此寻找其相邻交叉节点，3为已途径节点，因此剔除，判断可 方向性后剔除6，因此5没有相邻交叉节点，从候选路径池中移除路径1→3→5； [0089] 判断候选路径池size是否为0，此时候选路径池size≠0，取出候选路径池中路径 8 8 CN 113359774 B 说明书 6/6页 成本最小的一条路径的最后一位交叉节点作为新的初始交叉节点，候选路径中剩余路径1 →3→4，1→2→4，1→3→4转向成本高，1→2→4成本低，因此1→2→4成本最低，因此选择4 为新的初始交叉节点； [0090] 4的相邻交叉节点中包含目标交叉节点6，则按照步骤十二，将路径1→2→4→6放 入可用路径池。根据可用路径池的size判断是否跳出循环，如果size＞设定值，则跳出循 环，确定最短路径(可用路径池中成本函数最低的路径)。 9 9 CN 113359774 B 说明书附图 1/2页 图1 图2 10 10 CN 113359774 B 说明书附图 2/2页 图3 11 11

　　2、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问加。

　　3、成为VIP九游智能体育科技后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。

　　4、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

　　2024年烟台市福山区事业单位公开招聘工作人员（37名）笔试模拟试题及答案解析.docx

　　【新媒体环境下企业品牌形象危机的应对策略研究--以“特斯拉刹车门”事件为例开题报告（含提纲）4200字】.doc

　　电机优化软件：OptiSLang二次开发_（3）.OptiSLang基本使用方法.docx

　　2024年湖北省汉江国有资本投资集团有限公司招聘笔试参考题库含答案解析.docx

　　原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者