主页 > SEO算法 > 【车仔你懂得】导航路径规划知多少?

【车仔你懂得】导航路径规划知多少?

admin SEO算法 2020年03月20日

  大家好,【车仔你懂得】又双叒叕和大家见面了,上周我们一起畅谈了《高精度导航到底谁说了算》,大家都已经明确,未来无论是自动驾驶还是车联网的方方面面,都依赖于高精度地图。高精度地图,实现所有导航功能的先决条件。那么问题来了,在地图数据上,我们的路径是如何被规划的呢?为何地图软件会知道那些路用时最短,那些路不会堵车呢?请大家随车仔一起看下去。

  一般情况下,路径规划主要功能是搜索起止点之间的最优路径。注意,路径规划并不一定寻找最短路径,路径规划有一套系统的衡量指标——时间最短、距离最短或者时间/距离综合等等。

  发展至今,导航路径规划已经不仅仅限于以上三类,随着技术发展逐渐能够满足人们多种个性化的导航需求,实际上生活中我们还会体验到如下的导航技术:

  实际上,路径规划是根据一定需求在地图上进行路线选择。红绿灯少,是一种导航需求,随着移动互联网和大数据发展,这类导航需求将逐渐被满足,但是万变不离宗,所有导航需求,归根结底,还是在讨论距离和时间的问题。

  计算:导航引擎在得到目的地与自身位置信息后,就需要根据地图,选择算法,计算出最优的路径。

  按照算法,路径规划可以区分为静态路径规划和动态路径规划,静态路径规划算法的研究已经比较成熟,但目前在终端上的路径规划,当路程很长时,有时仍然存在资源利用率高,系统响应慢等问题。因此,目前我们日常基础到的基本上是动态路径规划。

  实际上,路径规划有很多算法,在导航中,经常提到的就是Dijkstra算法和A*算法。

  Dijkstra算法,中文译名为迪杰斯特拉算法,是由荷兰计算机科学家狄克斯特拉于1959年提出的。从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

  A*算法是导航路径计算中的标准算法。它比Dijkstra算法多了一个估算函数,若估算函数为0,A*算法也就退化为Dijkstra算法。

  但在一般的嵌入式硬件上,基于性能和内存的限制与要求,不能直接使用A*算法计算路径。所以,也有很多改进的方法。

  1.应用地图数据分层的思想,简化地图中道路的网络结构,也能提高路径规划的性能;

  2.起始点与目的地的方向考虑进去,扩展时,有方向性进行扩展,可以大大减少计算量和存储空间;

  3.保存曾经的规划记录,也能达到快速检索的能力。Google的地图规划好像就采用的这种思想;

  实际上,平时中长距离的导航路径规划一般都是分层做的。譬如说你要从广州到北京,开车怎么走,当然不可能直接在路上规划吧,这样计算量太大了。比较理想的方法是,我先知道到底要经过多少城市,从每一个城市到下一个城市之间如何走才能用高速连接起来,你需要访问的数据就小得多。当最后约束到一个区那么大的地方的时候,直接上DP还是可以在可接受的时间内做出来的。

  确定目的地,一般地图会显示目的地周边信息,然后点选详细信息,确认导航到次目的地。

  多种路径可选,时间最少,路径最短,不堵车,无收费站,有ETC,少走高速,沿途有休息区,或者必过某个城市等等。图例展示的地图,有一个严重缺陷,就是缺少路况信息,进行实施调整,实际上,从北京到秦皇岛,选择路线,走进京津高速,路况较好,不堵车,有可能比系统默认推荐的路线.好了,林志玲语音为您导航

  现在可以深刻理解,路线规划并不是给出最短路径。随着移动互联网的高速发展,诸如路况信息、本地化服务等需求,将逐渐成为未来路线规划的主要方向——个性化路线规划。不仅如此,路线规划,在未来的自动驾驶等一系列车联网应用场景当中将发挥着绝大作用。小吃培训:http://www.kssyseo.cn

广告位
标签: 三阶矩阵a*算法