一种激光叉车路径搜索方法

摘要

本发明公开的一种激光叉车路径搜索方法，包括如下步骤：S1、基于激光叉车运行环境中的主站点及子站点分别构建主有向图和子有向图，多个子站点可以从属于同一个主站点，一个子站点不能从属于两个不同的主站点；S2、确定距激光叉车的起始站点V_start及任务站点V_task；S3、检测V_start、V_task的站点属性，若存在子站点，则基于主有向图及子有向图分别规划主站点间的最短主路径、子站点间的最短子路径，对最短主路径与最短子路径进行拼接，形成V_start到V_task的最短路径。针对不同属性的站点分别建立了主有向图和子有向图，从而分离了不同属性站点间的路径搜索，减少最短路径搜索过程中的节点数量，减少数据处理量，进而提高了任务路径搜索效率，并且灵活性更好。

权利要求

1.一种激光叉车路径搜索方法，其特征在于，所述方法具体包括如下步骤：

S1、基于激光叉车运行环境中的主站点及子站点分别构建主有向图和子有向图，至少一个子站点从属于一个主站点，一个子站点不能从属于两个不同的主站点；

S2、确定激光叉车的起始站点V_start及任务站点V_task；

S3、检测V_start、V_task的站点属性，若存在子站点，则基于主有向图及子有向图分别规划主站点间的最短主路径、子站点间的最短子路径，对最短主路径与最短子路径进行拼接，形成V_start到V_task的最短路径；

若V_start为子站点，V_task为主站点，V_start到V_task的最短路径获取方法具体如下：

11)获取起始站点V_start对应的主站点V_m_star；

12)基于主有向图G1搜索从起始主站点V_m_start到任务站点V_task之间的最短主路径Path_m；

13)起始主站点V_m_start沿路径Path_m方向向前一定距离dist后，确定从属于起始主站点V_m_star且距其最近的起始子节点V_p_start；

14)基于子有向图搜索从起始站点V_start到起始子站点V_p_start之间最短子路径Path_s1；

15)将主路径Path_m中起始子站点V_p_start之前路径进行剔除，并将子路径Path_s1拼接到剔除后的主路径Path_m之前，形成从起始站点V_start到任务站点V_task之间的最短行驶路径。

2.如权利要求1所述激光叉车路径搜索方法，其特征在于，若V_start为主站点，V_task为子站点，V_start到V_task的最短路径获取方法具体如下：

21)获取任务站点V_task对应的主站点V_m_task；

22)基于主有向图G1搜索从起始站点V_start到任务主站点V_m_task之间的最短主路径Path_m；

23)任务主站点V_m_task沿路径Path_m延伸方向向前一定距离dist后，确定从属于任务主站点V_m_task且距其最近的任务子站点V_p_task；

24)基于子有向图获取从任务子站点V_p_task到任务站点V_task之间最短子路径Path_s2；

25)任务主站点V_m_task与任务子站点V_p_task形成路径Path_s3，依次将路径Path_s3和子路径Path_s2拼接至路径Path_m后，即形成从起始站点V_start到任务站点V_task的最短行驶路径。

3.如权利要求1所述激光叉车路径搜索方法，其特征在于，若V_start、V_task均为子站点，V_start到V_task的最短路径获取方法具体如下：

31)获取起始站点V_start、任务站点V_task对应的主站点，分别为起始主站点V_m_start和任务主站点V_m_task；

32)基于主有向图G1搜索从起始主站点V_m_start到任务主站点V_m_task之间的最短主路径Path_m；

33)起始主站点V_m_start沿路径Path_m方向向前一定距离dist后，确定从属于起始主站点V_m_star且距其最近的起始子站点V_p_start；任务主站点V_m_task沿路径Path_m延伸方向向前一定距离dist后，确定从属于任务主站点V_m_task且距其最近的任务子站点V_p_taskk；

34)基于子有向图获取从起始站点V_start到起始子站点V_p_start之间最短子路径Path_s1，及从任务子站点V_p_task到任务站点V_task之间最短子路径Path_s2；

35)将主路径Path_m中起始子站点V_p_start之前路径进行剔除，并将子路径Path_s1拼接到剔除后的主路径Path_m之前，获取从起始站点V_start到任务主站点V_m_task之间的最短行驶路径Path_1；

36)任务主站点V_m_task与任务子站点V_p_task形成路径Path_s3，依次将路径Path_s3和子路径Path_s2拼接至路径Path_1后，形成从起始站点V_start到任务站点V_task的最短行驶路径。

说明书

一种激光叉车路径搜索方法

技术领域

[0001] 本发明属于路径规划技术领域，更具体地，本发明涉及一种激光叉车路径搜索方法。

背景技术

[0002] 近年来，随着物料输送系统、自动化立体仓库等快速发展，叉车作为一种高效的装卸运输车辆，在制作业输送环节得到了较为广泛的应用。其中，激光叉车由于具有转弯半径小、自动化程度高等特点，在人工驾驶叉车应用场景中能够得到直接应用。

[0003] 由于激光叉车应用环境通常较为复杂，不仅存在较多设备，同时还存在设备操作人员，因而在激光叉车自动工作前，通常需要人为设置叉车行驶路径站点及工作站点等，并设计叉车行驶路径。通常情况下，对叉车行驶路径端点与叉车工作站点并不直接进行区分，直接基于叉车工作环境模型中所有节点生成一张有向图，不仅导致激光叉车最短路径搜索时，需要遍历有向图中过多节点，数据冗余量过大，搜索效率较低，同时忽略了节点间的不同属性，无法将有向图中的节点设置与激光叉车工作站点对应。

发明内容

[0004] 本发明提供一种激光叉车路径搜索方法，旨在改善上述问题。

[0005] 本发明是这样实现的，一种激光叉车路径搜索方法，所述方法具体包括如下步骤：

[0006] S1、基于激光叉车运行环境中的主站点及子站点分别构建主有向图和子有向图，多个子站点可以从属于同一个主站点，同一个子站点不能从属于两个不同的主站点；

[0007] S2、确定激光叉车的起始站点V_start及任务站点V_task；

[0008] S3、检测V_start、V_task的站点属性，若存在子站点，则基于主有向图及子有向图分别规划主站点间的最短主路径、子站点间的最短子路径，对最短主路径与最短子路径进行拼接，形成V_start到V_task的最短路径。

[0009] 进一步的，若V_start为子站点，V_task为主站点，V_start到V_task的最短路径获取方法具体如下：

[0010] 11)获取起始站点V_start对应的主站点V_m_star；

[0011] 12)基于主有向图G1搜索从起始主站点V_m_start到任务站点V_task之间的最短主路径Path_m；

[0012] 13)起始主站点V_m_start沿路径Path_m方向向前一定距离dist后，确定从属于起始主站点V_m_star且距其最近的起始子节点V_p_start；

[0013] 14)基于子有向图搜索从起始站点V_start到起始子站点V_p_start之间最短子路径Path_s1；

[0014] 15)将主路径Path_m中起始子站点V_p_start之前路径进行剔除，并将子路径Path_s1拼接到剔除后的主路径Path_m之前，形成从起始站点V_start到任务站点V_task之间的最短行驶路径。

[0015] 进一步的，若V_start为主站点，V_task为子站点，V_start到V_task的最短路径获取方法具体如下：

[0016] 21)获取任务站点V_task对应的主站点V_m_task；

[0017] 22)基于主有向图G1搜索从起始站点V_start到任务主站点V_m_task之间的最短主路径Path_m；

[0018] 23)任务主站点V_m_task沿路径Path_m延伸方向向前一定距离dist后，确定从属于任务主站点V_m_task且距其最近的任务子站点V_p_task；

[0019] 24)基于子有向图获取从任务子站点V_p_task到任务站点V_task之间最短子路径Path_s2；

[0020] 25)任务主站点V_m_task与任务子站点V_p_task形成路径Path_s3，依次将路径Path_s3和子路径Path_s2拼接至路径Path_m后，即形成从起始站点V_start到任务站点V_task的最短行驶路径。

[0021] 进一步的，若V_start、V_task均为子站点，V_start到V_task的最短路径获取方法具体如下：

[0022] 31)获取起始站点V_start、任务站点V_task对应的主站点，分别为起始主站点V_m_start和任务主站点V_m_task；

[0023] 32)基于主有向图G1搜索从起始主站点V_m_start到任务主站点V_m_task之间的最短主路径Path_m；

[0024] 33)起始主站点V_m_start沿路径Path_m方向向前一定距离dist后，确定从属于起始主站点V_m_star且距其最近的起始子站点V_p_start；任务主站点V_m_task沿路径Path_m延伸方向向前一定距离dist后，确定从属于任务主站点V_m_task且距其最近的任务子站点V_p_taskk；

[0025] 34)基于子有向图获取从起始站点V_start到起始子站点V_p_start之间最短子路径Path_s1，及从任务子站点V_p_task到任务站点V_task之间最短子路径Path_s2；

[0026] 35)将主路径Path_m中起始子站点V_p_start之前路径进行剔除，并将子路径Path_s1拼接到剔除后的主路径Path_m之前，获取从起始站点V_start到任务主站点V_m_task之间的最短行驶路径Path_1；

[0027] 36)任务主站点V_m_task与任务子站点V_p_task形成路径Path_s3，依次将路径Path_s3和子路径Path_s2拼接至路径Path_1后，形成从起始站点V_start到任务站点V_task的最短行驶路径。

[0028] 本发明提供的激光叉车路径搜索方法针对不同属性的站点分别建立了主有向图和子有向图，从而分离了不同属性站点间的路径搜索，减少最短路径搜索过程中的节点数量，减少数据处理量，进而提高了任务路径搜索效率，并且灵活性更好。

附图说明

[0029] 图1为本发明实施例提供的激光叉车路径搜索方法流程图；

[0030] 图2为本发明实施例提供的激光叉车路径示例图。

具体实施方式

[0031] 下面对照附图，通过对实施例的描述，对本发明的具体实施方式作进一步详细的说明，以帮助本领域的技术人员对本发明的发明构思、技术方案有更完整、准确和深入的理解。

[0032] 图1为本发明实施例提供的激光叉车路径搜索方法流程图，该方法具体包括如下步骤：

[0033] S1、基于激光叉车运行环境中的主站点及子站点分别构建主有向图和子有向图，主站点一般为无实际叉车作业任务的路径端点，子站点一般为叉车作业任务点，包括充电点、上下料点、待命点等。

[0034] 主站点与子站点之间存在从属关系，即子站点从属于其对应主站点，子站点中保存了其从属主站点对应标签，存在多个子站点可以从属于同一个主站点情况，而不存在同一个子站点从属于两个不同的主站点的情况；子站点可保存叉车作业属性，包括：充电点属性、上下料点属性、待命区属性，同时根据不同作业属性，保存相应参数，如上下料子站点保存相应叉齿抬升高度，并保存到数据库中。

[0035] 在本发明实施例中，根据主站点生成主有向图G1＝(V1,E1)，其中，V1表示图中所有具有主站点属性的节点，E1表示图中两节点之间的边；

[0036] 根据子站点属性生成子有向图G2＝(V2,E2)，其中，V2表示图中所有具有子站点属性的节点，E2表示图中两节点之间的边；主有向图G1及子有向图G2中的每条边都含有一个权值，其计算方法如下：

[0037]

[0038] 其中，wij为节点i,j之间边的权值，(x1,y1)为节点i的坐标，(x2,y2)为节点j的坐标。

[0039] S2、确定激光叉车的起始站点V_start及任务站点V_task；

[0040] S3、检测V_start、V_task的站点属性，若存在子站点，则基于主有向图及子有向图分别规划主站点间的最短主路径、子站点间的最短子路径，最短主路径与最短子路径的拼接即为V_start到V_task的最短路径。

[0041] 1、离当前位置及任务位置最近的站点均为主站点，其路径规划方法具体如下：基于路径搜索算法(Floyd算法、A*算法)在主有向图G1中搜索从当前站点到任务站点的最短路径；

[0042] 2、离当前位置及任务位置最近的站点均为子站点，其路径规划方法具体如下：

[0043] 1)假设离当前位置最近的起始站点为V_start、离任务位置最近的任务站点为V_task，V_start及V_task均为子站点；

[0044] 2)获取起始站点V_start、任务站点V_task对应的主站点，分别为起始主站点V_m_start和任务主站点V_m_task；

[0045] 3)对主有向图G1使用路径搜索算法搜索从起始主站点V_m_start到任务主站点V_m_task之间的最短主路径Path_m；

[0046] 4)起始主站点V_m_start沿路径Path_m方向向前一定距离dist后，确定距起始主站点V_m_start最近的起始子节点V_p_start，且起始子节点V_p_start从属于起始主站点V_m_star；任务主站点V_m_task沿路径Path_m延伸方向向前一定距离dist后，确定距任务主站点V_m_task最近的任务子站点V_p_task，且任务子站点V_p_task从属于任务主站点V_m_task；

[0047] 5)对子有向图使用路径搜索算法获取从起始站点V_start到起始子站点V_p_start之间最短子路径Path_s1，及从任务子站点V_p_task到任务站点V_task之间最短子路径Path_s2；

[0048] 6)主路径Path_m与子路径Path_s1在起始子站点V_p_start处交汇，将主路径Path_m中起始子站点V_p_start之前路径进行剔除，并将子路径Path_s1拼接到剔除后的主路径Path_m之前，获取从起始站点V_start到任务主站点V_m_task之间的最短行驶路径Path_1；

[0049] 7)任务主节点V_m_task是沿主路径Path_m的延伸方向前向一定距离dist后确定的，因而主路径Path_m与子路径Path_s2之间不存在相交部分，任务主站点V_m_task与任务子站点V_p_task形成路径Path_s3，依次将路径Path_s3和子路径Path_s2拼接至路径Path_1后，即得到从起始站点V_start到任务站点V_task的最短行驶路径Path_2。

[0050] (3)离当前位置最近的站点为子站点，离任务位置最近的站点为主站点，其路径规划方法具体如下：

[0051] 1)假设离当前位置最近的起始站点为V_start，离任务位置最近的任务站点为V_task，V_start为子站点，V_task为主站点；

[0052] 2)获取起始站点V_start对应的主站点，称为起始主站点V_m_start；

[0053] 3)对主有向图G1使用路径搜索算法搜索从起始主站点V_m_start到任务站点V_task之间的最短主路径Path_m；

[0054] 4)起始主站点V_m_start沿路径Path_m方向向前一定距离dist后，确定距起始主站点V_m_start最近的起始子节点V_p_start，且起始子节点V_p_start从属于起始主站点V_m_star；

[0055] 5)对子有向图使用路径搜索算法获取从起始站点V_start到起始子站点V_p_start之间最短子路径Path_s1；

[0056] 6)主路径Path_m与子路径Path_s1在起始子站点V_p_start处交汇，将主路径Path_m中起始子站点V_p_start之前路径进行剔除，并将子路径Path_s1拼接到剔除后的主路径Path_m之前，获取从起始站点V_start到任务站点V_task之间的最短行驶路径Path_1。

[0057] (4)离当前位置最近的站点为主站点，离任务位置最近的站点为子站点，其路径规划方法具体如下：

[0058] 1)假设离当前位置最近的起始站点为V_start、离任务位置最近的任务站点为V_task，V_start为主站点，V_task为子站点；

[0059] 2)获取任务站点V_task对应的主站点，称为任务主站点V_m_task；

[0060] 3)对主有向图G1使用路径搜索算法搜索从起始站点V_start到任务主站点V_m_task之间的最短主路径Path_m；

[0061] 4)任务主站点V_m_task沿路径Path_m延伸方向向前一定距离dist后，确定距任务主站点V_m_task最近的任务子站点V_p_task，任务子站点V_p_task从属于任务主站点V_m_task；

[0062] 5)对子有向图使用路径搜索算法获取从任务子站点V_p_task到任务站点V_task之间最短子路径Path_s2；

[0063] 6)任务主节点V_m_task是沿主路径Path_m的延伸方向前向一定距离dist后确定的，因而主路径Path_m与子路径Path_s2之间不存在相交部分，任务主站点V_m_task与任务子站点V_p_task形成路径Path_s3，依次将路径Path_s3和子路径Path_s2拼接至路径Path_m后，即得到从起始站点V_start到任务站点V_task的最短行驶路径Path_1。

[0064] 通过贝塞尔曲线平滑对上述(1)、(2)、(3)及(4)中起始站点V_start到任务站点V_task的最短路径进行平滑处理，平滑后路径即为叉车最终行驶路径，激光叉车基于上述行驶路径达到任务位置时，基于根据任务站点的在数据库中存储的参数信息进行相应的动作。

[0065] 结合图2对上述(2)离当前位置及任务位置最近的站点均为子站点的路径规划过程进行说明，说明具体如下：

[0066] P1～P19为主有向图G1中的主站点，Pm‑n为子有向图中G2中的子站点，表示从属于主站点m的第n个子站点，假设当前位置最近的子站点为P2‑4，离任务位置最近的子站点为P19‑4，从子站点P2‑4到子站点P19‑4的路径规划过程具体如下：

[0067] 获取子站点P2‑4到子站点P19‑4从属的主站点，分为为主站点P2和主站点P19，对主有向图G1通过路径搜素算法搜索出从主站点P2到主站点P19的最短路径Path_m：P2→P3→P4→P5→P6→P19。

[0068] 将主站点P2沿路径Path_m移动一定距离dist后，获取离主站点P2最近且从属于主站点P2的子站点P2‑1，将主站点P19沿路径Path_m的延伸方向移动一定距离dist后，获取离主站点P19最近且从属于主站点P19的子站点P19‑2；

[0069] 基于子有向图G2规划从子站点P2‑4到子站点P2‑1的最短路径Path_s1：P2‑4→P2‑3→P2‑1；基于子有向图G2规划从子站点P19‑2到子站点P19‑4的最短路径Path_s2：P19‑2→P19‑3→P19‑4；

[0070] 由于路径Path_m与路径Path_s1存在交汇站点P2‑1，在路径Path_m删除路段P2→P2‑1，将路径Path_s1拼接到路径Path_m之前，形成路径Path_1：P2‑4→P2‑3→P2‑1→P3→P4→P5→P6→P19；

[0071] 路径Path_m与路径Path_s2不存在交汇站点，将主站点P19到子站点P19‑2的路段构成路径Path_2，将路径Path_2及路径Path_s2依次拼接到路径Path_1上，形成从子站点P2‑4到子站点P19‑4的最短路径Path_3：P2‑4→P2‑3→P2‑1→P3→P4→P5→P6→P19→P19‑2→P19‑3→P19‑4。

[0072] 上面结合附图对本发明进行了示例性描述，显然本发明具体实现并不受上述方式的限制，只要采用了本发明的方法构思和技术方案进行的各种非实质性的改进，或未经改进将本发明的构思和技术方案直接应用于其它场合的，均在本发明的保护范围之内。