网易首页 > 网易数码 > 正文

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

0
分享至

(原标题:【车仔你懂得】导航路径规划知多少?)

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



iOS游戏:我们相距十万光年

一、何谓路径规划?

路径规划是指导航中物体从起点移动到终点时在地图上做出路线选择行为。

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

因此,路径规划根据衡量标准,可以大致分为一下类型:

最短路径:只考虑时间,不考虑距离或其他因素;

最快路径:只考虑距离,不考虑时间或其他因素;

50/50路径:同时考虑时间和距离因素。

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

   

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

二、我们导航路线是如何被规划出来的?

从过程上讲,导航路线的确定过程可以拆解成以下步骤:

输入:目的地、当前位置

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

输出:最优路径,或多条备选路径

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

那么,路径规划的算法有哪些?

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

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


Dijkstra算法原理图

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

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

例如:

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

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

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

4.合理优化路网结构,降低参与路径计算的路网规模;

5.合理优化路径规划算法数据结构,提高路径计算效率;

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

三、常见导航路径规划示例

1.打开地图应用,获取定位信息,自动获取出发地


如果定位位置,不是出发地,可以点击路线,手动输入出发地

    2.定位成功后,在搜索栏输入目的地



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

    3.确定进行路线规划


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

4.好了,林志玲语音为您导航


大家镇定点,我要开始导航了

编辑点评:

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

推荐相关阅读:

看脸时代 什么品牌的行车记录仪颜值高

火眼金睛 千万级像素行车记录仪更靠谱

刷脸不好使 行车记录仪还靠高性价比

黑夜地库都不怕 F2.0光圈的记录仪推荐

镜观其变智享行程 2016年智能后视镜横向评测


更多汽车用品资讯请关注车品达人公众号或加入ZOL车品QQ群


别说话,扫我



相关推荐
热点推荐
开国大将持枪回村为父报仇,百余人死在枪口下,邓公得知拍手叫好

开国大将持枪回村为父报仇,百余人死在枪口下,邓公得知拍手叫好

文史新知
2024-03-28 14:34:50
梅西抵达日本后回应缺战香港行比赛:没受伤但还是感觉不舒服,希望能再去香港

梅西抵达日本后回应缺战香港行比赛:没受伤但还是感觉不舒服,希望能再去香港

红星新闻
2024-02-06 13:04:12
A股回落,沪指午后失守3000点

A股回落,沪指午后失守3000点

每日经济新闻
2024-03-28 14:45:14
银行女职员的出轨经历,老公出差不在家,上司赖在家里不肯走

银行女职员的出轨经历,老公出差不在家,上司赖在家里不肯走

马军情感故事
2024-03-27 11:24:58
56岁男子相亲54岁女子,因化浓妆被拒,女子火冒三丈:化妆没毛病

56岁男子相亲54岁女子,因化浓妆被拒,女子火冒三丈:化妆没毛病

鬼谷子思维
2024-03-27 17:43:18
广西俩兄弟花5万买下凶宅,入住后怪事不断,真相让人大跌眼镜

广西俩兄弟花5万买下凶宅,入住后怪事不断,真相让人大跌眼镜

一场奇遇日记
2024-02-22 22:16:16
樊振东击败松岛辉空,陈梦击败帕瓦德,王曼昱击败米特兰姆

樊振东击败松岛辉空,陈梦击败帕瓦德,王曼昱击败米特兰姆

子水体娱
2024-03-28 18:10:05
国足没戏!亚洲8名额被瓜分,18强6队晋级,4队4战全胜,还差日韩

国足没戏!亚洲8名额被瓜分,18强6队晋级,4队4战全胜,还差日韩

小金体坛大视野
2024-03-27 20:04:35
凯特王妃手术后现身,外貌大变,引发网友热议

凯特王妃手术后现身,外貌大变,引发网友热议

可乐谈情感
2024-03-28 15:48:48
世预赛乱了:10分未出线,1分却还活着!国足喜讯:拿7分也能晋级

世预赛乱了:10分未出线,1分却还活着!国足喜讯:拿7分也能晋级

侃球熊弟
2024-03-27 22:30:33
这3人被查,涉及董事长、原党委书记等

这3人被查,涉及董事长、原党委书记等

加油大理
2024-03-28 18:10:08
姚明女儿又胖了!14岁身高190体重超近200斤,网友:这谁敢娶?

姚明女儿又胖了!14岁身高190体重超近200斤,网友:这谁敢娶?

吃瓜局
2024-03-27 15:26:58
王庭凯任天津市纪委书记,衡晓帆任天津市委常委

王庭凯任天津市纪委书记,衡晓帆任天津市委常委

澎湃新闻
2024-03-28 19:20:26
大S自乱阵脚!律师发声帮倒忙连忙删文,台媒曝服药致幻确有其事

大S自乱阵脚!律师发声帮倒忙连忙删文,台媒曝服药致幻确有其事

萌神木木
2024-03-28 12:14:20
前凸后翘在草原上拥抱太阳

前凸后翘在草原上拥抱太阳

农人老寓
2024-03-28 13:37:12
哪一刻让你觉得贫穷限制了你的想象力?网友的分享让人大开眼界!

哪一刻让你觉得贫穷限制了你的想象力?网友的分享让人大开眼界!

沫姐美食记
2024-03-25 15:46:10
李铁案今日开庭时间线:8点30开始   辩护律师谈李铁  预计到下午

李铁案今日开庭时间线:8点30开始   辩护律师谈李铁  预计到下午

直播吧
2024-03-28 15:04:41
司马南主演的电影彻底翻车了

司马南主演的电影彻底翻车了

清晖有墨
2024-03-27 19:19:32
原来他也是癌症已去世!一生未婚无人送终,死后遗产全赠予古天乐

原来他也是癌症已去世!一生未婚无人送终,死后遗产全赠予古天乐

简读视觉
2024-03-03 16:55:03
女主播直接报价格,10000玩一天,最低要一次性支付20天的费用

女主播直接报价格,10000玩一天,最低要一次性支付20天的费用

新游戏大妹子
2024-03-27 11:03:47
2024-03-28 19:54:44

头条要闻

原市委书记一家6人被留置 外甥靠他打招呼做了2亿生意

头条要闻

原市委书记一家6人被留置 外甥靠他打招呼做了2亿生意

体育要闻

疯狂的格林,冲刺的火箭

娱乐要闻

莱昂纳多与25岁新女友互相投喂超恩爱

财经要闻

疯狂!三个城市,三个地王!

科技要闻

小米汽车正式发布

汽车要闻

混动增程双模式 长安UNI-Z售11.79万起

态度原创

本地
手机
亲子
家居
公开课

本地新闻

专访|张伟潮:最年轻的龙头专职制造者

手机要闻

消息称苹果首款折叠屏iPhone推迟至2027年发布

亲子要闻

这3种孩子很难长高个,负责的家长一定要知道 #孩子健康 #疾病科普 #身高

家居要闻

邂逅浪漫,注入柔性的法式基因

公开课

30岁之前,你要学会的13件事情

无障碍浏览 进入关怀版
×