移动对象的路径规划方法、装置以及相关设备与流程

1.本公开涉及计算机技术领域，尤其涉及一种移动对象的路径规划方法、装置以及相关设备。


背景技术：

2.无人驾驶汽车的路径规划是指当发现驾驶环境有障碍物的时候，自主决策路径以躲避障碍物，从而安全到达目的地。无人驾驶汽车的路径规划与普通的gps(global positioning system，全球定位系统)导航区别很大，需要分别对动、静两种状态进行判定，并进行智能化决策，从而确保驾驶作业任务顺利完成。路径规划算法的好坏直接影响行车安全性，在无人驾驶汽车导航系统中起到决定性作用。
3.相关技术中常用的路径规划算法为a*(a-star)算法，而采用a*算法路径规划时，在路径转折多的情况下，节点选取不能很好的绕开障碍物，会造成安全性较低，不能适应复杂地图的路径规划，路径搜索效率不高等问题。
4.需要说明的是，在上述背景技术部分公开的信息仅用于加强对本公开的背景的理解，因此可以包括不构成对本领域普通技术人员已知的现有技术的信息。


技术实现要素：

5.本公开提供一种移动对象的路径规划方法、装置以及相关设备，至少在一定程度上克服相关技术在路径规划时，搜索过多非必要节点，导致路径搜索效率低的问题。
6.本公开的其他特性和优点将通过下面的详细描述变得显然，或部分地通过本公开的实践而习得。
7.根据本公开的一个方面，提供了一种移动对象的路径规划方法，包括：获取待规划路径的栅格化地图，其中，所述栅格化地图上包含：预先标记的多个关键节点以及待规划路径的起始节点和目标节点；从所述多个关键节点中选取所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的至少一个关键节点；根据所述起始节点、所述目标节点以及所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的各个关键节点，生成所述移动对象的路径规划信息。
8.在本公开的一些示例性实施例中，基于前述方案，从所述多个关键节点中选取所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的至少一个关键节点，包括：获取所述移动对象的当前节点，其中，所述当前节点为所述移动对象在栅格化地图中当前所处的节点；确定所述移动对象从当前节点移动到所述目标节点的目标向量；根据所述目标向量，从所述多个关键节点中选取所述移动对象从当前节点移动到所述目标节点的过程中所途径的下一个关键节点；重复执行如上步骤，直到所述移动对象所途径的下一个关键节点为所述目标节点。
9.在本公开的一些示例性实施例中，基于前述方案，根据所述目标向量，从所述多个关键节点中选取所述移动对象从当前节点移动到所述目标节点的过程中所途径的下一个
关键节点，包括：根据所述目标向量，从所述多个关键节点中选取距离所述目标节点最近的一个目标关键节点；判断所述目标关键节点是否是所述目标节点；若所述目标关键节点不是所述目标节点，则判断所述当前节点与所述目标关键节点之间是否存在障碍物；若所述当前节点与所述目标关键节点之间不存在障碍物，则确定所述目标关键节点为所述移动对象从当前节点移动到目标节点的过程中所途径的下一个关键节点。
10.在本公开的一些示例性实施例中，基于前述方案，在判断所述当前节点与所述目标关键节点之间是否存在障碍物之后，所述方法还包括：若所述当前节点与所述目标关键节点之间存在障碍物，则基于a星算法改进后的代价函数，确定所述移动对象从当前节点移动到所述目标关键节点的无障碍规划路径信息，其中，所述基于a星算法改进后的代价函数中包含移动物体到障碍物的碰撞距离代价因子；根据所述移动对象从当前节点移动到所述目标关键节点的无障碍规划路径信息，确定所述移动对象途径的下一个关键节点。
11.在本公开的一些示例性实施例中，基于前述方案，在基于a星算法改进后的代价函数，确定所述移动对象从当前节点移动到所述目标关键节点的无障碍规划路径信息之前，所述方法还包括：通过如下公式得到基于a星算法改进后的代价函数f(n)；
12.f(n)＝g(n)+k1h(n)+k2o(n)
13.其中，g(n)为从所述移动对象的起始节点到所述目标关键节点n的最小代价函数，h(n)为从所述目标关键节点n到所述移动对象的目标节点的路径的最小估计代价函数，o(n)为在所述移动对象在所述目标关键节点n的碰撞距离代价函数，k1为第一代价函数的权重，k2为第二代价函数的权重。
14.在本公开的一些示例性实施例中，基于前述方案，所述多个关键节点包括转向节点和死角节点，若所述目标关键节点不是所述目标节点，则判断所述当前节点与所述目标关键节点之间是否存在障碍物之前，所述方法还包括：判断从所述多个关键节点中选取距离所述目标节点最近的关键节点是否是所述死角节点；若所述关键节点是所述死角节点，则重新确定所述目标关键节点；若所述关键节点是所述转向节点，则判断所述当前节点与所述目标关键节点之间是否存在障碍物。
15.在本公开的一些示例性实施例中，基于前述方案，所述方法还包括：将所述移动对象的移动速度输入至预先训练好的防碰撞安全距离模型中，输出所述移动对象与障碍物之间的安全距离；根据所述安全距离，确定所述移动对象在所述目标关键节点的碰撞距离代价函数。
16.根据本公开的另一个方面，还提供了一种移动对象的路径规划装置，该装置包括：栅格地图获取模块，用于获取待规划路径的栅格化地图，其中，所述栅格化地图上包含：预先标记的多个关键节点以及待规划路径的起始节点和目标节点；关键节点选取模块，用于从所述多个关键节点中选取所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的至少一个关键节点；路径规划模块，用于根据所述起始节点、所述目标节点以及所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的各个关键节点，生成所述移动对象的路径规划信息。
17.根据本公开的再一个方面，还提供了一种电子设备，包括：处理器；以及存储器，用于存储所述处理器的可执行指令；其中，所述处理器配置为经由执行所述可执行指令来执行上述任意一种移动对象的路径规划方法。
18.根据本公开的又一个方面，还提供了一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现上述任意一种移动对象的路径规划方法。
19.本公开的实施例中提供的移动对象的路径规划方法、装置以及相关设备，首先，获取包含预先标记的多个关键节点以及待规划路径的起始节点和目标节点的栅格化地图；然后，从多个关键节点中选取移动对象从起始节点移动到目标节点的过程中所途径的至少一个关键节点，最后，根据起始节点、目标节点以及移动对象从起始节点移动到目标节点的过程中所途径的各个关键节点，生成移动对象的路径规划信息。
20.相较于现有技术中在路径规划时，搜索过多非必要节点，导致路径搜索效率低，本公开实施例中则在待规划路径的栅格化地图就已经标记好多个关键节点，在规划路径时不再需要大范围所搜其他非必要节点，只需要确定预先标记的多个关键节点中的那些是从起始节点移动到目标节点的过程中所途径的必须的关键节点，从而实现减少非必要节点的搜索过程，提高路径规划的效率的技术效果。
21.应当理解的是，以上的一般描述和后文的细节描述仅是示例性和解释性的，并不能限制本公开。
附图说明
22.此处的附图被并入说明书中并构成本说明书的一部分，示出了符合本公开的实施例，并与说明书一起用于解释本公开的原理。显而易见地，下面描述中的附图仅仅是本公开的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
23.图1示出本公开实施例中一种应用系统架构示意图；
24.图2示出本公开实施例中一种移动对象的路径规划方法示意图；
25.图3示出本公开实施例中一种待规划路径的栅格化地图；
26.图4示出本公开实施例中一种基于目标向量的关键节点选取策略图；
27.图5示出本公开实施例中一种障碍物检测区域示意图；
28.图6示出本公开实施例中一种安全距离与道路摩擦系数、移动对象移动速度的关系模型图；
29.图7示出本公开实施例中一种基于碰撞场距离扩展栅格图；
30.图8示出本公开实施例中一种对移动对象的路径规划算法整体流程图；
31.图9示出本公开实施例中一种移动对象的路径规划装置示意图；
32.图10示出本公开实施例中一种应用移动对象的路径规方法的电子设备示意图。
具体实施方式
33.现在将参考附图更全面地描述示例实施方式。然而，示例实施方式能够以多种形式实施，且不应被理解为限于在此阐述的范例；相反，提供这些实施方式使得本公开将更加全面和完整，并将示例实施方式的构思全面地传达给本领域的技术人员。所描述的特征、结构或特性可以以任何合适的方式结合在一个或更多实施方式中。
34.此外，所描述的特征、结构或特性可以以任何合适的方式结合在一个或更多实施例中。在下面的描述中，提供许多具体细节从而给出对本公开的实施例的充分理解。然而，
本领域技术人员将意识到，可以实践本公开的技术方案而没有特定细节中的一个或更多，或者可以采用其它的方法、组元、装置、步骤等。在其它情况下，不详细示出或描述公知方法、装置、实现或者操作以避免模糊本公开的各方面。
35.附图中所示的流程图仅是示例性说明，不是必须包括所有的内容和操作/步骤，也不是必须按所描述的顺序执行。例如，有的操作/步骤还可以分解，而有的操作/步骤可以合并或部分合并，因此实际执行的顺序有可能根据实际情况改变。
36.图1示出了可以应用本公开实施例中移动对象的路径规划方法的示例性应用系统架构示意图。如图1所示，该系统架构可以包括终端设备101、网络102和服务器103。
37.网络102用以在终端设备101和服务器103之间提供通信链路的介质，可以是有线网络，也可以是无线网络。
38.可选地，上述的无线网络或有线网络使用标准通信技术和/或协议。网络通常为因特网、但也可以是任何网络，包括但不限于局域网(local area network，lan)、城域网(metropolitan area network，man)、广域网(wide area network，wan)、移动、有线或者无线网络、专用网络或者虚拟专用网络的任何组合)。在一些实施例中，使用包括超文本标记语言(hyper text mark-up language，html)、可扩展标记语言(extensible markuplanguage，xml)等的技术和/或格式来代表通过网络交换的数据。此外还可以使用诸如安全套接字层(secure socket layer，ssl)、传输层安全(transport layer security，tls)、虚拟专用网络(virtual private network，vpn)、网际协议安全(internet protocolsecurity，ipsec)等常规加密技术来加密所有或者一些链路。在另一些实施例中，还可以使用定制和/或专用数据通信技术取代或者补充上述数据通信技术。
39.终端设备101可以是各种电子设备，包括但不限于智能手机、平板电脑、膝上型便携计算机、台式计算机、可穿戴设备、增强现实设备、虚拟现实设备等。
40.可选地，不同的终端设备101中安装的应用程序的客户端是相同的，或基于不同操作系统的同一类型应用程序的客户端。基于终端平台的不同，该应用程序的客户端的具体形态也可以不同，比如，该应用程序客户端可以是手机客户端、pc客户端等。
41.服务器103可以是提供各种服务的服务器，例如对用户利用终端设备101所进行操作的装置提供支持的后台管理服务器。后台管理服务器可以对接收到的请求等数据进行分析等处理，并将处理结果反馈给终端设备。
42.可选地，服务器可以是独立的物理服务器，也可以是多个物理服务器构成的服务器集群或者分布式系统，还可以是提供云服务、云数据库、云计算、云函数、云存储、网络服务、云通信、中间件服务、域名服务、安全服务、cdn(content delivery network，内容分发网络)、以及大数据和人工智能平台等基础云计算服务的云服务器。终端可以是智能手机、平板电脑、笔记本电脑、台式计算机、智能音箱、智能手表等，但并不局限于此。终端以及服务器可以通过有线或无线通信方式进行直接或间接地连接，本公开在此不做限制。
43.本领域技术人员可以知晓，图1中的终端设备、网络和服务器的数量仅仅是示意性的，根据实际需要，可以具有任意数目的终端设备、网络和服务器。本公开实施例对此不作限定。
44.下面，将结合附图及实施例对本示例实施方式中的移动对象的路径规划方法的各个步骤进行更详细的说明。
45.首先，本公开实施例中提供了一种可以应用但不限于在5g智慧园区中，对自动驾驶车辆进行路径规划，而在现有技术中对无人驾驶的车辆进行路径规划是指当发现驾驶环境有障碍物的时候，自主决策路径以躲避障碍物，从而安全到达目的地，无人驾驶汽车的路径规划与普通的全球定位系统(global positioning system，gps)导航区别很大，需要分别对动、静两种状态进行判定，并进行智能化决策，从而确保驾驶作业任务顺利完成。路径规划算法的好坏直接影响行车安全性，在无人驾驶汽车导航系统中起到决定性作用，其中，常用的路径规划算法均有其对应的适用范围及优缺点，具体地，常用的路径规划算法有迪杰斯特拉算(dijkstra)算法、最佳优先搜索算法(best-first-searching，bfs)以及a星(a-stat，a*)算法，上述三种常用的路径规划算法具体的优缺点如下：
46.dijkstra算法是一种单源性质的最优化算法形式，应用dijkstra算法可以获得任一节点和另一节点间可通行的最短距离。此算法特点是以起始节点为出发点，然后向着四周慢慢延伸和递进，最后延伸到预定的目标节点，因此该方法通常损耗时间非常长。
47.bfs算法与dijkstra算法有类似之处，最关键不同之处在于，该算法更加注重搜索路径时所承受的时间代价。因此该算法并未考虑距离出发点较近的位置，而是优先考察预定目标周围的位置，因而最终bfs算法的搜索路径并不是最优路径，这也是该算法缺点，bfs算法的优点是显著提升了算法的速度。
48.a*算法是一种可以适用于各类路况的启发式的人工智能算法，鲁棒性极佳。a*算法最显著的优点是将dijkstra算法和bfs算法结合起来，通过将初始点与节点的代价以及节点到目标点的启发式评价来分析当前节点，但a*算法路径规划时也会搜索过多非必要节点，导致路径搜索效率低。
49.而本公开实施例则会在待规划路径的栅格化地图中预先标记多个关键节点，在规划路径时也只需要对预先标记多个关键节点进行搜索，避免了现有技术中路径规划搜索过多非必要节点，导致路径搜索效率低的问题。
50.图2示出本公开实施例中一种移动对象的路径规划方法示意图，如图2所示，本公开实施例中提供的移动对象的路径规划方法，该方法包括如下步骤：
51.s201，获取待规划路径的栅格化地图，其中，栅格化地图上包含：预先标记的多个关键节点以及待规划路径的起始节点和目标节点。
52.在一些实施例中，如图3所示，本公开实施例中获取的待规划路径的栅格化地图可以是包括移动对象起始节点和目标节点的实际地图经过栅格化处理得到的，其中，移动对象起始节点是移动对象开始移动的起点，目标节点是移动对象最终达到目标的终点，并且，栅格化地图上还包括预先标记的多个关键节点，本公开实施例中的关键节点包括根据实际地图标记处的转向节点和/或死角节点以及障碍点。
53.s202，从多个关键节点中选取移动对象从起始节点移动到目标节点的过程中所途径的至少一个关键节点。
54.在一些实施例中，本公开实施例在多个关键节点中选取出的关键节点为对移动对象进行路径规划，搜索出的关键节点。
55.s203，根据起始节点、目标节点以及移动对象从起始节点移动到目标节点的过程中所途径的各个关键节点，生成移动对象的路径规划信息。
56.在一些实施例中，本公开实施例根据包含待规划路径的起始节点和目标节点的栅
格地图，以及选取出的移动对象从起始节点移动到目标节点的过程中所途径的关键节点，确定移动对象的路径规划信息，从而规划出移动对象的移动路径。
57.本公开的实施例中提供的移动对象的路径规划方法，首先，获取包含预先标记的多个关键节点以及待规划路径的起始节点和目标节点的栅格化地图；然后，从多个关键节点中选取移动对象从起始节点移动到目标节点的过程中所途径的至少一个关键节点，最后，根据起始节点、目标节点以及移动对象从起始节点移动到目标节点的过程中所途径的各个关键节点，生成移动对象的路径规划信息。相较于现有技术中在路径规划时，搜索过多非必要节点，导致路径搜索效率低，本公开实施例中则在待规划路径的栅格化地图就已经标记好多个关键节点，在规划路径时不再需要大范围所搜其他非必要节点，只需要搜索预先标记的多个关键节点中的哪些是从起始节点移动到目标节点的过程中所途径的必须的关键节点，从而实现减少非必要节点的搜索过程，提高路径规划的效率的技术效果。
58.在一些实施例中，从多个关键节点中选取移动对象从起始节点移动到目标节点的过程中所途径的至少一个关键节点，包括：获取移动对象的当前节点，其中，当前节点为移动对象在栅格化地图中当前所处的节点；确定移动对象从当前节点移动到目标节点的目标向量；根据目标向量，从多个关键节点中选取移动对象从当前节点移动到目标节点的过程中所途径的下一个关键节点；重复执行如上步骤，直到移动对象所途径的下一个关键节点为目标节点。只需要搜索目标向量周围的关键节点，减少了非必要节点的搜索过程，大大提升了路径规划的效率。
59.在一些实施例中，根据目标向量，从多个关键节点中选取移动对象从当前节点移动到目标节点的过程中所途径的下一个关键节点，包括：根据目标向量，从多个关键节点中选取距离目标节点最近的一个目标关键节点；判断目标关键节点是否是目标节点；若目标关键节点不是目标节点，则判断当前节点与目标关键节点之间是否存在障碍物；若当前节点与目标关键节点之间不存在障碍物，则确定目标关键节点为移动对象从当前节点移动到目标节点的过程中所途径的下一个关键节点。
60.具体地，在本公开实施例中，如图3所示，将移动对象在栅格地图中的起始节点设置为s，目标节点设置为g，而确定移动对象从当前节点移动到目标节点的目标向量sg，如图4所示，若a、b、c、d为目标向量sg周围的关键节点，基于目标向量sg选取趋近于目标节点g的关键节点n，通过计算a、b、c、d各个关键节点与目标节点g的曼哈顿距离，进而选取出距离最小的关键节点n，并且，根据栅格地图中的标记，判断出关键节点n并不是目标节点g，再判断sn两节点之间的路径是否存在障碍物，在sn两节点之间的路径不存在障碍物的情况下，按上述执行步骤重复确定下一段路径的关键节点，直到移动对象所途径的下一个关键节点为目标节点，进一步提高了路径规划的效率。
61.如图4所示，通过公式(1)计算出起始节点s与目标节点g的距离，并且，其他关键节点与目标节点g的曼哈顿距离均可以通过公式(1)计算求出：
62.dm＝|g
x-s
x
|+|g
y-sy|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)
63.其中，dm为起始节点s到目标节点g的曼哈顿距离，s
x
为起始节点s在x轴上的坐标，sy为起始节点s在y轴上的坐标，g
x
为目标节点g在x轴上的坐标，gy为目标节点g在y轴上的坐标，|g
x-s
x
|为起始节点s和目标节点g在x轴方向上的距离，|g
y-sy|为起始节点s和目标节点g在y轴方向上的距离。
64.在一些实施例中，在判断当前节点与目标关键节点之间是否存在障碍物之后，方法还包括：若当前节点与目标关键节点之间存在障碍物，则基于a星算法改进后的代价函数，确定移动对象从当前节点移动到目标关键节点的无障碍规划路径信息，其中，基于a星算法改进后的代价函数中包含移动物体到障碍物的碰撞距离代价因子；根据移动对象从当前节点移动到目标关键节点的无障碍规划路径信息，确定移动对象途径的下一个关键节点。根据本公开实施例中基于a星算法改进后的代价函数，通过在栅格化地图上标记关键节点，路径规划时只需要对关键节点搜索，大大减少了a星算法增量扩展搜索节点的次数，提升了路径规划的效率，解决了传统a星算法路径规划过程中，存在转折角度过大、转折次数多、路径规划距离长等问题。
65.在一些实施例中，在基于a星算法改进后的代价函数，确定移动对象从当前节点移动到目标关键节点的无障碍规划路径信息之前，方法还包括：通过公式(2)得到基于a星算法改进后的代价函数f(n)；
66.f(n)＝g(n)+k1h(n)+k2o(n)
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)
67.其中，g(n)为从移动对象的起始节点到目标关键节点n的最小代价函数，h(n)为从目标关键节点n到移动对象的目标节点的路径的最小估计代价函数，o(n)为在移动对象在目标关键节点n的碰撞距离代价函数，k1为第一代价函数的权重，k2为第二代价函数的权重。
68.更为详细地，本公开实施例中的k1越大，路径趋向目标节点速率越快，计算耗时越短，但这将会影响路径最优性，而k2取值则会直接影响规划路径与障碍物边界的距离，进而影响移动对象移动的安全性，根据本领域技术人员多次仿真和验证，本公开实施例中的k1＝2，k2＝2，当然，本公开实施例中的k1和k2取值并不局限于上述数值2，本领域技术人员可以根据实际情况对k1和k2取值进行灵活调整。
69.并且，本公开实施例中基于a星算法改进后的代价函数加入碰撞距离代价，降低了移动对象与障碍物碰撞率，大大提升了路径规划的安全性。
70.本公开实施例也如a星算法通过反复迭代，逐步选取代价值最小的关键节点，从而生成一条从s到n的无障碍规划路径。
71.在一些实施例中，多个关键节点包括转向节点和死角节点，若目标关键节点不是目标节点，则判断当前节点与目标关键节点之间是否存在障碍物之前，方法还包括：判断从多个关键节点中选取距离目标节点最近的关键节点是否是死角节点；若关键节点是死角节点，则重新确定目标关键节点；若关键节点是转向节点，则判断当前节点与目标关键节点之间是否存在障碍物。
72.在一些实施例中，在确定与目标节点g距离最小的关键节点n之后，判断n是否为路径死角节点，若是则需要重新进行关键节点n的选取；若不是，则继续判断起始节点s与关键节点n的搜索区域内是否存在障碍点。如图5所示，为起始节点s与关键节点n的搜索区域，搜索区域长为|n
x-s
x
|，宽度为道路长度，例如设置道路长度为7m。n
x
为被选定节点的x轴坐标。若搜索区域内不存在障碍节点，则车辆可以直接移到关键节点n，如果存在障碍点，则基于a星算法改进后的代价函数规划出一条到关键节点n的无障碍路径。
73.进一步地，本公开实施例将搜索区域内的障碍物分为两种，第一种，例如小尺寸移动概率高的障碍物，如道路旁静止的行人，长度l∈(1，2)m；第二种，例如移动概率低但尺寸较大的障碍物，如道路旁的停车，长度l∈(3，4)m。
74.在一些实施例中，本公开实施例中的上述方法还包括：将移动对象的移动速度输入至预先训练好的防碰撞安全距离模型中，输出移动对象与障碍物之间的安全距离；根据安全距离，确定移动对象在目标关键节点的碰撞距离代价函数。
75.具体地，本公开实施例基于移动对象的移动速度、安全距离及大量模拟仿真测试分析，设计了一种防碰撞安全距离模型，其中，移动对象与障碍物的安全距离由移动对象的移动速度，道路摩擦系数相关，更为详细地，本公开实施例通过公式(3)获得防碰撞安全距离模型：
76.ds＝k3v2/(2μg)+(2-μ)du
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(3)
77.其中，ds为移动对象与障碍物的安全距离，k3为不同类型障碍物的权重，当障碍物较大时，k3＝1.5，障碍物较小时，k3＝1.2；v是移动对象的移动速度；μ为移动对象与地面的摩擦系数；g为重力加速度，取值设为10m/s2；du为单位距离，取值为1m。
78.更为详细地，在本公开实施例中移动对象为车辆时，本领域技术人员基于大量车辆碰撞场景的仿真测试实验，得到如图6所示的安全距离与路面摩擦因数、车辆行驶速度的关系模型图，如图6所示，随着路面摩擦系数降低以及车辆行驶速度的增加，安全碰撞距离逐渐增大，这也符合现实世界中车辆行驶过程中驾驶员的避免碰撞习惯。
79.由公式(4)可以得到扩展栅格的总层数c为：
[0080][0081]
其中，公式(4)中的表示向上取整，将碰撞场距离重新赋值为10m
×
c，并作为扩展栅格最内层栅格代价值，依次向外以10m的倍数进行递减赋值，如果障碍物扩展栅格中包含障碍物栅格，则不对其进行赋值。如图7所示，当移动对象的移动速度为15m/s，移动对象与地面的摩擦系数为0.8时，由式(3)可得ds＝18.075m，由式(4)可得c＝2，因此，可以确定本公开实施例中的o(n)＝20m，赋予障碍物边界外第1层栅格，将代价值o(n)＝10m赋予障碍物边界外第2层栅格。
[0082]
在一种实施例中的，本公开实施例对移动对象的路径规划算法整体流程如图8所示，具体包括如下步骤：
[0083]
s801，获取待规划路径的栅格化地图，确定出移动对象的起始节点s和目标节点g；
[0084]
s802，根据实际地图在栅格化地图中标记处转向节点和死角节点；
[0085]
s803，基于起始节点s和目标节点g生成当前目标向量sg确定下一路径关键节点n；
[0086]
s8031，若选取的关键节点n是目标节点g，则选中该关键节点n，直接输出路径；
[0087]
s8032，若选取的关键节点n不是目标节点g，则根据当前起始节点s和选取的关键节点n形成搜索区域；
[0088]
s804，确定搜索区域是否存在障碍物；
[0089]
s8041，若该搜索区域并不存在障碍物，则直接将移动对象移动至关键节点n，再根据s和n两节点确定下一个目标向量sn，重复确定下下一个路径的关键节点，直到移动对象所途径的下一个关键节点为目标节点g；
[0090]
s8042，若该搜索区域存在障碍物，则基于a星算法改进后的代价函数进行增量扩展搜索最小代价节点；
[0091]
s805，确定是否生成从当前起始节点s到关键节点n的路径；若不能生成从当前起始节点s到关键节点n的路径，则返回步骤s8042，继续基于a星算法改进后的代价函数进行
增量扩展搜索最小代价节点，直到生成适合的关键节点，形成从当前起始节点s到适合的关键节点的路径；若能生成从当前起始节点s到关键节点n的路径，则返回步骤s803，再根据s和n两节点确定下一个目标向量sn，重复确定下下一个路径的关键节点，直到移动对象所途径的下一个关键节点为目标节点，生成一条从起始节点s到目标节点g的无障碍规划路径。
[0092]
基于同一发明构思，本公开实施例中还提供了一种移动对象的路径规划装置，如下面的实施例。由于该装置实施例解决问题的原理与上述方法实施例相似，因此该装置实施例的实施可以参见上述方法实施例的实施，重复之处不再赘述。
[0093]
图9示出本公开实施例中一种移动对象的路径规划装置示意图，如图9所示，该装置包括：
[0094]
栅格地图获取模块，用于获取待规划路径的栅格化地图，其中，栅格化地图上包含：预先标记的多个关键节点以及待规划路径的起始节点和目标节点。
[0095]
关键节点选取模块，用于从多个关键节点中选取移动对象从起始节点移动到目标节点的过程中所途径的至少一个关键节点。
[0096]
路径规划模块，用于根据起始节点、目标节点以及移动对象从起始节点移动到目标节点的过程中所途径的各个关键节点，生成移动对象的路径规划信息。
[0097]
本公开的实施例中提供的移动对象的路径规划装置，通过栅格地图获取模块，获取包含预先标记的多个关键节点以及待规划路径的起始节点和目标节点的栅格化地图；通过关键节点选取模块，从多个关键节点中选取移动对象从起始节点移动到目标节点的过程中所途径的至少一个关键节点，通过路径规划模块，根据起始节点、目标节点以及移动对象从起始节点移动到目标节点的过程中所途径的各个关键节点，生成移动对象的路径规划信息。相较于现有技术中在路径规划时，搜索过多非必要节点，导致路径搜索效率低，本公开实施例中则在待规划路径的栅格化地图就已经标记好多个关键节点，在规划路径时不再需要大范围所搜其他非必要节点，只需要确定预先标记的多个关键节点中的那些是从起始节点移动到目标节点的过程中所途径的必须的关键节点，从而实现减少非必要节点的搜索过程，提高路径规划的效率的技术效果。
[0098]
在一些实施例中，本公开实施例中的关键节点选取模块包括：获取节点子模块、确定向量子模块、选取节点子模块以及重复执行子模块，其中，获取节点子模块，用于获取移动对象的当前节点，其中，当前节点为移动对象在栅格化地图中当前的节点；确定向量子模块，用于确定移动对象从当前节点移动到目标节点的目标向量；选取节点子模块，用于根据目标向量，从多个关键节点中选取移动对象从当前节点移动到目标节点的过程中所途径的下一个关键节点；重复执行子模块，用于重复执行如上步骤，直到移动对象所途径的下一个关键节点为目标节点。
[0099]
在一些实施例中，本公开实施例中的选取节点子模块还用于根据目标向量，从多个关键节点中选取距离目标节点最近的一个目标关键节点；判断目标关键节点是否是目标节点；若目标关键节点不是目标节点，则判断当前节点与目标关键节点之间是否存在障碍物；若当前节点与目标关键节点之间不存在障碍物，则确定目标关键节点为移动对象从当前节点移动到目标节点的过程中所途径的下一个关键节点。
[0100]
在一些实施例中，在判断当前节点与目标关键节点之间是否存在障碍物之后，本公开实施例中的移动对象的路径规划装置还包括：无障碍路径规划模块以及关键节点确定
模块，其中，无障碍路径规划模块，用于若当前节点与目标关键节点之间存在障碍物，则基于a星算法改进后的代价函数，确定移动对象从当前节点移动到目标关键节点的无障碍规划路径信息，其中，基于a星算法改进后的代价函数中包含移动物体到障碍物的碰撞距离代价因子；关键节点确定模块，用于根据移动对象从当前节点移动到目标关键节点的无障碍规划路径信息，确定移动对象途径的下一个关键节点。
[0101]
在一些实施例中，在基于a星算法改进后的代价函数，确定移动对象从当前节点移动到目标关键节点的无障碍规划路径信息之前，本公开实施例中的移动对象的路径规划装置还包括：代价函数确定模块，其中，代价函数确定模块，用于通过公式(1)得到基于a星算法改进后的代价函数其中，g(n)为从移动对象的起始节点到目标关键节点n的最小代价函数，h(n)为从目标关键节点n到移动对象的目标节点的路径的最小估计代价函数，o(n)为在移动对象在目标关键节点n的碰撞距离代价函数，k1为第一代价函数的权重，k2为第二代价函数的权重。
[0102]
在一些实施例中，多个关键节点包括转向节点和死角节点，若目标关键节点不是目标节点，则判断当前节点与目标关键节点之间是否存在障碍物之前，本公开实施例中的移动对象的路径规划装置还包括：死角判断模块、重新确定节点模块以及障碍物确定模块，其中，死角判断模块，用于判断从多个关键节点中选取距离目标节点最近的关键节点是否是死角节点；重新确定节点模块，用于若关键节点是死角节点，则重新确定目标关键节点；及障碍物确定模块，用于若关键节点是转向节点，则判断当前节点与目标关键节点之间是否存在障碍物。
[0103]
在一些实施例中，本公开实施例中的移动对象的路径规划装置还包括：安全距离确定模块以及碰撞距离代价函数确定模块，其中，安全距离确定模块，用于将移动对象的移动速度输入至预先训练好的防碰撞安全距离模型中，输出移动对象与障碍物之间的安全距离；碰撞距离代价函数确定模块，用于根据安全距离，确定移动对象在目标关键节点的碰撞距离代价函数。
[0104]
所属技术领域的技术人员能够理解，本公开的各个方面可以实现为系统、方法或程序产品。因此，本公开的各个方面可以具体实现为以下形式，即：完全的硬件实施方式、完全的软件实施方式(包括固件、微代码等)，或硬件和软件方面结合的实施方式，这里可以统称为“电路”、“模块”或“系统”。
[0105]
下面参照图10来描述根据本公开的这种实施方式的电子设备10。图10显示的电子设备10仅仅是一个示例，不应对本公开实施例的功能和使用范围带来任何限制。
[0106]
如图10所示，电子设备10以通用计算设备的形式表现。电子设备10的组件可以包括但不限于：上述至少一个处理单元11、上述至少一个存储单元12、连接不同系统组件(包括存储单元12和处理单元11)的总线13。
[0107]
其中，存储单元存储有程序代码，程序代码可以被处理单元11执行，使得处理单元11执行本说明书上述“示例性方法”部分中描述的根据本公开各种示例性实施方式的步骤。
[0108]
在一些实施例中，当电子设备用于控制例如本公开上述基于知识图谱的问答方法时，处理单元11可以执行上述方法实施例的如下步骤：
[0109]
获取待规划路径的栅格化地图，其中，栅格化地图上包含：预先标记的多个关键节点以及待规划路径的起始节点和目标节点。
[0110]
从多个关键节点中选取移动对象从起始节点移动到目标节点的过程中所途径的至少一个关键节点。
[0111]
根据起始节点、目标节点以及移动对象从起始节点移动到目标节点的过程中所途径的各个关键节点，生成移动对象的路径规划信息。
[0112]
存储单元12可以包括易失性存储单元形式的可读介质，例如随机存取存储单元(ram)121和/或高速缓存存储单元122，还可以进一步包括只读存储单元(rom)123。
[0113]
存储单元12还可以包括具有一组(至少一个)程序模块125的程序/实用工具124，这样的程序模块125包括但不限于：操作系统、一个或者多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。
[0114]
总线13可以为表示几类总线结构中的一种或多种，包括存储单元总线或者存储单元控制器、外围总线、图形加速端口、处理单元或者使用多种总线结构中的任意总线结构的局域总线。
[0115]
电子设备10也可以与一个或多个外部设备14(例如键盘、指向设备、蓝牙设备等)通信，还可与一个或者多个使得用户能与该电子设备10交互的设备通信，和/或与使得该电子设备10能与一个或多个其它计算设备进行通信的任何设备(例如路由器、调制解调器等等)通信。这种通信可以通过输入/输出(i/o)接口15进行。并且，电子设备10还可以通过网络适配器16与一个或者多个网络(例如局域网(lan)，广域网(wan)和/或公共网络，例如因特网)通信。如图所示，网络适配器16通过总线13与电子设备10的其它模块通信。应当明白，尽管图中未示出，可以结合电子设备10使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、raid系统、磁带驱动器以及数据备份存储系统等。
[0116]
通过以上的实施方式的描述，本领域的技术人员易于理解，这里描述的示例实施方式可以通过软件实现，也可以通过软件结合必要的硬件的方式来实现。因此，根据本公开实施方式的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质(可以是cd-rom，u盘，移动硬盘等)中或网络上，包括若干指令以使得一台计算设备(可以是个人计算机、服务器、终端装置、或者网络设备等)执行根据本公开实施方式的方法。
[0117]
特别地，根据本公开的实施例，上文参考流程图描述的过程可以被实现为计算机程序产品，该计算机程序产品包括：计算机程序，计算机程序被处理器执行时实现上述移动对象的路径规划方法。
[0118]
在本公开的示例性实施例中，还提供了一种计算机可读存储介质，该计算机可读存储介质可以是可读信号介质或者可读存储介质。其上存储有能够实现本公开上述方法的程序产品。在一些可能的实施方式中，本公开的各个方面还可以实现为一种程序产品的形式，其包括程序代码，当程序产品在终端设备上运行时，程序代码用于使终端设备执行本说明书上述“示例性方法”部分中描述的根据本公开各种示例性实施方式的步骤。
[0119]
本公开中的计算机可读存储介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机访问存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、光纤、便携式紧凑磁盘只读存储器(cd-rom)、光存储器件、磁存储器件、或者上述的任意合适的组合。
[0120]
在本公开中，计算机可读存储介质可以包括在基带中或者作为载波一部分传播的数据信号，其中承载了可读程序代码。这种传播的数据信号可以采用多种形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。可读信号介质还可以是可读存储介质以外的任何可读介质，该可读介质可以发送、传播或者传输用于由指令执行系统、装置或者器件使用或者与其结合使用的程序。
[0121]
可选地，计算机可读存储介质上包含的程序代码可以用任何适当的介质传输，包括但不限于无线、有线、光缆、rf等等，或者上述的任意合适的组合。
[0122]
在具体实施时，可以以一种或多种程序设计语言的任意组合来编写用于执行本公开操作的程序代码，程序设计语言包括面向对象的程序设计语言—诸如java、c++等，还包括常规的过程式程序设计语言—诸如“c”语言或类似的程序设计语言。程序代码可以完全地在用户计算设备上执行、部分地在用户设备上执行、作为一个独立的软件包执行、部分在用户计算设备上部分在远程计算设备上执行、或者完全在远程计算设备或服务器上执行。在涉及远程计算设备的情形中，远程计算设备可以通过任意种类的网络，包括局域网(lan)或广域网(wan)，连接到用户计算设备，或者，可以连接到外部计算设备(例如利用因特网服务提供商来通过因特网连接)。
[0123]
应当注意，尽管在上文详细描述中提及了用于动作执行的设备的若干模块或者单元，但是这种划分并非强制性的。实际上，根据本公开的实施方式，上文描述的两个或更多模块或者单元的特征和功能可以在一个模块或者单元中具体化。反之，上文描述的一个模块或者单元的特征和功能可以进一步划分为由多个模块或者单元来具体化。
[0124]
此外，尽管在附图中以特定顺序描述了本公开中方法的各个步骤，但是，这并非要求或者暗示必须按照该特定顺序来执行这些步骤，或是必须执行全部所示的步骤才能实现期望的结果。附加的或备选的，可以省略某些步骤，将多个步骤合并为一个步骤执行，以及/或者将一个步骤分解为多个步骤执行等。
[0125]
通过以上实施方式的描述，本领域的技术人员易于理解，这里描述的示例实施方式可以通过软件实现，也可以通过软件结合必要的硬件的方式来实现。因此，根据本公开实施方式的技术方案可以以软件产品的形式体现出来，该软件产品可以存储在一个非易失性存储介质(可以是cd-rom，u盘，移动硬盘等)中或网络上，包括若干指令以使得一台计算设备(可以是个人计算机、服务器、移动终端、或者网络设备等)执行根据本公开实施方式的方法。
[0126]
本领域技术人员在考虑说明书及实践这里公开的发明后，将容易想到本公开的其它实施方案。本公开旨在涵盖本公开的任何变型、用途或者适应性变化，这些变型、用途或者适应性变化遵循本公开的一般性原理并包括本公开未公开的本技术领域中的公知常识或惯用技术手段。说明书和实施例仅被视为示例性的，本公开的真正范围和精神由所附的权利要求指出。

技术特征：
1.一种移动对象的路径规划方法，其特征在于，包括：获取待规划路径的栅格化地图，其中，所述栅格化地图上包含：预先标记的多个关键节点以及待规划路径的起始节点和目标节点；从所述多个关键节点中选取所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的至少一个关键节点；根据所述起始节点、所述目标节点以及所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的各个关键节点，生成所述移动对象的路径规划信息。2.根据权利要求1所述的移动对象的路径规划方法，其特征在于，从所述多个关键节点中选取所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的至少一个关键节点，包括：获取所述移动对象的当前节点，其中，所述当前节点为所述移动对象在栅格化地图中当前所处的节点；确定所述移动对象从当前节点移动到所述目标节点的目标向量；根据所述目标向量，从所述多个关键节点中选取所述移动对象从当前节点移动到所述目标节点的过程中所途径的下一个关键节点；重复执行如上步骤，直到所述移动对象所途径的下一个关键节点为所述目标节点。3.根据权利要求2所述的移动对象的路径规划方法，其特征在于，根据所述目标向量，从所述多个关键节点中选取所述移动对象从当前节点移动到所述目标节点的过程中所途径的下一个关键节点，包括：根据所述目标向量，从所述多个关键节点中选取距离所述目标节点最近的一个目标关键节点；判断所述目标关键节点是否是所述目标节点；若所述目标关键节点不是所述目标节点，则判断所述当前节点与所述目标关键节点之间是否存在障碍物；若所述当前节点与所述目标关键节点之间不存在障碍物，则确定所述目标关键节点为所述移动对象从当前节点移动到目标节点的过程中所途径的下一个关键节点。4.根据权利要求3所述的移动对象的路径规划方法，其特征在于，在判断所述当前节点与所述目标关键节点之间是否存在障碍物之后，所述方法还包括：若所述当前节点与所述目标关键节点之间存在障碍物，则基于a星算法改进后的代价函数，确定所述移动对象从当前节点移动到所述目标关键节点的无障碍规划路径信息，其中，所述基于a星算法改进后的代价函数中包含移动物体到障碍物的碰撞距离代价因子；根据所述移动对象从当前节点移动到所述目标关键节点的无障碍规划路径信息，确定所述移动对象途径的下一个关键节点。5.根据权利要求4所述的移动对象的路径规划方法，其特征在于，在基于a星算法改进后的代价函数，确定所述移动对象从当前节点移动到所述目标关键节点的无障碍规划路径信息之前，所述方法还包括：通过如下公式得到基于a星算法改进后的代价函数f(n)；f(n)＝g(n)+k1h(n)+k2o(n)其中，g(n)为从所述移动对象的起始节点到所述目标关键节点n的最小代价函数，h(n)
为从所述目标关键节点n到所述移动对象的目标节点的路径的最小估计代价函数，o(n)为在所述移动对象在所述目标关键节点n的碰撞距离代价函数，k1为第一代价函数的权重，k2为第二代价函数的权重。6.根据权利要求3所述的移动对象的路径规划方法，其特征在于，所述多个关键节点包括转向节点和死角节点，若所述目标关键节点不是所述目标节点，则判断所述当前节点与所述目标关键节点之间是否存在障碍物之前，所述方法还包括：判断从所述多个关键节点中选取距离所述目标节点最近的关键节点是否是所述死角节点；若所述关键节点是所述死角节点，则重新确定所述目标关键节点；若所述关键节点是所述转向节点，则判断所述当前节点与所述目标关键节点之间是否存在障碍物。7.根据权利要求6所述的移动对象的路径规划方法，其特征在于，所述方法还包括：将所述移动对象的移动速度输入至预先训练好的防碰撞安全距离模型中，输出所述移动对象与障碍物之间的安全距离；根据所述安全距离，确定所述移动对象在所述目标关键节点的碰撞距离代价函数。8.一种移动对象的路径规划装置，其特征在于，包括：栅格地图获取模块，用于获取待规划路径的栅格化地图，其中，所述栅格化地图上包含：预先标记的多个关键节点以及待规划路径的起始节点和目标节点；关键节点选取模块，用于从所述多个关键节点中选取所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的至少一个关键节点；路径规划模块，用于根据所述起始节点、所述目标节点以及所述移动对象从所述起始节点移动到所述目标节点的过程中所途径的各个关键节点，生成所述移动对象的路径规划信息。9.一种电子设备，其特征在于，包括：处理器；以及存储器，用于存储所述处理器的可执行指令；其中，所述处理器配置为经由执行所述可执行指令来执行权利要求1～7中任意一项所述的移动对象的路径规划方法。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1～7中任意一项所述的移动对象的路径规划方法。

技术总结
本公开提供了一种移动对象的路径规划方法、装置以及相关设备，涉及计算机技术领域。该方法包括：获取待规划路径的栅格化地图，其中，栅格化地图上包含：预先标记的多个关键节点以及待规划路径的起始节点和目标节点；从多个关键节点中选取移动对象从起始节点移动到目标节点的过程中所途径的至少一个关键节点；根据起始节点、目标节点以及移动对象从起始节点移动到目标节点的过程中所途径的各个关键节点，生成移动对象的路径规划信息。本公开能够在一定程度上克服相关技术在路径规划时，搜索过多非必要节点，导致路径搜索效率低的问题。导致路径搜索效率低的问题。导致路径搜索效率低的问题。


技术研发人员：李冬冬 魏莱 沈云 郭璐
受保护的技术使用者：中国电信股份有限公司
技术研发日：2023.07.17
技术公布日：2023/10/15