基于蚁群优化和离策略学习的机器人路径规划

赵广复，方加娟

(郑州职业技术学院软件工程系，河南郑州 450121)

1 研究背景

机器人路径规划是机器人领域的一个研究重点和难点，也是人工智能走向工业和生活必须要解决的一个关键问题。机器人的路径规划可以定义为：在一个具有障碍物的场景中，机器人从某初始位置出发，避开障碍物，寻求一条从初始位置到目标位置的最优路径。最优路径指的是路径长度最短，或是花费时间最短，或是路径上消耗的能量最少[1]。

从移动机器人路径规划的定义可以看出，移动机器人规划的关键问题可以分为三个部分：(1)路径规划是从初始位置到目标位置的一条路径；(2)规划出的路径必须要避开环境场所中的所有障碍物；(3)在满足条件(1)(2)的情况下，尽可能地根据机器人规划的具体优化目标，来寻求其运动轨迹。

根据机器人是否依赖在线产生的数据，机器人规划方法可以分为在线和离线的方法。离线方法是指机器人一开始就拥有全部的环境信息，机器人只需要根据已知环境信息和知识来进行规划即可。在线方法是指机器人在初始时刻并不知道环境的所有信息，可能只知道部分的信息，因此，机器人需要同时进行路径规划和获取环境的信息。郑延斌[2]提出了一种基于分层强化学习和人工势场的多agent路径规划算法，以提高规划的收敛速度和规划效率。将规划场景虚拟为一个人工势场，采用先验知识来初始化每点的势能值，并利用分层强化学习算法来更新策略。赵开新[3]提出了一种改进的自适应遗传算法，根据进化过程中对个体的适应度值，来对交叉概率和变异概率进行调节，使得算法能跳出局部最优解，求取全局近似最优解，并通过栅格法对机器人工作空间进行建模。祁若龙[4]采用概率论方法结合机器人的线性控制和卡尔曼滤波对机器人可行轨迹进行规划，并对先验概率进行评估，从而获得机器人的先验估计概率，采用高斯运动模型对可行轨迹评估，从而计算出避开障碍和到达目标点的概率。陈洋[5]分别考虑了空中飞行机器人和地面移动机器人的最大运动速度，在满足最小充电时间、最大滞空时间以及各目标位置的邻域的约束，将目标序列访问任务的总时间最短作为目标优化模型，从而将机器人系统路径规划问题转换为混合整数凸优化问题进行求解。唐建业[6]提出了一种改进的多项式插值轨迹规划方法，在满足运动学约束的前提下实现时间和冲击的综合最优，采用序列二次规划方法求得最优运动时间，综合关节空间位置序列的运动学参数确定最终的关节轨迹。方啸[7]首先定义了连续型的强化信号，采用强化学习信号对输入和输出量进行了定义，并设计了机器人自主学习寻路和避障的控制策略，在不同的初始位置和目标状态下进行仿真实验，并通过实验表明了基于启发式动态规划的方法使得机器人具有更好的适应能力。游晓明[8]定义了一种新的动态搜索诱导算子，并对动态搜索模型进行了定义，通过设计较大的阈值来增加多样性，同时利用衰减模型调整来加快算法收敛。

由于现实世界的机器人规划场景通常是动态变化的，因此，机器人规划通常要采用在线方法来寻求。本文通过离策略的强化学习算法来动态更新路径上各个位置点的信息素，然后通过蚁群算法来基于信息素寻求初始位置到目标位置的最优路径。通过机器人路径规划的仿真实例，对所提的方法进行验证，结果表明所提的方法能满足动态在线规划的需求，具有很强的适应能力。

2 机器人规划模型

机器人规划的环境场景首先需要被建模，使机器人可以对环境场景进行更为精确的表示。本文采用栅格对机器人规划的二维环境进行建模。在机器人规划环境场景中，障碍物、初始位置和目标都是初始时刻确定的，一旦确定则在规划的整个过程中均不会发生变化。

在对二维环境场景进行栅格化的过程中，可以通过对x轴方向和y轴方向分别进行等分来进行栅格化。图1是对一个二维的环境场景进行栅格化的图，其中黑色填充部分为障碍物，而其它坐标则是对场景进行栅格化的结果。

图1 环境场景栅格化图

图2 仿真场景设置

3 基于蚁群算法的机器人路径规划

3.1 蚁群算法

蚁群算法是Dorigo M[9]提出的一种蚁群系统算法，其主要思想是通过对蚂蚁行走路径上信息素进行实时更新，通过强化最优信息反馈加快算法的收敛。目前蚁群算法已经广泛应用于旅行商问题、车间调度问题、无线传感器路由控制问题以及机器人路径规划问题中。

经典的蚁群算法在通过正反馈机制寻求最优路径的同时，也会导致蚁群多样性缺失，使得全局搜索能力大为减弱。本文对蚁群算法的改进主要分为两个方向：(1)对蚁群信息素的更新方法进行改进；(2)对蚁群算法中当前位置到下一位置的转移概率进行改进。

3.2 蚁群信息素的更新

蚁群信息素通过离策略的学习算法进行实时更新，将路径上任意一个栅格点的信息素作为离策略学习算法中的长期回报来求解。任意时刻、任意栅格上的信息素都会采用离策略学习算法来进行全局更新。

在采用离策略算法对蚁群信息素进行更新时，采用离策略算法中的Q学习算法对各位置的蚁群信息素进行更新。

立即奖赏函数的设置为：达到目标状态后，获得一个较大的正值为10的立即奖赏；而在其它位置获得值为1的累积奖赏。

迁移函数的设置为：机器人向上移动时，x轴方向的坐标不变，而y轴方向的坐标加1；机器人向下移动时，x轴方向的坐标不变，而y轴方向的坐标减1；机器人向左移动时，x轴方向的坐标减1，而y轴方向的坐标不变；机器人向右移动时，x轴方向的坐标加1，而y轴方向的坐标不变。

算法1 基于离策略学习的信息素动态更新算法

输入：探索因子ε，折扣率γ，步长因子α，情节最大数ET，每个情节包含的最大时间步ETS；

初始化：状态空间X为所有栅格化的离散二维点，动作空间包含的动作有：向下(-1)，向上(+1)，向左(-2)，向右(+2)，原地(0)，初始化所有状态动作处的Q值为0,即Q0(x,u)=0，初始化当前状态x=x0；

Repeat(ET)

Loop(ETS)

(2)根据ε的值，以1-ε的概率选择最优动作a，以ε的概率选择其它动作；

(3)基于选择的动作和当前的状态，根据迁移函数将当前状态迁移到后续状态x′，并根据奖赏函数获得立即奖赏r；

(5)更新当前状态：x←x′；

(7)更新下一个状态处执行的动作：a←a′；

(8)更新当前时步；

End Loop

更新当前情节

End Repeat

输出：各状态动作处的Q值

3.3 改进的转移概率

为了增加多样性，在转移概率的基础上加入随机选择机制，如同离策略学习中的ε。设定随机参数s∈(0,1)，对于每个时间步t产生的随机数st∈(0,1)。当s≤st，必须通过计算转移概率来确定下一个可以选择的位置；当s≥st时，则查看当前位置旁边所有的可达位置，除去障碍位置和已经过的位置，随机选择一个可行的位置作为下一个要达到的位置：

①

其中，rand(allowedt)表示可行位置从非障碍位置和未经过的位置集allowedt中选择。

对于任意一个可行节点j，转移概率可以表示为：

②

在式②中，τij(t)为当前位置i到下一个可行位置j的路径ij上的信息素，这个信息素通过算法1来实时更新，而ηj为启发式因子，ηj为节点j的被访问的次数的倒数，即当下一个节点的访问次数越多，该节点由于已经被充分探索，因此避免访问该节点，以增加多样性。a和β分别为信息素和启发式信息的权重因子。

3.4 基于蚁群算法的机器人路径规划

本文提出的基于蚁群算法的机器人规划算法对传统蚁群算法的改进主要在于蚁群信息素更新方法和转移概率，分别如前文3.2节和3.3节所示。

算法2 基于蚁群算法的机器人规划算法

输入：探索因子ε，折扣率γ，步长因子α，情节最大数ET，每个情节包含的最大时间步ETS，信息素权重因子a，启发式信息的权重因子β，信息素的挥发因子ρ；

初始化：调用算法1求解出所有状态动作对处的Q值，并用于初始化信息素τij；

Repeat(T轮迭代)

(1)蚂蚁从初始位置出发；

(2)根据公式①，蚂蚁计算出下一个可行的位置节点集合；

(3)根据公式②计算蚂蚁转移到下一个可行位置节点的概率，选择概率最大的节点进行转移；

(4)调用算法1来计算各节点的Q值，并用于更新各节点的信息素Δτij(t+1)；

(5)更新各节点的信息素：τij(t+1)=(1-ρ)*τij(t)+ρΔτij(t+1)，其中，τij(t+1)和τij(t)分别表示t+1时刻和t时刻时路径ij上的信息素，Δτij(t+1)为t+1时刻通过算法1得到的实时信息素；

(6)更新当前迭代次数；

End Repeat

输出：选择从初始位置开始到目标位置中信息素最大的路径

4 仿真实验

在Matlab仿真环境下，对本文所提方法进行验证。仿真场景如图1所示，按图1对场景进行栅格化后，但图1并未标记初始位置和目标位置。因此，在对图1标记了初始位置和目标状态后，初始位置被标记为“Initial State”，其坐标位置为(1,1)，目标位置为“Goal”，其坐标位置为(5,7)。

仿真场景如图2所示。仿真环境参数为：探索因子ε=0.05，折扣率γ=0.9，步长因子α=0.5，情节最大数ET=100，每个情节包含的最大时间步ETS=200，信息素权重因子a=0.5，启发式信息的权重因子β=0.5，信息素的挥发因子ρ=0.4，最大迭代次数T=500。

将由本文方法得到的规划仿真结果收敛性与文献[2]中基于强化学习的机器人路径规划方法以及文献[8]所示的基于蚁群算法的机器人路径规划方法进行比较，得到的收敛结果如图3所示。

图3 简单障碍物环境下收敛曲线

图4 仿真得到的最优路径

从图3中可以看出，本文方法在第10个情节左右就开始趋于收敛，收敛的解为11个时间步；文献[2]方法直接采用强化学习算法来寻求最优解，但在40个情节时才开始收敛，且收敛解为12个时间步；文献[8]方法在第125个情节时收敛，收敛的时间步为11个时间步。

本文方法得到的最优路径，从初始位置到目标位置的最优路径一共包含两条，如图4所示，其中实心三角形组成的路径为其中一条最优路径，另一条最优路径从初始位置纵坐标5处仍然由实心三角形构成，而另一段路径由空心三角形构成。

5 结语

为了实现机器人的在线实时路径规划，本文提出一种基于蚁群优化和离策略学习的机器人规划方法。首先，提出了机器人规划模型，并采用栅格法对环境场景进行离散化；然后，设计了基于离策略学习算法的蚁群信息素初始化和更新方法；最后，提出了一种基于蚁群算法的机器人路径规划算法。对两个算法均进行了定义和描述。仿真实验证明，本文方法具有收敛速度快和收敛精度高的优点，具有很强的适应能力。