一种路径规划方法、装置和电子设备与流程

1.本技术涉及路径规划技术领域，特别是一种路径规划方法、装置和电子设备。


背景技术：

2.在路径规划的技术领域中，主流思想为采用基于dijkstra算法的分层(每层对应一个级别的剖分)精确计算。然而上述方法计算过程过于复杂，实际应用效率不高。若是用存储空间换计算时间，将所有可选地路径进行存储，再从中确定出最短路径，又需要过大的存储空间。示例性的，假设图g共有n个点，如果把所有可能的路径都存储起来，需要n的平方个路径的存储空间，当n的值很大时，往往对应了一个不可接受的内存容量。
3.因此，需要提供一种路径规划方法、装置和电子设备，以实现更高效，存储容量需求更小的路径规划。


技术实现要素：

4.鉴于上述问题，本技术实施例提供了一种路径规划方法、装置和电子设备，以便克服上述问题或者至少部分地解决上述问题。
5.本技术实施例的第一方面提供了一种路径规划方法，所述方法包括：
6.对路网进行剖分分层，得到多个层级以及每个层级的多个剖腔，每个所述剖腔中包括多个节点，所述节点分为剖腔边界点和剖腔内节点；所述多个节点中包括路径规划的起点和终点；
7.构造优先级队列，将所述起点的key值设为0，加入到所述优先级队列中；所述key值表示节点的预估价值；
8.执行待分析节点选择步骤：选择所述优先级队列中，key值最小的节点作为待分析节点出队，将所述待分析节点推入节点列表中；
9.执行下一节点确定步骤：根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，将所述下一节点放入所述优先级队列；利用所述下一节点，更新路径映射表；
10.重复所述待分析节点选择步骤和所述下一节点确定步骤，直至所述下一节点为所述终点；
11.从所述终点开始循环访问所述路径映射表，直至访问得到所述起点，获取从所述起点至所述终点的路径节点列表；
12.根据所述路径节点列表，得到最优路径。
13.在一种可能的实施方式中，所述根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，包括：
14.根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级低于所述终点所在层级的情况下，从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；
15.根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点与所述终点在同一层级的情况下，根据所述待分析节点和所述终点所在剖腔位置，确定所述下一节点。
16.在一种可能的实施方式中，所述在所述待分析节点与所述终点在同一层级的情况下，根据所述待分析节点和所述终点所在剖腔位置，确定所述下一节点，包括：
17.根据所述待分析节点和所述终点所在剖腔位置，确定在所述待分析节点所在层级更高一级的层级中，所述待分析节点与所述终点不在同一剖腔的情况下，从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；
18.在所述待分析节点所在层级更高一级的层级中，所述待分析节点与所述终点在同一剖腔的情况下，将所述终点确定为所述下一节点。
19.在一种可能的实施方式中，所述从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点，包括：
20.计算每个所述候选剖腔边界点的key值和路径价值，所述路径价值表示从所述起点至所述候选剖腔边界点的最短路径的预估价值；
21.计算所述待分析节点的路径价值；
22.在所述候选剖腔边界点满足如下公式的情况下，将所述候选剖腔边界点确定为所述下一节点，所述公式为：
23.所述待分析节点的路径价值+所述候选剖腔边界点的key值＜所述候选剖腔边界点的路径价值；
24.将所述下一节点的路径价值更新为：所述待分析节点的路径价值与所述候选剖腔边界点的key值的总和。
25.在一种可能的实施方式中，在对路网进行剖分分层之后，所述方法还包括：
26.将所有层级的存储策略设定为初始存储策略，所述初始存储策略为：不存储任何路径信息；
27.根据可使用的存储资源的大小，从高层级向低层级依次遍历，将多个层级的存储策略更新为第二存储策略，所述第二存储策略为：存储该层级的每个剖腔的所有剖腔边界点两两之间的路径信息；
28.在能够将所有层级的存储策略更新为所述第二存储策略的情况下，根据剩余的可使用的存储资源的大小，从高层级向低层级依次遍历，将多个层级的存储策略更新为第三存储策略，所述第三存储策略为：存储该层级的所有节点两两之间的路径信息。
29.在一种可能的实施方式中，所述根据所述路径节点列表，得到最优路径，包括：
30.根据所述路径节点列表中的节点顺序，设定其中任意在所述路径节点列表相邻的两个节点为第一节点和第二节点，所述第一节点所在层级为低层级，所述第二节点所在层级为更高一级的高层级；
31.确定所述第一节点和所述第二节点，在所述低层级中是否相邻；
32.在所述第一节点和所述第二节点在所述低层级中相邻的情况下，得到所述第一节点和所述第二节点之间的最短路径；
33.在所述第一节点和所述第二节点，在所述低层级中不相邻的情况下，根据所述低
层级的存储策略，确定是否存储有所述第一节点和所述第二节点之间的最短路径；
34.在所述低层级存储有所述第一节点和所述第二节点之间的最短路径的情况下，直接从存储数据中获取所述第一节点和所述第二节点之间的最短路径；
35.在所述低层级未存储有所述第一节点和所述第二节点之间的最短路径的情况下，利用最短路径算法计算得到所述第一节点和所述第二节点之间的最短路径。
36.在一种可能的实施方式中，根据所述路径节点列表，确定所述第一节点位于第三节点与所述第二节点中间，在确定所述第一节点和所述第二节点之间的最短路径之后，所述方法还包括：
37.确定所述第一节点和所述第二节点之间的最短路径经过的多个中间节点；
38.从所述多个中间节点中，确定出目标中间节点，所述目标中间节点为所述多个中间节点按照节点顺序排列时，最后一个与所述第一节点所在层级相同的节点；
39.将所述最短路径更新为所述目标中间节点与所述第二节点之间的路径；
40.重新计算所述第三节点与所述目标中间节点之间的路径。
41.在一种可能的实施方式中，所述根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，包括：
42.根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级高于所述终点所在层级，并且，在所述待分析节点所在层级更高一级的层级中，所述待分析节点和所述终点位于同一剖腔的情况下:
43.在所述待分析节点所在层级中，所述待分析节点和所述终点位于同一剖腔时，从所述待分析节点所在层级更低一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；
44.在所述待分析节点所在层级中，所述待分析节点和所述终点不位于同一剖腔时，从所述待分析节点所在层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；
45.根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级高于所述终点所在层级，并且，在所述待分析节点所在层级更高一级的层级中，所述待分析节点和所述终点不位于同一剖腔的情况下，在所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点。
46.本技术实施例第二方面提供了一种路径规划装置，所述装置包括：
47.分层模块，用于对路网进行剖分分层，得到多个层级以及每个层级的多个剖腔，每个所述剖腔中包括多个节点，所述节点分为剖腔边界点和剖腔内节点；所述多个节点中包括路径规划的起点和终点；
48.队列构造模块，用于构造优先级队列，将所述起点的key值设为0，加入到所述优先级队列中；所述key值表示节点的预估价值；
49.选择模块，用于执行待分析节点选择步骤：选择所述优先级队列中，key值最小的节点作为待分析节点出队，将所述待分析节点推入节点列表中；
50.下一节点确定模块，用于执行下一节点确定步骤：根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，将所述下一节点放入所述优先级队列；利用所述下一节点，更新路径映射表；
51.重复模块，用于重复所述待分析节点选择步骤和所述下一节点确定步骤，直至所述下一节点为所述终点；
52.路径节点列表获取模块，用于从所述终点开始循环访问所述路径映射表，直至访问得到所述起点，获取从所述起点至所述终点的路径节点列表；
53.最优路径确定模块，用于根据所述路径节点列表，得到最优路径。
54.本技术实施例第三方面提供了一种电子设备，包括存储器、处理器及存储在所述存储器上的计算机程序，所述处理器执行所述计算机程序以实现本技术实施例第一方面任一项所述的路径规划方法中的步骤。
55.本技术实施例提供了一种路径规划方法、装置和电子设备，所述方法包括：对路网进行剖分分层，得到多个层级以及每个层级的多个剖腔，每个所述剖腔中包括多个节点，所述节点分为剖腔边界点和剖腔内节点；所述多个节点中包括路径规划的起点和终点；构造优先级队列，将所述起点的key值设为0，加入到所述优先级队列中；所述key值表示节点的预估价值；选择所述优先级队列中，key值最小的节点作为待分析节点出队，将所述待分析节点u推入节点列表中；执行下一节点确定步骤：根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，将所述下一节点放入所述优先级队列；利用所述下一节点，更新路径映射表；重复所述待分析节点选择步骤和所述下一节点确定步骤，直至所述下一节点为所述终点；从所述终点开始循环访问所述路径映射表，直至访问得到所述起点，获取从所述起点至所述终点的路径节点列表；根据所述路径节点列表，得到最优路径。本技术实施例通过按照节点的优先级，根据当前的节点和终点的位置信息，确定下一节点，得到起点至终点中的多个节点的信息，生成对应的路径节点列表，最后根据该路径节点列表生成最优路径，实现了快速高效地确定最优路径。相比于直接遍历所有路径的方法，本技术实施例通过剖分分层，先确定起点至终点中经过的中间节点，再确定最优路径，节省了存储空间，提高了计算效率。
附图说明
56.为了更清楚地说明本技术实施例的技术方案，下面将对本技术实施例的描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本技术的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。
57.图1是本技术实施例提供的一种路径规划方法的步骤流程图；
58.图2是本技术实施例提供的一种节点的分布示意图；
59.图3是本技术实施例提供的一种最优路径规划步骤流程图；
60.图4是本技术实施例所提供的一种路径规划装置的分布示意图；
61.图5是本技术实施例所提供的一种电子设备的结构示意图。
具体实施方式
62.下面将结合本技术实施例中的附图更详细地描述本技术的示例性实施例。虽然附图中显示了本技术的示例性实施例，然而应当理解，可以以各种形式实现本技术而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了能够更透彻地理解本技术，并且能
够将本技术的范围完整的传达给本领域的技术人员。
63.在相关技术中，主流的路径规划算法是可定制路径规划算法(customizable route planning，crp)，其主流思想为基于dijkstra算法的分层(每层对应一个级别的剖分)精确计算。然而，上述方法计算过程过于复杂，实际应用效率不高，实际应用场景需要更快的计算方法。若是用存储空间换计算时间，将所有可选地路径进行存储，再从中确定出最短路径，又需要过大的存储空间。示例性的，假设图g共有n个点，如果把所有可能的路径都存储起来，需要n的平方个路径的存储空间，当n的值很大时，往往对应了一个不可接受的内存容量。
64.此外，路径规划的另一个可行的思路是启发式路径寻优，其代表算法是著名的a*算法，在大多数情况下它能够以远少于dijkstra算法的步骤找到相对的最优解。不同于dijkstra算法的同优先级遍历，a*算法在寻找下一个探索点时根据与目标相关联的启发式规则为每一个待探索点分配了不同的优先级，从而使得直观上距离目标更近的那些点相对更容易的被优先计算。
65.然而上述方法，crp算法计算步骤过于繁杂，或者所需存储容量需求过大，a*算法在需要为每一个待探索点分配优先级，在实际应用中需要计算的待探索点往往数量过多，导致整个计算过程所需时间较长。
66.为改善相关技术，本技术实施例提供了一种路径规划方法、装置和电子设备，为提高路径规划效率，以较小的计算资源和存储容量，获取最优路径。下面结合附图，通过一些实施例及其应用场景对本技术实施例提供的一种路径规划方法、装置和电子设备进行详细地说明。
67.本技术实施例第一方面提供了一种路径规划方法，参照图1，图1示出了一种路径规划方法的步骤流程图，如图1所示，所述方法包括：
68.步骤s101，对路网进行剖分分层，得到多个层级以及每个层级的多个剖腔，每个所述剖腔中包括多个节点，所述节点分为剖腔边界点和剖腔内节点；所述多个节点中包括路径规划的起点和终点。
69.其中，路网表示在一定区域内，有所有道路组成的交通体系，包含整个区域地图的路径信息。对路网进行剖分分层，在具体实施时，可以利用crp算法对路网进行剖分分层，具体的分层方法在本实施例中不进行限制。
70.通过剖分分层，可以得到多个层级，与地图的层级相似，每个层级表示不同的比例尺的地图。每个层级包括多个剖腔，一个剖腔表示一个子区域，示例性的，成都市地图作为一个层级，其中包括武侯区、锦江区和高新区，每个区作为一个剖腔，多个剖腔彼此相邻共同组成了一个层级。每个剖腔中包括多个节点，该剖腔的多个节点中，位于该剖腔内部的节点为剖腔内节点，位于该剖腔边界的节点为剖腔边界点。多个节点中包括路径规划的起点和终点。对于每个节点，可能同时属于一个或多个层级，在后文中所指的待分析节点的层级均代指该待分析节点所属的最高的层级。设路径规划的起点位于最低层级，路径规划的终点为位于最高层级的剖腔边界点。
71.在一种可能的实施方式中，在对路网进行剖分分层之后，所述方法还包括：
72.步骤s201，将所有层级的存储策略设定为初始存储策略，所述初始存储策略为：不存储任何路径信息；
73.步骤s202，根据可使用的存储资源的大小，从高层级向低层级依次遍历，将多个层级的存储策略更新为第二存储策略，所述第二存储策略为：存储该层级的每个剖腔的所有剖腔边界点两两之间的路径信息；
74.步骤s203，在能够将所有层级的存储策略更新为所述第二存储策略的情况下，根据剩余的可使用的存储资源的大小，从高层级向低层级依次遍历，将多个层级的存储策略更新为第三存储策略，所述第三存储策略为：存储该层级的所有节点两两之间的路径信息。
75.在相关技术中，利用crp算法进行剖分分层后，为了尽可能的提高最优路径计算效率，节省计算时间，会将该路网中所有可能的路径预先进行存储，从而直接从存储的路径中去确定最优路径。然而该方法需要大量的存储资源，在路网覆盖面积较大，节点较多的情况下，实际的存储资源往往无法满足需求。
76.本实施例提出，根据不同的层级的可用存储资源，设定不同的存储策略。在完成剖分分层后，对于其中任一层级，可采用如下三种不同的存储策略：1)初始存储策略：不存储任何路径信息。2)第二存储策略：存储本层级内的每个剖腔的两两剖腔边界点之间的路径信息。3)第三存储策略：存储本层级内的每个剖腔的所有节点两两之间的路径信息。
77.在具体实施时，先执行步骤s201，先设定每个层级都默认使用第一种策略，将所有层级的存储策略设定为初始存储策略，不存储任何路径信息。然后，执行步骤s202，从高层级向低层级依次遍历，根据可使用的存储资源的大小，将多个层级的存储策略更新为第二存储策略，第二存储策略为：存储该层级的每个剖腔的所有剖腔边界点两两之间的路径信息。示例性的，若一共有10个层级，有100m的存储资源，从高层级向低层级依次遍历，第10层级执行第二存储策略需要50m的存储资源，判断能够满足该存储资源，则将第10层级的存储策略更新为第二存储策略；第9层级需要30m，则对应地将第9层级的存储策略更新为第二存储策略；第8层级需要20m，则对应地将第8层级的存储策略更新为第二存储策略；第7层级需要10m，然而剩余存储资源为0，无法满足需求，所以将第7层级至第1层级的存储资源保持为初始存储策略。
78.然后执行步骤s203，在存储资源足够将所有层级的存储策略设定为第二存储策略的情况下，根据剩余的存储资源，再次从高层级向低层级依次遍历，将多个层级的存储策略更新为第三存储策略，所述第三存储策略为：存储该层级的所有节点两两之间的路径信息。示例性的，若一共有10个层级，将所有层级的存储策略设定为第二存储策略后，还剩余有100m的存储资源，从高层级向低层级依次遍历，第10层级将第二存储策略更新为第三存储策略，需要80m的存储资源，判断能够满足该存储资源，则将第10层级的存储策略更新为第三存储策略；将第9层级从第二存储策略更新为第三存储策略，需要50m，然而剩余存储资源为20m，无法满足需求，所以将第9层级至第1层级的存储资源保持为第二存储策略。
79.本技术实施例将存储策略分为初始存储策略、第二存储策略和第三存储策略，根据存储资源，灵活设定每个层级的存储策略，可以提高该路径规划方法的可用性，避免该方法受到存储资源的限制。
80.步骤s102，构造优先级队列，将所述起点的key值设为0，加入到所述优先级队列中；所述key值表示节点的预估价值。
81.参照图3，图3示出了一种最优路径规划步骤流程图，如图3所示，构造优先级队列u，该优先级队列中包括多个待探索节点，每个待探索节点有对应的key值，该key值表示节
点的预估价值，对应于优先级，key值越小，优先级越高。该key值可以通过对应的路径规划算法进行计算。具体的，可以利用a*算法中的公式f(n)＝g(n)+h(n)进行计算，在此算法中f(n)的大小表示key值。g(n)表示从待分析节点移动到该节点的移动代价，沿着到达该节点而生成的路径。h(n)表示从该节点移动到终点的估算成本，所以，f(n)或key值表示通过该节点的总代价或预估的总价值。示例性的，还可以采用a*算法计算key值。可以用dijkstra算法的启发式搜索，此时key值为g(n)在具体实施时，将起点的key值设为0，加入到优先级队列中(r如图3中的构造u，加入起点s，设起点s的key＝0)。
82.步骤s103，执行待分析节点选择步骤：选择所述优先级队列中，key值最小的节点作为待分析节点出队，将所述待分析节点推入节点列表中。
83.在具体实施时，在优先级队列非空时，从中选择key值最小的节点作为待分析节点出队，即从中选择优先级最高的一个节点作为待分析节点(如图3所示，在优先级队列u非空时，取出队节点u，将其作为待分析节点)。并且将该待分析节点推入节点列表中，所述节点列表用于存储待分析节点的节点信息，例如该节点的位置信息，key值信息等。由于在步骤s102中将起点加入到优先级队列中，且起点的key值为0，所以起点的优先级最高，一般情况下，会首先将起点作为第一个待分析节点出队。
84.步骤s104，执行下一节点确定步骤：根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，将所述下一节点放入所述优先级队列；利用所述下一节点，更新路径映射表。
85.在具体实施时，待分析节点的位置信息主要表示该待分析节点所在层级的信息，所在剖腔的信息，终点的位置信息主要表示该终点所在层级的信息和所在剖腔的信息。根据两者的信息确定出下一节点，具体的，可以利用a*算法，为每一个待探索点分配了不同的优先级，从而使得直观上距离目标更近的那些点相对更容易的被优先计算。所述下一节点，表示该最优路径在经过待分析节点后，所需要经过的下一个节点。利用该下一节点，更新路径映射表，该路径映射表用于表示该路径行驶方向或节点顺序，表示在最优路径中，行驶方向是由待分析节点向下一节点行驶。例如p(t)＝u，表示规划的路径是从u节点行驶至t节点的方向。
86.在具体实施时，待分析节点与终点之间的关系有三种可能：第一种情况是两个节点处在不同级别的不同剖腔；第二种情况是两个节点处在相同级别的不同剖腔；第三种情况是两个节点处在相同级别的相同剖腔。对于第一种情况，待分析节点需要利用a*算法的启发式策略向终点所在的层级边界靠拢，不断向本层级的边界进发，直到待分析节点与终点之间的关系符合第二种情况或第三种情况。对于第二种情况，待分析节点需要向终点所在的剖腔边界靠拢，直到与终点的关系符合第三种情况。对于第三种情况，待分析节点可以直接向终点靠拢即可。
87.步骤s105，重复所述待分析节点选择步骤和所述下一节点确定步骤，直至所述下一节点为所述终点。
88.由于在步骤s104中，将下一节点加入了优先级队列中，重新执行步骤s103，确定出了新的待分析节点(在一般情况下，在优先级队列中，刚加入该队列的“下一节点”的优先级最高，作为“待分析节点”出队)，从而根据新的待分析节点，重复执行步骤s104，得到新的下一节点，直至下一节点为终点，表示确定出了从起点至终点中的所有中间节点。
89.步骤s106，从所述终点开始循环访问所述路径映射表，直至访问得到所述起点，获取从所述起点至所述终点的路径节点列表。
90.在具体实施时，在步骤s105执行完成后，得到路径映射表，以及节点列表。路径映射表p中包括：从起点s至终点t的路径中的多个节点之间的节点映射方向。在最终的节点列表中包括所有待分析节点的节点信息(节点列表中的节点为每次执行步骤s103时，推入节点列表的待分析节点)。由于路径映射表只能存储节点与节点之间的映射方向信息，需要结合节点列表中的节点信息，生成路径节点列表(如图3所示，计算路径节点列表l)。该路径节点列表包括从起点s至终点t的路径中的多个路径节点的节点顺序和节点位置信息。
91.在具体实施时，顺序访问该路径节点列表l，获取任意两个相邻列表节点a和b，记其中层级最小的一个节点所在的层级为lm(如图3所示，获取a、b和lm)，如果lm不等于0，则递归获取a与b之间的中间节点，直至lm等于0为止。使得最终所得到的路径节点列表l中的节点都能显示在第0层级上。
92.步骤s107，根据所述路径节点列表，得到最优路径。
93.本技术实施例通过按照节点的优先级，根据当前的节点和终点的层级，剖腔的位置信息，确定下一节点，得到起点至终点中的多个节点的信息，生成对应的路径节点列表，最后根据该路径节点列表生成最优路径，实现了快速高效地确定最优路径。相比于直接遍历所有路径的方法，本技术实施例通过剖分分层，先确定起点至终点中经过的中间节点，再确定最优路径，节省了存储空间，提高了计算效率。
94.在一种可能的实施方式中，步骤s104，根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，还包括：
95.步骤s1041，根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级低于所述终点所在层级的情况下，从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点。
96.在具体实施时，如果待分析节点的层级低于终点的层级，为了向终点靠拢，需要向终点所在的层级靠拢，所以从待分析节点所在层级更高一级的层级中，待分析节点所在剖腔的多个候选剖腔边界点中，确定下一节点。其中，由于一个节点可能同时属于多个层级，所述终点所在层级表示终点作为剖腔边界点存在的层级。示例性的，待分析节点在第4层级，终点在第10层级(终点在第10层级中作为剖腔边界点存在)，为了向终点靠拢，从第5层级中，待分析节点所在剖腔的边界点中确定下一节点，从而使得该下一节点在层级上更加向终点靠近。具体的，可以利用a*算法计算多个候选剖腔边界点各自的key值，然后根据key值，从中确定下一节点。如图3所示，lu表示待分析节点的层级，lt表示终点t的层级，当lu小于lt时，遍历b(u，lu+1)，即从lu+1层级中遍历所有u所在剖腔的剖腔边界点，用a*算法计算每个点的key值，最终得到下一节点a，将该节点加入到优先级队列u中。
97.步骤s1042，根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点与所述终点在同一层级的情况下，根据所述待分析节点和所述终点所在剖腔位置，确定所述下一节点。
98.当待分析节点与终点位于同一层级，还可能存在两种情况：一种是待分析节点与终点不在同一剖腔，另一种是待分析节点与终点在同一剖腔。
99.在一种可能的实施方式中，所述步骤s1042，在所述待分析节点与所述终点在同一
层级的情况下，根据所述待分析节点和所述终点所在剖腔位置，确定所述下一节点，包括：
100.步骤s1042a，根据所述待分析节点和所述终点所在剖腔位置，确定在所述待分析节点所在层级更高一级的层级中，所述待分析节点与所述终点不在同一剖腔的情况下，从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点。
101.在具体实施时，待分析节点与终点在同一层级(如图3所示，lu＝lt时)，但在待分析节点所在层级更高一级的层级中，两个节点不在同一剖腔时(如图3所示，c(u，lt+1)不等于c(t，lt+1)时)，为了向终点靠拢，需要向终点所在的剖腔靠拢，所以从待分析节点所在层级更高一级的层级中，待分析节点所在剖腔的多个候选剖腔边界点中(如图3所示，遍历b(u，lu+1))，确定下一节点，即从lu+1层级中遍历所有u所在剖腔的剖腔边界点，用a*算法计算每个点的key值，最终得到下一节点a，将该节点加入到优先级队列u中。由于一个节点可能同时属于多个层级，这里的待分析节点的层级为该待分析节点所述的最高层级，当两者不在同一个剖腔时，需要在更高的一个层级中，从分析节点所在剖腔的多个候选剖腔边界点中，确定下一节点。示例性的，待分析节点在第9层级，终点在第9层级，两个节点在第10层级所在的剖腔不是同一个剖腔，为了向终点靠拢，从第10层级中，待分析节点所在剖腔的边界点中确定下一节点，从而使得该下一节点在第10层级上更加向终点靠近。具体的，可以利用a*算法计算多个候选剖腔边界点各自的key值，然后根据key值，从中确定下一节点。
102.步骤s1042b，在所述待分析节点所在层级更高一级的层级中，所述待分析节点与所述终点在同一剖腔的情况下，将所述终点确定为所述下一节点。
103.在具体实施时，在待分析节点所在层级更高一级的层级中，待分析节点与终点在同一层级，并且在同一剖腔时(如图3所示，c(u，lt+1)等于c(t，lt+1)时)，可以直接将终点确定为下一节点(如图3所示，设p(t)＝u)，表示起点与终点之间的节点均已经确定完全。示例性的，待分析节点在第9层级，终点在第9层级，两个节点在第10层级所在的剖腔是同一个剖腔，可以直接将下一节点确定为终点。
104.在一种可能的实施方式中，所述从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点，包括：
105.步骤s301，计算每个所述候选剖腔边界点的key值和路径价值，所述路径价值表示从所述起点至所述候选剖腔边界点的最短路径的预估价值。
106.在具体实施时，可以利用双向a*算法利用候选剖腔边界点a的key值和路径价值g(a)。其中g(a)表示的是从起点至该候选剖腔边界点a的最短路径的预估价值或代价。
107.步骤s302，计算所述待分析节点的路径价值；
108.在具体实施时，利用与步骤s301同样的方法(双向a*算法)，计算得到待分析节点u的路径价值g(u)，该路径价值表示起点至待分析节点u的最短路径的价值。
109.步骤s303，在所述候选剖腔边界点满足如下公式的情况下，将所述候选剖腔边界点确定为所述下一节点，所述公式为：
110.所述待分析节点的路径价值+所述候选剖腔边界点的key值＜所述候选剖腔边界点的路径价值；
111.参照图2，图2示出了一种节点的分布示意图，如图2所示，箭头为路径方向。其中，如图3所示，当g(u)+key＜g(a)时，g(u)表示起点s至待分析节点u的路径l1的代价或路径价
值，key表示的是待分析节点u至候选剖腔边界点a的代价或价值，表示起点s至候选剖腔边界点a的最短路径l2的代价或路径价值。由此，当起点s至待分析节点u再至候选剖腔边界点a的路径的总代价小于起点s至候选剖腔边界点a的总代价，表示候选剖腔边界点a在最优路径上。若所有的候选剖腔边界点均不满足该公式，则需要重新回到步骤s102。
112.步骤s304，将所述下一节点的路径价值更新为：所述待分析节点的路径价值与所述候选剖腔边界点的key值的总和。
113.此外，在确定出下一节点后，将下一节点的路径价值更新为：所述待分析节点的路径价值与所述候选剖腔边界点的key值的总和，即，g(a)＝g(u)+key。需要知道的是，待分析节点与下一节点表示最优路径中的关键节点，在两者之间还存在多个子节点。如图3所示，在确定下一节点后，获取a*路径，即可以利用a*算法计算从待分析节点u至下一节点a中的最短路径，或最短路径中经过的多个子节点：u-u
1-u2‑……‑uk-a。由此，本实施例利用双向a*算法计算key值和路径价值，从而从多个剖选剖腔边界点中，确定出下一节点，使得下一节点位于最优路径上，如图3所示，在确定下一节点后，获取a*路径，更新该节点的路径价值g(a)＝g(u)+key，更新路径映射表，即与待分析节点生成新的路径映射表。对应的，更新路径映射表为：p(a)＝uk，p(uk)＝u
k-1
，
…
，p(u1)＝u。在将该下一节点a加入到优先级队列u后，回到步骤s102。
114.在一种可能的实施方式中，所述步骤s104，根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，包括：
115.根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级高于所述终点所在层级，并且，在所述待分析节点所在层级更高一级的层级中，所述待分析节点和所述终点位于同一剖腔的情况下：
116.步骤s1043，在所述待分析节点所在层级中，所述待分析节点和所述终点位于同一剖腔时，从所述待分析节点所在层级更低一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点。
117.步骤s1044，在所述待分析节点所在层级中，所述待分析节点和所述终点不位于同一剖腔时，从所述待分析节点所在层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点。
118.在具体实施时，待分析节点u的层级高于终点t的层级时(如图3所示，lu大于lt时)，存在两种情况，一种是在更高一层级中，待分析节点u与终点t在同一剖腔中(如图3所示，c(u，lu+1)等于c(t，lu+1))；另一种是在更高一层级(lu+1)中，待分析节点与u终点t不在同一剖腔中(如图3所示，c(u，lu+1)不等于c(t，lu+1))。
119.在第一种情况下，还存在两种可能：一种可能是在待分析节点所在层级(lu)中，待分析节点u和终点t位于同一剖腔(如图3所示，c(u，lu)等于c(t，lu))；另外一种可能是在待分析节点所在层级(lu)中，待分析节点u和终点t没有位于同一剖腔(如图3所示，c(u，lu)不等于c(t，lu))。
120.在第一种可能中，为了向终点t靠拢，执行步骤s1043，向终点t所在的层级靠拢，所以从待分析节点所在层级(lu)更低一级的层级(用lu-1表示)中，待分析节点所在剖腔的多个候选剖腔边界点中(如图3所示，遍历b(u，lu-1))，确定下一节点。示例性的，待分析节点在第10层级，终点在第8层级，两个节点在第10层级所在的剖腔是同一个剖腔，为了向终点
靠拢，从第9层级中，待分析节点所在剖腔的边界点中确定下一节点，从而使得该下一节点在第9层级上更加向终点靠近。具体的，可以利用a*算法计算多个候选剖腔边界点各自的key值和各自对应的路径价值，然后根据公式：g(u)+key＜g(a)，从中确定下一节点a。
121.在第二种可能中，为了向终点t靠拢，执行步骤s1044，向终点t所在的剖腔靠拢，所以从待分析节点所在层级(lu)中，待分析节点所在剖腔的多个候选剖腔边界点中(如图3所示，遍历b(u，lu))，确定下一节点。示例性的，待分析节点在第10层级，终点在第8层级，两个节点在第10层级所在的剖腔不是同一个剖腔，为了向终点靠拢，从第10层级中，待分析节点所在剖腔的边界点中确定下一节点，从而使得该下一节点在第10层级上更加向终点靠近，使得两个节点在第10层级所在的剖腔为同一个剖腔。具体的，可以利用a*算法计算多个候选剖腔边界点各自的key值和各自对应的路径价值，然后根据公式：g(u)+key＜g(a)，从中确定下一节点a。
122.步骤s1045，根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级高于所述终点所在层级，并且，在所述待分析节点所在层级更高一级的层级中，所述待分析节点和所述终点不位于同一剖腔的情况下，在所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点。
123.在第二种情况(在更高一层级(lu+1)中，待分析节点与u终点t不在同一剖腔中)下，为了向终点t靠拢，执行步骤s1045。向终点t所在的层级靠拢，所以从待分析节点所在层级更高一级的层级中(lu+1)中，待分析节点所在剖腔的多个候选剖腔边界点中(如图3所示，遍历b(u，lu+1))，确定下一节点。示例性的，待分析节点在第10层级，终点在第8层级，两个节点在第10层级所在的剖腔不是同一个剖腔，为了向终点靠拢，从第11层级中，待分析节点所在剖腔的边界点中确定下一节点，使得两个节点在第11层级所在的剖腔为同一个剖腔。具体的，可以利用a*算法计算多个候选剖腔边界点各自的key值和各自对应的路径价值，然后根据公式：g(u)+key＜g(a)，从中确定下一节点a。
124.在一种可能的实施方式中，所述步骤s107，根据所述路径节点列表，得到最优路径，包括：
125.步骤s1071，根据所述路径节点列表中的节点顺序，设定其中任意在所述路径节点列表相邻的两个节点为第一节点和第二节点，所述第一节点所在层级为低层级，所述第二节点所在层级为更高一级的高层级。
126.在具体实施时，路径节点列表中包括了多个路径节点和所述多个路径节点的节点顺序。示例性的，路径节点列表p1可以表示为：起点s
→a→b→c→d→e→f→g→
终点t。对于该路径节点列表中的任意两个节点，若两个节点所在的层级(各自对应的最高层级)不同，则将所在层级更高的节点称为第二节点，所在层级更低的节点称为第一节点，两个节点之间往往还存在着多个子节点。示例性的，在b与c两个节点中，若b节点位于第7层级，c节点位于第8层级，则对应地将b节点作为第一节点，c节点作为第二节点。如图3所示，第一节点与第二节点对应a与b节点，两者中的低层级对应lm。
127.步骤s1072，确定所述第一节点和所述第二节点，在所述低层级中是否相邻。如图3所示，判断a与b在lm层级中是否相邻。
128.步骤s1073，在所述第一节点和所述第二节点在所述低层级中相邻的情况下，得到
所述第一节点和所述第二节点之间的最短路径。
129.对于两个节点在低层级直接相邻的情况下，表示两个节点距离很近，之间不存在多个子节点，可以直接获取两个节点之间的最短路径。
130.步骤s1074，在所述第一节点和所述第二节点，在所述低层级中不相邻的情况下，根据所述低层级的存储策略，确定是否存储有所述第一节点和所述第二节点之间的最短路径。
131.对于两个节点在低层级中不相邻的情况，需要根据在低层级中的存储策略，来确定最短路径。具体的，根据不同的层级的可用存储资源，设定不同的存储策略。在完成剖分分层后，对于其中任一层级，可采用如下三种不同的存储策略：1)初始存储策略：不存储任何路径信息。2)第二存储策略：存储本层级内的每个剖腔的两两剖腔边界点之间的路径信息。3)第三存储策略：存储本层级内的每个剖腔的所有节点两两之间的路径信息。
132.步骤s1075，在所述低层级存储有所述第一节点和所述第二节点之间的最短路径的情况下，直接从存储数据中获取所述第一节点和所述第二节点之间的最短路径。
133.所以，在该低层级为第3种存储策略时，预先存储有第一节点与第二节点之间的最短路径的信息，可以直接获取得到(如图3所示，在确定ab路径已存储时，直接读取存储路径)。在该低层级为第二存储策略时，当第一节点与第二节点为剖腔边界点的情况下，则预先存储有第一节点与第二节点之间的最短路径的信息，若第一节点与第二节点不是剖腔边界点，则没有预先存储有第一节点与第二节点之间的最短路径的信息，在该低层级为初始存储策略的情况下，同样无法直接获取得到第一节点与第二节点之间的最短路径。
134.步骤s1076，在所述低层级未存储有所述第一节点和所述第二节点之间的最短路径的情况下，利用最短路径算法计算得到所述第一节点和所述第二节点之间的最短路径。
135.当没有预先存储第一节点与第二节点之间的最短路径的情况下，可以利用最短路径算法来计算得到该路径。具体的，可以利用双向a*算法，来获取两个节点之间的最短路径。如图3所示，利用双向a*算法计算路径。
136.本实施例一方面根据对不同层级设定不同的存储策略，从而最大化地利用存储资源，灵活设置存储策略；另一方面，根据不同的存储策略，选择不同的获取最短路径的方法，充分利用存储资源对路径信息进行存储，在现有存储资源的基础上，尽可能的对路径信息进行存储，从而节省计算资源，提高路径规划效率。
137.在一种可能的实施方式中，所述第一节点位于第三节点与所述第二节点中间，在确定所述第一节点和所述第二节点之间的最短路径之后，所述方法还包括：
138.步骤s108，确定所述第一节点和所述第二节点之间的最短路径经过的多个中间节点。
139.在具体实施时，第一节点与第二节点之间还包括多个中间节点或者说是子节点。根据确定出的第一节点至第二节点的最短路径，可以确定出最短路径中的多个中间节点的节点顺序。示例性的，对于b与c两个节点，确定出最短路径l1，以及该路径上的多个中间节点：b
→
b1
→
b2
→
b3
→
b4
→
b5
→
b6
→
b7
→
c。
140.步骤s109，从所述多个中间节点中，确定出目标中间节点，所述目标中间节点为所述多个中间节点按照节点顺序排列时，最后一个与所述第一节点所在层级相同的节点。如图3所示，计算ak，当前路径为a-a
1-a2‑…‑
b，按顺序最后一个与a的层级相同的点为ak。
141.在第一节点与第二节点所在层级不同时，对于两个节点之间的多个中间节点，可能存在部分中间节点与第一节点的层级相同，一部分的中间节点与第二节点的层级相同。示例性的，对于b与c两个节点，确定出多个中间节点为：b
→
b1
→
b2
→
b3
→
b4
→
b5
→
b6
→
b7
→
c。其中，b1、b2、b3与b节点的层级相同为第7层级，剩余的b4、b5在第8层级，b6、b7与c节点的层级相同为第9节点。对应的，将b3确定为目标中间节点，b3是所有中间节点中最后一个与所述第一节点(b节点)所在层级相同的节点。
142.步骤s110，将所述最短路径更新为所述目标中间节点与所述第二节点之间的路径。
143.示例性的，对于b与c两个节点，原本确定出的最短路径为l1，即：b
→
b1
→
b2
→
b3
→
b4
→
b5
→
b6
→
b7
→
c。根据确定出的目标中间节点b3，将最短路径更新为l2，该路径为：b3
→
b4
→
b5
→
b6
→
b7
→
c。
144.步骤s111，重新计算所述第三节点与所述目标中间节点之间的路径。
145.在路径节点列表中，设第一节点位于第三节点与第二节点中间：第三节点
→
第一节点
→
第二节点。按照上述实施例所述的方法，可以知道按照节点顺序，节点所在的层级是逐渐向终点所在的层级靠近的，所以在该路径节点列表中，节点所在的层级是按照节点顺序逐渐升高的。示例性的，对于b与c两个节点，将原本的最短路径为l1(b
→
b1
→
b2
→
b3
→
b4
→
b5
→
b6
→
b7
→
c)更新为l2(b3
→
b4
→
b5
→
b6
→
b7
→
c)。b节点为第一节点，c节点为第二节点，按照路径节点列表：起点s
→a→b→c→d→e→f→g→
终点t，a节点为第三节点，对于b节点至b3节点的这一段路径则加入至a
→
b这一段路径，一并进行路径计算，即重新计算a节点至b3节点的最短路径。由于，b节点与b3节点的层级相同，在能够确定a节点至b节点的最短路径的情况下，则对应的，可以确定a节点至b3节点的最短路径。由于b3节点与b节点更加靠近终点，所以，可能a节点至b3节点之间存在更优的最短路径。
146.在具体实施时，如图3所示，修正前序路段。在得到修改正后的路段后，记录当前路段。重新根据路径节点列表l，获取另一对相邻节点，从而确定两个节点之间的最优路径。在所有节点之间的最优路径确定完成后，进行拼接，得到最终的从起点至终点的最优路径。由此，本技术实施例通过根据中间节点所在的层级，重新进行路段的划分，将一个层级的节点尽可能的在一条路段中进行规划，从而进一步确定当前所规划的路径为最优路径。
147.本技术实施例第二方面还提供了一种路径规划装置，参照图4，图4示出了一种路径规划装置的分布示意图，如图4所示，所述系统包括：
148.分层模块，用于对路网进行剖分分层，得到多个层级以及每个层级的多个剖腔，每个所述剖腔中包括多个节点，所述节点分为剖腔边界点和剖腔内节点；所述多个节点中包括路径规划的起点和终点；
149.队列构造模块，用于构造优先级队列，将所述起点的key值设为0，加入到所述优先级队列中；所述key值表示节点的预估价值；
150.选择模块，用于执行待分析节点选择步骤：选择所述优先级队列中，key值最小的节点作为待分析节点出队，将所述待分析节点推入节点列表中；
151.下一节点确定模块，用于执行下一节点确定步骤：根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，将所述下一节点放入所述优先级队列；利用所述下一节点，更新路径映射表；
152.重复模块，用于重复所述待分析节点选择步骤和所述下一节点确定步骤，直至所述下一节点为所述终点；
153.路径节点列表获取模块，用于从所述终点开始循环访问所述路径映射表，直至访问得到所述起点，获取从所述起点至所述终点的路径节点列表；
154.最优路径确定模块，用于根据所述路径节点列表，得到最优路径。
155.在一种可能的实施方式中，所述下一节点确定模块，包括：
156.第一确定子模块，用于根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级低于所述终点所在层级的情况下，从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；
157.第二确定子模块，用于根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点与所述终点在同一层级的情况下，根据所述待分析节点和所述终点所在剖腔位置，确定所述下一节点。
158.在一种可能的实施方式中，所述第二确定子模块，包括：
159.第一确定单元，用于根据所述待分析节点和所述终点所在剖腔位置，确定在所述待分析节点所在层级更高一级的层级中，所述待分析节点与所述终点不在同一剖腔的情况下，从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；
160.第二确定单元，用于在所述待分析节点所在层级更高一级的层级中，所述待分析节点与所述终点在同一剖腔的情况下，将所述终点确定为所述下一节点。
161.在一种可能的实施方式中，所述第一确定单元，包括：
162.预估价值计算子单元，用于计算每个所述候选剖腔边界点的key值和路径价值，所述路径价值表示从所述起点至所述候选剖腔边界点的最短路径的预估价值；
163.路径价值计算子单元，用于计算所述待分析节点的路径价值；
164.确定子单元，用于在所述候选剖腔边界点满足如下公式的情况下，将所述候选剖腔边界点确定为所述下一节点，所述公式为：
165.所述待分析节点的路径价值+所述候选剖腔边界点的key值＜所述候选剖腔边界点的路径价值；
166.更新子单元，用于将所述下一节点的路径价值更新为：所述待分析节点的路径价值与所述候选剖腔边界点的key值的总和。
167.在一种可能的实施方式中，所述装置还包括：
168.初始存储策略设定模块，用于将所有层级的存储策略设定为初始存储策略，所述初始存储策略为：不存储任何路径信息；
169.第二存储策略设定模块，用于根据可使用的存储资源的大小，从高层级向低层级依次遍历，将多个层级的存储策略更新为第二存储策略，所述第二存储策略为：存储该层级的每个剖腔的所有剖腔边界点两两之间的路径信息；
170.第三存储策略设定模块，用于在能够将所有层级的存储策略更新为所述第二存储策略的情况下，根据剩余的可使用的存储资源的大小，从高层级向低层级依次遍历，将多个层级的存储策略更新为第三存储策略，所述第三存储策略为：存储该层级的所有节点两两
之间的路径信息。
171.在一种可能的实施方式中，所述最优路径确定模块，包括：
172.节点确定子模块，用于根据所述路径节点列表中的节点顺序，设定其中任意在所述路径节点列表相邻的两个节点为第一节点和第二节点，所述第一节点所在层级为低层级，所述第二节点所在层级为更高一级的高层级；
173.相邻确定子模块，用于确定所述第一节点和所述第二节点，在所述低层级中是否相邻；
174.最短路径确定子模块，用于在所述第一节点和所述第二节点在所述低层级中相邻的情况下，得到所述第一节点和所述第二节点之间的最短路径；
175.存储确定子模块，用于在所述第一节点和所述第二节点，在所述低层级中不相邻的情况下，根据所述低层级的存储策略，确定是否存储有所述第一节点和所述第二节点之间的最短路径；
176.路径获取子模块，用于在所述低层级存储有所述第一节点和所述第二节点之间的最短路径的情况下，直接从存储数据中获取所述第一节点和所述第二节点之间的最短路径；
177.路径计算子模块，用于在所述低层级未存储有所述第一节点和所述第二节点之间的最短路径的情况下，利用最短路径算法计算得到所述第一节点和所述第二节点之间的最短路径。
178.在一种可能的实施方式中，根据所述路径节点列表，确定所述第一节点位于第三节点与所述第二节点中间，所述装置还包括：
179.中间节点确定模块，用于确定所述第一节点和所述第二节点之间的最短路径经过的多个中间节点；
180.目标中间节点确定模块，用于从所述多个中间节点中，确定出目标中间节点，所述目标中间节点为所述多个中间节点按照节点顺序排列时，最后一个与所述第一节点所在层级相同的节点；
181.路径更新模块，用于将所述最短路径更新为所述目标中间节点与所述第二节点之间的路径；
182.路径重计算模块，用于重新计算所述第三节点与所述目标中间节点之间的路径。
183.在一种可能的实施方式中，所述下一节点确定模块，包括：
184.根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级高于所述终点所在层级，并且，在所述待分析节点所在层级更高一级的层级中，所述待分析节点和所述终点位于同一剖腔的情况下:
185.第一下一节点确定子模块，用于在所述待分析节点所在层级中，所述待分析节点和所述终点位于同一剖腔时，从所述待分析节点所在层级更低一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；
186.第二下一节点确定子模块，用于在所述待分析节点所在层级中，所述待分析节点和所述终点不位于同一剖腔时，从所述待分析节点所在层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；
187.第三下一节点确定子模块，用于根据所述待分析节点的位置信息和所述终点的位
置信息，确定所述待分析节点所在层级高于所述终点所在层级，并且，在所述待分析节点所在层级更高一级的层级中，所述待分析节点和所述终点不位于同一剖腔的情况下，在所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点。
188.本发明实施例还提供了一种电子设备，参照图5，图5是本发明实施例提出的电子设备的结构示意图。如图5所示，电子设备100包括：存储器110和处理器120，存储器110与处理器120之间通过总线通信连接，存储器110中存储有计算机程序，该计算机程序可在处理器120上运行，进而实现本发明实施例公开的一种路径规划方法中的步骤。
189.本发明实施例还提供了一种计算机可读存储介质，其上存储有计算机程序/指令，该计算机程序/指令被处理器执行时实现本发明实施例公开的一种路径规划方法中的步骤。
190.本说明书中的各个实施例均采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似的部分互相参见即可。
191.本技术实施例是参照根据本技术实施例的方法、装置、电子设备和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理终端设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理终端设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
192.这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理终端设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
193.这些计算机程序指令也可装载到计算机或其他可编程数据处理终端设备上，使得在计算机或其他可编程终端设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程终端设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
194.尽管已描述了本技术实施例的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本技术实施例范围的所有变更和修改。
195.最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设备所固有的要素。在没有更多限制的情况下，由语句“包括一个
……”
限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的相同要素。
196.以上对本技术所提供的一种路径规划方法、装置和电子设备，进行了详细介绍，本
文中应用了具体个例对本技术的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本技术的方法及其核心思想；同时，对于本领域的一般技术人员，依据本技术的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本技术的限制。

技术特征：
1.一种路径规划方法，其特征在于，所述方法包括：对路网进行剖分分层，得到多个层级以及每个层级的多个剖腔，每个所述剖腔中包括多个节点，所述节点分为剖腔边界点和剖腔内节点；所述多个节点中包括路径规划的起点和终点；构造优先级队列，将所述起点的key值设为0，加入到所述优先级队列中；所述key值表示节点的预估价值；执行待分析节点选择步骤：选择所述优先级队列中，key值最小的节点作为待分析节点出队，将所述待分析节点推入节点列表中；执行下一节点确定步骤：根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，将所述下一节点放入所述优先级队列；利用所述下一节点，更新路径映射表；重复所述待分析节点选择步骤和所述下一节点确定步骤，直至所述下一节点为所述终点；从所述终点开始循环访问所述路径映射表，直至访问得到所述起点，获取从所述起点至所述终点的路径节点列表；根据所述路径节点列表，得到最优路径。2.根据权利要求1所述的路径规划方法，其特征在于，所述根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，包括：根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级低于所述终点所在层级的情况下，从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点与所述终点在同一层级的情况下，根据所述待分析节点和所述终点所在剖腔位置，确定所述下一节点。3.根据权利要求2所述的路径规划方法，其特征在于，所述在所述待分析节点与所述终点在同一层级的情况下，根据所述待分析节点和所述终点所在剖腔位置，确定所述下一节点，包括：根据所述待分析节点和所述终点所在剖腔位置，确定在所述待分析节点所在层级更高一级的层级中，所述待分析节点与所述终点不在同一剖腔的情况下，从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；在所述待分析节点所在层级更高一级的层级中，所述待分析节点与所述终点在同一剖腔的情况下，将所述终点确定为所述下一节点。4.根据权利要求2或3所述的路径规划方法，其特征在于，所述从所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点，包括：计算每个所述候选剖腔边界点的key值和路径价值，所述路径价值表示从所述起点至所述候选剖腔边界点的最短路径的预估价值；计算所述待分析节点的路径价值；在所述候选剖腔边界点满足如下公式的情况下，将所述候选剖腔边界点确定为所述下
一节点，所述公式为：所述待分析节点的路径价值+所述候选剖腔边界点的key值＜所述候选剖腔边界点的路径价值；将所述下一节点的路径价值更新为：所述待分析节点的路径价值与所述候选剖腔边界点的key值的总和。5.根据权利要求1所述的路径规划方法，其特征在于，在对路网进行剖分分层之后，所述方法还包括：将所有层级的存储策略设定为初始存储策略，所述初始存储策略为：不存储任何路径信息；根据可使用的存储资源的大小，从高层级向低层级依次遍历，将多个层级的存储策略更新为第二存储策略，所述第二存储策略为：存储该层级的每个剖腔的所有剖腔边界点两两之间的路径信息；在能够将所有层级的存储策略更新为所述第二存储策略的情况下，根据剩余的可使用的存储资源的大小，从高层级向低层级依次遍历，将多个层级的存储策略更新为第三存储策略，所述第三存储策略为：存储该层级的所有节点两两之间的路径信息。6.根据权利要求5所述的路径规划方法，其特征在于，所述根据所述路径节点列表，得到最优路径，包括：根据所述路径节点列表中的节点顺序，设定其中任意在所述路径节点列表相邻的两个节点为第一节点和第二节点，所述第一节点所在层级为低层级，所述第二节点所在层级为更高一级的高层级；确定所述第一节点和所述第二节点，在所述低层级中是否相邻；在所述第一节点和所述第二节点在所述低层级中相邻的情况下，得到所述第一节点和所述第二节点之间的最短路径；在所述第一节点和所述第二节点，在所述低层级中不相邻的情况下，根据所述低层级的存储策略，确定是否存储有所述第一节点和所述第二节点之间的最短路径；在所述低层级存储有所述第一节点和所述第二节点之间的最短路径的情况下，直接从存储数据中获取所述第一节点和所述第二节点之间的最短路径；在所述低层级未存储有所述第一节点和所述第二节点之间的最短路径的情况下，利用最短路径算法计算得到所述第一节点和所述第二节点之间的最短路径。7.根据权利要求6所述的路径规划方法，其特征在于，所述第一节点位于第三节点与所述第二节点中间，在确定所述第一节点和所述第二节点之间的最短路径之后，所述方法还包括：确定所述第一节点和所述第二节点之间的最短路径经过的多个中间节点；从所述多个中间节点中，确定出目标中间节点，所述目标中间节点为所述多个中间节点按照节点顺序排列时，最后一个与所述第一节点所在层级相同的节点；将所述最短路径更新为所述目标中间节点与所述第二节点之间的路径；重新计算所述第三节点与所述目标中间节点之间的路径。8.根据权利要求1所述的路径规划方法，其特征在于，所述根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，包括：
根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级高于所述终点所在层级，并且，在所述待分析节点所在层级更高一级的层级中，所述待分析节点和所述终点位于同一剖腔的情况下:在所述待分析节点所在层级中，所述待分析节点和所述终点位于同一剖腔时，从所述待分析节点所在层级更低一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；在所述待分析节点所在层级中，所述待分析节点和所述终点不位于同一剖腔时，从所述待分析节点所在层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点；根据所述待分析节点的位置信息和所述终点的位置信息，确定所述待分析节点所在层级高于所述终点所在层级，并且，在所述待分析节点所在层级更高一级的层级中，所述待分析节点和所述终点不位于同一剖腔的情况下，在所述待分析节点所在层级更高一级的层级中，所述待分析节点所在剖腔的多个候选剖腔边界点中，确定所述下一节点。9.一种路径规划装置，其特征在于，所述装置包括：分层模块，用于对路网进行剖分分层，得到多个层级以及每个层级的多个剖腔，每个所述剖腔中包括多个节点，所述节点分为剖腔边界点和剖腔内节点；所述多个节点中包括路径规划的起点和终点；队列构造模块，用于构造优先级队列，将所述起点的key值设为0，加入到所述优先级队列中；所述key值表示节点的预估价值；选择模块，用于执行待分析节点选择步骤：选择所述优先级队列中，key值最小的节点作为待分析节点出队，将所述待分析节点推入节点列表中；下一节点确定模块，用于执行下一节点确定步骤：根据所述待分析节点的位置信息和所述终点的位置信息，确定下一节点，将所述下一节点放入所述优先级队列；利用所述下一节点，更新路径映射表；重复模块，用于重复所述待分析节点选择步骤和所述下一节点确定步骤，直至所述下一节点为所述终点；路径节点列表获取模块，用于从所述终点开始循环访问所述路径映射表，直至访问得到所述起点，获取从所述起点至所述终点的路径节点列表；最优路径确定模块，用于根据所述路径节点列表，得到最优路径。10.一种电子设备，其特征在于，包括处理器和存储器，所述存储器存储可在所述处理器上运行的程序或指令，所述程序或指令被所述处理器执行时实现如权利要求1至8任一项所述的路径规划方法的步骤。

技术总结
本申请提供了一种路径规划方法、装置和电子设备，涉及路径规划技术领域，该方法包括：对路网进行剖分分层，得到多个层级以及每个层级的多个剖腔，每个剖腔中包括多个节点；多个节点中包括路径规划的起点和终点；构造优先级队列，将起点的key值设为0，加入到优先级队列中；选择优先级队列中，key值最小的节点作为待分析节点出队；执行下一节点确定步骤：根据待分析节点的位置信息和终点的位置信息，确定下一节点，将下一节点放入优先级队列；利用下一节点，更新路径映射表；重复下一节点确定步骤，直至下一节点为终点；从终点开始循环访问路径映射表，直至访问得到起点，获取从起点至终点的路径节点列表；根据路径节点列表，得到最优路径。径。径。


技术研发人员：李永瑾 许京奕 孙霞
受保护的技术使用者：北京大数据先进技术研究院
技术研发日：2023.04.28
技术公布日：2023/8/4