第2期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·333· 式中：k为常数，保证概率范围为(0,1)；ε为终点 免蚂蚁集中在某条路径上，将每条路径的信息素 诱导系数；ω为障碍物诱导系数；y:为移动机器 设置上下限为[tma,tm],当该条路径信息素浓度 人当前节点到下一步可到达所有节点的距离总 低于信息素下限时，将该条路径信息素设置为 和，σ为移动机器人下一步到达的节点与终点之 t,当该条路径信息素浓度高于信息素上限时， 间的距离，其值越小，则距离终点越近，被选择的 该条路径信息素设置为T,这样可以避免算法 概率也将越大，入为移动机器人下一步到达的节 陷人局部最优解，当蚁群经过一轮迭代后，挑选 点与其最近的障碍物之间的距离，优先考虑障碍 出最优路径，对其信息素进行更新，加强对最优 物相邻的节点，可以有效缩短无效路径，提高移 路径的利用，当所有蚂蚁完成一次迭代后，对路 动机器人避障能力。 径上的信息素进行全局更新： 2.2信息素分布策略 tt+l)=(1-pT0+△()，pe(0,1) (11) 在移动机器人路径规划之前，需要给栅格地 边亿，)包含在最优路径内 图环境的信息素进行初始化，初始化信息素采用 △= (12) 不均匀分布，障碍物栅格的信息素设置为0，加强 0,其他 起点至终点直线所涉及到栅格的信息素浓度，平 为了提高搜索效率，一只蚂蚁在一轮迭代中 行的向外衰减，将栅格地图建立直角坐标系，如 走过的完整路径将不被以后的蚂蚁所选择，对于 图4所示。 需要更新信息素的路径，可以是本轮迭代的最优 解，也可以是全局最优解。 2.3改进启发函数 结合变步长蚁群算法的优点，在直角坐标系 中，利用蚁群下一步到达的节点距离起点至终点 连线的长短，对启发函数进行改进，传统蚁群算 法的启发函数为蚁群下一步所选择的节点到终点 之间距离的倒数，如式(2)所示，该函数收敛性不 强，且容易使蚁群寻优路径冗长，改进后的启发 函数如下： 1V2 图4信息素分布策略 u=di+yCl (13) Fig.4 Pheromone distribution strategy 式中，(xy)为下一步所选择节点的坐标，当其距 连接移动机器人的起始点及终点，则该直线 离起点至终点对角线的长度越小，被选择概率则 方程为 越大，与传统蚁群算法的启发函数相比，改进后 y=-x+C,C∈N" (9) 的启发函数促使移动机器人将下一步选择的节点 在本文中，C取值为20或30，分别对应简单 趋近于移动机器人起点到终点连线处，使移动机 栅格环境和复杂栅格环境，令(O)=to为信息素 器人在路径寻优中能更快地找到最优解，提高了 浓度的初始值，根据初始信息素浓度的衰减方 算法的收敛速度，因此，改进后的启发函数作用 式，障碍物栅格的初始信息素τ。直接取0，非障碍 得到加强，有利于提高算法的收敛速度，提高算 物栅格初始信息素取值如下： 法的全局搜索能力。 T,y=-x+C C-1 3改进算法步骤 .T,y=-x+C±1 图5为变步长蚁群算法的流程图，算法的具 T0= C-2 .T,y=-x+C±2 (10) 体步骤如下： … 1)针对各项相关参数进行初始化：路径规划 1 的起始点及终点、信息素重要程度参数α、启发 ,，y=-x+1或y=-x+2C-1 因子重要程度参数B、迭代次数、蚂蚁数量、信息 式中：T为调整系数，T∈(1,20)，初试信息素的分 素挥发系数及增强系数等相关参数，建立地图二 布有利于蚁群提高搜索速度，快速收敛。 维栅格模型，邻接矩阵模型。 为了防止某条路径的信息素过高或过低，避 2)初始化信息素采用不均匀分布，加强起点k ε ω γis σ λ 式中： 为常数，保证概率范围为 (0,1)； 为终点 诱导系数； 为障碍物诱导系数； 为移动机器 人当前节点到下一步可到达所有节点的距离总 和， 为移动机器人下一步到达的节点与终点之 间的距离，其值越小，则距离终点越近，被选择的 概率也将越大， 为移动机器人下一步到达的节 点与其最近的障碍物之间的距离，优先考虑障碍 物相邻的节点，可以有效缩短无效路径，提高移 动机器人避障能力。 2.2 信息素分布策略 在移动机器人路径规划之前，需要给栅格地 图环境的信息素进行初始化，初始化信息素采用 不均匀分布，障碍物栅格的信息素设置为 0，加强 起点至终点直线所涉及到栅格的信息素浓度，平 行的向外衰减，将栅格地图建立直角坐标系，如 图 4 所示。 x y 0 图 4 信息素分布策略 Fig. 4 Pheromone distribution strategy 连接移动机器人的起始点及终点，则该直线 方程为 y = −x+C, C ∈ N ∗ (9) τi j(0) = τ0 τ0 在本文中，C 取值为 20 或 30，分别对应简单 栅格环境和复杂栅格环境，令 为信息素 浓度的初始值，根据初始信息素浓度的衰减方 式，障碍物栅格的初始信息素 直接取 0，非障碍 物栅格初始信息素取值如下： τ0 =    T, y = −x+C C −1 C ·T, y = −x+C ±1 C −2 C ·T, y = −x+C ±2 ··· 1 C ·T, y = −x+1或y = −x+2C −1 (10) 式中： T 为调整系数， T ∈ (1,20) ，初试信息素的分 布有利于蚁群提高搜索速度，快速收敛。 为了防止某条路径的信息素过高或过低，避 [τmin,τmax] τmin τmax 免蚂蚁集中在某条路径上，将每条路径的信息素 设置上下限为 ，当该条路径信息素浓度 低于信息素下限时，将该条路径信息素设置为 ，当该条路径信息素浓度高于信息素上限时， 该条路径信息素设置为 ，这样可以避免算法 陷入局部最优解，当蚁群经过一轮迭代后，挑选 出最优路径，对其信息素进行更新，加强对最优 路径的利用，当所有蚂蚁完成一次迭代后，对路 径上的信息素进行全局更新： τi j(t+1) = (1−ρ)· τi j(t)+ ∆τ best i j (t), ρ ∈ (0,1) (11) ∆τ best i j =    1 L best , 边(i, j)包含在最优路径内 0, 其他 (12) 为了提高搜索效率，一只蚂蚁在一轮迭代中 走过的完整路径将不被以后的蚂蚁所选择，对于 需要更新信息素的路径，可以是本轮迭代的最优 解，也可以是全局最优解。 2.3 改进启发函数 结合变步长蚁群算法的优点，在直角坐标系 中，利用蚁群下一步到达的节点距离起点至终点 连线的长短，对启发函数进行改进，传统蚁群算 法的启发函数为蚁群下一步所选择的节点到终点 之间距离的倒数，如式 (2) 所示，该函数收敛性不 强，且容易使蚁群寻优路径冗长，改进后的启发 函数如下： ηi j = 1 di j · √ 2 |xi +yj −C| (13) (xi 式中， , yj) 为下一步所选择节点的坐标，当其距 离起点至终点对角线的长度越小，被选择概率则 越大，与传统蚁群算法的启发函数相比，改进后 的启发函数促使移动机器人将下一步选择的节点 趋近于移动机器人起点到终点连线处，使移动机 器人在路径寻优中能更快地找到最优解，提高了 算法的收敛速度，因此，改进后的启发函数作用 得到加强，有利于提高算法的收敛速度，提高算 法的全局搜索能力。 3 改进算法步骤 图 5 为变步长蚁群算法的流程图，算法的具 体步骤如下： α β 1) 针对各项相关参数进行初始化：路径规划 的起始点及终点、信息素重要程度参数 、启发 因子重要程度参数 、迭代次数、蚂蚁数量、信息 素挥发系数及增强系数等相关参数，建立地图二 维栅格模型，邻接矩阵模型。 2) 初始化信息素采用不均匀分布，加强起点 第 2 期 徐玉琼，等：基于变步长蚁群算法的移动机器人路径规划 ·333·