CN112444263A

CN112444263A - 全局路径规划方法及装置

Info

Publication number: CN112444263A
Application number: CN202011003654.1A
Authority: CN
Inventors: 张卓; 颜波; 徐成; 张放; 李晓飞; 张德兆; 王肖; 霍舒豪
Original assignee: Chongqing Zhixing Information Technology Co Ltd
Current assignee: Beijing Idriverplus Technologies Co Ltd
Priority date: 2020-09-22
Filing date: 2020-09-22
Publication date: 2021-03-05
Anticipated expiration: 2040-09-22
Also published as: WO2022063005A1; CN112444263B

Abstract

本发明提供了一种全局路径规划方法，包括：获取非结构化道路中的可通行区域的第一骨架线并据此确定第二骨架线；获取可通行区域的靠右行驶路径；根据第二骨架线和靠右行驶路径，确定非结构化道路的多条边线和多个顶点；边线具有长度属性和方向属性；在进行全局路径规划前，将车辆当前位置和目标点映射到类结构化地图上；确定第一位置到类结构化地图的边线上的第一最近点集，以及第二位置到类结构化地图的边线上的第二最近点集，确定第一最近点集中的每个第一最近点至第二最近点集中的每个第二最近点的评价函数值；确定评价函数值最小的第一最近点至第二最近点之间的路径为最优路径。由此提高了全局路径规划的效率且提升了路径搜索结果的合理性。

Description

全局路径规划方法及装置

技术领域

本发明涉及自动驾驶技术领域，尤其涉及一种全局路径规划方法及装置。

背景技术

随着人工智能技术以及现代制造业的发展，自动驾驶技术已经逐渐走进人们的日常生活，并潜移默化的改变着人们的出行方式。无人驾驶技术可以简要的分为感知、预测、定位、决策、规划与控制几个方面。规划指的是路径规划，主要分为全局路径规划和局部路径规划。全局路径规划的目标是在确定区域内，合理搜索环境区域，考虑安全阈值后，生成从车辆当前位置到区域内任意目标位置的一条最优无碰撞路径。相比于结构化区域，非结构化区域缺少描述路径拓扑关系的信息，所以在非结构化区域内进行高效的全局路径规划更加具有挑战性。

目前无人驾驶全局路径规划方案主要分为基于栅格的图搜索算法以及基于随机采样的搜索算法两种：

1.基于栅格的图搜索算法以A*算法以及其变种算法为代表。其主要思想是将探索区域进行栅格化，以一个栅格为采样步长向周围空间探索。通过设计的启发式函数对每次采样点进行评价与筛选，择优后继续探索直至探索到目标点。在探索至目标点后，依据探索时设定的“父节点”得到最终的搜索路径。

2.基于随机采样的搜索算法以RRT算法为代表。其主要思想它以起始点作为根节点，通过随机采样增加叶子节点的方式，生成一个随机扩展树，当随机树中的叶子节点包含了目标点或进入了目标区域，便可以在随机树中找到一条由从初始点到目标点的路径。

基于栅格的搜索算法生成路径的合理性依赖栅格的形状和精度。对于范围大、路况复杂的非结构化区域，需要根据通行区域的宽度和形状采用不同的栅格大小和形状，不仅会增加地图的制作成本，也会增加计算量。

基于随机采样的搜索算法虽然不需要预先将地图进行栅格化，但是这是一种纯粹的随机搜索算法，对环境类型不敏感，当搜索空间中包含大量障碍物或狭窄通道约束时，算法的收敛速度慢，效率会大幅下降，而且难以在有狭窄通道的环境找到路径。

发明内容

本发明实施例的目的是提供一种全局路径规划方法及装置，以解决现有技术中的基于栅格的搜索算法生成路径的合理性依赖栅格的形状和精度，需要根据通行区域的宽度和形状采用不同的栅格大小和形状，不仅会增加地图的制作成本，也会增加计算量的问题以及基于随机采样的搜索算法对环境类型不敏感，当搜索空间中包含大量障碍物或狭窄通道约束时，算法的收敛速度慢，效率会大幅下降，而且难以在有狭窄通道的环境找到路径的问题。

第一方面，本发明提供了一种全局路径规划方法，所述全局路径规划方法包括：

获取非结构化道路中的可通行区域的第一骨架线；所述非结构化道路包括可通行区域和不可通行区域；

根据所述第一骨架线中的每个点与所述非结构化道路的边界的距离，确定第二骨架线；

获取所述可通行区域的靠右行驶路径；

根据所述第二骨架线和所述靠右行驶路径，确定非结构化道路的多条边线和多个顶点，所述多条边线和所述多个顶点组成类结构化地图；所述边线具有长度属性和方向属性，任意两条边线的交点为非结构化道路的顶点；

在进行全局路径规划前，将车辆当前位置和目标点映射到所述类结构化地图上；

根据车辆当前位置在所述类结构化地图中的第一位置，以及目标点在所述类结构化地图中的第二位置，确定所述第一位置到类结构化地图的边线上的第一最近点集，以及所述第二位置到类结构化地图的边线上的第二最近点集；

根据所述第一最近点集中的每个第一最近点到采样点沿边线的长度、每个第一最近点到采样点沿边线的方向以及采样点至每个第二最近点的距离，确定第一最近点集中的每个第一最近点至第二最近点集中的每个第二最近点的评价函数值；

确定评价函数值最小的第一最近点至第二最近点之间的路径为最优路径。

在一种可能的实现方式中，所述获取非结构化道路中的可通行区域的第一骨架线具体包括:

对所述非结构化道路中的可通行区域进行栅格化处理，将所述可通行区域划分为多个栅格；

根据每个栅格至所述不可通行区域的距离，确定每个栅格的栅格值；

当任一栅格值表示的为距离所述不可通行区域中的不同部分时，根据所述任一栅格值，确定第一骨架线。

在一种可能的实现方式中，所述获取所述可通行区域的靠右行驶路径具体包括：

获取与所述不可通行区域相邻的栅格；

根据与所述不可通行区域相邻的栅格的栅格值，确定靠右行驶路径。

在一种可能的实现方式中，进行栅格化处理时，根据车辆的宽度确定栅格大小；

根据车辆的宽度和最小转弯半径，确定靠右行驶路径到非结构化道路的边界的距离。

在一种可能的实现方式中，所述根据所述第一骨架线中的每个点与所述非结构化道路的边界的距离，确定第二骨架线具体包括：

当所述第一骨架线中的点距离所述可通行区域的边界的距离小于预设的距离阈值时，将所述第一骨架线中的点删除，得到第二骨架线。

在一种可能的实现方式中，所述边线具有方向属性具体包括：

获取靠右行驶路径上的任一边线上的任意一点；

判断所述任意一点的第一侧点和第二侧点是否在非结构化道路内；所述第一侧点和所述第二侧点设置在所述任意一点的两侧；

当所述第一侧点不在所述非结构化道路内时，确定所述任一边线的方向属性为第一方向，当所述第二侧点不在所述非结构化道路内时，确定所述任一边线的方向属性为第二方向；所述第一方向和所述第二方向互为反方向。

在一种可能的实现方式中，所述搜索所述第一位置到类结构化地图的边线上的第一最近点集，以及所述第二位置到类结构化地图的边线上的第二最近点集具体包括：

以所述第一位置为圆心，以预设第一半径为半径确定起始圆；

确定所述起始圆中的第一最近点集，并将所述第一最近点集中的每一第一最近点作为全局路径规划的起点；

以所述第二位置为圆心，以预设第二半径为半径确定终点圆；

确定所述终点圆中的第二最近点集，并将所述第二最近点集中的每一第二最近点作为劝募路径规划的终点。

在一种可能的实现方式中，所述根据所述第一最近点集中的每个第一最近点到采样点沿边线的长度、每个第一最近点到采样点沿边线的方向以及采样点至每个第二最近点的距离，确定第一最近点集中的每个第一最近点至第二最近点集中的每个第二最近点的评价值具体包括：

确定每个起点到采样点沿边线的长度；

确定每个起点到采样点沿边线的方向；

确定预设的第一权重值和所述长度的第一乘积；

确定预设的第二权重值和所述方向的第二乘积；

确定所述第一乘积和所述第二乘积的和值作为第一代价值；

确定所述采样点到目标点的距离作为第二代价值；

根据所述第一代价值和所述第二代价值，确定评价函数值。

第二方面，本发明提供了一种全局路径规划装置，所述全局路径规划装置包括：

获取单元，所述获取单元用于获取非结构化道路中的可通行区域的第一骨架线；所述非结构化道路包括可通行区域和不可通行区域；

确定单元，所述确定单元用于根据所述第一骨架线中的每个点与所述非结构化道路的边界的距离，确定第二骨架线；

所述获取单元还用于，获取所述可通行区域的靠右行驶路径；

所述确定单元还用于，根据所述第二骨架线和所述靠右行驶路径，确定非结构化道路的多条边线和多个顶点，所述多条边线和所述多个顶点组成类结构化地图；所述边线具有长度属性和方向属性，任意两条边线的交点为非结构化道路的顶点；

映射单元，所述映射单元用于在进行全局路径规划前，将车辆当前位置和目标点映射到所述类结构化地图上；

所述确定单元还用于，根据车辆当前位置在所述类结构化地图中的第一位置，以及目标点在所述类结构化地图中的第二位置，确定所述第一位置到类结构化地图的边线上的第一最近点集，以及所述第二位置到类结构化地图的边线上的第二最近点集；

所述确定单元还用于，根据所述第一最近点集中的每个第一最近点到采样点沿边线的长度、每个第一最近点到采样点沿边线的方向以及采样点至每个第二最近点的距离，确定第一最近点集中的每个第一最近点至第二最近点集中的每个第二最近点的评价函数值；

所述确定单元还用于，确定评价函数值最小的第一最近点至第二最近点之间的路径为最优路径。

第三方面，本发明提供了一种设备，包括存储器和处理器，存储器用于存储程序，处理器用于执行第一方面任一所述的方法。

第四方面，本发明提供了一种包含指令的计算机程序产品，当计算机程序产品在计算机上运行时，使得计算机执行如第一方面任一所述的方法。

第五方面，本发明提供了一种计算机可读存储介质，计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现如第一方面任一所述的方法。

通过应用本发明实施例提供的全局路径规划方法及装置，可以将非结构化道路进行拓扑化处理，得到其类结构化地图，从而通过类结构化地图经全局路径规划，以提高全局路径规划的效率，同时，本申请在进行路径评价时，可以结合类结构化地图中的边线的长度属性和方向属性，从而提升了路径搜索结果的合理性。

附图说明

图1为本发明实施例一提供的全局路径规划方法流程示意图；

图2为本发明实施例一提供的非结构化道路示意图；

图3为本发明实施例一提供的生成非结构化道路的类结构化地图的原理图；

图4为图3的区块图；

图5为本发明实施例一提供的分结构化道路的第一骨架线；

图6为本发明实施例一提供的第二骨架线及靠右行驶路径示意图；

图7为本发明实施例一提供的边线的方向属性示意图；

图8为本发明实施例一提供的具有方向属性的非结构化道路的示意图；

图9为本发明实施例一提供的第一最近点集和第二最近点集示意图；

图10为本发明实施例二提供的全局路径规划装置结构示意图。

具体实施方式

下面结合附图和实施例对本申请作进一步的详细说明。可以理解的是，此处所描述的具体实施例仅仅用于解释相关发明，而非对该发明的限定。另外还需要说明的是，为便于描述，附图中仅示出了与有关发明相关的部分。

需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本申请。

图1为本发明实施例一提供的全局路径规划方法流程示意图。本申请的执行主体为具有计算功能的终端、服务器或者处理器。本申请以将该方法应用在无人驾驶车辆为例进行说明，当将该方法应用在无人驾驶车辆时，该方法的执行主体为自动驾驶车辆控制单元(Automated Vehicle Control Unit，AVCU)，即无人驾驶车辆的中央处理器相当于无人驾驶车辆的“大脑”。本申请包括以下步骤：

步骤110，获取非结构化道路中的可通行区域的第一骨架线。

具体的，自动驾驶车辆在行驶中，会加载所行驶的区域的地图，该地图中，存在着结构化道路和非结构化道路。其中，非结构化道路与结构化道路相对立，结构化道路指的是高速公路、城市干道等结构化较好的公路，这类道路具有清晰的道路标志线，道路的背景环境比较单一，道路的几何特征也比较明显。对于结构化道路，可以很容易的获取路径之间的拓扑关系，然后根据拓扑关系进行全局路径规划。

非结构化道路一般是指城市非主干道、乡村街道等结构化程度较低的道路，这类道路没有车道线和清晰的道路边界，再加上受阴影和水迹等的影响，道路区域和非道路区域难以区分。非结构化道路包括可通行区域和不可通行区域。

参见图2，图2为本发明实施例一提供的非结构化道路示意图，图2中下部的点可以作为车辆的当前位置，上部的点作为当前车辆的目标点。深色区域为可通行区域，白色区域为不可通行区域。

对于类似图2中的非结构化道路，可以通过一定的处理，从而确定其第一骨架线。此处的处理，是栅格化处理，通过栅格化处理确定第一骨架线的步骤如下：

首先，对非结构化道路中的可通行区域进行栅格化处理，将可通行区域划分为多个栅格；其次，根据每个栅格至不可通行区域的距离，确定每个栅格的栅格值；最后，当任一栅格值表示的为距离不可通行区域中的不同部分时，根据任一栅格值，确定第一骨架线。

下面结合图3，对如何确定第一骨架线进行说明。

图3中黑色区域为不可通行区域，灰色区域为可通行区域，将不可通行区域视为障碍物，将图3中的非结构化道路的边界视为单独的障碍物，将可通行区域进行栅格化处理，每个栅格值表示到最近障碍物的距离，障碍物占据的栅格的栅格值为0，与障碍物相邻的栅格的栅格值记为1，依次向外延伸，直到由两个不同障碍物延伸到相同的栅格结束，比如栅格值为4，表示距离左右两侧的障碍物的距离都为4，则栅格值为4的栅格表示由两个不同障碍物延伸到相同的栅格，此时，延伸终止的栅格组成了该区域的第一骨架线。

图4为图3的区块图，参见图4，根据白线可以将可通行区域分为5个区块，对于1区而言，距离1区的点最近的障碍物是左侧的障碍物，其他侧的障碍物都没有左侧障碍物近。对于2区而言，距离2区最近的障碍物是上侧的障碍物，其他侧的障碍物都没有上侧的障碍物近。同理，对于5区而言，距离5区最近的障碍物就是中间的障碍物了，其他侧的障碍物都没有中间的障碍物近。

所以说，栅格值4的栅格和顶点的连线就是用来区分不同区块的，栅格值4的栅格和顶点的连线，其上侧的点距离上侧的障碍物更近，其下侧的点距离左侧的障碍物更近，连线恰好是分界线，因此被用来做骨架线。

同理，栅格值4的栅格取中心点的原因也类似，因为中心点距离左侧、上侧、中间障碍物的距离都是一样的，所以作为分界点。

由此，根据图3和图4所示，可以确定图2的非结构化道路的第一骨架线，图2所示的非结构化道路的第一骨架线如图5所示，图5为本发明实施例一提供的分结构化道路的第一骨架线。

其中，上述进行栅格化处理时的栅格大小，是根据车辆的宽度确定的，比如，栅格的大小和车辆的宽度成固定的比例，比如1:1，又或者，栅格的大小是根据车辆的长度和宽度确定的，比如栅格的大小为车辆的长度的平方加上宽度的平方后，再开方，从而根据车辆的长度和宽度，确定栅格大小，便于提高栅格处理时的速度。

步骤120，根据第一骨架线中的每个点与非结构化道路的边界的距离，确定第二骨架线。

具体的，对于第一骨架线，其是由多个边线组成的，当第一骨架线中的边线上的点距离可通行区域的边界的距离小于预设的距离阈值时，将第一骨架线中的边线删除，得到第二骨架线。

比如，第一骨架线上某个边线中如果有一个点距离非结构化道路的边界的距离小于预设距离阈值，则剔除该边线。

步骤130，获取可通行区域的靠右行驶路径。

具体的，在一个示例中，可以根据无人驾驶车辆的宽度和最小转弯半径，确定靠右行驶时的路径到非结构化道路的边界的距离，从而可以根据该距离和非结构化道路的边界，确定靠右行驶路径。其中，此处的距离，可以是车辆的宽度的一半与最小转弯半径之和。

在另一个示例中，可以获取与不可通行区域相邻的栅格；根据与不可通行区域相邻的栅格的栅格值，确定靠右行驶路径。比如，参见图3，与不可通行区域相邻的栅格值为1，则根据栅格值1，取栅格值为1的栅格的中心点进行连线，从而确定靠右行驶路径。

步骤140，根据第二骨架线和靠右行驶路径，确定非结构化道路的多条边线和多个顶点，多条边线和多个顶点组成类结构化地图；边线具有长度属性和方向属性，任意两条边线的交点为非结构化道路的顶点。

具体的，类结构化地图其实也就是类似结构化地图，在类结构化地图中，非结构化道路被处理为含有多条边线和多个顶点。

参见图6，图6为本发明实施例一提供的第二骨架线及靠右行驶路径示意图，图6中实线为第二骨架线，虚线为靠右行驶路径，图6中的第二骨架线和靠右行驶路径，称为边线，每条边线的交点，称为顶点，两个顶点之间为一条边线，边线不仅具有长度属性，还具有方向属性，边线中的第二骨架线为双向可通行，靠右行驶路径遵循靠右行驶的原则。

下面关于如何确定边线的方向属性进行说明：

具体的，首先获取靠右行驶路径上的任一边线上的任意一点；然后判断任意一点的第一侧点和第二侧点是否在非结构化道路内；第一侧点和第二侧点设置在任意一点的两侧；最后，当第一侧点不在非结构化道路内时，确定任一边线的方向属性为第一方向，当第二侧点不在非结构化道路内时，确定任一边线的方向属性为第二方向；第一方向和第二方向互为反方向。

参见图7，以边线AB为例，如果AB到非结构化道路的边界的距离为l，给定AB一个初始方向如图中箭头所示，即由A指向B，在AB边上任取一点C，沿与C点法线方向在C点左右两侧取点C_l和C_r。C_l和C_r符合如下公式：

CC_r＝CC_r＝l+ε 公式(1)

其中，CC_r为点C到点C_r的线段长度，CC_l为点C到点C_l的线段长度，ε是一个足够小的值，可以看做无穷小。

可以通过检测C_l和C_r是否在非结构化道路内，确定边线AB的方向属性。如果C_r不在非结构化道路内，则图8中箭头即为AB边线的方向，若C_l不在非结构化道路内，则图8中箭头的反方向即为AB边线的方向。

参见图8，非结构化道路的类结构化地图中，包括边线的长度属性、方向属性以及多个顶点。该方向属性可以通过箭头进行直观的表示，长度属性可以存储在数据库中，比如，边线具有边线ID，对应的边线ID对应该边线的长度属性。该边线ID和长度属性可以以表格的方式存储在数据库中。如边线AB的ID为01，对应的长度为5m，则将01与5米以表格的方式存储在数据库中。

步骤150，在进行全局路径规划前，将车辆当前位置和目标点映射到类结构化地图上。

具体的，自动驾驶车辆在行驶过程中，可以通过车辆上安装的传感器，比如惯性测量单元(Inertial measurement unit，IMU)、全球定位系统(Global Positioning System，GPS)等得到车辆当前的位置信息。

当服务器接收到用户终端的叫车服务信息时，比如，用户终端接收用户输入的出发地、目的地和出发时间等信息，服务器接收用户终端发送的出发地、目的地信息后，筛选出目标车辆，并将出发地、目的地和出发时间、出发人数等信息一起发送给目标车辆。

对于目标车辆，当车辆行驶过程中，需要进行全局路径规划，以便从出发地行驶至目的地，在进行全局路径规划之前，如果当前位置信息和目的地，即目标点，都处于上述得到的具有多条边线和多个顶点的类结构化地图中，可以将车辆当前位置和目标点映射在类结构化地图中。

其中，车辆当前位置可以是经纬度数据，而类结构化地图中的每个点，都具有位置信息，可以将车辆当前的经纬度数据映射到结构化地图中去，从而可以确定结构化地图中车辆的当前位置和目标点。

步骤160，根据车辆当前位置在类结构化地图中的第一位置，以及目标点在类结构化地图中的第二位置，确定第一位置到类结构化地图的边线上的第一最近点集，以及第二位置到类结构化地图的边线上的第二最近点集。

具体的，步骤160包括：首先，以第一位置为圆心，以预设第一半径为半径确定起始圆；其次，确定起始圆中的第一最近点集，并将第一最近点集中的每一第一最近点作为全局路径规划的起点；再次，以第二位置为圆心，以预设第二半径为半径确定终点圆；最后，确定终点圆中的第二最近点集，并将第二最近点集中的每一第二最近点作为劝募路径规划的终点。

其中，预设第一半径和预设第二半径可以是相同的，也可以是不同的。预设第一半径可以是根据车辆的宽度和固定值而确定，该固定值与第一位置周围的边线的数量和周围相邻边线的距离相关，比如，参见图9，第一位置为下方的小矩形框，第一位置处有三条边线，则以预设第一半径做圆后，要保证三条边线都处于起始圆中，得到的第一最近点集以下方的小矩形框周围的三个小五角星表示。

相应的，对终点圆的设置与对起始圆的设置方式相似，此处不再赘述。第二位置为上方的小矩形框，第一位置处有三条边线，则以预设第二半径做圆后，得到的第二最近点集以上方的小矩形框周围的三个小五角星表示。

步骤170，根据第一最近点集中的每个第一最近点到采样点沿边线的长度、每个第一最近点到采样点沿边线的方向以及采样点至每个第二最近点的距离，确定第一最近点集中的每个第一最近点至第二最近点集中的每个第二最近点的评价函数值。

具体的，步骤170包括：确定每个起点到采样点沿边线的长度；确定每个起点到采样点沿边线的方向；确定预设的第一权重值和长度的第一乘积；确定预设的第二权重值和方向的第二乘积；确定第一乘积和第二乘积的和值作为第一代价值；确定采样点到目标点的距离作为第二代价值；根据第一代价值和第二代价值，确定评价函数值。

采样点为在进行每次路径搜索时的一个点，路径搜索可以采用路径搜索算法来实现。比如启发式路径搜索算法中的A*算法等，本申请对此并不限定。

具体的，在一个示例中，当采用启发式路径搜索算法时，可以通过A*算法对应的评价评价函数进行评价，评价函数如公式(2)所示：

f＝g+h 公式(2)

g值为搜索的第一代价值，代表从搜索的起始点到当前采样点搜索所付出的代价。h值为当前采样点到目标点的第二代价值，可以用采样点到目标点的距离表示，此处的距离，包括但不限于欧式距离和曼哈顿距离。

其中，本申请可以通过公式(3)计算第一代价值。

g＝α*l+β*dir 公式(3)

其中，l表示起始点到当前采样点沿边线的长度，通过顶点将边线进行划分，两个顶点之间的边线作为一条边线，dir为起点到采样点沿边线的方向，其中，顺行记为0，逆行记为1，α为第一权重系数，表示路径长度对整条路的重要性，β为第二权重系数，表示方向对于整条路径的重要性。

α和β可以根据需求进行设定，比如如果不要求车辆正逆行的话，只要求能最短到达目标点的话，那么β的意义就不大，此时可以将β的值设定为比α值小，且β无限小，其具体的数值，需要经过多次模拟计算而确定。

步骤180，确定评价函数值最小的第一最近点至第二最近点之间的路径为最优路径。

后续，可以根据第一代价值和第二代价值，确定评价函数值，并根据评价函数值，确定评价函数值最小的对应最优路径。

比如，起始点有1、2、3，采样点为A，终点为4,5,6，则起始点至采样点，一共计算1-A、2-A、3-A三条路径的第一代价值，采样点至终点，计算A-4、A-5和A-6三条路径的第二代价值，然后任意相加，即1-A+A-4，1-A+A-5，1-A+A-6，2-A+A-4，2-A+A-5，2-A+A-6，3-A+A-4，3-A+A-5，3-A+A-6，计算这9个值，确定评价函数值最小的为一个局部路径，比如1-A+A-4最小，可以确定起始点1到采样点A再到终点4为最优路径。

通过应用本发明实施例提供的全局路径规划方法，可以将非结构化道路进行拓扑化处理，得到其类结构化地图，从而通过类结构化地图经全局路径规划，以提高全局路径规划的效率，同时，本申请在进行路径评价时，可以结合类结构化地图中的边线的长度属性和方向属性，从而提升了路径搜索结果的合理性。

图10为本发明实施例二提供的全局路径规划装置结构示意图，如图10所示，该全局路径规划装置应用在实施例一中的全局路径规划方法中，全局路径规划装置包括：获取单元210、确定单元220和映射单元230。

获取单元210用于获取非结构化道路中的可通行区域的第一骨架线；非结构化道路包括可通行区域和不可通行区域；

确定单元220用于根据第一骨架线中的每个点与非结构化道路的边界的距离，确定第二骨架线；

获取单元210还用于，获取可通行区域的靠右行驶路径；

确定单元220还用于，根据第二骨架线和靠右行驶路径，确定非结构化道路的多条边线和多个顶点，多条边线和多个顶点组成类结构化地图；边线具有长度属性和方向属性，任意两条边线的交点为非结构化道路的顶点；

映射单元230用于在进行全局路径规划前，将车辆当前位置和目标点映射到类结构化地图上；

确定单元220还用于，根据车辆当前位置在类结构化地图中的第一位置，以及目标点在类结构化地图中的第二位置，确定第一位置到类结构化地图的边线上的第一最近点集，以及第二位置到类结构化地图的边线上的第二最近点集；

确定单元220还用于，根据第一最近点集中的每个第一最近点到采样点沿边线的长度、每个第一最近点到采样点沿边线的方向以及采样点至每个第二最近点的距离，确定第一最近点集中的每个第一最近点至第二最近点集中的每个第二最近点的评价函数值；

确定单元220还用于，确定评价函数值最小的第一最近点至第二最近点之间的路径为最优路径。

进一步的，获取单元210具体用于：对非结构化道路中的可通行区域进行栅格化处理，将可通行区域划分为多个栅格；根据每个栅格至不可通行区域的距离，确定每个栅格的栅格值；当任一栅格值表示的为距离不可通行区域中的不同部分时，根据任一栅格值，确定第一骨架线。

进一步的，获取单元210具体用于：获取与不可通行区域相邻的栅格；根据与不可通行区域相邻的栅格的栅格值，确定靠右行驶路径。

其中，进行栅格化处理时，根据车辆的宽度确定栅格大小；根据车辆的宽度和最小转弯半径，确定靠右行驶路径到非结构化道路的边界的距离。

进一步的，确定单元220具体用于：

当第一骨架线中的点距离可通行区域的边界的距离小于预设的距离阈值时，将第一骨架线中的点删除，得到第二骨架线。

其中，边线具有方向属性具体包括：

获取靠右行驶路径上的任一边线上的任意一点；

判断任意一点的第一侧点和第二侧点是否在非结构化道路内；第一侧点和第二侧点设置在任意一点的两侧；

当第一侧点不在非结构化道路内时，确定任一边线的方向属性为第一方向，当第二侧点不在非结构化道路内时，确定任一边线的方向属性为第二方向；第一方向和第二方向互为反方向。

进一步的，确定单元220具体用于：

以第一位置为圆心，以预设第一半径为半径确定起始圆；

确定起始圆中的第一最近点集，并将第一最近点集中的每一第一最近点作为全局路径规划的起点；

以第二位置为圆心，以预设第二半径为半径确定终点圆；

确定终点圆中的第二最近点集，并将第二最近点集中的每一第二最近点作为劝募路径规划的终点。

进一步的，确定单元220具体用于：

确定每个起点到采样点沿边线的长度；确定每个起点到采样点沿边线的方向；确定预设的第一权重值和长度的第一乘积；确定预设的第二权重值和方向的第二乘积；确定第一乘积和第二乘积的和值作为第一代价值；确定采样点到目标点的距离作为第二代价值；根据第一代价值和第二代价值，确定评价函数值。

通过应用本发明实施例提供的全局路径规划装置，可以将非结构化道路进行拓扑化处理，得到其类结构化地图，从而通过类结构化地图经全局路径规划，以提高全局路径规划的效率，同时，本申请在进行路径评价时，可以结合类结构化地图中的边线的长度属性和方向属性，从而提升了路径搜索结果的合理性。

本发明实施例三提供了一种设备，包括存储器和处理器，存储器用于存储程序，存储器可通过总线与处理器连接。存储器可以是非易失存储器，例如硬盘驱动器和闪存，存储器中存储有软件程序和设备驱动程序。软件程序能够执行本发明实施例提供的上述方法的各种功能；设备驱动程序可以是网络和接口驱动程序。处理器用于执行软件程序，该软件程序被执行时，能够实现本发明实施例一提供的方法。

本发明实施例四提供了一种包含指令的计算机程序产品，当计算机程序产品在计算机上运行时，使得计算机执行本发明实施例一提供的方法。

本发明实施例五提供了一种计算机可读存储介质，计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时实现本发明实施例一提供的方法。

专业人员应该还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。

结合本文中所公开的实施例描述的方法或算法的步骤可以用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器(RAM)、内存、只读存储器(ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的存储介质中。

以上的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims

1.一种全局路径规划方法，其特征在于，所述全局路径规划方法包括：

获取所述可通行区域的靠右行驶路径；

2.根据权利要求1所述的方法，其特征在于，所述获取非结构化道路中的可通行区域的第一骨架线具体包括:

3.根据权利要求2所述的方法，其特征在于，所述获取所述可通行区域的靠右行驶路径具体包括：

获取与所述不可通行区域相邻的栅格；

4.根据权利要求2所述的方法，其特征在于，进行栅格化处理时，根据车辆的宽度确定栅格大小；

5.根据权利要求1所述的方法，其特征在于，所述根据所述第一骨架线中的每个点与所述非结构化道路的边界的距离，确定第二骨架线具体包括：

6.根据权利要求1所述的方法，其特征在于，所述边线具有方向属性具体包括：

获取靠右行驶路径上的任一边线上的任意一点；

7.根据权利要求1所述的方法，其特征在于，所述搜索所述第一位置到类结构化地图的边线上的第一最近点集，以及所述第二位置到类结构化地图的边线上的第二最近点集具体包括：

8.根据权利要求7所述的方法，其特征在于，所述根据所述第一最近点集中的每个第一最近点到采样点沿边线的长度、每个第一最近点到采样点沿边线的方向以及采样点至每个第二最近点的距离，确定第一最近点集中的每个第一最近点至第二最近点集中的每个第二最近点的评价值具体包括：

确定每个起点到采样点沿边线的长度；

确定每个起点到采样点沿边线的方向；

确定预设的第一权重值和所述长度的第一乘积；

确定预设的第二权重值和所述方向的第二乘积；

确定所述第一乘积和所述第二乘积的和值作为第一代价值；

确定所述采样点到目标点的距离作为第二代价值；

根据所述第一代价值和所述第二代价值，确定评价函数值。

9.一种全局路径规划装置，其特征在于，所述全局路径规划装置包括：

10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，计算机程序被处理器执行时执行如权利要求1-8任一所述的方法。