基于蚁群算法的无人设备路径规划∗

孙雨婷 杨纱纱 高新春

（1.江苏科技大学电子信息学院 镇江 212003）（2.江南造船（集团）有限责任公司 上海 201913）

1 引言

随着城市建设的发展，越来越多的科技园区正在兴起［1］，因此如何解决园区内的交通问题是十分迫切的。在园区内需要大量的通勤车作为后勤保障，并且园区内可能建有涉及国家机密的企业，因此本文提出自动驾驶汽车的路径规划，可减少与企业无关的人员进入园区，减少意外的发生。

无人驾驶汽车是一种通过电脑系统实现无人驾驶的智能汽车。在互联网时代正得到长足的发展，无人驾驶汽车利用多种传感器、定位导航系统以及人工智能算法，自动安全的实现汽车驾驶［2］，而自动驾驶汽车中的路径规划决策功能则为自动驾驶车辆研究中最基础以及最关键的内容［3］。

国内外学者已经做出了很多的研究与发展。陈卫等人在蚁群算法应用在自动捡球机器人路径规划算法中取得了一定的成果［4］；杜鹏桢，唐振民等研究了一种面向对象的多角色蚁群算法及其旅行商问题求解的解决方案，并进行仿真实验［5］；李巧玲对蚁群算法做出了改进，实现了对制造系统的物流配送路径的优化［6］；王红军等借助改进的并行蚁群算法实现了设施温室机器人的多点路径规划［7］；Châari I等采用了新的启发函数，使得算法的全局搜索能力更强，但限制了算法的精度与收敛速度［8］。

本文基于蚁群算法，提出园区内通勤车自动驾驶路径规划方案，首先根据园区内通勤车停靠站点建立环境地图，根据欲乘车人员所选择的站点结合环境地图构造解空间，更新算法参数进行迭代，最终输出最短路径进行驾驶。

2 问题描述

以图1所示的某地图为例，图中箭头所指为通勤车的起点站与终点站，途中星星所示为通勤车沿途的停靠站。可见，若不行驶过无人候车的站点，不仅可以节约车上乘客的时间，也节约了通勤车的能源，减少道路的拥挤情况。在园区内各个站点均设有压力传感装置，当压力传感装置检测到站台有人候车时，则立即向正在行驶的通勤车发出信号，通勤车收到站台的信号后开始进行路径规划计算，以最短的路径行驶去搭载乘客。车辆在站台停靠等待乘客上车时，利用此段时间进行此段行驶时间内收到的有乘客的站台信息，并进行路径规划，使用统筹学的原理尽量减少乘客的等待时间。为保证通勤车不会一直在部分站点之间徘徊，规定当车辆驶过此站点后，不再对此站点进行新的路径规划，即当通勤车A驶过1号站点后，若压力传感装置检测到1号站台有乘客，此时通勤车A不会返回去搭载1号站台的乘客，乘客需等待下一辆通勤车。为保障行车安全防止出现安全事故，在同一路段每次仅有一辆通勤车在路上行驶。通勤车行驶时的起点和终点均为固定的停车场，方便通勤车进行停放和检修等操作。

图1 某地图与停靠站

3 蚁群算法

3.1 蚁群算法原理

昆虫学家在研究蚂蚁的蚁群算法是由意大利学者Dorigo M提出的一种模仿蚂蚁寻觅食物的新兴群智能算法［9～10］，在后续的研究中，其他学者又将此算法运用在了旅行商问题（traveling salesman problem，TSP）的求解上［11～12］。该方法利用蚂蚁在路上留下的信息素含量来判断的优化程度，具有正反馈与分布协作式的特点，有较强的鲁棒性，易与其他算法结合［13］。

通勤车在园区内行驶类似于旅行商问题，基本蚁群算法求解TSP的方式如下，初始时刻有m个蚂蚁随机分布，并保证没有蚂蚁在同一位置，蚁群须经历n个城市［14］，dij（i，j=1，2，3，…，n）表示不同城市i与j间的距离，且记城市i与城市j在t时刻二者路径上的信息素的浓度为τij（t），而第k（k=1，2，3，…，m）个蚂蚁从城市i向城市j走访的关键因素是状态转移概率Pkij，状态转移概率Pkij由多个参数综合计算得来［15］，计算公式为式（1）：

其中allowk（k=1，2，3…，m）表示了蚂蚁k需要走过的城市的集合［16］；ηij(t)代表了蚂蚁在城市i向城市j移动的期望值，其是按照自身的适应性定义的一种启发式函数ηij=1/dij；α的值越大，城市路径间信息素越重要，β的值越大，启发函数对城市选择的影响越大；taubk表示蚂蚁禁忌表，禁忌表能够跟随蚂蚁的行走进行更新记录，克服了真实环境下蚁群不能实时更新的不足［17］。

信息素在环境找中是存在挥发现象的，为了模仿蚂蚁在进行城市中转移时路径上的信息素持续挥发的状态［18］，在路径信息计算时加入了挥散因子ρ对路径上的信息素进行优化和更新，这样可以减少路径上的信息素持续累计过高带来的影响，ρ一般取0～1之间的值。

当全部的蚂蚁实现了完成了一次完整的城市走访后，计算更新所有城市间的信息素的值［19］，如式（2）：

3.2 算法实现

采用图2的算法流程进行路径规划。

图2 算法流程

4 实验分析

本文将蚁群算法应用于科技园区内无人驾驶通勤车行驶路径的规划中，使用Matlab进行算法仿真实验，算法仿真的环境为Windows 10，64bit；Matlab 2014a，处理器为inter core i7；主频2.8GHz；内存为16.0GB。

目前较为常用的两大类构建仿真环境的方法，一是基于网格的方法，二是基于网路或图的方法。本文采用栅格法属于基于网格模型，栅格法结构较为简单并且易于实现，是比较常用的模型环境［21］。

4.1 环境建立

本文建立20*20共400格的栅格地图，在Mat⁃lab中按顺序使用矩阵对栅格进行初始化，黑色栅格表示建筑物，白色栅格表示道路，如图所示，通勤车的始发站处于1号栅格，终点站处于400号栅格，在85号栅格，237号栅格，305号栅格均设有站点，图3中浅色色块所示。

4.2 不邻近站台仿真实验

在任意两个不邻近站台之间搜索最短路径。如图3所示，选择两个不邻近站台，初始点选为85号栅格，终点选为237号栅格，派出50只蚂蚁，共100波次，图4为搜索出的最短路径。

图3 道路和建筑初始化

图4 某不邻近站台的路径规划

4.3 邻近站台仿真实验

在任意两个邻近站台之间搜索最短路径。如图5所示，选择两不邻近站台，初始点选为1号栅格起点站，终点选为85号栅格，派出50只蚂蚁，共100波次，图5所示为搜索出的最短路径。

图5 某邻近站台的路径规划

4.4 全部站台仿真实验

当全部站台均有乘客时，通勤车行驶模式仅在有乘客候车的最近的两个站台间进行路径规划，当全部站台均有乘客时，通勤车将从起始站开始在两两站台间进行路径规划，最终合成结果图如图6所示。派出50只蚂蚁，共100波次。

图6 全部站台均有乘客图

4.5 仅首尾站台仿真实验

仅在起点处有乘客乘车，此时通勤车行驶的线路最短。如图7所示，此时的收敛曲线如图8，可见算法较快达到收敛并保持稳定。

图7 最短路径

图8 收敛曲线

5 结语

本文阐述了蚁群算法的原理，并分析了蚁群优势与缺陷，将蚁群算法应用在无人驾驶的通勤车的路径规划上，并基于栅格法建立仿真环境进行模型仿真。仿真表明算法可用于科技园区内无人驾驶的通勤车进行搭载乘客的路径规划，实验表明本文方法具有一定的可靠性和实时性。规划的路径在转弯处离建筑物较近，在实际应用中可能存在危险，计划在后续工作中将其作为工作方向。