基于路径拓展蚁群算法的机器人路径规划方法

摘要

本发明涉及一种基于路径拓展蚁群算法的机器人路径规划方法，将运用蚁群算法到机器人路径规划领域，提出路径拓展蚁群算法优化策略，优化机器人路径寻优效率，引入了信息素分布时变性、信息素更新策略、路径位置拐点优化和局部最优路径拓展，并加入位置拐点参数和总体评价作为路径的评价标准。通过对这三种算法进行仿真分析和实际试验，验证了基于路径拓展蚁群算法优化策略的机器人路径规划搜索能力更强，算法效率更高，所寻路径更短。有效抑制了算法陷入局部最优并实现了机器人最优路径搜索，使机器人可以快速地避开障碍物安全到达目标点。

主权项

一种基于路径拓展蚁群算法的机器人路径规划方法，其特征在于，采用栅格法对机器人工作环境进行建模，获得随机地图，其中白色栅格为自由栅格，为机器人可行区域，黑色栅格为障碍栅格，为机器人不能通行的区域，单位栅格与机器人大小相当，并从左至右、从上至下对模型中的栅格进行编码，一个栅格代表一个位置节点，将路径拓展蚁群算法优化应用到移动机器人路径规划中，具体步骤如下：1)设置最大循环次数为N_max和改进蚁群算法循环次数N_ACO，每段路径上信息素的初始值为0，设置起始点和目标点，将m只蚂蚁放于起始点；2)每只蚂蚁根据如下状态移动规则公式选择下一个位置点，当蚂蚁到达目标点时，记录该蚂蚁路径长度及其所包含路段信息，并初始化禁忌表，$P_{ij}^k\left(t\right)=\left\{\begin{array}{cc}\frac{{\tau }_{ij}^{\alpha }\left(t\right){\eta }_{jE}^{\beta }\left(t\right)}{{\Sigma }_{s\in {\mathrm{allowed}}_k}{\tau }_{is}^{\alpha }\left(t\right){\eta }_{jE}^{\beta }\left(t\right)},& j\in {\mathrm{allowed}}_k\\ 0,& otherwise\end{array}\right.,$其中，s为当前有转移概率的位置节点，为蚂蚁k在位置节点i选择位置点j的转移概率；τ_ij(t)表示t时刻在位置节点i与位置节点j之间的路段(i，j)上的信息素浓度，α是次方，根据描述积累信息的重要性来设定；η_jE(t)表示从位置节点j向目标位置节点E移动的启发函数，β是次方，根据描述启发函数的重要性来设定；α和β均为正实数；η_jE(t)其值设定为E_p/L_jE，L_jE为位置节点j到目标位置节点E的距离，E_p为一适当正常数；allowed_k为t时刻允许蚂蚁k(k＝1，2，...，m)通过的位置节点集合；3)当代k只蚂蚁全部路径规划完成后，比较出局部最优路径，运用路径位置拐点优化方法对局部最优路径进行优化，得出局部更优路径；4)按改进蚁群算法信息素浓度更新对其该局部最优路径上的信息浓度进行全局更新，更新策略：经过n个时刻，蚂蚁k完成了一次循环，既蚂蚁k找寻到当前的最优路径，对该路径的信息素浓度做出调整，该路径上路段(i，j)上的信息素量变化公式τ_ij(t+n)为：τ_ij(t+n)＝ρ·τ_ij(t)+Δτ_ij(t，t+n)${\mathrm{\Delta \tau }}_{ij}\left(t,t+n\right)={\Sigma }_{k=1}^m{\mathrm{\Delta \tau }}_{ij}^k(t,t+n)$其中，L_k为蚂蚁k在本次循环中所走的最优路径长度；Q(t)为蚂蚁k在最优路径上释放的信息素量；τ_ij(t)表示t时刻在位置节点i与位置节点j之间的路段(i，j)上的信息素浓度；表示蚂蚁k在时刻(t，t+n)留在路径(i，j)上的信息素量；Δτ_ij(t，t+n)表示本次循环中路径(i，j)的信息素的增量；ρ为信息素挥发率系数，设置系数ρ＜1来避免路径上信息素量的无限累加；5)重复步骤2)、3)、4)直到循环次数N＞N_ACO，结束改进蚁群算法迭代；6)判断是否存在最优路径；7)运用局部最优路径拓展，对已寻局部最优路径拓展优化，寻找最优路径；8)若循环次数N＞N_max则程序结束，否则转到步骤7；当达到最大循环次数为N_max时算法结束，数据库中保存从起始点到目标点的全局最优路径，并绘制最优路径坐标图为所需移动机器人路径规划。