CN112947485B - 路径规划方法及系统 - Google Patents

Abstract

本发明提供一种路径规划方法及系统，该路径规划方法包括：获取多个候选轨迹线路；基于候选轨迹线路上的所有轨迹点的位置信息，确定候选轨迹线路对应的多个位置网格；基于位置网格与候选轨迹线路的对应关系，确定每一位置网格对应的多个候选轨迹线路；从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路；获取目标对象的位置信息；基于目标对象的位置信息以及每个位置网格对应的参考轨迹线路，确定目标轨迹线路。本发明提供的路径规划方法及系统，通过在离线过程计算出每个位置网格对应的参考轨迹线路，在线过程根据目标对象的位置信息来确定目标轨迹线路，这样可以降低运算复杂度，提高轨迹规划效率和准确率。

Description

路径规划方法及系统

技术领域

本发明涉及数据处理技术领域，尤其涉及一种路径规划方法及系统。

背景技术

随着大数据技术的发展，利用历史数据来对目标对象的运动路径进行规划日益受到重视，路径规划在很多领域都有广泛的应用。比如航海领域的船舶航行轨迹规划、城市道路网规划导航、物流管理中的车辆路线规划以及机器人或者无人机的运动路径规划。

目前的路径规划方法，往往是在给定起始地点和目标地点后，根据目标对象的类型、道路限行和天气情况等物理参数来给出几条备选路线，由用户从备选路线中自行选择合适的路线。然而目前的路径规划方法规划出的路径比较单一，不够精细，且响应时间较长，稳定性较差。

发明内容

本发明提供一种路径规划方法及系统，用以解决现有技术中规划出的路径比较单一，不够精细，且响应时间较长，稳定性较差的缺陷，实现降低运算复杂度，提高轨迹规划效率和准确率。

本发明提供一种路径规划方法，该路径规划方法包括：获取终点为目标地点的多个候选轨迹线路；基于所述候选轨迹线路上的所有轨迹点的位置信息，确定所述候选轨迹线路对应的多个位置网格，所述位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格；基于所述位置网格与所述候选轨迹线路的对应关系，确定每一所述位置网格对应的多个候选轨迹线路；从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路；获取目标对象的位置信息；基于所述目标对象的位置信息以及每个所述位置网格对应的参考轨迹线路，确定目标轨迹线路。

根据本发明提供的一种路径规划方法，所述获取终点为目标地点的多个候选轨迹线路，包括：获取终点为目标地点的多个原始轨迹线路；若所述原始轨迹线路中相邻的两个原始轨迹点之间的距离大于目标距离阈值时，基于大圆航线算法，在所述相邻的两个原始轨迹点之间插入虚拟轨迹点；基于所述原始轨迹点和所述虚拟轨迹点，得到多个所述候选轨迹线路。

根据本发明提供的一种路径规划方法，所述基于所述候选轨迹线路上的所有轨迹点的位置信息，确定所述候选轨迹线路对应的多个位置网格，包括：基于所述候选轨迹线路上的所有轨迹点的位置信息，将与每一轨迹点之间的距离在目标半径阈值范围内的位置网格作为所述候选轨迹线路对应的多个位置网格。

根据本发明提供的一种路径规划方法，所述从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路，包括：确定每个所述候选轨迹线路从所述位置网格到目标地点的里程参数；从多个候选轨迹线路筛选出所述里程参数最小的候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路。

根据本发明提供的一种路径规划方法，所述从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路，包括：确定每个所述候选轨迹线路上的处于所述位置网格之后的最近轨迹点与所述位置网格的距离参数；从多个候选轨迹线路筛选出所述距离参数最小的候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路；基于所述位置网格与所述参考轨迹线路上的轨迹点构成的角度以及目标角度阈值，确定所述参考轨迹线路上的平滑接入点。

根据本发明提供的一种路径规划方法，所述从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路，包括：基于目标对象的类型、目标对象的大小、季节信息以及目标对象的单位信息中的至少一个，从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路。

根据本发明提供的一种路径规划方法，所述路径规划方法还包括：基于所述目标对象的速度信息、所述目标对象的位置信息以及所述目标轨迹线路，确定所述目标对象到达目标地点的时间信息。

本发明还提供一种路径规划系统，该路径规划系统包括：第一获取模块，用于获取终点为目标地点的多个候选轨迹线路；第一确定模块，用于基于所述候选轨迹线路上的所有轨迹点的位置信息，确定所述候选轨迹线路对应的多个位置网格，所述位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格；第二确定模块，用于基于所述位置网格与所述候选轨迹线路的对应关系，确定每一所述位置网格对应的多个候选轨迹线路；筛选模块，用于从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路；第二获取模块，用于获取目标对象的位置信息；第三确定模块，用于基于所述目标对象的位置信息以及每个所述位置网格对应的参考轨迹线路，确定目标轨迹线路。

本发明还提供一种电子设备，包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，所述处理器执行所述计算机程序时实现如上述任一种所述路径规划方法的步骤。

本发明还提供一种非暂态计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现如上述任一种所述路径规划方法的步骤。

本发明提供的路径规划方法及系统，通过在离线过程计算出每个位置网格对应的参考轨迹线路，在线过程根据目标对象的位置信息来确定目标轨迹线路，这样可以降低运算复杂度，提高轨迹规划效率和准确率。

附图说明

为了更清楚地说明本发明或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1是本发明提供的路径规划方法的流程示意图；

图2是本发明提供的路径规划方法的获取候选轨迹线路的原理图；

图3是本发明提供的路径规划系统的结构示意图；

图4是本发明提供的电子设备的结构示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚，下面将结合本发明中的附图，对本发明中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

下面结合图1至图4描述本发明的路径规划方法及系统。

如图1所示，本发明提供一种路径规划方法，该路径规划方法包括：如下步骤110至步骤160。

其中，步骤110、获取终点为目标地点的多个候选轨迹线路。

可以理解的是，该路径规划方法可以用于船舶、车辆、飞机或者其他可以移动的目标对象的轨迹规划中，候选轨迹线路可以是预置的多条现有线路，候选轨迹线路可以为经过反复测量和实验确定的线路，比如在航海领域，候选轨迹线路可以为经过探测的可行路线，比如可以为避开了礁石或者湍流的安全路线，本实施例的路径规划方法可以应用在全球航海场景，那么候选轨迹线路的数量单位可以为千万级别的。

当候选轨迹线路是航海领域的线路，则每条候选轨迹线路可以记录船舶标识、始发港、目的港、离开始发港的时间、到达目的港的时间、航行距离、平均航速、船舶类型和路径关键点，海量航线可以覆盖全球。

如图2所示，此处可以对众多轨迹线路中进行筛选操作，选择终点为目标地点P的多个候选轨迹线路，比如图2中L1、L2、L3、L4、L5和L6等多条候选轨迹线路，比如终点可以选定为山东青岛，那么此处获取到的候选轨迹线路的终点都是山东青岛。

步骤120、基于候选轨迹线路上的所有轨迹点的位置信息，确定候选轨迹线路对应的多个位置网格，位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格。

可以理解的是，位置网格可以是按照目标边长对世界坐标系划分出的多个矩形网格，多个矩形网格的形状和大小都相同，可以将全球按照经纬度坐标划分为多个位置网格，位置网格能够用于对目标对象进行定位，比如可以确定海上航行的船舶所处的位置网格，从而根据位置网格对该船舶进行定位。

与此同时，候选轨迹线路也是由多个轨迹点连接而成的线路，每个轨迹点可以具有对应的经纬度坐标，也就是每个轨迹点均具有特有的位置信息，可以候选轨迹线路的轨迹点的位置信息，来与对应的位置网格进行匹配，也就是可以确定轨迹点对应的位置网格，当确定每个轨迹点对应的位置网格时，就确定了候选轨迹线路所对应的多个位置网格。

也就是说，每条候选轨迹线路都可以匹配有多个位置网格。

步骤130、基于位置网格与候选轨迹线路的对应关系，确定每一位置网格对应的多个候选轨迹线路。

可以理解的是，由于不同的候选轨迹线路之间会存在临近点，也就是说，多条候选轨迹线路会同时对应同一个位置网格，因此，一个位置网格可能对应有多条候选轨迹线路。

此处根据上一步骤中确定的每条候选轨迹线路与位置网格的对应关系，能够找到每一个位置网格所对应的多个候选轨迹线路。换言之，给定一个位置网格，就能够找到对应于该位置网格的多条候选轨迹线路。

步骤140、从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路。

可以理解的是，此处可以基于目标规则，以每个位置网格为单位，从该位置网格所对应的多个候选轨迹线路中确定一个候选轨迹线路，将该候选轨迹线路作为该位置网格所对应的参考轨迹线路。

这种目标规则可以是剩余里程最小原则，也就是从该位置网格对应的候选轨迹线路中挑选出剩余里程最短的那一条作为参考轨迹线路，剩余里程指的是以该位置网格为起点，目标地点为终点，以候选轨迹线路为行驶轨迹所计算出来的位移长度。

这种目标规则还可以是剩余时间最短原则，也就是从该位置网格对应的候选轨迹线路中挑选出剩余行驶时间最短的那一条作为参考轨迹线路，剩余时间指的是以该位置网格为起点，目标地点为终点，以候选轨迹线路为行驶轨迹所计算出来的行驶耗时。

这种目标规则还可以是气温适宜原则，也就是从该位置网格对应的候选轨迹线路中挑选出气温最适宜的那一条作为参考轨迹线路，气温适宜指的是天气或者温度等气候环境最适宜目标对象行驶，比如，对于某些货运船舶来说，货物的保藏温度不能过低，因此可以选择温度适当高一些的候选轨迹线路来行驶。

当然这种目标规则还可以为其他规则，本实施例并不对其进行限制，本领域技术人员可以根据实际的场景需求来进行选择。

步骤150、获取目标对象的位置信息。

可以理解的是，目标对象的位置信息是实时采集的，目标对象在移动时位置会发生变化，此处获取到的就是目标对象的实时位置信息。可以基于GPS设备、北斗设备或者雷达设备采集目标对象的位置信息，比如可以使用GPS设备采集船舶的经纬度数据。

步骤160、基于目标对象的位置信息以及每个位置网格对应的参考轨迹线路，确定目标轨迹线路。

可以理解的是，在确定了目标对象的位置信息时，就能够确定目标对象所处的位置网格，也能够确定目标对象一定范围内的位置网格，此处可能存在两种情况，一种情况是目标对象所处的位置网格正好对应有参考轨迹线路，那么就将该参考轨迹线路作为目标轨迹线路；另一种情况是目标对象所处的位置网格并未对应有参考轨迹线路，此时可以找到距离目标对象最近的对应有参考轨迹线路的位置网格，将该位置网格所对应的参考轨迹线路作为目标轨迹线路。

对应有参考轨迹线路的位置网格指的是，该位置网格有候选轨迹线路经过，也就有参考轨迹线路经过。

在确定了目标轨迹线路后，目标对象可以平稳地移动到该目标轨迹线路中，按照该目标轨迹线路行驶。

经过归纳可知，在进行步骤110-步骤140的过程中，并没有将目标对象纳入到考虑范围，也就是并没有利用目标对象相关的数据，也就是步骤110-步骤140并不涉及到服务器端和客户端在线连接的过程，这其实就是一种离线计算的方法，只是在步骤150-步骤160才使用了目标对象的位置信息，此时就需要从客户端向服务器端发送目标对象的位置信息，这就是在线计算的过程。

此处将复杂的运算过程进行离线计算，而进行在线计算的过程只是进行了简单的检索匹配计算，这样能够降低运算难度，能够提高运算效率。

目前，基于AIS(Automatic Identification System，船舶自动识别系统，简称AIS系统)设备发送的船舶位置、航速和目的地等信息可以提供船位服务。航速和船位等部分信息由船载设备自动采集，准确度较高，预抵港日期由船上工作人员手动填写，可靠性较低。从对预抵港时间多年的使用经验来看，存在准确性和更新不及时两类问题。通过考察同行业的船舶航路规划业务，发现由于缺乏庞大的基础航线路网，一般使用关键点生成路径。

然而使用关键点生成路径，一方面由于关键点数量有限，普遍存在两个问题，一是部分港口不可达，二是规划的路径单一，不够精细。另一方面由于采用线规划算法，系统响应时间较长，且不稳定。

本实施例通过网格结构统一了基础航路关键点和船舶实时船位的提升过程，在离线过程中对千万级真实航线的路径关键点进行提升，通过网格和目的港遍历预先完成航路规划，将数据存储到数据库中。在实时航路规划服务中加载这些静态数据可以省去路径规划所需的计算量，仅通过船舶位置提升后的网格索引查询结果即可。这种方式显著地提高了系统响应效率，同时能够为目标对象规划出准确合理的轨迹，提高轨迹规划的准确率。

本发明提供的路径规划方法，通过在离线过程计算出每个位置网格对应的参考轨迹线路，在线过程根据目标对象的位置信息来确定目标轨迹线路，这样可以降低运算复杂度，提高轨迹规划效率和准确率。

在一些实施例中，上述步骤110、获取终点为目标地点的多个候选轨迹线路，包括：获取终点为目标地点的多个原始轨迹线路；若原始轨迹线路中相邻的两个原始轨迹点之间的距离大于目标距离阈值时，基于大圆航线算法，在相邻的两个原始轨迹点之间插入虚拟轨迹点；基于原始轨迹点和虚拟轨迹点，得到多个候选轨迹线路。

可以理解的是，此处候选轨迹线路可以是对原始轨迹线路进行密集化操作得到的，原始轨迹线路上的相邻的原始轨迹点之间的距离可能过大，可能超过目标距离阈值，目标距离阈值可以为10km，当原始轨迹线路中相邻的两个原始轨迹点之间的距离大于目标距离阈值时，可以使用大圆航线算法，在相邻的原始轨迹点之间插入虚拟轨迹点，虚拟轨迹点的数量可以预先设定，也可以根据原始轨迹点之间的距离来确定，此处不进行限定。

在插入了虚拟轨迹点之后，再将原始轨迹点和虚拟轨迹点取并集，就将原始轨迹线路转化为候选轨迹线路了。

比如在航海场景中，可以从数据库中加载所有原始轨迹线路Route＝{r₁,r₂,…,r_i,…,r_n}，i,n∈N,0＜i＜n，n是原始轨迹线路的数量，r_i是使用某艘船舶的真实航行轨迹生成的航线，它包含船舶标识MMSI、船舶类型st、始发港p_begin、始发港离港时间atd、目的港p_end和目的港到达时间ata。令全球港口集合为Port，则p_begin,p_end∈Port。

以p_end对原始轨迹线路分组，令得到的原始轨迹线路的集合为Route_j＝{r₁,r₂,…,r_k,…,r_m}，j,k,m∈N,0＜j＜n,0＜k＜m，m为该分组Route_j中的原始轨迹线路的数量。

对于Route_j中的任一原始轨迹线路r_k，令该原始轨迹线路上的关键点集合为Pos，且Pos＝{p₁,p₂,…,p_i,…,p_l}，i,l∈N,0＜i＜l，l为原始轨迹线路r_k上的关键点数量。

从p₁开始每两个点计算它们之间的距离，当距离大于一定值时，使用大圆航线算法在两个点之间等距离插入点，这个步骤实现了航线轨迹点的密集化，记新的关键点集合为P，且P＝｛p₁,p₂,…,p_i,…,p_q}，i,q∈N,0＜i＜q，q为P中点的数量，可知l≤q，这样就得到了候选轨迹线路。

在一些实施例中，上述步骤120、基于候选轨迹线路上的所有轨迹点的位置信息，确定候选轨迹线路对应的多个位置网格，包括：基于候选轨迹线路上的所有轨迹点的位置信息，将与每一轨迹点之间的距离在目标半径阈值范围内的位置网格作为候选轨迹线路对应的多个位置网格。

可以理解的是，候选轨迹线路有多个轨迹点，此处设置目标轨迹阈值，比如可以为1km，可以以候选轨迹线路上的轨迹点为基础，找到与轨迹点距离为目标半径阈值范围内的位置网格，将这些位置网格作为候选轨迹线路对应的位置网格。

比如在航海场景中，对于候选轨迹线路的轨迹点集合P，对每个轨迹点p_i设置一个目标半径阈值r_i，通过r_i计算轨迹点p_i的外接矩形rect_i，获取外接矩形的顶点V＝{v₁,v₂,v₃,v₄}，基于V获取最大经度lon_max，最小经度lon_min，最大纬度lat_max，最小纬度lat_min。

按固定跨度span在经纬度表示的地球上划分位置网格Grid＝{g₁,…,g_i,…,g_n}，i,n∈N,0＜i＜n，n是位置网格的数量，则任意位置网格g_i设计一个可表示该位置网格的位置，假设在Grid上统一取g_i左上顶点的位置表示该位置网格，则g_i可表示为(tl_lon100_i,tl_lat100_i)，上述位置网格的跨度为0.01°经度，0.01°纬度。

对于任意位置(lon_j,lat_j)，假设该位置的单位为1°经度，1°纬度的浮点数，定义lon100_j＝lon_j*100，lon100_j取整后记为n_lon100_j，lat100_j＝lat_j*100，lat100_j取整后记为n_lat100_j。

设该位置位于位置网格g_j，且g_j左上顶点的坐标为(tl_lon100_j,tl_lat100_j)，若n_lon100_j＜0，且lon100_j有非0有效值，则tl_lon100_j＝n_lon100_j-1，否则tl_lon100_j＝n_lon100_j。若n_lat100_j＞0且lat100_j有非0有效值，则tl_lat100_j＝n_lat100_j+1，否则tl_lat100_j＝n_lat100_j。

记上述根据位置获取位置网格的方法为位置提升算法，记为promote。使用promote方法，根据上面的固定span可以计算与点p_i的外接矩形rect_i相交的所有位置网格Grid_i＝{g₁,…,g_k,…,g_m}，k,m∈N,0＜k＜m，m为与rect_i相交的网格数量。

上述Grid_i表示点p_i附近的位置网格。遍历P的每一个点可以得出一条候选轨迹线路r_k经过的位置网格集合G＝{g₁,…,g_i,…,g_q}，i,q∈N,0＜i＜q，q表示航线r_k附近的位置网格数量。

对于到达同一个目的港port_i的所有候选轨迹线路，应用上述步骤可以生成位置网格集合GP＝{g₁,…,g_i,…,g_s}，i,s∈N,0＜i＜s，s表示所有到达port_i的候选轨迹线路的位置网格数量。

对于位置网格集合GP中任一位置网格g_i，可能有若干候选轨迹线路在附近，设位置网格g_i附近的候选轨迹线路集合为R_i＝{r₁,…,r_j,…,r_t}，j,t∈N,0＜j＜t，t为g_i附近的候选轨迹线路数量。对于任一候选轨迹线路r_i均记录有船舶标识MMSI、船舶类型ST、船公司COMP、船长LEN、船宽W、始发港PB、始发港离开时间ATD、目的港PE以及目的港到港时间ATA等数据。

按照上述任一特征对候选轨迹线路分类，可得到该特征各个取值下的候选轨迹线路集合。比如按照船公司COMP分类，且船公司集合comp＝{ca,cb,cc,cd}，则可从R_i中提取候选轨迹线路集合RCA_i，RCB_i，RCC_i，RCD_i，他们分别是船公司ca，cb，cc，cd通过网格g_i的候选轨迹线路集合。很明显

设RCA_i≠Φ，且RCA_i＝{r₁,…,r_j,…,r_x}，j,x∈N,0＜j＜x，x为经过网格g_i的船公司ca的候选轨迹线路数量。如上可以根据MMSI、ST、PB等进行候选轨迹线路分组。

在一些实施例中，上述步骤140、从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路，包括：确定每个候选轨迹线路从位置网格到目标地点的里程参数；从多个候选轨迹线路筛选出里程参数最小的候选轨迹线路，作为每个位置网格对应的参考轨迹线路。

可以理解的是，里程参数可以用于表示候选轨迹线路的剩余里程。可以从该位置网格对应的候选轨迹线路中挑选出剩余里程最短的那一条作为参考轨迹线路，剩余里程指的是以该位置网格为起点，目标地点为终点，以候选轨迹线路为行驶轨迹所计算出来的位移长度。

在一些实施例中，上述步骤140、确定每个候选轨迹线路上的处于位置网格之后的最近轨迹点与位置网格的距离参数；从多个候选轨迹线路筛选出距离参数最小的候选轨迹线路，作为每个位置网格对应的参考轨迹线路；基于位置网格与参考轨迹线路上的轨迹点构成的角度以及目标角度阈值，确定参考轨迹线路上的平滑接入点。

可以理解的是，距离参数为从位置网格出发，到候选轨迹线路上处于位置网格之后的距离位置网格最近的轨迹点之间的距离值，该轨迹点可以为真实的轨迹点，也就是并非密集化处理给出的虚拟轨迹点，可以得到每个候选轨迹线路所对应的距离参数，将距离参数最小的那个候选轨迹线路作为参考轨迹线路。

在确定参考轨迹线路后，位置网格需要平滑接入到参考轨迹线路，此时可以基于平滑接入算法来得到参考轨迹线路上的平滑接入点。

平滑接入算法的过程可以为：将位置网格与参考轨迹线路上的平滑接入点以及平滑接入点的下一轨迹点所构成的角度与目标角度阈值进行比较，将满足目标角度阈值的轨迹点作为平滑接入点。

比如在航海场景中，对于非空集合RCA_i，设位置网格g_i的中心点坐标为(lon,lat)，对于RCA_i中任一航线r_j，假设密集化前位于位置网格g_i之后的下一个轨迹点为(r_lon_j,r_lat_j)，计算点(lon,lat)与点(r_lon_j,r_lat_j)之间的距离d_j。对RCA_i中所有候选轨迹线路计算上述距离后可得到距离集合Dist＝{d₁,…,d_j,…,d_x}。从Dist中选择一条距离d_j最小的航线作为该位置网格到达目的港的适配航线r_fit，也就是参考轨迹线路。

以上述方法可以确定位置网格g_i所有分组下到达同一目的港的参考轨迹线路。

下面是确定r_fit的过程，该过程计算(lon,lat)与(r_lon_j,r_lat_j)的距离时，选取的位置点(r_lon_j,r_lat_j)需要考虑接入后的平滑性，即要求以(lon,lat)为起点，(r_lon_j,r_lat_j)为中点，(r_lon_j+1,r_lat_j+1)为末点的角α要大于阈值α_threshold，这个过程由平滑介入算法完成。

记录的r_fit信息包含航线标识、网格g_i到目的港的距离、网格g_i的标识、平滑接入点索引j和目的港标识等。将这样的数据保存在数据库中，设这个表为table_grid，同时设保存千万级航线的表为table_route。

从table_grid和table_route中分别加载位置网格和参考轨迹线路的数据，使用平衡二叉树结构建立内存数据模型，分别记为和map_grid map_route。map_grid的键设计为元组(grid_index,pid,group,type)，其中grid_index为位置网格索引，pid为目标地点标识，group为组别(如MMSI，COMP等)，type是相应组别下的类型(如船公司组别下的公司ca)，记上述元组为tp。map_route的键设计为route_id，即参考轨迹线路的标识。

在一些实施例中，上述步骤140、从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路，包括：基于目标对象的类型、目标对象的大小、季节信息以及目标对象的单位信息中的至少一个，从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路。

可以理解的是，此处还可以根据目标对象的类型、目标对象的大小、季节信息和目标对象的单位信息，来确定参考轨迹线路，目标对象的单位信息用于表示目标对象的商业归属，季节信息可以表示本次行驶任务所处的季节，比如可以为春季、夏季、秋季或者冬季，目标对象的大小指的是目标对象的形状尺寸，此处是综合考虑以上因素，来判断哪一候选轨迹线路是该位置网格所对应的最适宜的路线，作为参考轨迹线路，这样能够进一步提升轨迹线路规划的准确率。

在一些实施例中，该路径规划方法还包括：基于目标对象的速度信息、目标对象的位置信息以及目标轨迹线路，确定目标对象到达目标地点的时间信息。

可以理解的是，在确定了目标轨迹线路之后，可以确定目标对象的行驶起点，即目标对象的位置信息，而目标轨迹线路的终点是确定的，就是目标地点，那么就能够知道目标对象将要行驶的里程，此时结合目标对象的速度信息，就能够计算出目标对象沿着目标轨迹线路行驶的耗时，结合目标对象的当前时间信息，就能够确定目标对象到达目标地点的时间信息。

比如在航海场景下，服务器在接收到客户端实时发送的航路规划请求后，设船舶的位置信息为(lon,lat)，使用位置提升算法promote获取该位置信息对应的位置网格gi，若gi不为空，则构建元组tp。

预设客户请求中该船舶到达的港口为p_x，服务分析后发现使用船公司类别可为该船舶规划质量高的路径，且客户请求中的船舶所属船公司为ca，则可构建键值tp_tmp＝(gi,p_x,COMP,ca)，使用tp_tmp去map_grid中可查询到船位到目的港的剩余距离dist，平滑接入点索引p_idx，航线标识r_id，使用r_id去map_grid中获取航线轨迹Track＝{p₁,…,p_i,…,p_n}，i,n∈N,0＜i＜n，n表示该航线的轨迹点数。

根据p_idx从Track中获取剩余轨迹Path＝{p_{p_idx},…,p_j,…,p_n}，p_idx,j∈N,0＜p_idx≤j≤n。

结合船舶统计航速或瞬时航速sog可以计算船舶预计到达目的港p_x的时间ETA。上述过程通过查询和简单计算即可完成船舶的航路规划。

下面对本发明提供的路径规划系统进行描述，下文描述的路径规划系统与上文描述的路径规划方法可相互对应参照。

如图3所示，本发明还提供一种路径规划系统，该路径规划系统包括：第一获取模块310、第一确定模块320、第二确定模块330、筛选模块340、第二获取模块350和第三确定模块360。

第一获取模块310，用于获取终点为目标地点的多个候选轨迹线路。

第一确定模块320，用于基于候选轨迹线路上的所有轨迹点的位置信息，确定候选轨迹线路对应的多个位置网格，位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格。

第二确定模块330，用于基于位置网格与候选轨迹线路的对应关系，确定每一位置网格对应的多个候选轨迹线路。

筛选模块340，用于从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路。

第二获取模块350，用于获取目标对象的位置信息。

第三确定模块360，用于基于目标对象的位置信息以及每个位置网格对应的参考轨迹线路，确定目标轨迹线路。

图4示例了一种电子设备的实体结构示意图，如图4所示，该电子设备可以包括：处理器(processor)410、通信接口(Communications Interface)420、存储器(memory)430和通信总线440，其中，处理器410，通信接口420，存储器430通过通信总线440完成相互间的通信。处理器410可以调用存储器430中的逻辑指令，以执行路径规划方法，该方法包括：获取终点为目标地点的多个候选轨迹线路；基于候选轨迹线路上的所有轨迹点的位置信息，确定候选轨迹线路对应的多个位置网格，位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格；基于位置网格与候选轨迹线路的对应关系，确定每一位置网格对应的多个候选轨迹线路；从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路；获取目标对象的位置信息；基于目标对象的位置信息以及每个位置网格对应的参考轨迹线路，确定目标轨迹线路。

此外，上述的存储器430中的逻辑指令可以通过软件功能单元的形式实现并作为独立的产品销售或使用时，可以存储在一个计算机可读取存储介质中。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分或者该技术方案的部分可以以软件产品的形式体现出来，该计算机软件产品存储在一个存储介质中，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例所述方法的全部或部分步骤。而前述的存储介质包括：U盘、移动硬盘、只读存储器(ROM，Read-Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁碟或者光盘等各种可以存储程序代码的介质。

另一方面，本发明还提供一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，计算机能够执行上述各方法所提供的路径规划方法，该方法包括：获取终点为目标地点的多个候选轨迹线路；基于候选轨迹线路上的所有轨迹点的位置信息，确定候选轨迹线路对应的多个位置网格，位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格；基于位置网格与候选轨迹线路的对应关系，确定每一位置网格对应的多个候选轨迹线路；从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路；获取目标对象的位置信息；基于目标对象的位置信息以及每个位置网格对应的参考轨迹线路，确定目标轨迹线路。

又一方面，本发明还提供一种非暂态计算机可读存储介质，其上存储有计算机程序，该计算机程序被处理器执行时实现以执行上述各提供的路径规划方法，该方法包括：获取终点为目标地点的多个候选轨迹线路；基于候选轨迹线路上的所有轨迹点的位置信息，确定候选轨迹线路对应的多个位置网格，位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格；基于位置网格与候选轨迹线路的对应关系，确定每一位置网格对应的多个候选轨迹线路；从多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个位置网格对应的参考轨迹线路；获取目标对象的位置信息；基于目标对象的位置信息以及每个位置网格对应的参考轨迹线路，确定目标轨迹线路。

以上所描述的系统实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

Claims (10)

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

获取终点为目标地点的多个候选轨迹线路；

基于所述候选轨迹线路上的所有轨迹点的位置信息，确定所述候选轨迹线路对应的多个位置网格，所述位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格；

基于所述位置网格与所述候选轨迹线路的对应关系，确定每一所述位置网格对应的多个候选轨迹线路；

从每一所述位置网格对应的多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路；

获取目标对象的位置信息；

基于所述目标对象的位置信息以及每个所述位置网格对应的参考轨迹线路，确定目标轨迹线路。

2.根据权利要求1所述的路径规划方法，其特征在于，所述获取终点为目标地点的多个候选轨迹线路，包括：

获取终点为目标地点的多个原始轨迹线路；

若所述原始轨迹线路中相邻的两个原始轨迹点之间的距离大于目标距离阈值时，基于大圆航线算法，在所述相邻的两个原始轨迹点之间插入虚拟轨迹点；

基于所述原始轨迹点和所述虚拟轨迹点，得到多个所述候选轨迹线路。

3.根据权利要求1所述的路径规划方法，其特征在于，所述基于所述候选轨迹线路上的所有轨迹点的位置信息，确定所述候选轨迹线路对应的多个位置网格，包括：

基于所述候选轨迹线路上的所有轨迹点的位置信息，将与每一轨迹点之间的距离在目标半径阈值范围内的位置网格作为所述候选轨迹线路对应的多个位置网格。

4.根据权利要求1所述的路径规划方法，其特征在于，所述从每一所述位置网格对应的多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路，包括：

确定每一所述位置网格对应的所述候选轨迹线路从所述位置网格到目标地点的里程参数；

从每一所述位置网格对应的多个候选轨迹线路筛选出所述里程参数最小的候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路。

5.根据权利要求1所述的路径规划方法，其特征在于，所述从每一所述位置网格对应的多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路，包括：

确定每一所述位置网格对应的所述候选轨迹线路上的处于所述位置网格之后的最近轨迹点与所述位置网格的距离参数；

从每一所述位置网格对应的多个候选轨迹线路筛选出所述距离参数最小的候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路；

基于所述位置网格与所述参考轨迹线路上的轨迹点构成的角度以及目标角度阈值，确定所述参考轨迹线路上的平滑接入点。

6.根据权利要求1所述的路径规划方法，其特征在于，所述从每一所述位置网格对应的多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路，包括：

基于目标对象的类型、目标对象的大小、季节信息以及目标对象的单位信息中的至少一个，从每一所述位置网格对应的多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路。

7.根据权利要求1至6中任一项所述的路径规划方法，其特征在于，还包括：

基于所述目标对象的速度信息、所述目标对象的位置信息以及所述目标轨迹线路，确定所述目标对象到达目标地点的时间信息。

8.一种路径规划系统，其特征在于，包括：

第一获取模块，用于获取终点为目标地点的多个候选轨迹线路；

第一确定模块，用于基于所述候选轨迹线路上的所有轨迹点的位置信息，确定所述候选轨迹线路对应的多个位置网格，所述位置网格为将世界坐标系以目标边长划分出的多个相同的矩形网格；

第二确定模块，用于基于所述位置网格与所述候选轨迹线路的对应关系，确定每一所述位置网格对应的多个候选轨迹线路；

筛选模块，用于从每一所述位置网格对应的多个候选轨迹线路中筛选出一个候选轨迹线路，作为每个所述位置网格对应的参考轨迹线路；

第二获取模块，用于获取目标对象的位置信息；

第三确定模块，用于基于所述目标对象的位置信息以及每个所述位置网格对应的参考轨迹线路，确定目标轨迹线路。

9.一种电子设备，包括存储器、处理器及存储在所述存储器上并可在所述处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1至7中任一项所述路径规划方法的步骤。

10.一种非暂态计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现如权利要求1至7中任一项所述路径规划方法的步骤。

Images