路径规划方法、装置、电子设备及介质

摘要

本申请提供一种路径规划方法、装置、电子设备及介质。该方法在获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数后，基于每条有向路径被经过的次数，采用路径冲突预测算法，对每条有向路径进行冲突预测，得到每条有向路径对应的路径冲突系数；基于路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵；采用预设的路径规划算法，遍历更新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。该方法解决了多辆穿梭车的路径冲突问题，期望考虑正在执行任务的穿梭车的路径基础上，找出其冲突少、转弯少的路径，保证整个跨巷道多层穿梭车仓储系统的稳定高效运行。

权利要求

1.一种路径规划方法，其特征在于，所述方法包括：获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数；所述有向路径为所述穿梭车路径网络中两节点间的路径；所述节点表示所述穿梭车路径网络中穿梭车的停靠位置；

基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数；

基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵；所述距离矩阵中的元素表示节点间有向路径的路径距离；

采用预设的路径规划算法，遍历所述更新后的距离矩阵，规划当前规划周期内穿梭车的行驶路径。

2.如权利要求1所述的方法，其特征在于，在前一规划周期为初始规划周期时，所述前一规划周期对应的距离矩阵为初始距离矩阵；所述初始距离矩阵的配置步骤包括：配置每条有向路径的预设路径完好概率；所述路径完好概率为每条有向路径的可通过概率；

基于所述预设路径完好概率，得到所述初始距离矩阵。

3.如权利要求1所述的方法，其特征在于，获取预设时间段内穿梭车路径网络中每条有向路径被经过的次数，包括：

获取预设时间段内每条有向路径在第一方向上被经过的第一次数，以及获取相应有向路径在第二方向上被经过的第二次数；

其中，所述第一次数为有向路径被经过的真实次数，第二次数为相应有向路径被经过的放大次数，所述放大次数为所述真实次数与放大系数的乘积。

4.如权利要求3所述的方法，其特征在于，基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数，包括：

针对每条有向路径，基于所述有向路径对应的所述第一次数和所述第二次数，采用路径冲突预测算法，对所述有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数。

5.如权利要求4所述的方法，其特征在于，所述路径冲突预测算法表示为：；

其中，a0为初始值；N为预设的次数阈值；nl为第l条有向路径被经过的次数。

6.如权利要求1所述的方法，其特征在于，基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵，包括：将所述前一规划周期对应的距离矩阵中节点间有向路径的路径距离与相应有向路径对应的路径冲突系数作差，得到所述每条有向路径对应的新路径距离；

基于所述每条有向路径对应的新路径距离，得到更新后的距离矩阵。

7.如权利要求1所述的方法，其特征在于，采用预设的路径规划算法，遍历所述更新后的距离矩阵，规划当前规划周期内穿梭车的行驶路径，包括：遍历所述穿梭车路径网络中的节点，针对遍历到的当前节点，执行如下步骤：获取所述当前节点为起始节点对应的候选有向路径，以及所述候选有向路径的行驶方向；

根据上一次获取的历史最短有向路径的行驶方向和所述当前节点为起始节点时的候选有向路径的行驶方向，确定当前行驶方向变化信息；其中，所述历史最短有向路径为所述当前节点为终点节点时的最短有向路径；

基于预设的行驶方向变化信息与方向变化值的对应关系，获取所述当前行驶方向变化信息对应的方向变化值；

将所述方向变化值和所述候选有向路径的距离的和确定为所述候选有向路径的路径距离；

将候选有向路径中路径距离最短的有向路径确定为所述当前节点为起始节点时的最短有向路径，并将所述最短有向路径的终点节点确定为新的当前节点，返回执行获取所述当前节点为起始节点对应的有向路径中的最短行驶路径的步骤；

在满足遍历结束条件时，基于遍历过程中确定的最短有向路径，规划当前规划周期内穿梭车的行驶路径。

8.一种路径确定装置，其特征在于，所述装置包括：获取单元，用于获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数；

所述有向路径为所述穿梭车路径网络中两节点间的路径；所述节点表示所述穿梭车路径网络中穿梭车的停靠位置；

以及，基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数；

更新单元，用于基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵；所述距离矩阵中的元素表示节点间有向路径的路径距离；

规划单元，用于采用预设的路径规划算法，遍历所述更新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。

9.一种电子设备，其特征在于，所述电子设备包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过通信总线完成相互间的通信；

存储器，用于存放计算机程序；

处理器，用于执行存储器上所存储的程序时，实现权利要求1‑7任一所述的方法步骤。

10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现权利要求1‑7任一所述的方法步骤。

说明书

路径规划方法、装置、电子设备及介质

技术领域

[0001] 本申请涉及数据处理技术领域，具体而言，涉及一种路径规划方法、装置、电子设备及介质。

背景技术

[0002] 随着物流中心业务类型的多样化、复杂化，四向穿梭车作为新的自动化存储技术逐渐走进人们的视野。四向穿梭车作为多层穿梭车的升级版，实现多向行驶、跨巷道高效、
灵活作业、空间最大化。近几年，越来越多的四向穿梭车得到了成功的应用，但是在控制调
度、路径搜索算法等方面仍具有较高难度及研究价值。

[0003] 跨层跨巷道多层穿梭车仓储系统（Tier‑to‑tier and aisle‑to‑aisle shuttle based storage and retrieval system，TTAASBS/RS）是在跨层穿梭车仓储系统基础上发
展起来的快速存取、检索系统，它主要依靠巷道口的提升机以及巷道内的转载车以及穿梭
车配合完成调度任务。其中，提升机在仓库边沿负责穿梭车的跨层运动，转载车则安装在垂
直于巷道位置负责穿梭车的跨巷道运动，穿梭车依靠转载车、提升机进行跨层跨巷道运动。
作业方式包括单一入库作业、单一出库作业以及复合作业。四向穿梭车的优势就是可以跨
巷道作业，可以体现出很好的灵活性。在一个整体的运动区域来说，多个四向穿梭车同时工
作，随之而来的是路径规划。

[0004] 为了解决路径冲突的问题，需要对行驶的路径进行规划。

发明内容

[0005] 本申请实施例的目的在于提供一种路径规划方法、装置、电子设备及介质，用以解决路径冲突问题，确定穿梭车的可行驶路径。

[0006] 第一方面，提供了一种路径规划方法，该方法可以包括：

[0007] 获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数；所述有向路径为所述穿梭车路径网络中两节点间的路径；所述节点表示所述穿梭车路径网络中穿梭车
的停靠位置；

[0008] 基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数；

[0009] 基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵；所述距离矩阵中的元素表示节点间有向路径的路径距离；

[0010] 采用预设的路径规划算法，遍历所述更新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。

[0011] 在一个可能的实现中，所述初始距离矩阵的配置步骤包括：

[0012] 配置每条有向路径的预设路径完好概率；所述路径完好概率为每条有向路径的可通过概率；

[0013] 基于所述预设路径完好概率，得到所述初始距离矩阵。

[0014] 在一个可能的实现中，在前一规划周期为初始规划周期时，所述前一规划周期对应的距离矩阵为初始距离矩阵；获取预设时间段内穿梭车路径网络中每条有向路径被经过
的次数，包括：

[0015] 获取预设时间段内每条有向路径在第一方向上被经过的第一次数，以及获取相应有向路径在第二方向上被经过的第二次数；

[0016] 其中，所述第一次数为有向路径被经过的真实次数，第二次数为相应有向路径被经过的放大次数，所述放大次数为所述真实次数与放大系数的乘积。

[0017] 在一个可能的实现中，基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数，包
括：

[0018] 针对每条有向路径，基于所述有向路径对应的所述第一次数和所述第二次数，采用路径冲突预测算法，对所述有向路径进行冲突预测，得到所述每条有向路径对应的路径
冲突系数。

[0019] 在一个可能的实现中，所述路径冲突预测算法表示为：

[0020] ；

[0021] 其中，a0为初始值；N为预设的次数阈值；nl为第l条有向路径被经过的次数。

[0022] 在一个可能的实现中，基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵，包括：

[0023] 将所述前一规划周期对应的距离矩阵中节点间有向路径的路径距离与相应有向路径对应的路径冲突系数作差，得到所述每条有向路径对应的新路径距离；

[0024] 基于所述每条有向路径对应的新路径距离，得到更新后的距离矩阵。

[0025] 在一个可能的实现中，采用预设的路径规划算法，遍历所述更新后的距离矩阵，规划当前规划周期内穿梭车的行驶路径，包括：

[0026] 遍历所述穿梭车路径网络中的节点，针对遍历到的当前节点，执行如下步骤：

[0027] 获取所述当前节点为起始节点对应的候选有向路径，以及所述候选有向路径的行驶方向；

[0028] 根据上一次获取的历史最短有向路径的行驶方向和所述当前节点为起始节点时的候选有向路径的行驶方向，确定当前行驶方向变化信息；其中，所述历史最短有向路径为
所述当前节点为终点节点时的最短有向路径；

[0029] 基于预设的行驶方向变化信息与方向变化值的对应关系，获取所述当前行驶方向变化信息对应的方向变化值；

[0030] 将所述方向变化值和所述候选有向路径的距离的和确定为所述候选有向路径的路径距离；

[0031] 将候选有向路径中路径距离最短的有向路径确定为所述当前节点为起始节点时的最短有向路径，并将所述最短有向路径的终点节点确定为新的当前节点，返回执行获取
所述当前节点为起始节点对应的有向路径中的最短行驶路径的步骤；

[0032] 在满足遍历结束条件时，基于遍历过程中确定的最短有向路径，规划当前规划周期内穿梭车的行驶路径。

[0033] 第二方面，提供了一种路径规划装置，该装置可以包括：

[0034] 获取单元，用于获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数；所述有向路径为所述穿梭车路径网络中两节点间的路径；所述节点表示所述穿梭车路
径网络中穿梭车的停靠位置；

[0035] 以及，基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数；

[0036] 更新单元，用于基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵；所述距离矩阵中的元素表示节点间有向路径
的路径距离；

[0037] 规划单元，用于采用预设的路径规划算法，遍历所述更新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。

[0038] 在一个可能的实现中，在前一规划周期为初始规划周期时，所述前一规划周期对应的距离矩阵为初始距离矩阵；所述装置还包括配置单元；所述初始距离矩阵的配置步骤
包括：

[0039] 所述配置单元，用于配置每条有向路径的预设路径完好概率；所述路径完好概率为每条有向路径的可通过概率；

[0040] 所述获取单元，还用于基于所述预设路径完好概率，得到所述初始距离矩阵。

[0041] 在一个可能的实现中，所述获取单元，具体用于获取预设时间段内每条有向路径在第一方向上被经过的第一次数，以及获取相应有向路径在第二方向上被经过的第二次
数；其中，所述第一次数为有向路径被经过的真实次数，第二次数为相应有向路径被经过的
放大次数，所述放大次数为所述真实次数与放大系数的乘积。

[0042] 在一个可能的实现中，所述获取单元，还具体用于针对每条有向路径，基于所述有向路径对应的所述第一次数和所述第二次数，采用路径冲突预测算法，对所述有向路径进
行冲突预测，得到所述每条有向路径对应的路径冲突系数。

[0043] 在一个可能的实现中，所述路径冲突预测算法表示为：

[0044] ；

[0045] 其中，a0为初始值；N为预设的次数阈值；nl为第l条有向路径被经过的次数。

[0046] 在一个可能的实现中，所述更新单元，具体用于将所述前一规划周期对应的距离矩阵中节点间有向路径的路径距离与相应有向路径对应的路径冲突系数作差，得到所述每
条有向路径对应的新路径距离；

[0047] 以及，基于所述每条有向路径对应的新路径距离，得到更新后的距离矩阵。

[0048] 在一个可能的实现中，所述规划单元，具体用于：

[0049] 遍历所述穿梭车路径网络中的节点，针对遍历到的当前节点，执行如下步骤：

[0050] 获取所述当前节点为起始节点对应的候选有向路径，以及所述候选有向路径的行驶方向；

[0051] 根据上一次获取的历史最短有向路径的行驶方向和所述当前节点为起始节点时的候选有向路径的行驶方向，确定当前行驶方向变化信息；其中，所述历史最短有向路径为
所述当前节点为终点节点时的最短有向路径；

[0052] 基于预设的行驶方向变化信息与方向变化值的对应关系，获取所述当前行驶方向变化信息对应的方向变化值；

[0053] 将所述方向变化值和所述候选有向路径的距离的和确定为所述候选有向路径的路径距离；

[0054] 将候选有向路径中路径距离最短的有向路径确定为所述当前节点为起始节点时的最短有向路径，并将所述最短有向路径的终点节点确定为新的当前节点，返回执行获取
所述当前节点为起始节点对应的有向路径中的最短行驶路径的步骤；

[0055] 在满足遍历结束条件时，基于遍历过程中确定的最短有向路径，规划当前规划周期内穿梭车的行驶路径。

[0056] 第三方面，提供了一种电子设备，该电子设备包括处理器、通信接口、存储器和通信总线，其中，处理器，通信接口，存储器通过通信总线完成相互间的通信；

[0057] 存储器，用于存放计算机程序；

[0058] 处理器，用于执行存储器上所存放的程序时，实现上述第一方面中任一所述的方法步骤。

[0059] 第四方面，提供了一种计算机可读存储介质，该计算机可读存储介质内存储有计算机程序，所述计算机程序被处理器执行时实现上述第一方面中任一所述的方法步骤。

[0060] 本申请实施例提供的路径规划方法，在获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数后，有向路径为穿梭车路径网络中两节点间的路径；节点表示穿
梭车路径网络中穿梭车的停靠位置，基于每条有向路径被经过的次数，采用路径冲突预测
算法，对每条有向路径进行冲突预测，得到每条有向路径对应的路径冲突系数；基于路径冲
突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩
阵；距离矩阵中的元素表示节点间有向路径的路径距离；采用预设的路径规划算法，遍历更
新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。该方法参考多辆穿梭车所占路
径的路径长度，以及冲突车辆总数，来规划穿梭车的可行驶路径，解决了多辆穿梭车的路径
冲突问题，期望考虑正在执行任务的穿梭车的路径基础上，找出其冲突少、转弯少的路径，
保证整个跨巷道多层穿梭车仓储系统的稳定高效运行。

附图说明

[0061] 为了更清楚地说明本申请实施例的技术方案，下面将对本申请实施例中所需要使用的附图作简单地介绍，应当理解，以下附图仅示出了本申请的某些实施例，因此不应被看
作是对范围的限定，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以
根据这些附图获得其他相关的附图。

[0062] 图1为本申请实施例提供的一种穿梭车路径网络的结构示意图；

[0063] 图2为本申请实施例提供的一种穿梭车之间的路径干涉的干涉类型示意图；

[0064] 图3为本申请实施例提供的一种路径规划方法的流程示意图；

[0065] 图4为本申请实施例提供的一种栅格地图中移动方向的示意图；

[0066] 图5为本申请实施例提供的另一种栅格地图中移动方向的示意图；

[0067] 图6为本申请实施例提供的再一种栅格地图中移动方向的示意图；

[0068] 图7为本申请实施例提供的再一种栅格地图中移动方向的示意图；

[0069] 图8为本申请实施例提供的一种通过A*算法、Dijkstra，以及本申请路径规划方法生成穿梭车的全局路径的示意图；

[0070] 图9为本申请实施例提供的一种路径规划装置的结构示意图；

[0071] 图10为本申请实施例提供的一种电子设备的结构示意图。

具体实施方式

[0072] 下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本申请一部分实施例，并不是全部的实施例。基于本
申请实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施
例，都属于本申请保护的范围。

[0073] 为了方便理解，下面对本发明实施例中涉及的名词进行解释：

[0074] 距离矩阵，是一个包含一组点两两之间距离的矩阵（即二维数组）。因此给定N个欧几里得空间中的点，其距离矩阵就是一个非负实数作为元素的N×N的对称矩阵。由于本申
请应用在两点间的有向路径中，故两两之间点对的数量为N ×（N‑1），即距离矩阵中独立元
素的数量，其中，方向不一样，路径距离不一样。

[0075] A*算法，A*（A‑Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速
度越快。

[0076] A*算法通过下面函数 来计算每个节点的优先级。其中： 是节点 的综合优先级。 是节点 距离起点的代价，即从初始位置A沿着已生成的路径
到指定待检测格子的移动开销。 是节点 距离终点的预计代价，即待测格子到目标节
点B的估计移动开销，也是A*算法的启发函数。

[0077] 在栅格地图中，穿梭车只能进行上下左右四个方向移动，使用曼哈顿距离，即：

[0078] ，式中参数： 为当前节点 的 坐标， 为当前节点 的 坐标， 为当前节点 的 坐标， 为当前节点 的 坐标。

[0079] A*算法在迭代过程中，每次从open_set中选取f(n)值最小（优先级最高）的节点作为下一个待遍历的节点。

[0080] 另外，A*算法使用两个集合来表示待遍历的节点与已经遍历过的节点，通常称之为open_set和close_set。

[0081] 在给定的跨巷道多层穿梭车仓储系统对应的运输网络（或称“穿梭车路径网络”）中，往往要利用已知的各边的可靠性概率，求出指定顶点S到终点T的一条可靠性概率最大
的路径，此路径称为由S到T的路径最大可靠性，也称为最大可靠路。

[0082] 穿梭车路径网络分别由穿梭车、入库提升机、出库提升机、层入库暂存位、层出库暂存位、纵向/横向移动通道、出/入库提升机、换层提升机，及存储货位构成（图1所示）。货
物搬运分为水平搬运与垂直方向搬运。货物水平搬运由穿梭车负责，通过横向或纵向通道
可移动到任意位置；货物垂直方向通过出入库提升机完成；穿梭车的垂直方向移动，通过换
层提升机进行。整个水平方向搬运工作，通过一台车进行，只进行一次装卸（不需进行中间
环节接力），提高系统整体运行稳定性与可靠性（任一车辆异常，可进行锁定区域位置，不影
响其他车辆作业）。货物存储分为货位暂存区与货位存储区，靠近提升机出入库位置，设有
出入库暂存区，进行出入库货物的临时存储，利于充分利用穿梭车与提升机作业能力。

[0083] 如图2所示，对于穿梭车之间的路径干涉，分为如下三种情况：

[0084] A类‑路径成环：多车有向路径构成 有向环，成环后可能会构成路径的死锁，造成任务无法完成；

[0085] B类‑点冲突：以不同行驶方向经过同一个点；

[0086] C类‑边冲突：以相反方向经过相同2个点；

[0087] 本申请提供的路径确定方法采用A*算法和最大可靠路的路径规划算法的基本思想，使得多辆穿梭车的路径分布均匀，减少不同穿梭车路径的点冲突与边冲突，降低了实时
路径搜索中避让策略的复杂度，提高了路径搜索效率。该方法可以应用在穿梭车任务聚集
的场景中，解决多辆穿梭车路径干涉问题，期望考虑正在执行任务的穿梭车的路径基础上，
找出其干涉少、转弯少的路径，保证整个跨巷道多层穿梭车仓储系统的稳定高效运行。

[0088] 以下结合说明书附图对本申请的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明，并且在不冲突的情况下，本申
请中的实施例及实施例中的特征可以相互组合。

[0089] 图3为本申请实施例提供的一种路径规划方法的流程示意图。如图3所示，该方法可以包括：

[0090] 步骤310、获取预设时间段内穿梭车路径网络中每条有向路径被经过的次数。

[0091] 该预设时间段可以是待执行任务的穿梭车的工作时间段，也可以是设置的路径确定周期的时间段。

[0092] 结合图1，该穿梭车路径网络中的有向路径为穿梭车路径网络中两节点间存在行驶方向的路径。节点是指穿梭车可停靠的位置点。

[0093] 穿梭车路径网络中存在执行其他任务的穿梭车时，待执行任务的穿梭车才会与执行其他任务的穿梭车存在路径冲突，故需要考虑执行其他任务的穿梭车在穿梭车路径网络
中的路径占用情况，排除执行其他任务的穿梭车使用的路径，就可以得到待执行任务的穿
梭车的行驶路径，故以预设时间段为待执行任务的穿梭车的工作时间段为例，首先要获取
该预设时间段内每条有向路径被执行其他任务的穿梭车经过的次数。

[0094] 且由于有向路径存在方向，故可以按照穿梭车行驶方向，获取每条有向路径在第一方向上被经过的第一次数，以及获取相应有向路径在第二方向上被经过的第二次数。第
一方向与第二方向互为反方向，即第一方向为向左，则第二方向为向右；或者，第一方向为
向右，则第二方向为向左。

[0095] 其中，第一次数为有向路径被经过的真实次数，第二次数为相应有向路径被经过的放大次数，放大次数为所述真实次数与放大系数的乘积。

[0096] 例如，节点i到节点j的有向路径B[i,j]被经过的1次数后的第一次数为1，其被经过的2次数后的第一次数为2；而节点j到节点i的有向路径B[j,i]被经过的1次数后的第二
次数为10，其被经过的2次数后的第二次数为20，即真实次数与放大系数10的乘积。

[0097] 其中，放大系数是为了区分出穿梭车在节点j与节点i的行驶方向，放大系数越大，越能区分出方向，通过在节点j与节点i间的有向路径区别出不同穿梭车的行驶方向，可有
效避免不同穿梭车路径的点冲突与边冲突。

[0098] 需要说明的是，放大系数太大可能会影响其他待执行任务的穿梭车的路径确定放大系数可以根据实际情况进行预先设置。

[0099] 步骤320、基于每条有向路径被经过的次数，采用路径冲突预测算法，对每条有向路径进行冲突预测，得到每条有向路径对应的路径冲突系数。

[0100] 具体实施中，针对每条有向路径，基于该有向路径对应的第一次数和第二次数，采用路径冲突预测算法，对有向路径进行冲突预测，得到每条有向路径对应的路径冲突系数。

[0101] 例如，若有向路径A在第一方向被经过的第一次数为N1，有向路径A在第二方向被经过的第二次数为10N1，则为了保证有向路径A不存在点冲突或边冲突，可以将第一方向确
定为行驶方向。

[0102] 在一些实施例中，路径冲突预测算法可以表示为： 。其中，a0为初始阶段权值；N为预设的次数阈值，N值大小表征有向路径或节点对于多辆穿梭车占用路
径的敏感程度；nl为第l条有向路径被经过的次数。 的值为第l条有向路
径对应的路径冲突系数。

[0103] 上述实施方式，通过对每条有向路径对应的第一方向被经过的次数和第二方向被经过的次数进行预测，以分析相应有向路径会发生点冲突或边冲突的可能，且通过路径冲
突系数来表征发生点冲突或边冲突的可能。

[0104] 步骤330、基于路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵。

[0105] 距离矩阵中的元素表示节点间有向路径的路径距离，携带方向的路径距离。

[0106] 在执行该步骤之前，预先配置初始距离矩阵，初始距离矩阵的配置步骤包括：

[0107] 步骤一，配置每条有向路径的预设路径完好概率；路径完好概率为每条有向路径的可通过概率。

[0108] 穿梭车路径网络中，各节点间有向路完好概率可以初始设置为 。

[0109] 其中，

[0110]

[0111] 顶点i与顶点j为穿梭车路径网络中的任意两个节点。顶点i与顶点j有相邻边表示顶点i与顶点j间存在可到达路径，顶点i与顶点j没有相邻边表示顶点i与顶点j间不存在可
到达路径。

[0112] 步骤二，基于预设路径完好概率，得到初始距离矩阵。

[0113] 两点之间距离矩阵为 ，将 做如下变换：

[0114]

[0115] 的初始值为 ， 为除0与∞外的值，根据业务需要可以将 配置为0.9‑0.99间的值。

[0116] 之后，基于路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵。例如，若前一规划周期为初始规划周期，则前一规划周期对
应的距离矩阵为初始距离矩阵，此时基于路径冲突系数对初始距离矩阵内节点间的距离矩
阵进行更新，得到当前规划周期对应的更新后的距离矩阵。

[0117] 具体的，将前一规划周期对应的距离矩阵中节点间有向路径的路径距离与相应有向路径对应的路径冲突系数作差，得到每条有向路径对应的新路径距离，并基于每条有向
路径对应的新路径距离，得到更新后的距离矩阵。

[0118] 有向路径的更新算法可以表示为：

[0119] ；

[0120] 其中，aij为节点i与节点j对应的有向路径。

[0121] 上述实施方式，通过各路径的可靠性概率，以及穿梭车路径网络中各穿梭车对路径的占用情况，可得到起始点S到目标点T的一条可靠性概率最大的路径，即由S到T的最大
可靠路。

[0122] 步骤340、采用预设的路径规划算法，遍历更新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。

[0123] 具体实施中，采用的预设的路径规划算法可以为A*算法，A*算法可以遍历穿梭车路径网络中的各节点，针对遍历到的当前节点，执行如下步骤：

[0124] 获取当前节点为起始节点对应的候选有向路径，以及候选有向路径的行驶方向；此时可以获取到的候选有向路径可以为至少一条，以及每条候选有向路径对应的以当前节
点为起始节点，以其他节点为终点节点的路径方向。

[0125] 根据上一次获取的历史最短有向路径的行驶方向和当前节点为起始节点时的候选有向路径的行驶方向，确定当前行驶方向变化信息。其中，历史最短有向路径为当前节点
为终点节点时的最短有向路径。

[0126] 具体的，将上一次获取的历史最短有向路径的行驶方向与每条候选有向路径的行驶方向作比较，查看在经过历史最短有向路径，且将要经过相应候选有向路径时，确定候选
有向路径对应的行驶方向变化，如同向、反向或其他方向（如与历史最短有向路径的行驶方
向成90度的方向）。

[0127] 其中，当前节点为起始节点时的候选有向路径的行驶方向由起始节点与该候选有向路径的终点节点确定。

[0128] 例如，在栅格地图中，使用RCA对于有向路径中节点的状态进行描述：R‑在地图中的横坐标，C‑在地图中的纵坐标，A‑行驶方向，对于有向路径中节点的状态描述增加了方向
维度，如图4‑图7所示，存在初始起点S0、过程起点S和目标点T。

[0129] 初始起点S0在地图中的坐标为（4，2，2）；过程起点S在地图中的坐标为（3，2，2）；目标点T在地图中的坐标为（2，2，2）。

[0130] 且图4‑图7中的行驶方向均为S0（4，2，2）—>S（3，2，2），之后由S（3，2，2）—>T（2，2，2）。由于不同栅格地图中各点位置不同，故行驶方向不同。

[0131] 图4中由S0（4，2，2）向上移动至S（3，2，2），之后由S（3，2，2）向右移动至T（2，2，2），即S0—>S的路径方向与S—>T的路径方向为其他方向。

[0132] 图5中由S0（4，2，2）向上移动至S（3，2，2），之后由S（3，2，2）向上移动至T（2，2，2），即S0—>S的路径方向与S—>T的路径方向为同向。

[0133] 图6中由S0（4，2，2）向上移动至S（3，2，2），之后由S（3，2，2）向左移动至T（2，2，2），即S0—>S的路径方向与S—>T的路径方向为其他方向。

[0134] 图7中由S0（4，2，2）向上移动至S（3，2，2），之后由S（3，2，2）向下移动至T（2，2，2），即S0—>S的路径方向与S—>T的路径方向为反向。

[0135] 由此可知，点S方向由S0—>S移动方向确定，S—>T移动方向与S0—>S移动方向不一致，则点S位置需要旋转，即转弯。

[0136] 进一步的，基于预设的行驶方向变化信息与方向变化值的对应关系，获取当前行驶方向变化信息对应的方向变化值。其中，预设的行驶方向变化信息transFlag与方向变化
值的对应关系可以包括：行驶方向变化信息为同向时，方向变化值为0；行驶方向变化信息
为反向时，方向变化值为1；行驶方向变化信息为其他方向时，方向变化值为2，即可以表示
为：

[0137]

[0138] 之后，将方向变化值和相应候选有向路径的距离的和确定为候选有向路径的路径距离，并将最短路径距离对应的候选有向路径确定为当前节点为起始节点时的最短有向路
径，并将最短有向路径的终点节点确定为新的当前节点，返回执行获取当前节点为起始节
点对应的有向路径中的最短行驶路径的步骤。

[0139] 在满足遍历结束条件时，基于遍历过程中确定的所有最短有向路径，确定出当前规划周期内穿梭车的行驶路径。

[0140] 上述实施例，通过A*算法实现在穿梭车路径网络中进行节点的遍历和有向路径查找，基于方向变化值和相应有向路径的距离的和来确定最短有向路径，使得穿梭车在任务
执行中更改路径次数明显减少，即解决点冲突或边冲突，且一定程度上保证转弯数少的结
果，由此得到的最短有向路径明显优于现有方式仅搜索最短路径距离得到的最短有向路
径。

[0141] 也就是说，因为候选有向路径是基于更新后的距离矩阵来确定的，且更新后的距离矩阵在一定程度上避免了路径上的点冲突或边冲突问题，故穿梭车在候选有向路径行驶
可避免一定程度的点冲突或边冲突；同时基于方向变化值和相应候选有向路径的距离的和
来确定最短有向路径，可以使最短有向路径中出现较少的点冲突或边冲突或出现较少次数
的转弯；或者，最短有向路径中出现较少的点冲突或边冲突，以及较少次数的转弯，由此可
以提高穿梭车的工作效率。

[0142] 针对本申请路径规划的仿真与分析结果：

[0143] 为了验证该方法的有效性，在MATLAB中进行了仿真。图所示穿梭车地图为例，分别通过AStar算法、Dijkstra，以及本申请路径规划方法（即融合A*算法与最大可靠路算法）生
成穿梭车的全局路径。穿梭车根据任务下发先后时间确定其路径搜索顺序，但是其路径，主
要考虑的元素为：

[0144] 1、路径中边冲突数量‑车辆路径行驶的反向边；

[0145] 2、转弯次数；

[0146] 3、路径中点冲突数量‑重复经过的点数量；

[0147] 选取2个任务情形进行比较，分别为：[13,26]‑>[3,14]，[8,5]‑>[18,26]（点分别由行数与列数进行组合表示），如图8所示，[13,26]‑>[3,14]形成路径1，即起点1到终点1；
[8,5]‑>[18,26] 形成路径2，即起点2到终点2。其比较分析结果为：

[0148]

[0149] 从上述结果可以看出，本文融合最大可靠路与A*改进算法，可以搜索到边冲突、转弯数少的路径，符合实际穿梭车库路径规划的实际需求，使得任务执行中更改路径次数明
显减少，且一定程度上保证转弯数少的结果，路径明显优于其他方法搜索的路径。

[0150] 本申请实施例提供的路径规划方法，在获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数后，有向路径为穿梭车路径网络中两节点间的路径；节点表示穿
梭车路径网络中穿梭车的停靠位置，基于每条有向路径被经过的次数，采用路径冲突预测
算法，对每条有向路径进行冲突预测，得到每条有向路径对应的路径冲突系数；基于路径冲
突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩
阵；距离矩阵中的元素表示节点间有向路径的路径距离；采用预设的路径规划算法，遍历更
新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。该方法参考多辆穿梭车所占路
径的路径长度，以及冲突车辆总数，来规划穿梭车的可行驶路径，解决了多辆穿梭车的路径
冲突问题，期望考虑正在执行任务的穿梭车的路径基础上，找出其冲突少、转弯少的路径，
保证整个跨巷道多层穿梭车仓储系统的稳定高效运行。

[0151] 与上述方法对应的，本发明实施例还提供一种路径规划装置，如图9所示，该路径规划装置包括：获取单元910、更新单元920和规划单元930；

[0152] 获取单元910，用于获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数；所述有向路径为所述穿梭车路径网络中两节点间的路径；所述节点表示所述穿梭
车路径网络中穿梭车的停靠位置；

[0153] 以及，基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数；

[0154] 更新单元920，用于基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵；所述距离矩阵中的元素表示节点间有向路
径的路径距离；

[0155] 规划单元930，用于采用预设的路径规划算法，遍历所述更新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。

[0156] 在一个可能的实现中，在前一规划周期为初始规划周期时，所述前一规划周期对应的距离矩阵为初始距离矩阵；所述装置还包括配置单元940；所述初始距离矩阵的配置步
骤包括：

[0157] 配置单元940，用于配置每条有向路径的预设路径完好概率；所述路径完好概率为每条有向路径的可通过概率；

[0158] 获取单元910，还用于基于所述预设路径完好概率，得到所述初始距离矩阵。

[0159] 在一个可能的实现中，获取单元910，具体用于获取预设时间段内每条有向路径在第一方向上被经过的第一次数，以及获取相应有向路径在第二方向上被经过的第二次数；
其中，所述第一次数为有向路径被经过的真实次数，第二次数为相应有向路径被经过的放
大次数，所述放大次数为所述真实次数与放大系数的乘积。

[0160] 在一个可能的实现中，获取单元910，还具体用于针对每条有向路径，基于所述有向路径对应的所述第一次数和所述第二次数，采用路径冲突预测算法，对所述有向路径进
行冲突预测，得到所述每条有向路径对应的路径冲突系数。

[0161] 在一个可能的实现中，所述路径冲突预测算法表示为：

[0162] ；

[0163] 其中，a0为初始值；N为预设的次数阈值；nl为第l条有向路径被经过的次数。

[0164] 在一个可能的实现中，更新单元920，具体用于将所述前一规划周期对应的距离矩阵中节点间有向路径的路径距离与相应有向路径对应的路径冲突系数作差，得到所述每条
有向路径对应的新路径距离；

[0165] 以及，基于所述每条有向路径对应的新路径距离，得到更新后的距离矩阵。

[0166] 在一个可能的实现中，规划单元930，具体用于：

[0167] 遍历所述穿梭车路径网络中的节点，针对遍历到的当前节点，执行如下步骤：

[0168] 获取所述当前节点为起始节点对应的候选有向路径，以及所述候选有向路径的行驶方向；

[0169] 根据上一次获取的历史最短有向路径的行驶方向和所述当前节点为起始节点时的候选有向路径的行驶方向，确定当前行驶方向变化信息；其中，所述历史最短有向路径为
所述当前节点为终点节点时的最短有向路径；

[0170] 基于预设的行驶方向变化信息与方向变化值的对应关系，获取所述当前行驶方向变化信息对应的方向变化值；

[0171] 将所述方向变化值和所述候选有向路径的距离的和确定为所述候选有向路径的路径距离；

[0172] 将候选有向路径中路径距离最短的有向路径确定为所述当前节点为起始节点时的最短有向路径，并将所述最短有向路径的终点节点确定为新的当前节点，返回执行获取
所述当前节点为起始节点对应的有向路径中的最短行驶路径的步骤；

[0173] 在满足遍历结束条件时，基于遍历过程中确定的最短有向路径，规划当前规划周期内穿梭车的行驶路径。

[0174] 本发明上述实施例提供的路径规划装置的各功能单元的功能，可以通过上述各方法步骤来实现，因此，本发明实施例提供的路径规划装置中的各个单元的具体工作过程和
有益效果，在此不复赘述。

[0175] 本发明实施例还提供了一种电子设备，如图10所示，包括处理器1010、通信接口1020、存储器1030和通信总线1040，其中，处理器1010，通信接口1020，存储器1030通过通信
总线1040完成相互间的通信。

[0176] 存储器1030，用于存放计算机程序；

[0177] 处理器1010，用于执行存储器1030上所存放的程序时，实现如下步骤：

[0178] 获取当前路径规划内穿梭车路径网络中每条有向路径被经过的次数；所述有向路径为所述穿梭车路径网络中两节点间的路径；所述节点表示所述穿梭车路径网络中穿梭车
的停靠位置；

[0179] 基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数；

[0180] 基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵；所述距离矩阵中的元素表示节点间有向路径的路径距离；

[0181] 采用预设的路径规划算法，遍历所述更新后的距离矩阵，确定当前规划周期内穿梭车的行驶路径。

[0182] 在一个可能的实现中，在前一规划周期为初始规划周期时，所述前一规划周期对应的距离矩阵为初始距离矩阵；所述初始距离矩阵的配置步骤包括：

[0183] 配置每条有向路径的预设路径完好概率；所述路径完好概率为每条有向路径的可通过概率；

[0184] 基于所述预设路径完好概率，得到所述初始距离矩阵。

[0185] 在一个可能的实现中，获取预设时间段内穿梭车路径网络中每条有向路径被经过的次数，包括：

[0186] 获取预设时间段内每条有向路径在第一方向上被经过的第一次数，以及获取相应有向路径在第二方向上被经过的第二次数；

[0187] 其中，所述第一次数为有向路径被经过的真实次数，第二次数为相应有向路径被经过的放大次数，所述放大次数为所述真实次数与放大系数的乘积。

[0188] 在一个可能的实现中，基于所述每条有向路径被经过的次数，采用路径冲突预测算法，对所述每条有向路径进行冲突预测，得到所述每条有向路径对应的路径冲突系数，包
括：

[0189] 针对每条有向路径，基于所述有向路径对应的所述第一次数和所述第二次数，采用路径冲突预测算法，对所述有向路径进行冲突预测，得到所述每条有向路径对应的路径
冲突系数。

[0190] 在一个可能的实现中，所述路径冲突预测算法表示为：

[0191] ；

[0192] 其中，a0为初始值；N为预设的次数阈值；nl为第l条有向路径被经过的次数。

[0193] 在一个可能的实现中，基于所述路径冲突系数，更新前一规划周期内穿梭车路径网络中节点间的距离矩阵，得到更新后的距离矩阵，包括：

[0194] 将所述前一规划周期对应的距离矩阵中节点间有向路径的路径距离与相应有向路径对应的路径冲突系数作差，得到所述每条有向路径对应的新路径距离；

[0195] 基于所述每条有向路径对应的新路径距离，得到更新后的距离矩阵。

[0196] 在一个可能的实现中，采用预设的路径规划算法，遍历所述更新后的距离矩阵，规划当前规划周期内穿梭车的行驶路径，包括：

[0197] 遍历所述穿梭车路径网络中的节点，针对遍历到的当前节点，执行如下步骤：

[0198] 获取所述当前节点为起始节点对应的候选有向路径，以及所述候选有向路径的行驶方向；

[0199] 根据上一次获取的历史最短有向路径的行驶方向和所述当前节点为起始节点时的候选有向路径的行驶方向，确定当前行驶方向变化信息；其中，所述历史最短有向路径为
所述当前节点为终点节点时的最短有向路径；

[0200] 基于预设的行驶方向变化信息与方向变化值的对应关系，获取所述当前行驶方向变化信息对应的方向变化值；

[0201] 将所述方向变化值和所述候选有向路径的距离的和确定为所述候选有向路径的路径距离；

[0202] 将候选有向路径中路径距离最短的有向路径确定为所述当前节点为起始节点时的最短有向路径，并将所述最短有向路径的终点节点确定为新的当前节点，返回执行获取
所述当前节点为起始节点对应的有向路径中的最短行驶路径的步骤；

[0203] 在满足遍历结束条件时，基于遍历过程中确定的最短有向路径，规划当前规划周期内穿梭车的行驶路径。

[0204] 上述提到的通信总线可以是外设部件互连标准（Peripheral Component Interconnect，PCI）总线或扩展工业标准结构（Extended Industry  Standard 
Architecture，EISA）总线等。该通信总线可以分为地址总线、数据总线、控制总线等。为便
于表示，图中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。

[0205] 通信接口用于上述电子设备与其他设备之间的通信。

[0206] 存储器可以包括随机存取存储器（Random Access Memory，RAM），也可以包括非易失性存储器（Non‑Volatile Memory，NVM），例如至少一个磁盘存储器。可选的，存储器还可
以是至少一个位于远离前述处理器的存储装置。

[0207] 上述的处理器可以是通用处理器，包括中央处理器（Central Processing Unit，CPU）、网络处理器（Network Processor，NP）等；还可以是数字信号处理器（Digital Signal 
Processing，DSP）、专用集成电路（Application Specific Integrated Circuit，ASIC）、现
场可编程门阵列（Field‑Programmable Gate Array，FPGA）或者其他可编程逻辑器件、分立
门或者晶体管逻辑器件、分立硬件组件。

[0208] 由于上述实施例中电子设备的各器件解决问题的实施方式以及有益效果可以参见图3所示的实施例中的各步骤来实现，因此，本发明实施例提供的电子设备的具体工作过
程和有益效果，在此不复赘述。

[0209] 在本发明提供的又一实施例中，还提供了一种计算机可读存储介质，该计算机可读存储介质中存储有指令，当其在计算机上运行时，使得计算机执行上述实施例中任一所
述的路径规划方法。

[0210] 在本发明提供的又一实施例中，还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述实施例中任一所述的路径规划方法。

[0211] 本领域内的技术人员应明白，本申请实施例中的实施例可提供为方法、系统、或计算机程序产品。因此，本申请实施例中可采用完全硬件实施例、完全软件实施例、或结合软
件和硬件方面的实施例的形式。而且，本申请实施例中可采用在一个或多个其中包含有计
算机可用程序代码的计算机可用存储介质（包括但不限于磁盘存储器、CD‑ROM、光学存储器
等）上实施的计算机程序产品的形式。

[0212] 本申请实施例中是参照根据本申请实施例中实施例的方法、设备（系统）、和计算机程序产品的流程图和／或方框图来描述的。应理解可由计算机程序指令实现流程图和／或
方框图中的每一流程和／或方框、以及流程图和／或方框图中的流程和／或方框的结合。可提
供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理
设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行
的指令产生用于实现在流程图一个流程或多个流程和／或方框图一个方框或多个方框中指
定的功能的装置。

[0213] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指
令装置的制造品，该指令装置实现在流程图一个流程或多个流程和／或方框图一个方框或
多个方框中指定的功能。

[0214] 这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或
其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和／或方框图一
个方框或多个方框中指定的功能的步骤。

[0215] 尽管已描述了本申请实施例中的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释
为包括优选实施例以及落入本申请实施例中范围的所有变更和修改。

[0216] 显然，本领域的技术人员可以对本申请实施例中实施例进行各种改动和变型而不脱离本申请实施例中实施例的精神和范围。这样，倘若本申请实施例中实施例的这些修改
和变型属于本申请实施例中权利要求及其等同技术的范围之内，则本申请实施例中也意图
包含这些改动和变型在内。