基于栅格模型机器人路径规划的量子蚁群算法

张　晨，游晓明

(上海工程技术大学 电子电气工程学院，上海 201620)



基于栅格模型机器人路径规划的量子蚁群算法

张晨，游晓明

(上海工程技术大学 电子电气工程学院，上海 201620)

摘要针对复杂环境中移动机器人路径规划问题，提出了一种基于量子-蚁群算法(QACA)融合的路径规划算法。该算法的核心是在蚁群系统(ACS)中引入量子算法中的量子态矢量和量子旋转门来分别表示和更新信息素，增加位置的多样性,加快算法的收敛速度。通过仿真实验表明，该算法可增加算法的随机性，较传统的蚁群算法具有更好的种群多样性，更快的收敛速度和全局寻优能力，即使在障碍物较复杂的环境下，也能迅速规划出一条最优路径。

关键词量子进化算法；蚁群算法；复杂环境；栅格法；路径规划

目前，不少学者用改进的遗传算法、神经网络、随机树等方法对机器人路径进行规划。但不少算法在一定程度上存在搜索空间大、算法复杂、效率较低等问题[1]。尤其是当障碍物的数目增加或地形障碍趋于复杂时，不少路径规划算法的复杂度会大幅增加，甚至无法求解。如基于遗传算法的机器人路径规划方法，该方法对路径规划环境中的路径进行编码构成遗传个体，在进行选择、交叉、变异等遗传操作时要加很多的约束条件。当环境趋于复杂、障碍物数目增加时、约束条件就会很复杂，甚至无法求解。朱正等尝试最优最差蚂蚁算法作路径规划，仿真结果表明可以很好地避免障碍物，快速找到一条机器人最优移动路径[2]。然而，要么复杂度过大，或没有完全避免路径死锁问题。本文使陷入死锁的蚂蚁逐步逃逸，为更好的解决搜索效率低，收敛速度慢，提出了一种新的算法-量子蚁群算法，在蚁群算法的基础上，将量子进化算法中的态矢量和量子旋转门引入蚁群算法，在该算法中态矢量和量子旋转门分别表示和更新信息素，加快了算法的收敛速度及避免了早熟收敛。仿真实验比较了在不同环境下本文算法与文献[3]算法的搜索性能，另外分析了主要参数的确定规则，并作了仿真对比实验。

1量子蚁群算法

1.1量子编码特性

在经典计算中，信息被编码为位(bit)链。量子比特是量子计算中的基本信息单元，其是定义在二维复向量空间中的一个单位向量,该空间由一对特定的标准正交基{|0〉,|1〉}张成。即一个量子位除了可处于|0〉或|1〉,还可处于两者之间的任意线性组合,这称为叠加态[4]。一个量子位的叠加态可用二维Hilbert空间的单位向量|ψ〉来描述

|ψ〉=α|0〉+β|1〉

(1)

其中，α和β均是复数,分别称为量子态|0〉和|1〉的概率幅,代表对量子比特进行测量时；|ψ〉为一种量子态的表示；α2和β3分别表示量子比特处于“0”态和“1”态的概率，且满足归一化条件[5]

α2+β2=1

(2)

1.2量子蚁群算法基本原理

定义ξ(ξ∈[0,π])为一个量子位的相位，ξ=arctan(β/α)，则第i(i=1,2,…,m)个量子位的相位为ξi=arctan(βi/αi)。用符号di表示第i个量子位概率幅αi和βi的商,di=βi/αi, 其中di的值代表此量子位的相位ξ在平面坐标中所处的位置[6]。于是有m个量子位的个体j的概率幅可表示为

(3)

(4)

量子蚁群算法中的概率转移规则是

(5)

其中，q为[0,1]区间内的一随机数；q0为[0,1]区间内的一个常数。当q>q0时，b′的选择由转移概率公式决定

(6)

1.3信息素更新策略

信息素的更新分为蚂蚁个体信息素的局部更新和蚁群信息素的全局更新。每只蚂蚁在一次遍历结束后，先按照式(7)进行个体信息素的局部更新[7]

τ(t+1)=(1-ρ1)τ(t)+ρ1Δτij

(7)

当所有的蚂蚁对节点完成遍历后，再进行信息素的全局更新。只有当前路径最短的蚂蚁能在其经过的路径上留下信息素，信息素更新的规则如下

(8)

1.4量子旋转门自适应调整策略

在量子算法中选用量子旋转门来进行更新操作，量子旋转门的调整操作如下

(9)

其中，i=1,2,…,m;[αi,βi]T为第i个量子位的概率幅;θi为第i个量子位的旋转角度，其大小和方向根据一个事先确定的调整策略,通过查表得到。文中θi的大小和方向通过式(10)自动调整[8]。

θi=Δθ×f(αi,βi)

(10)

1.5量子蚁群算法流程

(3)蚂蚁按照状态转移规则式(5)和式(6)选择下一个城市，并更新禁忌表；

(4)按照式(7)完成信息素的局部更新；

(5)判断是否所有蚂蚁完成遍历，若是，转向步骤(6),否则返回步骤(3)继续遍历下一个城市；

(6)记录下本次迭代中的较优解，使用3-opt法进行局部优化；

(7)应用量子旋转门规则更新反应蚂蚁各节点信息的量子信息强度；

(8)按照式(8)完成信息素全局更新，同时更新启发因子和全局信息素挥发系数；

(9)判断是否连续若次出现搜索停滞现象，若是，重置信息素，否则转向步骤(10)；

(10)判断是否满足收敛条件或最大迭代次数，若满足，转向步骤(11)，否则清空禁忌表并返回步骤(1)，直至达到收敛条件或最大迭代次数；

(11)输出最优路径长度和最优路径。

2仿真实验

为说明算法的优越性，文中选用文献[3]中朱正的改进蚁群算法进行测试，迭代次数为100次，实线为本算法寻找到的最优路径，虚线为文献[3]寻找到的最优路径。从下图可看出，本算法能快速，准确的寻找到最优路径，虽在有些障碍物聚集处，选择的路径稍有偏差，可能是由于可选方向上最大信息素的搜索造成的。为不失一般性，文中又随机测试了一些规模较为复发的地图，每个算法迭代100次，参数设置如表1所示，图1和图2为算法对栅格地图测试得到的结果。

表1　各参数设置

图1　复杂环境1下两种算法路径比较

图2　Z-型环境下两种算法比较

由以上两个实验可看出，与文献[3]和其他改进蚁群算法相比，本算法显示出了良好的快速求解性能，且在规模较大、环境复杂的情况下，解的质量也显示了较高的稳定性。此外，还发现在起始点和目标点之间只有一条通道客观存在，无论路径多么复杂，本算法均能迅速准确的规划出最优路径。表2为两种算法实验结果对比。

表2　两种算法实验结果对比

3参数选择分析

3.1量子位个数 对算法性能影响

过大，影响算法的随机性能和全局搜索能力，算法波动性较大，本文算法中m最优为8或12，如图3所示。

3.2Q对算法性能的影响

Q越大，有利于增强搜索时的正反馈性能，收敛速度越快，将导致算法的全局搜索能力变差，本算法中Q的值最优为3，在50代左右处收敛，避免算法陷入局部最优，如图4所示。

图3　不同 值下算法收敛曲线图

图4　不同 值下算法的收敛曲线图

4结束语

传统的蚁群算法，路径精度不够高，算法的搜索效率较低，若只依靠信息素和距离信息是难以找到一条从起始点到目标点的优化路径，并容易陷入死锁。本文提出了一种复杂环境下路径规划的量子蚁群算法。给出了新的信息素表达规则，增加最优路径上信息量的随机性，同时采用量子旋转门对信息素进行更新，加快了算法的收敛速度，且对路径转移规则进行了合理的改进，提高了算法的搜索能力，使蚂蚁对最优路径更为敏感，更好地适应信息素环境。仿真结果表明，与传统算法相比，该算法具有更高的精度、速度快、稳定性高、效果好等特点，即使在复杂环境下，只要客观要求合理，该算法便能快速的规划出安全的最优路径。

参考文献

[1]赵俊生,李跃光,张远平.一种改进的量子蚁群算法及其应用[J].计算机应用与软件,2010,27(7):133-135.

[2]孙波,陈卫东,席裕庚.基于粒子群优化算法的移动机器人全局路径规划[J].控制与决策,2005,20(9):1052-1055.

[3]朱正,刘士荣,张波涛.一种基于改进蚁群算法的移动机器人全局路径规划方法[C].北京：中国自动化学会控制理论专业委员会:d卷,2011.

[4]魏唯,欧阳丹彤,吕帅,等.动态不确定环境下多目标路径规划方法[J].计算机学报,2011,34(5):836-846.

[5]Fatemeh K P,Ehsan S. Mobile robots path planning using ant colony optimization and fuzzy logic algorithms in unknown dynamic environments[C].Hongkong: International Conference on Control,Automation,Robotics and Embeded Systems,2013.

[6]柳长安,鄢小虎,刘春阳,等.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5):1220-1224.

[7]刘徐迅,曹阳,陈晓伟.基于移动机器人路径规划的鼠群算法[J].控制与决策,2008,23(9):1060-1064.

[8]Han Kuk-Hyun,Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problems[C]. Piscataway, USA:Proceeding. of IEEE Conference on Evolutionary Computation, IEEE Press, 2000.

[9]朱庆保.动态复杂环境下的机器人路径规划蚂蚁预测算法[J].计算机学报,2005,28(11):1898-1905.

Improved Quantum ant Colony Algorithm of Path Planning for Mobile Robot Based on Grid Model

ZHANG Chen, YOU Xiaoming

(College of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China)

AbstractFor mobile robot path planning in complex environments, an ant colony algorithm based on quantum (QACA) is proposed to plan the optimal collision-free path. The core of the algorithm is the introduction of the quantum state vector of quantum algorithm to respect the pheromone and quantum revolving gate to update the pheromone in ant colony system (ACS), in order to increase the diversity of position and to speed up the convergence speed of the algorithm. Simulation comparison shows that the algorithm can increase the randomness of the algorithm with better population diversity, higher convergence speed and better global optimization ability than the traditional ant colony algorithm, and can quickly find a optimal path planning even in the very complex environment.

Keywordsquantum evolutionary algorithm; ant colony algorithm; complex environment; grids; path planning

收稿日期:2015- 11- 6

基金项目:国家自然科学基金资助项目(61075115)；上海市教委科研创新重点基金资助项目(12ZZ185)；上海市学科专业建设基金资助项目(XKCZ1212)；创新课题资助项目(14KY0210)

作者简介:张晨(1990-)，女，硕士研究生。研究方向：嵌入式系统与智能算法。游晓明(1963-)，女，博士，教授。研究方向：智能信息处理理论及应用等。

doi:10.16180/j.cnki.issn1007-7820.2016.07.001

中图分类号TP301.6

文献标识码A

文章编号1007-7820(2016)07-001-04