开发者社区> 开发者学习资源库> 正文

路径规划技术演进之路

简介: 2019杭州云栖大会大师零距离大咖有约,由高德资深地图技术专家杨帆主讲。本文主要围绕技术是什么展开讲解,同时介绍了路径规划技术的演进历程,及技术人的成长主要会遇到深度、广度和系统性等三个问题。

摘要:2019杭州云栖大会大师零距离大咖有约,由高德资深地图技术专家杨帆主讲。本文主要围绕技术是什么展开讲解,同时介绍了路径规划技术的演进历程,及技术人的成长主要会遇到深度、广度和系统性等三个问题。

精彩直播回放

以下为精彩视频内容整理:
所谓路径规划就是在用户选择完起点和终点之后,所提供的一条路径。出行的方式包括自驾、步行、公共交通等。路径规划的主要工作就是针对亿万用户的情况下,在极短的时间内提供给用户一条最优的路线。

一、技术是什么

1.技术的定义

在《技术的本质》这本书中,作者给出了对技术的定义,其中包括三个定义。第一,技术是某种组合。第二,技术的每个组件也是缩微技术。第三,所有技术的本质都是效应与现象。

2.技术的特点

图1.png

如上图所示为一张树状图,但其实可以理解成为网状图,因为不是一个现象只出来一个技术,也可能出现很多技术,并且上层的技术不一定是完全互相隔离的,也有可能是互相依赖的。从图中可以看出,技术有以下三个特点:

  • 技术是有层次结构的,分为高层和底层,这并不代表技术的好坏,而是指技术之间的相互利用。例如制造汽车作为一种技术,其中高层技术是指汽车的三大件,包括底盘、发动机和变速箱,更低层的技术可以理解为是材料学方面的或者是动力学方面的。
  • 技术是模块化的。比如汽车的三大件属于汽车的模块。此外,在程序员写程序设计的时候,模块化是非常实用的。
  • 技术是可以被重构的。重构的含义分为三层,第一层含义是指每一项技术的自身是可以通过自然界或者自身的方式被完善,目前所有的技术都不是完美的。第二层含义是指上层的技术可以通过下层的两个技术的推动得以完善。第三层含义是指可以引用其他技术。

二、为什么有技术

图2.png

技术是为了解决某些问题而存在的。例如,针对架构的重构技术,问题可以分为以下5类:
1.业务诉求。比如双十一大促销活动。
2.协作。比如如何让成百上千的程序员在一起做一项工作。
3.伸缩性。
4.效率。
5.成本。比如用电的费用。

三、路径规划技术演进

图3.png

如上图所示,竖条为路径规划技术的演进历程。Dijkstra为路径规划最经典的算法,也作为后续所有算法的基石。在求最短距离时它是最经典的算法,但是在中国的路径规划或者全球的路径规划中并不适用,因为中国有四千多万条路,假如计算从西藏到黑龙江的路程,在计算机寻址中可能需要遍历几千万次,根据计算机的性能不可能在很短的时间内得出结果,可能需要等待三分钟的时间。这时,需要对其进行优化,并且找到技术的突破点。前人也提供了一些例子,例如Bi-Dijkstra,与Dijkstra相比,Bi-Dijkstra的搜索空间是一个椭圆,而Dijkstra的搜索空间是一个圆。

Dijkstra可以理解为是在不停的寻找最短的路线,有可能最短的路在边上就会走出范围。而A Star是设定了一个方向,必须沿着向终点的方向走,同时增加一个参数使得提高性能。

Multi-Layers是指将道路进行分层,分为底层路网和高层路网。方式是从底层路网到高层路网的升级,比如从村道上升到县道,再从县道上升到国道,直到上升到高速公路。使用一种减枝的方法使得路径规划查找的数目更少,性能更快。直到2010年还一直使用这种方法。此方法解决了性能问题,实现了在几秒钟之内能够提供给用户一条路线。同时也带来了最优路线的选取问题。

CH算法可以理解为全国的路网是由很多条路、边和节点组成的,利用计算机缓存的原理,将两个点之间的距离缓存下来。算法主要是将全国任意两个点之间的距离预先的计算出来,需要时可以通过查找得到,这样做可以减少遍历的边数,使得性能得到极大的提升。大概几毫秒就可以得到任何两点的路线。但是也存在新的问题,实时的关注路况的动态变化是必要的,比如道路拥堵问题。

CBR算法是指道路进行区域化。将全国化分为很多个区域,比如区域可以分为M个入口和N个出口,将M个入口和N个出口的最短距离和最短时间计算出来并且进行缓存。这样就可以找到一条从M1到N3的最短距离。其主要思路是分层,一个省作为一个区域或者一个市作为一个区域视为一层,另一层进行聚合变成几个省或几个市为一个区域,每一层的结果都是递归的。CH算法是一个线性算法,无法实现并行,而CBR则不同,是可以并行运算的,从而可以节约时间。

Cpu-Cahce 是为了设计精巧的数据结构、达到性能的最优化而设计的。随着用户的不断需求,中国的限行问题对时间推衍有着很大的约束,时间推衍问题也是必需要解决的。

高德实现了TDR算法,在业界内处于领先位置。针对对于货车的路径规划是比较复杂的,因为货车的车型需要避让很多的限高杆和限重路段。目前,如何用一套算法解决上述问题,高德提出了RCH算法。

四、技术人的成长

图4.png

技术人的成长主要会遇到深度、广度和系统性三个问题。
首先研究下技术的深度问题。例如,制造汽车的行业必须要会制造发动机和引擎,直到会制造更深层的零件,可以理解为制造的东西越多,深度越深,离原理越近,离原理越近,离其他技术复用的可能性就越大。此时,在遇到新的事物的情况下会比其他人更有优势、更有创新感。

其次针对技术的广度问题,除了自身的技术线还希望理解周边的技术线或者更上层的技术。技术的广度第一个层面可以帮助人们理解日常工作中的上下游,包括理解上游部门、下游部门及兄弟部门的工作进程,使得更好的配合工作,达到最好的优化。周边的部门在技术上做了一个很小的改动,就有可能达到目标。另一层面是指技术的相互使用,因为技术之间是互通的,并且技术的组合产生新的技术会达到意想不到的效果。例如,对于路线规划的技术方面,需要懂得路线规划的算法,并且需要了解路径规划的服务,包括C++服务及Java服务,还需要了解阿里怎样做容灾,因为遇到的问题有可能是相通的,可能还需要了解搜索的技术,这些了解到的技术会在工作中提供非常大的帮助。

最后是关于系统性的概念,是指将了解的技术组织成一个有机的整体,也指技术与技术之间的连接。

版权声明:本文中所有内容均属于阿里云开发者社区所有,任何媒体、网站或个人未经阿里云开发者社区协议授权不得转载、链接、转贴或以其他方式复制发布/发表。申请授权请邮件developerteam@list.alibaba-inc.com,已获得阿里云开发者社区协议授权的媒体、网站,在转载使用时必须注明"稿件来源:阿里云开发者社区,原文作者姓名",违者本社区将依法追究责任。 如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:developer2020@service.aliyun.com 进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
上一篇:开放平台能为开发者带来什么价值? 下一篇:读懂POLARDB不能错过的18篇深度文章!

开发者免费资源中心,技术电子书、会议PPT、论文资料持续供应中

官方博客
官网链接