导航路线动态规划方法、装置、计算机设备及存储介质与流程

1.本发明涉及智能导航技术领域，具体涉及一种导航路线动态规划方法、装置、计算机设备及存储介质。


背景技术：

2.目前的导航路线规划方法，往往根据导航终端的当前的地理位置信息，在未通行的导航路线中获取多个待验证路线，根据待验证路线的实时路况信息、导航终端的当前的地理位置信息以及导航路线的终点位置信息等生成规划的导航路线提供给用户。但是这些方法往往只考虑了某些因素，如距离、路况等，而忽略了限行时间关系、交通流量或设施分布等限制条件。因此需要一种更全面、更智能的导航引导路线方法来解决这个问题。本发明意在解决现有导航路线规划方法中，难以在满足限制条件的同时合理安排行车路线的问题。


技术实现要素：

3.有鉴于此，本发明提供了一种导航路线动态规划方法、装置、计算机设备及存储介质，以解决现有导航路线规划方法中，难以在满足限制条件的同时合理安排行车路线的问题。
4.第一方面，本发明提供了一种导航路线动态规划方法，包括：接收起点和终点生成道路网格模型；根据道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代价函数建立状态模型，代价函数为从起点至终点需要满足的规则和限制条件；根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线。
5.在本发明实施例中，通过生成道路网格模型，在导航路线规划中考虑从起点至终点需要满足的规则和限制条件，即在状态模型中引入代价函数，实现了根据目标函数、转移函数及代价函数共同确定最优导航路线的目的，从而可以得到满足规则和限制条件的最优导航路线。提高了导航路线规划的全面性，解决了现有导航路线规划方法中，难以在满足限制条件的同时合理安排行车路线的问题。
6.在一种可选的实施方式中，接收起点和终点生成道路网格模型，包括：基于起点和终点生成预设区域的栅格地图；将栅格地图中的路口及拐角点作为节点，将栅格地图中的道路或街道作为有向边，得到道路网格模型。在本发明实施例中，基于起点和终点生成预设区域的栅格地图，确定栅格地图中的节点和有向边，从而实现了将现实世界中的区域转化为包含一系列节点和有向边的道路网格模型的目的，为最优导航路线的求解提供了计算基础。
7.在一种可选的实施方式中，根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线，包括：根据状态模型以及转移函数确定任一节点对应的代价值及前驱结点；根据目标函数、多个前驱结点以及对应的代价值确定最优导航路线，目标函数为确定最优导航路线的单一目标或多个目标的组合。在本发明实施例中，根据目标函数如导
航路线的时间最短搜索代价值最小的前驱结点，达到了根据多个代价值最小的前驱结点确定最优导航路线的目的。
8.在一种可选的实施方式中，代价值由转移函数确定，转移函数等于起点至任一节点的实际代价与任一节点至目标节点的预估代价之和。在本发明实施例中，通过转移函数实现了对任一节点代价值的计算，从而根据代价值实现对最优导航路线的求解。
9.在一种可选的实施方式中，状态模型还包括：已等待时间，代价函数包括：限行规定，在根据状态模型以及转移函数确定任一节点对应的代价值及前驱结点之后，方法还包括：获取当前时刻；若当前时刻在限行规定的限行时段内，记录已等待时间并重新计算任一节点对应的代价值。在本发明实施例中，在计算节点的代价值及前驱结点时，考虑代价函数如限行规定的影响，从而实现了令最优导航路线满足规则和限制条件的目的。并且代价函数可以根据具体情况进行设置，包含一个或多个规则和限制条件，从而提高了导航路线规划的全面性。
10.在一种可选的实施方式中，在根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线之后，方法还包括：获取车辆行驶的实时状态信息；根据实时状态信息以及最优导航路线进行反向检查；确定实时最优导航路线；选择实时最优导航路线对应的导航方式。在本发明实施例中，通过获取车辆行驶的实时状态信息，进行反向检查，实现了根据突发情况调整最优导航路线的目的，提高了导航路线动态规划的实时性和准确性。通过选择导航方式，为用户提供更智能的导航服务，达到了提高导航的效率和安全性的效果。
11.在一种可选的实施方式中，确定实时最优导航路线包括：根据当前时刻以及限行时段确定最优导航路线对应的车速。在本发明实施例中，将限行规定下的等待问题转化成动态控制前进车速，从而达到了解决限行区域不能停车的问题。
12.第二方面，本发明提供了一种导航路线动态规划装置，包括：道路网格模型生成模块，用于接收起点和终点生成道路网格模型；状态模型构建模块，用于根据道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代价函数建立状态模型，代价函数为从起点至终点需要满足的规则和限制条件；最优导航路线求解模块，用于根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线。
13.在一种可选的实施方式中，道路网格模型生成模块包括：栅格地图生成单元，用于基于起点和终点生成预设区域的栅格地图；道路网格模型得到单元，用于将栅格地图中的路口及拐角点作为节点，将栅格地图中的道路或街道作为有向边，得到道路网格模型。
14.在一种可选的实施方式中，最优导航路线求解模块包括：代价值及前驱结点确定单元，用于根据状态模型以及转移函数确定任一节点对应的代价值及前驱结点；最优导航路线确定单元，用于根据目标函数、多个前驱结点以及对应的代价值确定最优导航路线，目标函数为确定最优导航路线的单一目标或多个目标的组合。
15.在一种可选的实施方式中，代价值由转移函数确定，转移函数等于起点至任一节点的实际代价与任一节点至目标节点的预估代价之和。
16.在一种可选的实施方式中，状态模型还包括：已等待时间，代价函数包括：限行规定，装置还包括：当前时刻获取模块，用于获取当前时刻；重计算模块，用于若当前时刻在限行规定的限行时段内，记录已等待时间并重新计算任一节点对应的代价值。
17.在一种可选的实施方式中，装置还包括：实时状态信息获取模块，用于获取车辆行驶的实时状态信息；反向检查模块，用于根据实时状态信息以及最优导航路线进行反向检查；实时最优导航路线确定模块，用于确定实时最优导航路线；导航方式选择模块，用于选择实时最优导航路线对应的导航方式。
18.在一种可选的实施方式中，实时最优导航路线确定模块包括：车速确定单元，用于根据当前时刻以及限行时段确定最优导航路线对应的车速。
19.第三方面，本发明提供了一种计算机设备，包括：存储器和处理器，存储器和处理器之间互相通信连接，存储器中存储有计算机指令，处理器通过执行计算机指令，从而执行上述第一方面或其对应的任一实施方式的导航路线动态规划方法。
20.第四方面，本发明提供了一种计算机可读存储介质，该计算机可读存储介质上存储有计算机指令，计算机指令用于使计算机执行上述第一方面或其对应的任一实施方式的导航路线动态规划方法。
附图说明
21.图1是根据本发明实施例的导航路线动态规划方法的流程示意图；
22.图2是根据本发明实施例的另一导航路线动态规划方法的流程示意图；
23.图3是根据本发明实施例的又一导航路线动态规划方法的流程示意图；
24.图4是根据本发明实施例的导航路线动态规划装置的结构框图；
25.图5是本发明实施例的计算机设备的硬件结构示意图。
具体实施方式
26.为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
27.需要说明的是，在本发明的描述中，术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本发明的实施例能够以除了在这里图示或描述的那些以外的顺序实施。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。术语“安装”、“相连”、“连接”应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或一体地连接；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，还可以是两个元件内部的连通，可以是无线连接，也可以是有线连接。对于本领域的普通技术人员而言，可以具体情况理解上述术语在本发明中的具体含义。
28.本发明实施例提供了一种导航路线动态规划方法，通过在状态模型中引入代价函数以达到在导航路线规划中考虑从起点至终点需要满足的规则和限制条件的效果，提高了导航路线动态规划的全面性。
29.根据本发明实施例，提供了一种导航路线动态规划方法实施例，需要说明的是，在
附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统中执行，并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤。
30.在本实施例中提供了一种导航路线动态规划方法，可用于上述的移动终端，如手机、平板电脑、车载终端等，图1是根据本发明实施例的导航路线动态规划方法的流程图，如图1所示，该流程包括如下步骤：
31.步骤s101，接收起点和终点生成道路网格模型。可选地，起点和终点分别对应车辆导航的始发地和目的地，基于起点和终点生成道路网格模型，该道路网格模型为包含一系列节点和有向边的栅格地图。
32.步骤s102，根据道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代价函数建立状态模型，代价函数为从起点至终点需要满足的规则和限制条件。可选地，道路网格模型中任意两个节点间的距离可通过经纬度计算获得；车辆速度可以是某一路段(任意两个节点间)车辆的平均速度；代价函数为从起点至终点需要满足的规则和限制条件，如限行规定、限速规定、红绿灯信息等；行驶时间可根据距离和车辆速度进行计算；上述信息可通过地图软件的公开数据接口获取。
33.步骤s103，根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线。可选地，目标函数为确定最优导航路线的目标，转移函数用于计算代价值即节点转移花费的代价，如花费的时间或距离，当目标函数为导航时间最短时，通过转移函数根据状态模型计算起点至终点上的多个代价最小的节点，从而确定最优导航路线。
34.本实施例提供的导航路线动态规划方法，通过生成道路网格模型，在导航路线规划中考虑从起点至终点需要满足的规则和限制条件，即在状态模型中引入代价函数，实现根据目标函数、转移函数以及代价函数共同确定最优导航路线的目的。从而可以得到满足规则和限制条件的最优导航路线。提高了导航路线规划的全面性，解决了现有导航路线规划方法中，难以在满足限制条件的同时合理安排行车路线的问题。
35.在本实施例中提供了一种导航路线动态规划方法，可用于上述的移动终端，如手机、平板电脑、车载终端等，图2是根据本发明实施例的另一导航路线动态规划方法的流程示意图，如图2所示，该流程包括如下步骤：
36.步骤s201，接收起点和终点生成道路网格模型。详细请参见图1所示实施例的步骤s101，在此不再赘述。在一些可选的实施方式中，上述步骤s201包括：
37.步骤a1，基于起点和终点生成预设区域的栅格地图。具体地，利用遥感数据、卫星图像等技术，将起点和终点间对应的现实世界中的城市建筑和道路等对象转化为二维平面上的图形，即栅格地图。
38.步骤a2，将栅格地图中的路口及拐角点作为节点，将栅格地图中的道路或街道作为有向边，得到道路网格模型。具体地，将栅格地图中的每一个路口(或交叉口)作为一个节点，节点间的距离取决于它们之间的物理距离。再将每条道路或街道抽象为一条有向边，该有向边的起点和终点为相邻节点。如果一条道路上某一点的道路走向发生变化，则需要插入一个或多个拐角点来表示道路走向变化的位置，并将这些拐角点作为节点。例如，在一个t字路口处增加一个拐角点。从而得到包含多个节点和有向边的道路网格模型。
39.步骤s202，根据道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代
价函数建立状态模型，代价函数为从起点至终点需要满足的规则和限制条件。详细请参见图1所示实施例的步骤s102，在此不再赘述。
40.步骤s203，根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线。
41.具体地，上述步骤s203包括：
42.步骤s2031，根据状态模型以及转移函数确定任一节点对应的代价值及前驱结点。可选地，假设状态模型包括：任意两个节点间的距离d；行驶时间t即行驶这条路线所需要的总时间，车辆速度v，即行驶这条路线时的车辆速度；代价函数c，本实施例中以代价函数c为限行规定为例，求解最优导航路线。需要说明的是，代价函数c可根据具体情况进行设置，如还可以包括限速规定、红绿灯信息、拥堵信息等。在一些可选的实施方式中，代价值由转移函数确定，转移函数等于起点至任一节点的实际代价与任一节点至目标节点的预估代价之和，可使用如下公式进行计算：f(node)＝g(node)+h(node)，其中f(node)代表任一节点的转移函数(估价函数)，f(node)的值即代价值，可记为fn，g(node)表示从起点到该节点的实际代价，如所需要花费的时间，h(node)表示该节点到目标节点的预估代价，如两点之间直线距离的长度。当节点n转移到它的任一相邻节点m时，将前往该节点的代价值从n开始更新为当前代价值加上节点n到节点m的代价值f(n,m)，即fm＝min{fn+f(n,m)}，当有多个前驱节点可到达节点m时，取代价值最小的前驱节点。
43.步骤s2032，根据目标函数、多个前驱结点以及对应的代价值确定最优导航路线，目标函数为确定最优导航路线的单一目标或多个目标的组合。可选地，目标函数可以设置为单一的目标，如最小距离或最短时间；也可以设置为多个目标的组合，并进行权衡和优化，如将最小行驶距离和最短时间进行线性组合。本实施例以最小行驶距离和最短时间的线性组合作为目标函数，对于每个节点n，根据a*算法，在搜索过程中不断更新该节点的状态(fn,pre(n))，其中，pre(n)代表从起点s到节点n取最小代价值时节点n的前驱节点，即使用当前生成的路径求解节点n的代价值时，检查是否有更小的代价值，如果有，则更新节点n的代价值和它的前驱结点。将收集到的前驱节点及对应的代价值按顺序存储在列表中：[(fs,pre(1)),(f1,pre(2)),...,(f{t-1},pre(t))]，通过倒叙遍历，即从终点开始，沿着前驱结点移动直至起点，得到从起点s到终点t的最优导航路线。
[0044]
在一些可选的实施方式中，状态模型还包括：已等待时间，在步骤s2031之后，方法还包括：获取当前时刻；若当前时刻在限行规定的限行时段内，记录已等待时间并重新计算任一节点对应的代价值。具体地，状态模型s＝(d,t,v,c,w)，w表示已等待时间，用于处理限行规定下的等待问题，即当到达一个限行区域且当前时刻处于限行时间段内时，需要停在该节点等待一段时间(例如n分钟)，以符合限行规定。其他参数详细请参见步骤s2031，在此不再赘述。对于现行规定，在每一个节点的扩展中即计算代价值和前驱节点的过程中，需要考虑当前节点所处的位置是否受到限制条件(限行规定)的影响。示例性地，可以根据当前时刻判断是否符合限行规定。如果当前时刻在限行时间段内，则需要记录已等待时间，并重新计算当前节点的代价值f(node)。本实施例提供的导航路线动态规划方法，在计算节点的代价值及前驱结点时，考虑代价函数如限行规定的影响，从而实现了令最优导航路线满足规则和限制条件的目的。并且代价函数可以根据具体情况进行设置，包含一个或多个规则和限制条件，达到了提高导航路线规划的全面性的效果。
[0045]
在本实施例中提供了一种导航路线动态规划方法，可用于上述的移动终端，如手机、平板电脑、车载终端等，图3是根据本发明实施例的又一导航路线动态规划方法的流程示意图，如图3所示，该流程包括如下步骤：
[0046]
步骤s301，接收起点和终点生成道路网格模型。详细请参见图1所示实施例的步骤s101，在此不再赘述。
[0047]
步骤s302，根据道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代价函数建立状态模型，代价函数为从起点至终点需要满足的规则和限制条件。详细请参见图1所示实施例的步骤s102，在此不再赘述。
[0048]
步骤s303，根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线。详细请参见图1所示实施例的步骤s103，在此不再赘述。
[0049]
步骤s304，获取车辆行驶的实时状态信息。具体地，导航中有些情况无法预测，如交通堵塞、突发事故等，此时可以采用实时动态调整策略进行路线优化。首先需要获取车辆行驶的实时状态信息。
[0050]
步骤s305，根据实时状态信息以及最优导航路线进行反向检查。具体地，根据步骤s304获取的实时状态信息，对于计算出的最优导航路线进行反向检查，查看是否有更优的导航路线。
[0051]
步骤s306，确定实时最优导航路线。具体地，由于车辆行驶的实时状态信息是变化的，如突发的交通堵塞、突发事故等可能使得先前计算的最优导航路线不再最优，因此可根据获取的实时状态信息重新计算实时最优导航路线。提高了导航路线动态规划的实时性和准确性。
[0052]
在一些可选的实施方式中，上述步骤s306包括：根据当前时刻以及限行时段确定最优导航路线对应的车速。具体地，在实际导航中，对限行规定下的等待问题，等待n分钟可以转化成动态控制前进车速，使得到达限行节点时刚好限行时间结束，车辆能够顺利通过，避免进行停车等待。
[0053]
步骤s307，选择实时最优导航路线对应的导航方式。可选地，为实时最优导航路线选择合适的导航方式，导航方式包括：路线规划、语音提示及地图展示等。具体来说，可以利用语音转换技术将文字信息转化为语音提示，并借助地图展示工具向用户展示路线规划结果。本实施例提供的导航路线动态规划方法能够为用户提供更全面、更智能的导航服务，提高导航的效率和安全性。
[0054]
在本实施例中还提供了一种导航路线动态规划装置，该装置用于实现上述实施例及优选实施方式，已经进行过说明的不再赘述。如以下所使用的，术语“模块”可以实现预定功能的软件和/或硬件的组合。尽管以下实施例所描述的装置较佳地以软件来实现，但是硬件，或者软件和硬件的组合的实现也是可能并被构想的。
[0055]
本实施例提供一种导航路线动态规划装置，如图4所示，包括：
[0056]
道路网格模型生成模块401，用于接收起点和终点生成道路网格模型；状态模型构建模块402，用于根据道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代价函数建立状态模型，代价函数为从起点至终点需要满足的规则和限制条件；最优导航路线求解模块403，用于根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线。
[0057]
在一种可选的实施方式中，道路网格模型生成模块包括：栅格地图生成单元，用于基于起点和终点生成预设区域的栅格地图；道路网格模型得到单元，用于将栅格地图中的路口及拐角点作为节点，将栅格地图中的道路或街道作为有向边，得到道路网格模型。
[0058]
在一种可选的实施方式中，最优导航路线求解模块包括：代价值及前驱结点确定单元，用于根据状态模型以及转移函数确定任一节点对应的代价值及前驱结点；最优导航路线确定单元，用于根据目标函数、多个前驱结点以及对应的代价值确定最优导航路线，目标函数为确定最优导航路线的单一目标或多个目标的组合。
[0059]
在一种可选的实施方式中，代价值由转移函数确定，转移函数等于起点至任一节点的实际代价与任一节点至目标节点的预估代价之和。
[0060]
在一种可选的实施方式中，状态模型还包括：已等待时间，代价函数包括：限行规定，装置还包括：当前时刻获取模块，用于获取当前时刻；重计算模块，用于若当前时刻在限行规定的限行时段内，记录已等待时间并重新计算任一节点对应的代价值。
[0061]
在一种可选的实施方式中，装置还包括：实时状态信息获取模块，用于获取车辆行驶的实时状态信息；反向检查模块，用于根据实时状态信息以及最优导航路线进行反向检查；实时最优导航路线确定模块，用于确定实时最优导航路线；导航方式选择模块，用于选择实时最优导航路线对应的导航方式。
[0062]
在一种可选的实施方式中，实时最优导航路线确定模块包括：车速确定单元，用于根据当前时刻以及限行时段确定最优导航路线对应的车速。
[0063]
上述各个模块和单元的更进一步的功能描述与上述对应实施例相同，在此不再赘述。
[0064]
本实施例中的导航路线动态规划装置是以功能单元的形式来呈现，这里的单元是指asic(application specific integrated circuit，专用集成电路)电路，执行一个或多个软件或固定程序的处理器和存储器，和/或其他可以提供上述功能的器件。
[0065]
本发明实施例还提供一种计算机设备，具有上述图4所示的导航路线动态规划装置。
[0066]
请参阅图5，图5是本发明可选实施例提供的一种计算机设备的结构示意图，如图5所示，该计算机设备包括：一个或多个处理器10、存储器20，以及用于连接各部件的接口，包括高速接口和低速接口。各个部件利用不同的总线互相通信连接，并且可以被安装在公共主板上或者根据需要以其它方式安装。处理器可以对在计算机设备内执行的指令进行处理，包括存储在存储器中或者存储器上以在外部输入/输出装置(诸如，耦合至接口的显示设备)上显示gui的图形信息的指令。在一些可选的实施方式中，若需要，可以将多个处理器和/或多条总线与多个存储器和多个存储器一起使用。同样，可以连接多个计算机设备，各个设备提供部分必要的操作(例如，作为服务器阵列、一组刀片式服务器、或者多处理器系统)。图5中以一个处理器10为例。
[0067]
处理器10可以是中央处理器，网络处理器或其组合。其中，处理器10还可以进一步包括硬件芯片。上述硬件芯片可以是专用集成电路，可编程逻辑器件或其组合。上述可编程逻辑器件可以是复杂可编程逻辑器件，现场可编程逻辑门阵列，通用阵列逻辑或其任意组合。
[0068]
其中，所述存储器20存储有可由至少一个处理器10执行的指令，以使所述至少一
个处理器10执行实现上述实施例示出的方法。
[0069]
存储器20可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序；存储数据区可存储根据计算机设备的使用所创建的数据等。此外，存储器20可以包括高速随机存取存储器，还可以包括非瞬时存储器，例如至少一个磁盘存储器件、闪存器件、或其他非瞬时固态存储器件。在一些可选的实施方式中，存储器20可选包括相对于处理器10远程设置的存储器，这些远程存储器可以通过网络连接至该计算机设备。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
[0070]
存储器20可以包括易失性存储器，例如，随机存取存储器；存储器也可以包括非易失性存储器，例如，快闪存储器，硬盘或固态硬盘；存储器20还可以包括上述种类的存储器的组合。
[0071]
该计算机设备还包括输入装置30和输出装置40。处理器10、存储器20、输入装置30和输出装置20可以通过总线或者其他方式连接，图5中以通过总线连接为例。
[0072]
输入装置30可接收输入的数字或字符信息(如导航的起点和终点)，以及产生与该计算机设备的用户设置以及功能控制有关的键信号输入，例如触摸屏、小键盘、鼠标、轨迹板、触摸板、指示杆、一个或者多个鼠标按钮、轨迹球、操纵杆等。输出装置40可以包括显示设备、辅助照明装置(例如，led)和触觉反馈装置(例如，振动电机)等。上述显示设备包括但不限于液晶显示器，发光二极管，显示器和等离子体显示器。在一些可选的实施方式中，显示设备可以是触摸屏。
[0073]
本发明实施例还提供了一种计算机可读存储介质，上述根据本发明实施例的方法可在硬件、固件中实现，或者被实现为可记录在存储介质，或者被实现通过网络下载的原始存储在远程存储介质或非暂时机器可读存储介质中并将被存储在本地存储介质中的计算机代码，从而在此描述的方法可被存储在使用通用计算机、专用处理器或者可编程或专用硬件的存储介质上的这样的软件处理。其中，存储介质可为磁碟、光盘、只读存储记忆体、随机存储记忆体、快闪存储器、硬盘或固态硬盘等；进一步地，存储介质还可以包括上述种类的存储器的组合。可以理解，计算机、处理器、微处理器控制器或可编程硬件包括可存储或接收软件或计算机代码的存储组件，当软件或计算机代码被计算机、处理器或硬件访问且执行时，实现上述实施例示出的方法。
[0074]
虽然结合附图描述了本发明的实施例，但是本领域技术人员可以在不脱离本发明的精神和范围的情况下做出各种修改和变型，这样的修改和变型均落入由所附权利要求所限定的范围之内。

技术特征：
1.一种导航路线动态规划方法，其特征在于，所述方法包括：接收起点和终点生成道路网格模型；根据所述道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代价函数建立状态模型，所述代价函数为从起点至终点需要满足的规则和限制条件；根据目标函数、转移函数以及所述状态模型求解起点至终点对应的最优导航路线。2.根据权利要求1所述的导航路线动态规划方法，其特征在于，所述接收起点和终点生成道路网格模型，包括：基于起点和终点生成预设区域的栅格地图；将所述栅格地图中的路口及拐角点作为节点，将所述栅格地图中的道路或街道作为有向边，得到道路网格模型。3.根据权利要求1所述的导航路线动态规划方法，其特征在于，所述根据目标函数、转移函数以及所述状态模型求解起点至终点对应的最优导航路线，包括：根据所述状态模型以及转移函数确定任一节点对应的代价值及前驱结点；根据目标函数、多个前驱结点以及对应的代价值确定最优导航路线，所述目标函数为确定最优导航路线的单一目标或多个目标的组合。4.根据权利要求3所述的导航路线动态规划方法，其特征在于，所述代价值由转移函数确定，所述转移函数等于起点至所述任一节点的实际代价与所述任一节点至目标节点的预估代价之和。5.根据权利要求3所述的导航路线动态规划方法，其特征在于，所述状态模型还包括：已等待时间，所述代价函数包括：限行规定，在所述根据所述状态模型以及转移函数确定任一节点对应的代价值及前驱结点之后，所述方法还包括：获取当前时刻；若所述当前时刻在所述限行规定的限行时段内，记录已等待时间并重新计算任一节点对应的代价值。6.根据权利要求5所述的导航路线动态规划方法，其特征在于，在所述根据目标函数、转移函数以及所述状态模型求解起点至终点对应的最优导航路线之后，所述方法还包括：获取车辆行驶的实时状态信息；根据所述实时状态信息以及最优导航路线进行反向检查；确定实时最优导航路线；选择所述实时最优导航路线对应的导航方式。7.根据权利要求6所述的导航路线动态规划方法，其特征在于，所述确定实时最优导航路线包括：根据当前时刻以及限行时段确定最优导航路线对应的车速。8.一种导航路线动态规划装置，其特征在于，所述装置包括：道路网格模型生成模块，用于接收起点和终点生成道路网格模型；状态模型构建模块，用于根据所述道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代价函数建立状态模型，所述代价函数为从起点至终点需要满足的规则和限制条件；最优导航路线求解模块，用于根据目标函数、转移函数以及所述状态模型求解起点至
终点对应的最优导航路线。9.一种计算机设备，其特征在于，包括：存储器和处理器，所述存储器和所述处理器之间互相通信连接，所述存储器中存储有计算机指令，所述处理器通过执行所述计算机指令，从而执行权利要求1至7中任一项所述的导航路线动态规划方法。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机指令，所述计算机指令用于使计算机执行权利要求1至7中任一项所述的导航路线动态规划方法。

技术总结
本发明涉及智能导航技术领域，公开了一种导航路线动态规划方法、装置、计算机设备及存储介质，方法包括：接收起点和终点生成道路网格模型；根据道路网格模型中任意两个节点间的距离、行驶时间、车辆速度及代价函数建立状态模型；根据目标函数、转移函数以及状态模型求解起点至终点对应的最优导航路线。本发明在导航路线规划中考虑从起点至终点需要满足的规则和限制条件如限行规定、拥堵信息等，即在状态模型中引入代价函数，实现了根据目标函数、转移函数及代价函数共同确定最优导航路线的目的，从而可以得到满足规则和限制条件的最优导航路线。提高了导航路线规划的全面性，解决了难以在满足限制条件的同时合理安排行车路线的问题。线的问题。线的问题。


技术研发人员：陈航 程治 王晓晨 柳宇翔
受保护的技术使用者：重庆长安汽车股份有限公司
技术研发日：2023.06.26
技术公布日：2023/10/11