浅论车辆路径规划的算法

黄淑彤

摘 要：随着计算机技术、电信技术、智能化的不断进步发展，决定人们出行方式之一的汽车智能化发展得更为迅速，为了辅助驾驶员操控汽车，便利出行，且提升安全性能，研究人员开发了路径规划功能。路径规划属于智能车领域的重要分支之一。本文首先介绍导航系统以路径规划为核心的部分工作原理，再核心介绍了路径规划的两大基本算法，Dijkstra算法和Floyd算法， 最后简单展望了路径规划应用于不同行业带来的益处。

关键词：路径规划;导航系统;迪杰特斯拉算法;弗洛伊德算法

中图分类号：TP273 文献标识码：A 文章编号：1671-2064（2019）03-0032-03

1 路径规划概述

路径规划即在周围有障碍物的环境中，按照一定的评价标准，寻找一条从起始位置到终止位置的无碰撞路径[1]。属于运动规划的一种，与轨迹规划同属于运动规划。其中路径规划包括全局路径规划（也叫静态规划）和局部路径规划（也叫动态规划）[1]。静态规划要储备一切环境信息，以地图查询为主，相对简单。而动态路径规划，即随时根据环境变化更改推荐的路径，再按需求提供最适路径，需要传感器实时传达动点当前所在位置的相关信息[1，3]。

2 运用路径规划的导航系统

车载式导航，即携有全球定位系统功能的工具，能实时定位、检测路况、自动规划路线、进行语音服务通知的一种便捷的车载工具[1]。导航系统为车辆规划路径时离不开路径规划技术，车载导航中的路径规划实际是计算机领域与定位领域共同的产物。导航核心的技术之一就是卫星定位，卫星定位是进行路径规划的基础[1]。以北斗卫星计划的标配为例，卫星定位是基于三球交会原理来工作的，系统需要5颗静止轨道卫星、30颗非静止轨道卫星[2，5]。其中系统中的GEO（即任意两个静止卫星）它们的坐标是已知的，两者各自将半径定为与发出者的距离，通过画第一个圆来形成球面，焦点处即发出者的位置，两者的距离需要与地面进行双向测距，这是通过地面中心接收站与众多卫星的位置交互完成的[2，4]。中心站借助卫星传达过来的电子地图，形成第二个以地球球心为圆心的圆，这时半径是与地面的垂直距离，圆弧的第二个焦点就是用户的二维位置[2，4，5]。这样借助球半径、圆弧焦点等讯息确定下来相应距离，以便位置解算，进而定下坐标位置，最终发送回地面，由导航系统实时接收[4]。有了准确位置后，系统再按照经过卫星覆盖的路况数字地图来分析路径数据，按照一系列路径算法为使用者规划出最适路径。

3 经典的最短路径算法

3.1 Dijkstra算法

在上述的导航系统中，选择出发地和目的地之后，两地之间有许多条可选择的行程路径，但是，由于选择及要求的不同，对应的最佳路径也不同。所以，为了计算出最短路径，前人提出了dijkstra和弗洛伊德基本算法。

dijkstra算法，即通过使路径长度按次序累计从而产生最短路径，路径规划中运用该算法，逐步计算由起点到终点的路途中每个分岔口的之间的最短距离，之后不断累加距离值，且每进行一步都要依赖前一步的最短路径的基础，环环相扣，直到最终将每个岔口的距离都分析全，完整比较后求解得最短路径。再加上其他的考虑因素之后得到的最优路径被提供给驾驶员，这能让使用者在运用路径规划时很大程度享用便利[6，8]。

下面简述dijkstra算法实例：

传统dijkstra算法中要引入两个数组，分别是简单一维数组和二维数组以及一个邻接矩阵如图1。下面给出了一简单的有向图算法工作原理如下：本图共有4个节点v1，v2，v3，v4.现在要寻找到从v1到其他各点的最短距离。在四个点间各自有不同的权值对应不同的距离，运算时需要全部歷遍每个点及每个距离。首先由起点v1开始，算法规定在有向图中，若某一点到本位点，则用0表示，比如该有向图中v1到v1点即本位到本位，用坐标表示（v1，0）。若某一点没有指向另一点的有向线段则用+∞表示比如v1没有指向到v4的有向线段，故在v1的迭代中用坐标表示即（v1，+∞）。从v1到v4每次迭代，都是先找到最小的权值，这个过程需要进行比较，v1到v1为0，一定比正无穷及任何大于零的值小于是迭代1的min值就是0，用双*表示，在下次迭代时就不再改变记录下的坐标了，但下次迭代仍然需要在此基础上加上本值。如图中明显v1只能到v2，第二个min值是5加0，在用双*记录下后，继续查寻第三个min值，由于指向已确定是v1到v4，此时v3到v1是无意义的计算，直接略去，故在权值5的基础上加上3得到的距离值8即为所求值，加*再次如上。按照上述规则我们易知接下来的操作步骤了。等到结束时，为确保每个点都已经检查过了，直接检查集合T即可，若集合T包含了所有需要遍历的元素，那么就可直接看最后一次迭代的值，此例中即为23，最终得出结论：从v1到v4的最短路径值为23，其中经过了v2、v3两个点。该算法完成[6]。

3.2 弗洛伊德算法

前面表1所述的Dijkstra算法是求单源最短路径，即起点已经定下比如v1到其他任意Vx的最短路径，而弗洛伊德算法是可以解决任意两个点的最短路径的一种更方便有利的算法，譬如四个点中可以直接得到V2到V3的最短路径。过程更复杂一点，如下：首先我们需要引入两个邻接矩阵，D矩阵（distance）和一个P矩阵，D这个矩阵能够表示任意两点的距离，另一个P矩阵则表示的是任意两点的最短路径确定下来之后，用于储存路程中间所经过的那些节点。这样不仅距离最短可知，中间经过点也可知了。两个矩阵都采用的（N×N）型，这里的n表示的是节点的个数，即Vx的x的数值。N×N表示的N行×N列将在下面的矩阵中用到。D矩阵中的元素用a[i][j]表示，此处的i和j表示任意值，而i、j的范围都是0到（n-1），因为计算机是从0开始共n项到n-1。故i等于0其实是第一个节点，所以a[0][1]表示的是从节点V1到节点V2的最短距离，在矩阵中则表示第一行第二列对应的坐标值。借鉴上面算法，若两个节点没有指向路径，那么D矩阵中表示为∞而a[m][m]对应的值就是0。为了便于理解，矩阵计算过程用图2表示。首先第一个表格展示了任意两个点的距离值，但是之后的距离值发生了变化，被替代成了最短路径距离，其中计算采用的公式如下：a[i][k-1]+a[k-1][j]<a[i][j]。定义更新次数为k时，k的取值范围是1到n，一共有多少个节点则要更新多少次。由给定的有向图可知当k=4就更新完了，每次变化的其实是k值。下面以第一列为例，当k=1时，进行第一次遍历，要将第一列的每个数与与第一行的每个数都相加一遍看是否比该行该列的坐标值更小，若更小就替换。而i及k的值是范围内的任意值。

如图a[0][0]=0，a[1][0]=∞，a[2][0]=4，a[3][0]=10，各距离值填完表格1之后，我们按照第一行与第一列、第二行与第二列、第三行与第三列、第四行与第四列形成十字交叉结构，交叉点为a[0][0]、a[1][1]、a[2][2]、a[3][3]。定下来值[k-1]之后，再按照公式，比较a[0][1]+a[1][0]=5+∞，而a[1][1]=0。故可知a[0][1]+a[1][0]>a[1][1].经过比较发现还是原来的a[1][1]=0更加小，所以不再改动该数值接着进行a[2][0]+a[0][1]=4+5=9，而原来的a[2][1]=∞，明显9<∞，故求得了新的v3到v2的最短路径9，于是我们将9作为新的a[2][1]的值取代了原来的∞，做了加粗符号，这个新的9也跟着延续用在下一个表格中，这样按照同样的规律相加后比较，依次遍历比较每一个a[i][j-1]+a[i-1][j]的值和a[i][j]的值大小，选择更小的值。在本例中，以a[0][0]为交叉点时，有a[2][1]从∞变成了9，a[3][1]从∞变成了15。K=2，以a[1][1]为交叉点时，有a[0][2]从∞变成了8，有a[3][2]从∞变成了18.k=3，以a[2][2]为交叉点时，有a[1][0]从∞变成了7，a[1][3]从∞变成了18.最终以a[3][3]作为交叉点时，即k取最后的4时，代表最后一次遍历，发现并无交换项，不替换任何值，所以得到的最后一个表格即为最终D矩阵的结果。D矩阵完成后，已经得到各点间的最短距离值了。

接着开始P矩阵，引入b[i][j]作为距离坐标值，其实是a[i][j]在p矩阵中的另一种表示。其对应的公式如下：b[i][j]=b[i][k-1]，这时变化的值是b[i][k-1]，如上述知k仍是变值，仍然是1到n（本例只取到4）的范围。基于D矩阵变化的情况，相应的在P矩阵中做出调整。如上例原始矩阵（即表格1），因为在第一列时j=0，所以定为第一列所有行定位的值都为0，第二列所有行定位的值都为2，第三列所有行定位的值都为3，一直到第N列所有行是N终止（本例只取到N=4）。接下来根据D矩阵中的变化，开始第一次更替，K=1时，对应表格2，由a[2][1]从∞变成了9，故要变化b[2][1]这时由公式知，i=2，b[2][1]就被b[2][1-1]=b[2][0]=0取代了。接着发现K=1时a[3][1]从∞变成了15，相应的b[3][1]就被b[3][1-1]=b[3][0]=0取代了。表格2中已经加粗标示出来了。结束了k=1之后，继续进行k=2，发现K=2时a[0][2]从∞变成了8，相应的b[0][2]就被b[0][2-1]=b[0][1]=1取代了，同时发现K=2时a[3][2]从∞变成了18，相应的b[3][2]就被b[3][2-1]=b[3][1]=0取代了，表格3完成，继续k=3，发现K=3时a[1][0]从∞变成了7，相应的b[1][0]就被b[1][3-1]=b[1][2]=2取代了，且发现K=3时a[1][3]从∞变成了18，相应的b[1][3]就被b[1][3-1]=b[1][2]=2取代了.结束了表格4之后，由于k取最后的值4时，对应在D矩阵中无替换项，所以直接由表格4复制数据之后得到表格5。遍历了所有值之后P矩阵就完成了。

这样经过P矩阵及D矩阵的计算，就直接可求得任意两个点的间距最短是多少，且这个过程中所经历的点位数都很明晰清楚。如图3所示。

4 路径规划的应用

路径规划目前在科技前端颇受重视，现在的主要应用如下：（1）在机器人领域，能保证机器人行动无错，运用路径规划对周围环境进行抽象建模和形象还原，进而确保路径最佳。机器人的伸展机械摆臂运动同样要事先构造运动轨迹，借助路径规划更加精准有序。（2）无人机在空中飞行时，借助路径规划方案的导向在空域中无人机能更高效地适应陌生环境。（3）城市道路网借助路径规划在智能领域的涉猎，同样也收益匪浅，目前城市交通大多数将地标从以前的静止图像换成了如今的电子实时变换屏。（4）在刑事办案方面对于跨省捕获罪犯、排查目标犯罪车辆运动行径等需要耗费大量的工作量，而路径规划帮助警方节约了大量人力物力，成效快，节约了宝贵时间，也带来了巨大便利，给公共治安、警方办案帮助颇多，是真正意义上的便利社会。

参考文献

[1] 张青.导航系统中路径规划的研究[D].武汉科技大学，2008.

[2] 严勇，姚亮亮，李朝辉.北斗卫星导航系统现状及测量中的应用[J].经纬天地，2018（05）：29-32.

[3] 赵学青.导航技术的发展与展望[A].中国指挥与控制学会.2013第一届中国指挥控制大会论文集[C].中国指挥与控制学会：中国指挥与控制学会，2013：3.

[4] 朱照荣.北斗卫星导航系统的发展与应用[A].卫星导航系统应用与繁荣2011[C].中国卫星导航定位协会，2011：3.

[5] 陳军.北斗卫星导航定位系统应用综述[A].中国高科技产业化研究会智能信息处理产业化分会.第九届全国信号和智能信息处理与应用学术会议专刊[C].中国高科技产业化研究会智能信息处理产业化分会：中国高科技产业化研究会，2015：4.

[6] 王运.汽车导航路径规划算法研究[J].汽车实用技术，2017（21）：202-204.