一种移动机器人动态环境下的路径规划

唐建平, 宋红生, 王东署

(1.郑州大学 电气工程学院 河南 郑州 450001；2.郑州大学 国际教育学院 河南 郑州 450001)

0 引言

移动机器人路径规划问题是指在有障碍物的环境中，给定起始点和终止点，寻找一条较优的运动路径，使机器人能安全、无碰撞的行走且路径最短[1].当前静态环境下路径规划主要是采用全局规划的方法并采用相应算法对路径进行优化，如遗传算法、神经网络和模糊算法等[2].而在动态未知环境中，由于环境等因素的局限性，研究起来比较复杂，逐渐成为研究的热点.近年来，很多学者针对未知环境下的机器人路径规划做了大量研究，并取得了一定的成果.其中有代表性的成果是滚动窗口规划方法[3].该算法以起始点到机器人和机器人到目标点之间的距离作为启发信息构造代价函数，以此引导子目标的映射，在子目标引导下，局部视野窗口向子目标或沿障碍物滚动.但该算法不具备智能性，只能靠复杂的逻辑判断进行滚动，容易沿障碍再滚回到原处，形成死锁和振荡，规划的路径也难以达到全局最优.

针对上述不足，本文采用全局路径规划和局部避障规划相结合的思想，针对环境中存在静态障碍物和动态障碍物的情况，提出了一种动态未知环境中自主机器人路径规划的新方法.相对于其他算法，蚁群算法对初始路线要求不高，而且在搜索过程中不需要进行人工的调整，并且所需参数少，故首先采用蚁群算法规划一条趋于目标的全局优化路径，然后在此全局优化路径的指引下采用滚动窗口的动态避障和信息反馈的策略进行局部避障规划.采用这种全局指导下的局部避障的方法能确保机器人安全无碰撞且路径较优，从而为动态环境下自主机器人路径规划提供了一种新思路.

1 问题描述

设机器人的工作空间为二维平面上的有限平面区域，其中分布着有限个已知静态障碍物Sobsi(i=1,…,n)和有限个未知动态障碍物Dobsi(i=1,…,m).将机器人模型化为点状机器人，并且无全局环境信息.在任一时刻，它只能实时探测到以其当前位置为中心，r为半径区域内的环境信息(包括障碍物位置、速度).路经规划的目的是使机器人由起点Pinit安全无碰地到达终点Pgoal.本文提出的方法分为趋向于目标的全局运动规划和躲避障碍物的局部运动规划.全局路径规划根据环境感知模块提供的静止障碍物信息，采用蚁群算法确定出一条未考虑动态障碍物的初始全局优化路径，然后，机器人按照全局优化路径趋向于目标，期间通过传感器不断探测滚动窗口内的动态障碍物信息，根据对障碍物的预测判断会不会发生碰撞，从而安全到达目标并且保证路径较优.

2 环境建模

环境建模的目的是建立一个便于计算机模拟进行路径规划使用的环境模型.环境建模是机器人路径规划的重要环节，是实现物理空间到算法处理抽象空间的一个映射[4].

本文利用栅格法模拟机器人的工作环境，建立环境模型.为实现设想的路径规划算法，在机器人运动空间建模时作如下假定：1)移动机器人在二维有限空间中运动；2)所有动态障碍物的运动轨迹均为已知,即动态障碍物运动路径确定，而随时间变化的规律未知；机器人匀速运动；3)机器人每走一步即走一个栅格的中心点,任意时刻机器人能探测到以当前栅格中心点为中心，r为半径区域内的环境信息.

3 基于蚁群算法趋向目标的全局路径规划

3.1 蚂蚁算法步骤

Step1初始化.

每一轮蚂蚁的数目为m，将蚂蚁放置在出发点S，并把S加入到禁忌表tabuk中(k=1,2,3,…).列表tabuk记录了每一轮蚂蚁k当前所走过的节点.τij(t)表示t时刻在(i,j)边上残留的信息量，令初始时刻各条边上的信息量为同一常数，τij(0)=τ0(τ0为常数).设置实验迭代次数NG=1，最大代数为NGMAX.

Step2根据策略选择下一节点j.

在时刻t，蚂蚁从节点i转移到节点j的概率为

其中，allowedk={1,2,…,n}表示蚂蚁k下一步允许选择的所有节点.α和β分别表示路径上信息量和启发式因子ηij的重要程度.启发式因子ηij表示蚂蚁从节点i转移到节点j的期望程度，通常取ηij=1/dij,dij表示节点i和节点j之间的距离.

Step3信息素更新.

式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走路径的长度.

Step4NG++，若NG>NGMAX，则停止，否则转到Step 2.

Step5输出最优路径，算法结束.

4 基于滚动窗口的局部避障策略

4.1 基于滚动窗口的局部避障原理

基于滚动窗口的路径规划算法的基本原理如下所述.1)场景预测：在滚动的每一步，机器人根据其探测到的局部窗口范围内的环境信息，用启发式方法生成局部子目标，并对动态障碍物的运动进行预测，判断机器人行进过程中是否可能与动态障碍物相碰撞.2)滚动窗口优化：机器人根据窗口内的环境信息及预测结果，选择局部规划算法，确定向子目标行进的局部路径，并实施当前策略，即依据所规划的局部路径行进一步，窗口相应向前滚动.3)反馈初始化：在新的滚动窗口产生后，根据传感器所获取的最新信息，对窗口内的环境及障碍物运动状况进行更新[6].

4.2 针对各种预测情况的避碰策略

1)若预测到将要发生机器人和动态障碍物正面相撞的情况时，机器人必须放弃原行进计划，即时生成局部子目标，并将碰撞点所在栅格设置为临时静态障碍物，然后采用蚁群算法在当前位置与局部子目标之间重新规划出一条局部避碰路径，以替代原有路径.

2)若预测到将要发生机器人和动态障碍物侧面相撞的情况时，机器人只需在原地等待Δt时间后，再按照原规划路径行进.

3)若预测到机器人与动态障碍物不会发生任何碰撞，则直接按原规划路径行进.

5 仿真

将机器人工作平面划分成20×20个栅格，起始栅格序号取1，目标栅格序号取400.障碍物栅格的序号随机生成.蚁群算法中参数取值如下，m=20,α=1,β=1,C=0.5,ρ=0.7,Q=100.

5.1 存在静态障碍物情况下的仿真

在全局未知静态环境下，通过蚁群算法寻找出全局优化路径.图1是大多数蚂蚁选择前往目标点的一条路径，这条路径就是所要的最优路径，即机器人的移动路径.图2为最短路径随迭代次数变化的收敛曲线图，灰线代表普通蚁群算法所得到的平均路径长度和最短路径长度，黑线代表改进后蚁群算法所得到的平均路径长度和最短路径长度.改进后的蚂蚁算法收敛速度更快，迭代10次就得到收敛的路径解，算法的收敛已趋于稳定.求得最短路径为32.382 0.

5.2 存在未知障碍物情况下的仿真

1)预测正面碰撞.图3中粗直线表示动态障碍物运动轨迹，由左下向左上运动，机器人在按照全局优化路径行走过程中预测到行走路线和运动障碍物的轨迹有交点，并且会发生正面碰撞.此时机器人放弃原行进计划重新规划出一条局部避碰路径，以替代图1所示的原有路径.

2)预测侧面碰撞.图4中粗直线表示障碍物运动轨迹，动态障碍物由左下向右上运动，轨迹如图4，机器人在进行过程中预测到可能发生侧面碰撞，准备采取原地等待障碍物先通过的避碰策略.

以上仿真实验结果表明，用蚁群算法可以得到较优的全局路径；在局部避碰规划中，所采用的各种避碰策略能使机器人安全避开动态障碍物.全局路径规划和局部避碰策略的结合，可以有效确保机器人从起始点安全运动到目标点，且解决了机器人运动过程中可能会遇到的死锁和振荡现象.

图2 最短路径随迭代次数变化的收敛曲线

图3 正面碰撞图

图4 侧面碰撞

6 总结

本文针对动态环境中自主机器人路径规划问题，提出了一种由趋于目标的全局运动规划和躲避障碍物的局部运动规划相结合的路径规划新方法.该方法采用基于蚁群算法的全局路径规划和基于滚动窗口的局部避碰规划相结合的总体策略，较好地解决了路径规划中整体与局部的关系，同时兼顾了可行路径的安全性和优化性.仿真实验结果证明了本文算法的有效性，但本文只讨论了障碍物运动轨迹为已知情况下的路径规划问题，针对动态障碍物更为复杂的一般情况还有待于进一步研究.

[1] 李磊,叶涛,谭民,等.移动机器人技术研究现状与未来[J].机器人，2002，24(1)：475-480.

[2] 俞辉,裴振奎,陈继东.一种改进的蚁群聚类算法[J].郑州大学学报：理学版，2010,42(3):59-62.

[3] 席裕庚.一类动态不确定环境下机器人的滚动路径规划[J].自动化学报,2009，28(2)：3-5.

[4] 贾修一,于绍越,商琳,等.基于Rough集和蚁群算法的属性约简方法[J].广西师范大学学报：自然科学版,2006,24(4)：83-86.

[5] Dorigo M,Gambardella L M,Middendorf M,et al.Guest editorial: special section on ant colony optimization[J].IEEE Transactions on Evolutionary Computation,2002,6(4): 317-319.

[6] 张纪会,徐心和.一种新的进化算法-蚁群算法[J].系统工程理论与实践,2007(3)：2-6.