未知环境中基于量子蚁群优化的移动机器人实时路径规划

张高林,张继宇,周 萌

(1.中国石化催化剂有限公司技术信息部，北京 100029； 2.哈尔滨工程大学自动化学院，黑龙江 哈尔滨 150001；3.国网湖北省电力有限公司团风县供电公司，湖北 黄冈 438000)

0 引 言

随着移动机器人技术的快速发展，以及其工业化的程度不断提高，移动机器人能够在工业制造、探测、侦察、运输、医疗服务等各个领域服务社会。移动机器人的路径规划问题是保证移动机器人正常工作的基础，因此得到了越来越多的关注。移动机器人的路径规划要求机器人可以自主地规划一条由起点到终点的满足一些优化条件的安全无碰的路径。目前的路径规划方法整体上可以分为2类：全局路径规划和实时路径规划。

近年来，已经提出了许多有效的全局路径规划算法。Zhang等[1]通过人工势场的概念构建蚁群优化(ACO)的启发式信息。改进的ACO可以保持障碍物和AUV之间的安全距离。Liu等[2]在搜索移动机器人全局最优路径的过程中，通过结合信息素扩散和几何局部最优化改进ACO。该算法解决了传统ACO收敛速度的问题。朴松昊等[3]采用基于链接图的遗传算法建立全局优化路径并采用基于行为的方法进行局部路径规划，可以很好地解决全局与局部路径规划的关系。Jaradar等[4]提出模糊人工势场法，该方法结合了人工势场技术与模糊理论。Yao等[5]在机器人路径规划问题中提出了异构特征蚁群优化(HFACO)算法。在HFACO中，定义了2种蚂蚁，蚂蚁A通过随机搜索和广泛搜索找到路径，并将信息素留给蚂蚁B来开发和优化路径。张福浩等[6]提出了基于Dijkstra算法的邻接点算法来解决最短路径优化问题。HFACO可以有效缩短执行时间。但当地图比例变大时，很容易陷入局部最优。Cekmez等[7]通过使用多蚁群ACO实施无人机路径规划，其中N个蚁群在相同的问题下分布式地工作，并且在特定的时间间隔内将其本地殖民地知识分享到其他群落中。多群体ACO可以降低陷入局部最优的概率，但算法收敛过程中存在长期停滞。此外，潘成浩等[8]提出了改进的自适应遗传算法来解决物流机器人的路径规划问题；秦元庆等[9]提出了基于粒子群的移动机器人路径规划方法；陈卫东等[10]提出了基于模糊算法的移动机器人路径规划方法。

全局路径规划虽然可以快速地得到全局最优路径，但其要求已知全局的环境信息，而机器人的工作环境多数是不确定的。机器人在对环境没有先验知识的情况下，只能根据传感器实时探测到的环境信息进行路径规划。一些研究已经解决了无人系统的在线路径规划问题。陈曦等[11]提出了一种精英免疫遗传算法(IGAE)，用于移动机器人的最优路径规划。其中，定义了一种新的抗体相似性，以减少计算量并提高收敛速度，但IGAE并未改善解决方案的质量。Gong等[12]提出了一种基于粒子群算法的局部最优策略来处理机器人路径规划的不确定信息。在所提出的方法中，机器人总是返回运动开始时规划的全局路径，这导致更长的路径。Sfeir等[13]基于改进的人工势场方法处理未知环境中移动机器人的导航。其提出了一种新的排斥潜力形式，以便在目标靠近障碍物时减少振荡并避免冲突。新方法改善了轨迹的平滑度和长度，但不能提高寻求全局最优的能力。一些改进的蚁群系统算法实现了移动机器人的实时路径规划[14-15],这些算法可能需要一些时间才能收敛到最优解，从而影响机器人的安全性，避免一些复杂的障碍时，这些算法的性能很差。此外，针对移动机器人在未知环境下的路径规划问题，曹清云等[16]提出了一种文化基因算法规划与Morphin算法混合路径规划方法；潘成浩等[17]提出了一种松弛的Dijkstra算法；刘国栋等[18]提出了基于遗传算法的路径规划方法。

本文将量子蚁群优化与局部搜索方法相结合，解决了移动机器人在未知环境下的实时路径规划问题。仿真结果表明，这是一种简单快速高效的算法，即使在复杂的未知环境中，它也可以快速地为移动机器人实时规划无障碍路径。

1 激光测距仪仿真模型

1.1 激光测距仪的主要参数

移动机器人自主工作时，必须用自身装配的激光测距仪探测周围环境信息。本文的移动机器人只在二维空间中运动，图1为激光测距仪模型示意图。其水平开角为180°，最大探测半径为80 m，共180个光束，波束角为1°。测距仪的原始数据是一些离散的点，每个数据点都包含距离和方位角。

图1 激光测距仪模型示意图

1.2 激光测距仪的数据处理

激光测距仪模型识别障碍物表面特征点的基本思路如下：根据180个光束与障碍物表面之间的距离计算机器人坐标系中障碍物表面特征点的坐标，将障碍物表面特征点的坐标从机器人坐标系转换为整体坐标系。3个坐标系之间的位置关系如图2所示，其中XGOGYG为整体坐标系，XRORYR为机器人坐标系，XLOLYL为激光测距仪坐标系。

图2 移动机器人路径规划中的3个坐标系

(1)

则p在机器人坐标系下的坐标为：

(2)

其中，laL为激光测距仪距移动机器人中心的距离，α为激光测距仪的水平开角。

(3)

2 量子蚁群优化算法

在本文的量子蚁群优化算法(Quantum Ant Colony Optimization， QACO)中，蚁群根据选择概率、信息素矩阵和环境信息选择下一个路径点。QACO中的每只蚂蚁携带一组代表蚂蚁当前位置信息的量子比特，当蚂蚁数量相同时，蚂蚁将搜索空间加倍。QACO采用量子旋转操作来增加种群位置的多样性，避免早熟收敛，克服了蚁群算法由于搜索空间中种群多样性的丧失导致容易陷入局部最优的缺陷。

2.1 编码方式

本文中，量子蚂蚁的节点位置由对应的量子比特的概率表示。量子信息素是用量子比特编码的。假设蚁群中有n个蚂蚁，量子蚂蚁路径上的量子信息素用m个量子比特表示，即QACO的维数为m。本文采用二进制编码，则蚁群携带的一组量子比特可表示为：

(4)

其中，|αji|2+|βji|2=1,i=1,2,…,m,j=1,2,…,n。显然，第j只量子蚂蚁具有2m个量子状态。因此，算法的搜索空间以及搜索速度都得到了提升。

2.2 自适应旋转门

量子比特根据旋转门的操作而更新，这有利于蚁群得到最佳个体。

(5)

式(5)中，θi=ed/d′×Δθ×S(αji,βji)为第i个量子位的旋转角度，其中，Δθ和S(αji,βji)分别为第i个量子位的旋转角度的大小和方向；d为机器人与障碍物间的最短距离，d′表示算法启动距离。在算法执行的早期，θi取一个较大的值来提高搜索效率，随着迭代次数的增加，θi逐渐减小，算法更专注于局部搜索。

2.3 状态转移策略

假设当前时刻，蚂蚁j在路径点a处，在下一时刻，蚂蚁j根据式(6)选择路径点b：

(6)

(7)

2.4 信息素更新策略

2.4.1 局部信息素更新策略

路径规划的适应度函数fj可表述为：

fj=ε1ej+ε2dj

(8)

其中，ej为蚂蚁j选择的下一路径点到目标点的欧氏距离，dj为蚂蚁j的行走距离。

信息素局部更新规则如下：

(9)

(10)

其中，ρ为信息素挥发率，Q为与收敛速度相关的参数，fj为蚂蚁j建立路径的适应度函数。

2.4.2 全局信息素更新策略

对每次迭代得到的最优蚂蚁antop(t)携带的信息素作如下更新：

τji(t+1)=φτji(t)

(11)

(12)

其中，φ为调节因子，C1为大于1的常数。

Lop(t)表示每一代蚂蚁得到的最短路径，如果满足条件Lop(t)

τji(t+1)=ψτji(t)

(13)

(14)

其中，ψ为调节因子，C2为大于1的常数。

2.5 基于QACO的实时路径规划方法步骤

步骤1初始化初始位置、目标位置等相关参数。

步骤2规划从起始位置到目标位置的全局路径。

步骤3移动机器人从当前位置向着目标点移动的同时，根据激光测距仪探测数据实时更新地图信息。

步骤4判断是否达到目标点，若到达目标点，移动机器人减速停车。

步骤5如果激光测距仪探测到碰撞冲突，则调用基于QACO的实时路径规划算法。

步骤6判断移动机器人是否完全避开障碍，若是，则跳转至步骤3；否则返回步骤5。

3 仿真实验及分析

在仿真实验中，移动机器人的速度为4 m/s，地图大小为1200 m×800 m。激光测距仪的探测频率为10 Hz，机器人和障碍物间的安全距离为10 m。本文分别在50组不同环境下对QACO和ACO的路径规划结果进行了比较，路径代价、算法耗时以及算法收敛迭代次数的统计分析结果如表1所示。显而易见，无论从路径代价、算法耗时还是收敛速度方面，QACO均优于ACO。

表1 基于ACO和QACO的实时路径规划方法性能比较

算法平均路径长度/m平均耗时/ms平均收敛代数ACO1620.52174.32189QACO1544.86163.01152

为了更具体地展示ACO和QACO在不同环境下的实时路径规划表现，本文设计了3组不同复杂程度的仿真案例。仿真结果如图3～图5所示。

(a) 实时路径对比

(b) 适应度函数收敛曲线对比图3 仿真案例1中实时路径规划结果比较

从仿真案例1的实验结果可以看出，基于QACO的路径规划方法得到的路径优于传统蚁群方法得到的路径。相较于ACO、QACO不仅收敛速度更快，而且搜索能力更强。

图4 仿真案例2中实时路径规划结果比较

在仿真案例2中，面对凹槽状连续障碍物，传统蚁群算法在规划过程中出现严重震荡，其一旦陷入局部极小，很难脱困。对于量子蚁群算法来说，自适应量子旋转门的应用有利于其跳出局部最优，从而在复杂环境中成功规划路径。

图5 仿真案例3中QACO实时路径规划方法规划结果

仿真案例3显示出基于量子蚁群算法的实时路径规划器在复杂环境中的有效性。

4 结束语

针对传统蚁群算法收敛速度慢或者容易陷入局部最优的问题，本文提出了一种量子蚁群优化算法，将其用于解决移动机器人路径规划问题。首先通过统计实验证明了所提出的量子蚁群优化方法在路径代价、算法耗时以及收敛速度方面均优于传统的蚁群算法。然后针对3组不同复杂度环境的仿真实验验证了量子蚁群优化算法的有效性以及稳定性。