张金炜 王文扬 郭蓬 高嵩

摘  要： 为了实现在障碍物环境下规划出符合无人车行驶曲率并安全避障的路径，提出一种蚁群算法与四次贝塞尔曲线融合的路径规划方法。首先在栅格地图下利用蚁群算法规划出从起始点到目标点的全局最短路径;然后将路径分割成有限个位置点，在每两个点之间生成具有行驶曲率、避障安全距离的贝塞尔曲线;最后形成一条连续的无人车行驶路径。经过仿真验证，证明了此方法的有效性和可行性。

关键词： 路径规划; 蚁群算法; 贝塞尔曲线; 行驶曲率; 避障; 安全距离

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

Unmanned vehicle path planning based on ant colony quartic Bezier curve

ZHANG Jinwei1， 2， WANG Wenyang2， GUO Peng2， GAO Song2

（1. Hebei University of Technology， Tianjin 300132， China;

2. China Automotive Technology & Research Center Co.， Ltd.， Tianjin 300300， China）

Abstract： In order to plan the path conforming to driving curvature and safe obstacle avoidance of unmanned vehicle in the obstacle environment， a path planning method fusing ant colony optimization algorithm and quartic Bezier curve is proposed. The ant colony optimization algorithm is used to plan the global shortest path from the starting point to the target point under the grid map. The path is divided into a finite number of points， and the Bezier curve with driving curvature and safe obstacle avoidance distance is generated between every two points. After that， a continuous unmanned driving path is formed. The effectiveness and feasibility of this method are verified with simulation.

Keywords： path planning; ant colony optimization algorithm; Bezier curve; driving curvature; obstacle avoidance; safe distance

0  引  言

路徑规划[1]是无人驾驶学中一个重要的领域，它的目的是在有障碍物的环境中按照某种优化指标（如路径长度、时间、安全距离等）搜索出一条从出发点到目标点的最优或近似最优的路径。

路径规划算法吸引了国内外众多研究者的广泛研究，现有的方法可以分为五大类，分别是：传统路径规划算法（模拟退火法、人工势场法等）[2]、启发式搜索算法（Dijkstra算法、A*算法及其变种等）[3]、离散优化算法（模型预测算法、几何轨线算法等）[4]、随机采样算法（随机路图法、快速随机拓展树法等）[5?6]和智能仿生算法（遗传算法、蚁群算法、神经网络等）[7]。

蚁群算法又称蚂蚁算法，是一种在图中搜索最优或者次优路线的智能算法。在1992年，MarccDorigo博士提出了蚁群算法[8]，它的主要思想是蚂蚁在搜索食物过程中会形成一定的规则，在这种规则下每只蚂蚁都能沿着相同路径找到食物。

贝塞尔曲线方法是法国工程师Bezier在1962年为了设计汽车车身形状提出的[9]，之后贝塞尔曲线由于具有良好的数学特性而被广泛应用到车辆路径规划领域[10?11]。

1  算法描述

1.1  蚁群算法

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

1.2  贝塞尔曲线

贝塞尔曲线的定义严格依赖于确定该段曲线控制点的个数，[N+1]个顶点可以定义[N]次多项式的曲线。贝塞尔曲线上各点的参数方程为：

2  算法融合的路径规划

算法流程图如图1所示。

图1  融合算法流程图

1） 构造解空间

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

2） 节点选择

每次迭代有[M]只蚂蚁搜索路径，一共经过[N]次迭代，设置出发点[S]，目标点[E]，每只蚂蚁选择下一个节点[j]的方法是：

3） 信息素更新

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

4） 分割路径点

将蚁群算法输出的路径点从起始位置每隔3个点取一个路径坐标，一直取到目标点。每两个路径坐标之间可以通过5个控制点唯一确定平面内一条四阶贝塞尔曲线，如图2所示。

图2  四阶贝塞尔曲线示例图

5） 生成贝塞尔曲线

6） 路径选择

在生成贝塞尔曲线的算法中，设置多个规划方向可以生成若干条路径，以避障安全距离为选择路径的条件，可以从中得到符合要求的路径，如下两点为算法判断逻辑：

① 在路径上每个点与障碍物的距离都大于或等于避障安全距离。

② 若经过条件①选择出来的路径大于一条，则进行长度比较，选择其中最短路径。

3  仿真实验与验证

3.1  建立仿真环境

有两大类构建环境模型的方法：一是基于网络或图的模型方法，二是基于网格模型的方法。本文利用建立栅格图[13]的方法，此方法属于网格模型中的一种。栅格图法结构简单、易于实现，是常用的建模方法。

建立20×20的栅格地图，共有400个正方形栅格，按照从左往右、从上到下的顺序对栅格进行1～400编号。白色栅格代表道路，黑色栅格代表障碍物。如图3所示。

图3  仿真环境图

3.2  蚁群算法的仿真

在20×20的仿真地图中，选择390号位置为起始点，30号位置为目标点，设置80只蚂蚁，迭代200次搜索出最短路径。图4中线条为蚁群算法搜索出的路径，图5为收敛曲线，随着迭代次数的增加，平均路径长度和最小路径长度趋于稳定。

图4  蚁群算法路径图

图5  收敛曲线

3.3  四次贝塞尔曲线的仿真

图6为四次贝塞尔曲线仿真图，仿真中选择390号位置为起始点，147号位置为目标点，设置规划的方向角度为60°，90°和120°，一共生成3条曲线，再设置安全距离为0.5个单位栅格长度，经过3条曲线的长度比较，选择最短路径并符合安全距离要求。

3.4  融合算法的仿真

图7为蚁群算法与贝塞尔曲线结合的路徑仿真图，图中粗实线为蚁群算法搜索的路径，虚线为贝塞尔曲线，灰色线条为两者融合后的路径，经过与图4比较可以看出，此路径符合无人车行驶曲率以及避障安全距离的条件，此次仿真证明了文中方法是优于蚁群算法的路径规划。

4  结  语

有关蚁群算法改进的方法有很多，其中有两大类方法：一类是基于蚁群算法的改进;一类是与其他算法结合的改进。本文采用后一种方法，结合四次贝塞尔曲线，生成具有无人车行驶曲率和避障安全距离的最优路径，并且应用Matlab进行3组仿真实验，经过对比验证了本文方法的有效性和可行性。

图6  贝塞尔曲线仿真图

图7  融合仿真图

参考文献

[1] 杨俊成，李淑霞，蔡增玉.路径规划算法的研究与发展[J].控制工程，2017，24（7）：1473?1480.

YANG Juncheng， LI Shuxia， CAI Zengyu. Research and deve?lopment of path planning algorithm [J]. Control engineering， 2014， 24（7）： 1473?1480.

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

GUO Fengcai， REN Weijian， LIU Donghui. Research on path planning method based on improved artificial potential field method [J]. Automation technology and applications， 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] 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] FUNKE J， THEODOSIS P， HINDIYEH R， et al. Up to the limits： Autonomous Audi TTS [C]// 2012 Intelligent Vehicles Symposium. Alcala de Henares： IEEE， 2012： 541?547.

[10] JOLLY K G， KUMAR R S， VIJAYAKUMAR R. A Bezier curve based path planning in a multi?agent robot soccer system without violating the acceleration limits [J]. Robotics & autonomous systems， 2009， 57（1）： 23?33.

[11] CHOI J W， CURRY R E， ELKAIM G H. Curvature?conti?nuous trajectory generation with corridor constraint for autonomous ground vehicles [C]// The 49th IEEE Conference on Decision and Control. Atlanta： IEEE， 2011： 7166?7171.

[12] 陈成，何玉庆，卜春光，等.基于四阶贝塞尔曲线的无人车可行轨迹规划[J].自动化学报，2015，41（3）：486?496.

CHEN Cheng， HE Yuqing， BU Chunguang， et al. Feasible trajectory generation for autonomous vehicles based on quartic Bezier curve [J]. Acta automatica sinica， 2015， 41（3）： 486?496.

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

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