基于Floyd算法的无人驾驶汽车路径规划模型

吴梓乔，苏越

（长安大学汽车学院，陕西 西安 710064）

前言

近些年来，随着互联网产业的迅速发展，传统的以人为主导操纵汽车的理念受到了极大冲击，汽车的智能化发展已成为时代需求，汽车与互联网的紧密结合已成为一个无法避免的趋势。其中，无人驾驶技术便是最耀眼也是相对较为成熟的一个代表，自从1970年于美国提出无人驾驶的概念后，研发进展十分迅速，各项试验都取得了瞩目的成就。但是与此同时，无人驾驶技术仍有不少问题亟待解决。其中，如何在没有驾驶员操纵的条件下，自动寻找最佳的行驶路径到达目的地，便是一个较为突出的问题，无论是对于无人驾驶进行的可行性还是经济性，这都是一个需要克服的问题。

1 驾驶路径规划

1.1 路径设计

在一般情况下，为了找到一条符合实际情况的最佳路径，我们需要综合行驶距离、道路质量、交通状况等多类因素进行综合考虑。这类问题属于多目标优化问题的一种，在复杂的道路情况下很难建立一个合适的模型来综合考虑所有的变量。因此，从简化问题的角度上出发，可以选取其中最为重要的一个因素来进行考虑，将该问题转换为单目标优化。显然，若要寻找一个最能体现最佳的变量，无论是从成本还是从所需的时间上来综合考虑，走最短的路径是最佳的。因此可以将驾驶路径理解为行走最短路径，解决方案即为寻找最短路径。

常用的路径规划算法有Dijkstra算法、Floyd算法、SPFA算法、最佳优先算法（BFS）、A*算法。考虑到Floyd算法适用范围的广泛性，以及在稠密图上，运行效率要高于执行V次Dijkstra算法，也要高于执行V次SPFA算法。因此，本文主要讨论以Floyd算法为基础的无人驾驶汽车路径规划。

1.2 Floyd算法

Floyd算法是一种利用动态规划的思想来寻求加权图中任意节点之间的最短路径的算法[1]，与Dijkstra算法相似，但时间复杂度要高于Dijkstra算法。Floyd算法可以解决正确处理有向图的最短路径问题，允许图中带有负权值的边，但不允许包含带有负权值边组成的回路[2]。对于在以距离为变量的背景下，该方案完全可以适用。

2 路径规划模型

2.1 模型的建立

假设在一个环境中，一共有n个路口，每一个路口都与数量不定的其余路口相连接，在这里引入两个概念，一个是距离矩阵D，一个是路径矩阵P，二者都是n×n的矩阵。

距离矩阵 D中的 d(i,j)表示 i,j路口间的距离，其中i=(1,2,3,...,n)，j=(1,2,3,...,n)：

路径矩阵P中的path(i,j)代表i通往j经过的路口, 其中i=(1,2,3,...,n)，j=(1,2,3,...,n)：

从对路径矩阵P的分析中可以发现，现有的路径方案仅有直通的两个路口，i→j，并没有一个中间的过渡路口，显然这是不成立的。因此，必须要至少引入一个过渡路口 k，即 i→k→j才引入了中转。在没引入一个新的路口后，刷新原有的路径矩阵D与距离矩阵P的信息，如此迭代n次后，便得到了最终的任意两点间最短间距以及方案。

因此，Floyd算法一共分为以下几个步骤：

第一步：根据已有数据得到初始距离矩阵D与路径矩阵P，其中 d(i,j)为已知 i与 j路口最短距离，path(i,j)为从 i→j经过的路口；

第二步：更新矩阵信息。引入新的路口k，如果d(i,k)+d(k,j)＜d(i,j)，则 d(i,j)= d(i,k)+d(k,j),path(i,j)=path(i,k)；

第三步：如果d(i,j)＜0，则停止，否则k=k+1后返回第二步继续进行迭代，直至k=n。

2.2 Floyd算法利用matlab的求解[3]

以如下路况为例说明：

图1 路径选择模型

初步计算得到初始距离矩阵D与路径矩阵P：

引入新的路口k，利用matlab采用三层循环结构进行迭代处理：

for k=1:n

for i=1:n

for j=1:n

if D(i,k)+D(k,j)＜D(i,j)

D(i,j)=D(i,k)+D(k,j);

path(i,j)=path(i,k);

end

end

end

end

最终得到起始点到目标点的最短距离为19，途中经历的路径为1→3→4→5→7。

2.3 模型评价

该模型在仅考虑行驶距离的条件下具有很高的参考价值，在每一次计算中都可以得到一个确定的结果，自动规划出最短路径以及行驶方案，计算效率相对较高。此外，该模型也有较为灵活的一点，在某条道路封闭后，

初始条件改变下，可以将这条道路与其余路口的距离定义为∞，重新计算，规划处新路线，符合实际情况。

但与此同时，该模型的弊端也非常明显，在路径选择时，无法综合考虑其他的因素，仅能单方面的考虑行驶的距离，无法给出一个理想最佳的路径，不可以单一地应用在路径规划上。

3 小结

本文利用了Floyd算法，以matlab进行求解线路求解为例，描述了无人驾驶汽车的路径规划上，以行驶距离最短为目标的路径。在一定程度上，具有可观的参考价值。但是无法综合更多的因素进行考虑，在实际生活中还无法直接应用，只能作为一定意义上的参考。

无人驾驶技术应用于实际生活中还有很长的一段路要走。在接下来的发展中，关于其路径规划问题，未来的发展必须要结合实际中的多类情况来进行综合处理，进行多目标优化计算。

参考文献

[1] 张熙.基于网络测量的互联网路由优化系统的设计与实现[D].北京邮电大学,2014.

[2] 石松.基于城市路网的浮动车数据处理与应用[D].北京邮电大学,2015.

[3] 王海英,黄强,李传涛,褚宝增.图论算法及其 MATLAB实现[M].北京航空航天大学出版社,2010,22.