本公开提供了用于通过确定车辆可以行驶通过的一组路点的最佳排序来提高车辆操作效率的技术。
背景技术：
1、全局运动规划可以用于确定车辆要遵循的路线。用于全局运动规划的算法包括基于增量搜索的规划器(诸如快速探索随机树(rrt))、使用道路结构的基于图的规划方法、基于采样的方法(诸如概率路线图路径(prm)规划)等。
技术实现思路
1、计算机将所述路点划分为集群，通过执行优化算法将所述集群布置成上层排序，通过对所述集群执行所述优化算法将所述集群内的所述路点布置成相应的下层排序，并且通过根据所述上层排序将所述下层排序中的所述路点级联来以最终排序输出所述路点。最终排序定义了通过最终排序中的路点的路线，车辆可以沿着所述路线行驶。例如，计算机可以将路点划分为第一集群、第二集群和第三集群。计算机将集群布置成{第二集群、第一集群、第三集群}的上层排序。所述计算机确定所述第一集群中的所述路点的第一下层排序、所述第二集群中的所述路点的第二下层排序以及所述第三集群中的所述路点的第三下层排序。所述计算机以如下最终排序输出路点：处于第二下层排序的所述第二集群中的所述路点，然后是处于第一下层排序的所述第一集群中的所述路点，并且然后是处于第三下层排序的所述第三集群中的所述路点。然后，车辆可以行驶到最终排序中的路点。
2、使用这些技术可以显著减少处理时间。例如，进行了基于本公开的实验以确定车辆行驶通过位于旧金山港湾区的路点的顺序。在一个试验中，将路点在地理上划分为集群，并且将用于最小化能量消耗(例如，燃料或电荷)的优化算法应用于每个集群中的路点和作为组的集群，如本文所述(在图4中示出)。处理时间为约2.5小时。在第二试验中，在没有聚类的情况下将相同的优化算法应用于路点。处理时间约为7.5小时，并且车辆行驶到路点消耗的预期能量也较高。
3、一种计算机包括处理器和存储器，并且所述存储器存储指令，所述指令可由处理器执行以进行以下操作：根据至少一个度量将地理区域中的多个路点划分为多个集群，通过执行优化算法将所述集群布置成上层排序，通过对相应集群执行所述优化算法来将所述相应集群内的所述路点布置成多个相应下层排序，以及通过根据所述上层排序将所述下层排序中的所述路点级联来以最终排序输出所述路点。所述最终排序定义通过所述最终排序中的所述路点的最终路线。
4、在示例中，所述指令还可以包括用于指示车辆导航所述最终路线的指令。
5、在示例中，所述指令还可以包括用于确定所述最终排序中的连续路点之间的多条中间路线的指令，所述最终路线包括所述中间路线。
6、在示例中，所述至少一个度量可包括距离、地理密度、行驶时间或能量消耗中的至少一者。
7、在示例中，用于执行所述优化算法的指令可包括用于最小化与由所述优化算法输出的排序定义的路线相关联的成本的指令。在另外的示例中，所述成本可以包括距离、行驶时间或能量消耗中的至少一者。
8、在示例中，所述指令还可以包括用于进行以下操作的指令：在将所述路点布置成所述下层排序之前，确定相应集群的多个起始路点和结束路点，并且所述起始路点和结束路点可用作对当在所述相应集群上执行时的所述优化算法的约束。在另外的示例中，用于确定起始路点和结束路点的指令可以包括用于基于上层排序来确定起始路点和结束路点的指令。
9、在又另外的示例中，用于确定起始路点和结束路点的指令可以包括用于确定起始路点和结束路点以最小化上层排序中所述集群中的连续集群之间的成对成本的指令。在再另外的示例中，所述成对成本可以包括距离、行驶时间或能量消耗中的至少一者。
10、在示例中，所述指令还可以包括用于确定相应集群的代表性路点的指令，并且用于确定上层排序的指令可以包括用于对代表性路点执行优化算法的指令。
11、在示例中，所述指令还可以包括用于将所述集群中的第一集群中的所述路点划分为多个另外的集群，并且将所述第一集群中的所述另外的集群布置成中层排序的指令。在另外的示例中，用于将所述集群布置成所述上层排序的指令可以包括用于将所述另外的集群插入所述上层排序中所述第一集群的位置中的指令，其中所述另外的集群处于所述中层排序。
12、在示例中，所述指令还可以包括用于进行以下操作的指令：确定所述集群中的第一集群满足聚类条件，并且在确定所述第一集群满足所述聚类条件时，将所述第一集群中的所述路点划分为多个另外的集群。在另外的示例中，所述指令还可以包括用于进行以下操作的指令：在将第一集群中的所述路点划分为另外的集群时，将所述第一集群中的所述另外的集群布置成中层排序。在再另外的示例中，用于将所述集群布置成所述上层排序的指令可以包括用于将所述另外的集群插入所述上层排序中所述第一集群的位置中的指令，其中所述另外的集群处于所述中层排序。
13、在又另外的示例中，所述指令还可以包括用于进行以下操作的指令：将第一集群中的路点迭代地划分为另外的集群，直到聚类条件不再得到满足。在再另外的示例中，用于确定所述上层排序的指令可包括用于将紧接前一迭代中的相应另外的集群内的一次迭代中的所述另外的集群迭代地布置成相应的中层排序的指令。在又一另外的示例中，用于确定所述上层排序的所述指令可以包括用于进行以下操作的指令：将来自一次迭代的另外的集群迭代地插入紧接前一迭代中的包括来自该一次迭代中的所述另外的集群的另外的集群的位置中，其中来自该一次迭代中的另外的集群处于相应的中层排序。
14、一种方法包括：根据至少一个度量将地理区域中的多个路点划分为多个集群，通过执行优化算法将所述集群布置成上层排序，通过对相应集群执行所述优化算法来将所述相应集群内的所述路点布置成多个相应下层排序，以及通过根据所述上层排序将所述下层排序中的所述路点级联来以最终排序输出所述路点。所述最终排序定义通过所述最终排序中的所述路点的最终路线。
1.一种方法，其包括：
2.如权利要求1所述的方法，其还包括指示车辆导航所述最终路线。
3.如权利要求1所述的方法，其还包括确定所述最终排序中的连续路点之间的多条中间路线，所述最终路线包括所述中间路线。
4.如权利要求1所述的方法，其中所述至少一个度量包括距离、地理密度、行驶时间或能量消耗中的至少一者。
5.如权利要求1所述的方法，其中执行所述优化算法包括最小化与由所述优化算法输出的排序定义的路线相关联的成本。
6.如权利要求5所述的方法，其中所述成本包括距离、行驶时间或能量消耗中的至少一者。
7.如权利要求1所述的方法，其还包括在将所述路点布置成所述下层排序之前，确定所述相应集群的多个起始路点和结束路点；其中所述起始路点和所述结束路点用作对当在所述相应集群上执行时的所述优化算法的约束。
8.如权利要求7所述的方法，其中确定所述起始路点和所述结束路点包括基于所述上层排序确定所述起始路点和所述结束路点。
9.如权利要求1所述的方法，其还包括确定所述相应集群的代表性路点，其中确定所述上层排序包括对所述代表性路点执行所述优化算法。
10.如权利要求1所述的方法，其还包括将所述集群中的第一集群中的所述路点划分为多个另外的集群，并且将所述第一集群中的所述另外的集群布置成中层排序。
11.如权利要求10所述的方法，其中将所述集群布置成所述上层排序包括将所述另外的集群插入所述上层排序中所述第一集群的位置中，其中所述另外的集群处于所述中层排序。
12.如权利要求1所述的方法，其还包括确定所述集群中的第一集群满足聚类条件，并且在确定所述第一集群满足所述聚类条件时，将所述第一集群中的所述路点划分为多个另外的集群。
13.如权利要求12所述的方法，其还包括将所述第一集群中的所述路点迭代地划分为另外的集群直到所述聚类条件不再得到满足。
14.如权利要求13所述的方法，其中确定所述上层排序包括将紧接前一迭代中的相应另外的集群内的一次迭代中的所述另外的集群迭代地布置成相应的中层排序。
15.一种计算机，其包括处理器和存储器，所述存储器存储指令，所述指令能够由所述处理器执行以执行如权利要求1–14中的一项所述的方法。
