蚁群算法在无人驾驶园区参观路线的应用

郭蓬 张金炜 戎辉 王文扬 高嵩 何佳

摘  要： 针对无人车在中国汽车技术研究中心院区内参观线路的规划问题，提出一种基于蚁群算法参观路线规划的方法。首先利用栅格搭建环境地图，然后通过蚁群算法设置始末位置、构造解空间、更新信息素、增加迭代次数、判断路径长度，最后输出最短路线。文中根据参观要求做出三种不同路径规划方案以验证算法的可行性。

关键词： 无人车; 蚁群算法; 路线规划; 信息表; 栅格地图; 最短路线

中图分类号： TN911.1?34                        文献标识码： A                         文章编号： 1004?373X（2019）11?0149?04

Abstract： A visit route planning method based on ant colony optimization algorithm is presented to solve the planning problem of the visit route of unmanned vehicle in district of China Automotive Technology and Research Center. The grid is used to construct the environment map， and the ant colony optimization algorithm is used to set the beginning and end positions， construct the solution space， update the pheromones， increase the number of iterations， judge the path length， so as to output the shortest route. Three different schemes are made according to visit requirements， which are used to verify the feasibility of the algorithm

Keywords： unmanned vehicle; ant colony optimization algorithm; route planning; pheromone; grid map; shortest route

0  引  言

无人车路径规划是当前无人驾驶领域的关键技术之一。路径规划可以分为全局路径规划和局部路径规划[1]，全局路径规划又称为静态路径规划，它是在环境已知的情况下由初始位置到目标位置寻找一条最优或者近似最优的无碰撞路径。局部路径规划又称为动态路径规划，它是在环境未知的情况下通过感知系统实时感知周围环境做出局部行驶路线。路径规划的算法有很多，大致可以分为五大类：传统路径规划算法（模拟退火法、人工势场法等）[2]、启发式搜索算法（Dijkstra算法、A*算法及其变种等）[3]、离散优化算法（模型预测算法、几何轨线算法等）[4]、随机采样算法（随机路图法、快速随机拓展树法等）[5?6]和智能仿生算法（遗传算法、蚁群算法、神经网络等）[7]。

蚁群算法（ACO）是一种模拟进化算法，又称为蚂蚁算法，是由Dorigo等人提出[8]的，主要是仿照蚂蚁群体在觅食过程中寻找路径，即巢与食物之间的最短路径行为进行路径规划。

本文利用基于蚁群算法的无人车在中国汽车技术研究中心院区内规划参观路线。首先根据实际需要建立环境地图，进而选择初始点和目标点，构造解空间，更新信息素，增加迭代次数，判断路径长度，最后输出最短路线。Matlab仿真实验证明了本文方法的有效性，可用于院区内参观路线的路径规划。

1  问题描述

如图1所示为中国汽车技术研究中心院区，其横向长度为534 m，纵向长度为462 m，道路宽14 m，共有19个试验室，按照参观规定只开放NVH试验室、电磁电气试验室、零部件试验室2、性能开放综合试验室2、汽车安全试验室等五个试验室，图1中[l]为无人车出发位置，②～⑥为试验室停车位置，⑦为出口位置。

图1  中国汽车技术研究中心院区

本文根據具体要求，利用蚁群算法给出三种方案，以验证蚁群算法在院区内规划参观路线的可行性。

方案一：验证蚁群算法是否能够搜索最短路径，采用在任意两个试验室之间寻找最短行驶路线的方法，以验证蚁群算法搜索最短路径的可行性。

方案二：根据参观要求，在特殊情况下仅开放三个试验室，磁电气试验室、汽车安全试验室以及零部件试验室2。利用蚁群算法计算出三个实验室的参观顺序以及最短路线。

方案三：五个试验室全部开放，并且规定NVH试验室为第一个参观的实验室，汽车安全试验室为最后一个参观的实验室，利用蚁群算法计算出五个实验室的参观顺序以及最短路线。

2  蚁群算法

蚂蚁寻找路径不是单只蚂蚁的行为，而是一个群体性的行为。它们互相协作，每只蚂蚁都会在所走的路径上留下信息素（路径长度的倒数）[9?10]，当下一只蚂蚁路过该路径时就会利用信息素做出下一步的判断，并且会释放出自己的信息素，这样就形成了信息素的积累[11]，使得后续蚂蚁可以选择信息素强的路径，随着大量蚂蚁在信息素的作用下不断搜索路径，最终会得到一条最优或者次优路径[12?13]。蚁群算法流程图如图2所示。

1） 构造解空间

采用在二维空间内构建解空间的方法，构造栅格地图，用白色栅格表示可行驶区域，黑色栅格表示障碍物区域，对栅格进行数字标号处理，只有白色栅格才能成为搜索路径的节点，设置出发点和目标点，然后通过选择概率公式选择下一个节点，直至选择到目标点，这样所有经过的栅格就组成了解空间。

图2  蚁群算法流程图

2） 节点选择

每次迭代有[M]只蚂蚁搜索路径，一共经过[N]次迭代，设置出发点为[S]，目标点为[E]，每只蚂蚁选择下一个节点[j]的方法是：计算当前节点[j]与四周节点[i]之间的选择概率[Pi，j]，利用选择概率[Pi，j]选择下一节点。[Pi，j]的计算方法如下：

式中：[i]代表当前节点的周围八个节点数字标号集合;[τi，j]为信息素;[ηi，j]为启发值;[B]为影响因子;[w]表示没有被选择点的集合。

3） 信息素更新

通常有两种信息素更新方法，第一种如式（2）所示，叫做实时信息素更新，即当前蚂蚁在路径搜索中每过一个节点就会对该节点进行信息素更新。本文即采用该方法。

3  仿真实验与验证

本文将蚁群算法应用于无人车院区参观路线的规划中，为验证本文方法的可行性和有效性，采用Matlab进行大量仿真实验。算法运行环境如下：Windows7，64 bit;Matlab，R2017a;处理器Intel[?] Xeon[?] CPU E5?1620;主频3.50 GHz;内存32 GB。

3.1  建立仿真环境

针对无人车参观路线的规划问题，本文需要根据真实环境搭建环境模型。有两大类构建环境模型的方法：一是基于网络或图的模型方法;二是基于网格的模型方法。如前文所述，蚁群算法利用建立栅格图的方法，此方法属于网格模型中的一种。栅格图法结构简单、易于实现，是常用的建模方法。

本文建立25×25的栅格地图，共有625个正方形栅格，按照从左往右、从上到下的顺序对栅格进行1～625编号。白色栅格代表道路，黑色栅格代表建筑物。按照院区实际尺寸规划栅格地图，因为真实道路宽约20 m，所以设计每单位長度栅格表示实际长度20 m，如图3所示。

图3  仿真环境图

3.2  仿真实验一

任意两个试验室之间搜索最短路径。如图4所示，选择两个试验室，NVH试验室和性能开发综合试验室2。选择初始点84号栅格，目标点294号栅格，设置80只蚂蚁，迭代100次，将搜索出的路径进行长度比较选择出最短路径，如图中曲线所示为最短路径。

图4  仿真实验一

3.3  仿真实验二

三个试验室之间选择最短路径，选择电磁电气试验室、零部件试验室2以及汽车安全试验室，在三个试验室之间经过6种不同组合的仿真实验，选择如图5曲线所示路线，参观顺序为起始点、电磁电气试验室、汽车安全试验室、零部件试验室2、出口，此顺序为参观这三个试验室最短行驶路径，其中1号栅格是无人车起始点，609号栅格是无人车出口位置。

图5  仿真实验二

3.4  仿真实验3

五个试验室之间搜索最短路径，按照规定NVH试验室第一个参观，汽车安全试验室最后一个参观，所以共有24种不同组合方式，经过仿真验证，图6曲线所示为最短行驶路径。

图6  仿真实验三

参观顺序为起始点、NVH试验室、电磁电气试验室、零部件试验室2、汽车安全试验室、出口。

4  结  论

本文在院区静态环境下，利用栅格对无人车在院区的行驶环境创建模型图，通过蚁群算法规划出参观线路，得到以下三种实验结论：

1） 利用蚁群算法可以得到参观院区内任意两个试验室的最短路线。

2） 在开放三个试验室的情况下，通过6组实验可得到正确的参观顺序和最短路径。

3） 在五个试验室全部开放的情况下，通过24组实验可得到正确的参观顺序和最短路径。

实验仿真结果证明，蚁群算法可用于中汽中心院区三种参观需求的全局路径规划。后续拟将基于蚁群算法的全局路径规划和局部路径规划进行结合算法开发并上车进行实际运行。

参考文献

[1] 孙梅.移动机器人路径规划技术综述[J].山东工业技术，2016（21）：164.

SUN Mei. Overview of path planning technology for mobile robots [J]. Shandong industrial technology， 2016（21）： 164.

[2] 霍凤财，任伟建，刘东辉.基于改进的人工势场法的路径规划方法研究[J].自动化技术与应用，2016，35（3）：63?67.

HUO Fengcai，  REN Weijian， LIU Donghui. Research on path planning method based on improved artificial potential field method [J]. Automation technology and application， 2016， 35（3）： 63?67.

[3] ZHANG L， SUN L， ZHANG S， et al. Trajectory planning for an indoor mobile robot using quintic Bezier curves [C]// 2015 IEEE International Conference on Robotics and Biomimetics. Zhuhai： IEEE， 2015： 757?762.

[4] CHU K， LEE M， SUNWOO M. Local path planning for off?road autonomous driving with avoidance of static obstacles [J]. IEEE transactions on intelligent transportation systems， 2012， 13（4）： 1599?1616.

[5] 余卓平，李奕姗，熊璐.无人车运动规划算法综述[J].同济大学学报（自然科学版），2017，45（8）：1150?1159.

YU Zhuoping， LI Yishan， XIONG Lu. Unmanned vehicle motion planning algorithm review [J]. Journal of Tongji University （Natural Science Edition）， 2017， 45（8）： 1150?1159.

[6] 孙丰财，张亚楠，史旭华.改进的快速扩展随机树路径规划算法[J].传感器与微系统，2017，36（9）：129?131.

SUN Fengcai， ZHANG Yanan， SHI Xuhua. Improved rapid expansion of random tree path planning algorithm [J]. Transducer and microsystem technologies， 2017， 36（9）： 129?131.

[7] 于树科，瞿国庆，祁宏宇，等.蚁群遗传融合算法在移动机器人路径规划中的应用[J].火力与指挥控制，2017，42（12）：88?91.

YU Shuke， QU Guoqing， QI Hongyu， et al. Application of ant colony genetic fusion algorithm in mobile robot path planning [J]. Fire control and command control， 2017， 42（12）： 88?91.

[8] 王志中.基于改进蚁群算法的移动机器人路径规划研究[J].机械设计与制造，2018（1）：242?244.

WANG Zhizhong. Based on improved ant colony algorithm for mobile robot path planning study [J]. Journal of mechanical design and manufacturing， 2018（1）： 242?244.

[9] HASSAN S， YOON J. Virtual maintenance system with a two?staged ant colony optimization algorithm [C]// 2011 IEEE International Conference on Robotic and Automation. Shanghai： IEEE， 2011： 931?936.

[10] DENG Yan， HU Hongyu， TIAN Xiaolu， et al. A path planning method for substation laser inspection robot based on improved ant colony algorithm [C]// The 2nd International Conference on Computer Engineering， Information Science & Application Technology. [S.l.]： Atlantis Press， 2017： 62?69.

[11] ESCARIO J B， JIMENEZ J F， GIRON?SIERRA J M. Ant co?lony extended： experiments on the traveling salesman problem [J]. Expert systems with applications，2015， 42： 390?410.

[12] ERIN B， ABIYEV R， IBRAHIM D. Teaching robot navigation in the presence of obstacles using a computer simulation program [J]. Procedia： social and behacioral sciences， 2010， 2（2）： 565?571.

[13] 史恩秀，陈敏敏，李俊，等.基于蚁群算法的移动机器人全局路径规划方法研究[J].农业机械学报，2014，45（6）：53?57.

SHI Enxiu， CHEN Minmin， LI Jun， et al. Study on global path planning for mobile robot based on ant colony algorithm [J]. Transactions of the Chinese society of agricultural machi?nery， 2014， 45（6）： 53?57.

[14] 胡玉文.城市环境中基于混合地图的智能车辆定位方法研究[D].北京：北京理工大学，2014.

HU Yuwen. Hybrid map based localization method for unmanned ground vehicle in urban scenario [D]. Beijing： Beijing Institute of Technology， 2014.