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

2018-05-28吴梓乔苏越

汽车实用技术 2018年9期

吴梓乔，苏越

（长安大学汽车学院，陕西西安 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。