论文部分内容阅读
摘 要：为了进一步提高自主驾驶汽车真实动态环境下快速、准确的自主避障能力，提出了一种基于粒子群参数优化（PSO）的改进蚁群算法（AC）模型实现了对自动驾驶汽车在自动避障时规划路径的全局快速优化分析。首先，建立了自驾车辆的自主避障路径规划模型;其次，利用PSO中粒子间的协作和信息共享模式搜索全局信息;再次，利用全局信息更新策略优化AC的路径搜索能力;最后，采用PSO和AC融合算法求解出最佳的避障路径。仿真结果表明，粒子群算法对蚁群算法模型进行了改进，从而实现了对自驾车辆自主避障路径的快速、准确的实时动态规划。
关键词：自主驾驶汽车;路径规划;蚁群算法;粒子群优化;自主避障
Abstract：In order to further improve the accurate response and fast response ability of autonomous obstacle avoidance in real dynamic environment， an improved AC （ant colony algorithm） model based on PSO （Particle Swarm Optimization） is proposed to realize the global and fast optimization analysis of autonomous obstacle avoidance path planning for self-driving vehicles. Firstly， an autonomous obstacle avoidance path planning model for self-driving vehicles is established; secondly， the global pheromone is searched by using the cooperation and information sharing mode between particles in PSO; thirdly， the global pheromone updating strategy is used to optimize the path searching ability of AC; finally， an innovative way of integrating PSO and AC is used to obtain the optimal path of autonomous obstacle avoidance for self-driving vehicles. The simulation results show that the AC model is improved by PSO to realize the fast and accurate planning of autonomous obstacle avoidance path for self-driving vehicles.
Key words： self-driving vehicle; path planning; ant colony algorithm; particle swarm optimization; autonomous obstacle avoidance
自動驾驶车辆的自主避障已经成为无人驾驶车辆领域的热门话题[1]。为了有效保护自动驾驶车辆行驶状态下的人身和财产安全，许多研究者将人工智能技术和算法应用于自驾车辆的自主避碰和动态路径规划问题之中[2]。其中，蚁群算法在路径规划的应用方面效果尤为突出[3]。
然而，在现实生活中，自动驾驶车辆的自主避障技术尚未得到相关立法和工程技术行业的广泛推广[4]，其主要原因是相关技术尚未达到成熟和可控的水平。蚁群算法是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们发现蚁群在觅食过程中，个体蚂蚁的行为相对简单，但是蚂蚁群体行为却具有一定的智能性。在觅食时，多样性使蚂蚁不会走进死胡同而无限循环，是一种创新能力;正反馈使优良信息保存下来，是一种学习强化能力。两者的巧妙结合使智能行为涌现，如果多样性过剩，系统过于活跃，会导致过多的随机运动，陷入混沌状态;如果多样性不够，正反馈过强，会导致僵化，当环境变化时蚁群不能相应调整。同时，蚁群算法本身存在诸如收敛响应时间长，易于进入局部最优解的问题[5]。单一算法无法独立完美地解决自动驾驶车辆自主避障路径规划的实际应用问题。基于此背景，多种智能算法的结合已成为解决自动驾驶车辆自主避障问题的路径规划的发展趋势。因此，下面本文介绍一种基于粒子群优化的改进蚁群算法。
2.自动驾驶车辆自主避障路径技术路线优化的建立
自动驾驶车辆的自主避障对实时响应和的可控性有很高的要求，因此路径规划评估十分重要。结合PSO算法和AC算法各自的优点，图1给出了自动驾驶车辆自主避障路径规划优化设计的技术设计路线：
自驾车辆自主避障路径的具体技术路线优化：
1.使用PSO算法，构造时空的粒子集合：Ω（pi）（xi，yi，zi，tpi）;
2.建立粒子动态搜索模式，优化粒子适应度函数;
3.通过适应度函数动态调整全局信息素（使用循环迭代）;
4.建立蚁群算法，找出最短路径函数（建立信息素更新方法）;
5.在时空中增加全局信息素干预;
6.通过全局范围信息素的积累和路径优化的迭代工作，得到了自驾车辆自主避障行为的规划路径。
3.基于PSO的改进蚁群自主避障路径优化模型
3.1基于PSO的适应度函数模型 PSO是一种基于种群的随机优化控制技术，受种群行为特征的启发，用于解决优化问题。每个优化问题的潜在解决方案可以被认为是n维搜索空间中的一个点，称为“粒子”。所有粒子都具有由目标函数确定的适应度值，并且每个粒子具有确定其方向和距离的速度。然后粒子跟随当前最优粒子在解空间中搜索。
每个粒子可以被视为n维搜索空间中的搜索个体。粒子的当前位置是相应优化问题的备选解决方案。粒子的飞行过程是个体的搜索过程。粒子的飞行速度可以根据粒粒子向自身的历史最佳位置和邻域或整个群体的历史最佳位置聚集来进行。粒子只有两个属性：速度和位置，速度代表粒子的运动速度，位置代表粒子的运动方向。每个粒子独立搜索的最优解决方案称为独立极值，粒子群中的最优独立极值是当前的全局的最优解。速度和位置不断迭代和更新。最终，获得满足终止条件的最优解。
3.1.1 PSO算法的初始化
PSO用于通过粒子间的协作和信息共享获得满足自行驾驶车辆自主避障的路径规划优化要求时空中最佳的定位点。结合算法更能有效提高求解过程中的收敛速度和最优解精度，找到最优调度方案[6，7]。
粒子的速度矢量和当前时空位置用公式（1）和（2）表示。
（1）
（2）
在公式（1）和（2）中，Vi+1是粒子的速度矢量，Pi+1是时间t时粒子的位置，pbesti代表单粒子的最佳位置，gbesti代表整个群体的实际最佳位置，c0，c1，c2代表路径规划过程中粒子群的调整系数，c0是0到1之间的随机数，c1，c2是0到2之间的随机数. Vi是Vi+1，pbesti-Pi和gbesti-Pi之间的向量和，代表粒子速度的更新受当前速度，感知模式和群体信息的影响。
3.1.2 适应性函数的意义
在自动驾驶车辆自主避障路径优化的背景下，PSO的动态响应适应度函数定义如下[8]。
（3）
在公式（3）中，在时间t，（xp，yp，zp）是粒子的空间坐标，（xS，yS，zS）是起点坐标，（xD，yD，zD）是结束点坐标。
表示从当前位置到终点的p粒子的估计值。 表示从起点到当前位
置的距离之和， 。 Ob代表預测障碍信息量。当 时，Ob很清晰;当 时，Ob比较清晰;当 时，Ob为一般清晰;当 时，Ob相对模糊。
3.2基于AC的全局信息素更新
蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径原理。当蚂蚁在寻找食物来源时，它们会在它们所经过的路径中释放信息素，这是蚂蚁在觅食过程中进行种群交流的一种特性，因此在一定范围内的其他蚂蚁可以检测并因此影响它们未来的行为。当越来越多的蚂蚁通过某些路径时，它们会留下越来越多的信息素，导致信息素浓度增加，从而选择该路径的蚂蚁的概率就会更高，这也会导致在该路径上的信息素浓度增强。该选择过程称为蚂蚁的自催化行为。蚂蚁行走路径用于表示待优化问题的可行解，整个蚁群的所有路径构成了待优化问题的解空间。路径较短的蚂蚁会释放更多的信息素。随着时间的推移，在较短路径上累积的信息素浓度逐渐增加，选择该路径的蚂蚁数量也在增加。
3.2.1 AC的初始化
蚂蚁之间的信息传递是通过称为信息素的物质实现的。通常，AC的信息素累积过程受路径规划更新过程中信息量的影响[9]。
路径优化过程中AC的信息更新方法如公式（4）所示。
（4）
在公式（4）中， 表示循环中路径ij上的信息量的总增量; ρ表示信息的挥发程度，范围从0到1; 表示在此循环中蚂蚁k在路径ij上离开的信息增量; Cf表示在该循环中蚂蚁k在路径ij上留下的信息量的增量相关系数。
3.2.2 全局信息素的动态更新策略
根据PSO在全局时空中的适应性函数，在AC的迭代过程中调整了全局情况下的信息素分布和积累[10]。
通过调整Cf，可以实现信息素累积的全局调度。 Cf的具体形式如下所示。
（5）
在公式（5）中，RBest表示最优规划路径数据，f（pi）min表示粒子群适应性函数的最小值，f（pi）max表示粒子群适应性函数的最大值。 4.仿真分析
为了验证基于PSO优化AC的自动驾驶车辆自主避障路径优化问题的可行性，从规划路径自身优化程度和路径规划的时效性两个维度进行了仿真验证。
4.1规划路径模拟
根据自驾车辆自主避障的路径规划要求，从规划路径的相对优化程度进行比较工作，如图2所示。
如图2所示，由于PSO + AC的复杂度高于AC，在路径规划优化的初始阶段（迭代次数<50），PSO + AC路径规划优化的相对增长率低于AC的。但随着迭代次数的增加，PSO + AC的路径优化度具有明显的优势。当迭代次数在90和130之间时，路径规划使用AC算法一度陷入局部最优解的情况，间接导致AC的路径规划优化的相对程度的降低。
4.2路径规划的及时性模拟
根据自动驾驶车辆自主避障的路径规划要求，对规划路径的时效性进行了比较，如图3所示。
如图3所示，AC算法在最短路径优化的整个过程中频繁波动。相比较而言，PSO + AC算法的波动更加稳定。其主要原因是：在路径规划的早期阶段，PSO被用来驱动AC全局信息素的动态更新策略。同时，在T≈751 ms时，PSO + AC方法接近接近94.5%的最短路径并保持该状态。在T ≈ 792 ms时，AC方法接近最短路径方法达到77.0%并保持该状态。
5.结论
在分析自驾车辆自主避障路径优化的过程中，通过对蚁群算法和粒子群算法分别进行改进，利用两种算法自身优势相结合的方式建立一种蚁群粒子群算法，提高了云计算资源调度效率，解决云计算中资源调度方案优化问题。实验结果表明，该算法所消耗的时间更少，效果更好[11]。PSO与AC的结合解决办法在计算初期的路径规划与避障能力相较于AC单独解决方法偏差较大，得出最优路径所需时间相对较长，但在实际运用中，总体路径规划结果与效率很大程度的优于AC单独解决方式的效果。并且，在路径规划的稳定性上，PSO与AC的结合使自动避障车在避障的成功率方面有了显著的提升。同时，该方法提高了自驾车辆在自主避障过程中对于全局最优路径的搜索能力和避障的准确性。
参考文献：
[1]Polvara R， Sharma S， Wan J， et al. Obstacle Avoidance Approaches for Autonomous Navigation of Unmanned Surface Vehicles[J]. Journal of Navigation， 2017， 71（1）：1-16.
[2]Lee U， Yoon S， Shim H C， et al. Local path planning in a complex environment for self-driving car[C]// IEEE International Conference on Cyber Technology in Automation. 2014.
[3]Jie C， Fang Y， Tao J. Path planning under obstacle-avoidance constraints based on ant colony optimization algorithm[C]// IEEE International Conference on Communication Technology. 2018.
[4]Larson J， Bruch M， Ebken J. Autonomous Navigation and Obstacle Avoidance for Unmanned Surface Vehicles[J]. Proceedings of SPIE - The International Society for Optical Engineering， 2006， 6230：623007-623007-12.
[5]朱宏伟， 游晓明， 刘升. 基于粒子群参数优化的同构双种群蚁群算法[J]. 测控技术， 2007， 33（3）：279-285.
[6]Li G， Chou W. Path planning for mobile robot using self-adaptive learning particle swarm optimization[J]. Science China Information Sciences， 2018， 61（5）：052204.
[7]El-Shorbagy， M.A， Hassanien A E. Particle Swarm Optimization from Theory to Applications[J]. International Journal of Rough Sets and Data Analysis， 2018， 5.
[8]譚冠政， 贺欢， Sloman A. 基于ACS算法的移动机器人实时全局最优路径规划[J]. 自动化学报， 2019，001-009
[9]粒子群蚁群结合算法在车辆调度问题中的应用研究[J]. 陈磊. 湖北工业大学学报. 2016（05）
[10]Wu J， Chen B， Kai Z， et al. Ant pheromone route guidance strategy in intelligent transportation systems[J]. Physica A Statistical Mechanics & Its Applications， 2018， 503：S0378437118301225.
[11]萨日娜. 基于蚁群粒子群优化算法的云计算资源调度方案[J]. 吉林大学学报（理学版）. 2017（06）
关键词：自主驾驶汽车;路径规划;蚁群算法;粒子群优化;自主避障
Abstract：In order to further improve the accurate response and fast response ability of autonomous obstacle avoidance in real dynamic environment， an improved AC （ant colony algorithm） model based on PSO （Particle Swarm Optimization） is proposed to realize the global and fast optimization analysis of autonomous obstacle avoidance path planning for self-driving vehicles. Firstly， an autonomous obstacle avoidance path planning model for self-driving vehicles is established; secondly， the global pheromone is searched by using the cooperation and information sharing mode between particles in PSO; thirdly， the global pheromone updating strategy is used to optimize the path searching ability of AC; finally， an innovative way of integrating PSO and AC is used to obtain the optimal path of autonomous obstacle avoidance for self-driving vehicles. The simulation results show that the AC model is improved by PSO to realize the fast and accurate planning of autonomous obstacle avoidance path for self-driving vehicles.
Key words： self-driving vehicle; path planning; ant colony algorithm; particle swarm optimization; autonomous obstacle avoidance
自動驾驶车辆的自主避障已经成为无人驾驶车辆领域的热门话题[1]。为了有效保护自动驾驶车辆行驶状态下的人身和财产安全，许多研究者将人工智能技术和算法应用于自驾车辆的自主避碰和动态路径规划问题之中[2]。其中，蚁群算法在路径规划的应用方面效果尤为突出[3]。
然而，在现实生活中，自动驾驶车辆的自主避障技术尚未得到相关立法和工程技术行业的广泛推广[4]，其主要原因是相关技术尚未达到成熟和可控的水平。蚁群算法是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们发现蚁群在觅食过程中，个体蚂蚁的行为相对简单，但是蚂蚁群体行为却具有一定的智能性。在觅食时，多样性使蚂蚁不会走进死胡同而无限循环，是一种创新能力;正反馈使优良信息保存下来，是一种学习强化能力。两者的巧妙结合使智能行为涌现，如果多样性过剩，系统过于活跃，会导致过多的随机运动，陷入混沌状态;如果多样性不够，正反馈过强，会导致僵化，当环境变化时蚁群不能相应调整。同时，蚁群算法本身存在诸如收敛响应时间长，易于进入局部最优解的问题[5]。单一算法无法独立完美地解决自动驾驶车辆自主避障路径规划的实际应用问题。基于此背景，多种智能算法的结合已成为解决自动驾驶车辆自主避障问题的路径规划的发展趋势。因此，下面本文介绍一种基于粒子群优化的改进蚁群算法。
2.自动驾驶车辆自主避障路径技术路线优化的建立
自动驾驶车辆的自主避障对实时响应和的可控性有很高的要求，因此路径规划评估十分重要。结合PSO算法和AC算法各自的优点，图1给出了自动驾驶车辆自主避障路径规划优化设计的技术设计路线：
自驾车辆自主避障路径的具体技术路线优化：
1.使用PSO算法，构造时空的粒子集合：Ω（pi）（xi，yi，zi，tpi）;
2.建立粒子动态搜索模式，优化粒子适应度函数;
3.通过适应度函数动态调整全局信息素（使用循环迭代）;
4.建立蚁群算法，找出最短路径函数（建立信息素更新方法）;
5.在时空中增加全局信息素干预;
6.通过全局范围信息素的积累和路径优化的迭代工作，得到了自驾车辆自主避障行为的规划路径。
3.基于PSO的改进蚁群自主避障路径优化模型
3.1基于PSO的适应度函数模型 PSO是一种基于种群的随机优化控制技术，受种群行为特征的启发，用于解决优化问题。每个优化问题的潜在解决方案可以被认为是n维搜索空间中的一个点，称为“粒子”。所有粒子都具有由目标函数确定的适应度值，并且每个粒子具有确定其方向和距离的速度。然后粒子跟随当前最优粒子在解空间中搜索。
每个粒子可以被视为n维搜索空间中的搜索个体。粒子的当前位置是相应优化问题的备选解决方案。粒子的飞行过程是个体的搜索过程。粒子的飞行速度可以根据粒粒子向自身的历史最佳位置和邻域或整个群体的历史最佳位置聚集来进行。粒子只有两个属性：速度和位置，速度代表粒子的运动速度，位置代表粒子的运动方向。每个粒子独立搜索的最优解决方案称为独立极值，粒子群中的最优独立极值是当前的全局的最优解。速度和位置不断迭代和更新。最终，获得满足终止条件的最优解。
3.1.1 PSO算法的初始化
PSO用于通过粒子间的协作和信息共享获得满足自行驾驶车辆自主避障的路径规划优化要求时空中最佳的定位点。结合算法更能有效提高求解过程中的收敛速度和最优解精度，找到最优调度方案[6，7]。
粒子的速度矢量和当前时空位置用公式（1）和（2）表示。
（1）
（2）
在公式（1）和（2）中，Vi+1是粒子的速度矢量，Pi+1是时间t时粒子的位置，pbesti代表单粒子的最佳位置，gbesti代表整个群体的实际最佳位置，c0，c1，c2代表路径规划过程中粒子群的调整系数，c0是0到1之间的随机数，c1，c2是0到2之间的随机数. Vi是Vi+1，pbesti-Pi和gbesti-Pi之间的向量和，代表粒子速度的更新受当前速度，感知模式和群体信息的影响。
3.1.2 适应性函数的意义
在自动驾驶车辆自主避障路径优化的背景下，PSO的动态响应适应度函数定义如下[8]。
（3）
在公式（3）中，在时间t，（xp，yp，zp）是粒子的空间坐标，（xS，yS，zS）是起点坐标，（xD，yD，zD）是结束点坐标。
表示从当前位置到终点的p粒子的估计值。 表示从起点到当前位
置的距离之和， 。 Ob代表預测障碍信息量。当 时，Ob很清晰;当 时，Ob比较清晰;当 时，Ob为一般清晰;当 时，Ob相对模糊。
3.2基于AC的全局信息素更新
蚁群算法的基本原理来源于自然界中蚂蚁觅食的最短路径原理。当蚂蚁在寻找食物来源时，它们会在它们所经过的路径中释放信息素，这是蚂蚁在觅食过程中进行种群交流的一种特性，因此在一定范围内的其他蚂蚁可以检测并因此影响它们未来的行为。当越来越多的蚂蚁通过某些路径时，它们会留下越来越多的信息素，导致信息素浓度增加，从而选择该路径的蚂蚁的概率就会更高，这也会导致在该路径上的信息素浓度增强。该选择过程称为蚂蚁的自催化行为。蚂蚁行走路径用于表示待优化问题的可行解，整个蚁群的所有路径构成了待优化问题的解空间。路径较短的蚂蚁会释放更多的信息素。随着时间的推移，在较短路径上累积的信息素浓度逐渐增加，选择该路径的蚂蚁数量也在增加。
3.2.1 AC的初始化
蚂蚁之间的信息传递是通过称为信息素的物质实现的。通常，AC的信息素累积过程受路径规划更新过程中信息量的影响[9]。
路径优化过程中AC的信息更新方法如公式（4）所示。
（4）
在公式（4）中， 表示循环中路径ij上的信息量的总增量; ρ表示信息的挥发程度，范围从0到1; 表示在此循环中蚂蚁k在路径ij上离开的信息增量; Cf表示在该循环中蚂蚁k在路径ij上留下的信息量的增量相关系数。
3.2.2 全局信息素的动态更新策略
根据PSO在全局时空中的适应性函数，在AC的迭代过程中调整了全局情况下的信息素分布和积累[10]。
通过调整Cf，可以实现信息素累积的全局调度。 Cf的具体形式如下所示。
（5）
在公式（5）中，RBest表示最优规划路径数据，f（pi）min表示粒子群适应性函数的最小值，f（pi）max表示粒子群适应性函数的最大值。 4.仿真分析
为了验证基于PSO优化AC的自动驾驶车辆自主避障路径优化问题的可行性，从规划路径自身优化程度和路径规划的时效性两个维度进行了仿真验证。
4.1规划路径模拟
根据自驾车辆自主避障的路径规划要求，从规划路径的相对优化程度进行比较工作，如图2所示。
如图2所示，由于PSO + AC的复杂度高于AC，在路径规划优化的初始阶段（迭代次数<50），PSO + AC路径规划优化的相对增长率低于AC的。但随着迭代次数的增加，PSO + AC的路径优化度具有明显的优势。当迭代次数在90和130之间时，路径规划使用AC算法一度陷入局部最优解的情况，间接导致AC的路径规划优化的相对程度的降低。
4.2路径规划的及时性模拟
根据自动驾驶车辆自主避障的路径规划要求，对规划路径的时效性进行了比较，如图3所示。
如图3所示，AC算法在最短路径优化的整个过程中频繁波动。相比较而言，PSO + AC算法的波动更加稳定。其主要原因是：在路径规划的早期阶段，PSO被用来驱动AC全局信息素的动态更新策略。同时，在T≈751 ms时，PSO + AC方法接近接近94.5%的最短路径并保持该状态。在T ≈ 792 ms时，AC方法接近最短路径方法达到77.0%并保持该状态。
5.结论
在分析自驾车辆自主避障路径优化的过程中，通过对蚁群算法和粒子群算法分别进行改进，利用两种算法自身优势相结合的方式建立一种蚁群粒子群算法，提高了云计算资源调度效率，解决云计算中资源调度方案优化问题。实验结果表明，该算法所消耗的时间更少，效果更好[11]。PSO与AC的结合解决办法在计算初期的路径规划与避障能力相较于AC单独解决方法偏差较大，得出最优路径所需时间相对较长，但在实际运用中，总体路径规划结果与效率很大程度的优于AC单独解决方式的效果。并且，在路径规划的稳定性上，PSO与AC的结合使自动避障车在避障的成功率方面有了显著的提升。同时，该方法提高了自驾车辆在自主避障过程中对于全局最优路径的搜索能力和避障的准确性。
参考文献：
[1]Polvara R， Sharma S， Wan J， et al. Obstacle Avoidance Approaches for Autonomous Navigation of Unmanned Surface Vehicles[J]. Journal of Navigation， 2017， 71（1）：1-16.
[2]Lee U， Yoon S， Shim H C， et al. Local path planning in a complex environment for self-driving car[C]// IEEE International Conference on Cyber Technology in Automation. 2014.
[3]Jie C， Fang Y， Tao J. Path planning under obstacle-avoidance constraints based on ant colony optimization algorithm[C]// IEEE International Conference on Communication Technology. 2018.
[4]Larson J， Bruch M， Ebken J. Autonomous Navigation and Obstacle Avoidance for Unmanned Surface Vehicles[J]. Proceedings of SPIE - The International Society for Optical Engineering， 2006， 6230：623007-623007-12.
[5]朱宏伟， 游晓明， 刘升. 基于粒子群参数优化的同构双种群蚁群算法[J]. 测控技术， 2007， 33（3）：279-285.
[6]Li G， Chou W. Path planning for mobile robot using self-adaptive learning particle swarm optimization[J]. Science China Information Sciences， 2018， 61（5）：052204.
[7]El-Shorbagy， M.A， Hassanien A E. Particle Swarm Optimization from Theory to Applications[J]. International Journal of Rough Sets and Data Analysis， 2018， 5.
[8]譚冠政， 贺欢， Sloman A. 基于ACS算法的移动机器人实时全局最优路径规划[J]. 自动化学报， 2019，001-009
[9]粒子群蚁群结合算法在车辆调度问题中的应用研究[J]. 陈磊. 湖北工业大学学报. 2016（05）
[10]Wu J， Chen B， Kai Z， et al. Ant pheromone route guidance strategy in intelligent transportation systems[J]. Physica A Statistical Mechanics & Its Applications， 2018， 503：S0378437118301225.
[11]萨日娜. 基于蚁群粒子群优化算法的云计算资源调度方案[J]. 吉林大学学报（理学版）. 2017（06）