《武汉工程大学学报》 2008年03期
110-113
出版日期：2008-03-31
ISSN:1674-2869
CN:42-1779/TQ
基于遗传算法的自主机器人避障方法研究
0引言机器人足球比赛己经成为当前人工智能和机器人领域的研究热点之一，它的兴起促进了多智能体系统、分布式人工智能和机器人学以及视觉系统等领域的研究与发展.设计和开发自主足球机器人是最具挑战性的研究项目，因为自主型足球机器人是真正的分布式智能体系统，每个机器人由独立的环境感知、行为决策及运动控制系统组成，并且通过无线通讯交换信息实现多机器人合作.机器人路径规划是指在足球机器人的比赛中，实时的给出机器人到达目标点的安全，高效运动路线，安全是让机器人有更好的避开障碍物，不产生碰撞，高效是让机器人尽可能到达目标点所用的时间最短.下面将详细的阐述在势场法（Artificial potential Filed , APFF）的基础上，使用遗传算法对其进行的改进.1人工势场法的定义人工势场法最先由Khatib提出［1］,实质上是对机器人的运行空间人为的定义一个抽象势场，该势场为目标位姿的引力场与障碍物的斥力场的叠加.就是将整个比赛场地虚拟成一个有力存在的场地，把力分为引力和斥力，根据比赛的进行，场上队员会发生变化，因而整个力场中各部分的受力情况也会发生变化，新局面策略系统可以根据场上的这种变化去实时地控制足球机器人的运动情况.具体而言，要先建立引力场和斥力场，如图1所示；在机器人周围分布着类似于环状的虚拟力场，机器人与球之间表现为引力，机器人与机器人之间表现为斥力，通过对参数的调节，一方面可以使双方机器人相遇时会改变方向；另一方面，可以在寻找目标球时绕过对方球员，达到实时避障，争夺足球控制权的效果.图1人工势场
Fig.1Artificial potential 因此，在这里对人工势场定义为
U（X）=UG（X）+U0（X）（1）
式（1）中UG（X）为目标位姿的引力场,U0（X）为障碍物的斥力场.定义引力和斥力分别为对应引力场和斥力场的负梯度，根据空间动力学方程和拉格朗日方程，可推导出人工势场对机器人的作用力F（X）为
F（X）=Ft（X）+Fr（X）（2）
式（2）中Ft（X）为目标位姿对机器人的引力，Fr（X）为障碍物对机器人的斥力.1.1目标球的引力场函数及障碍物的斥力场函数目标球的引力场函数为
UG（X）=12k（X-Xg）2则引力为目标势函数的负梯度：
Ft（X）=-grad［UG（X）］=-k（X-Xg）
其中k为比例因子，X为目标当前位置，Xg目标点位置.碍物的斥力场函数采用FIRAS(Force Inducing an Artificial Repulsion from the Surface)函数：
U0（X）=12η1X-X0-1ρ2，（X-X0）<ρ
0，（X-X0）≥ρ（5）
式（5）中,η为位置增益系数,ρ为单个障碍物最大影响距离,X-X0为机器人在空间位置与障碍物的最短距离.相应的斥力为
Fr（X）=-gard（U0（X））=
η1X-X0-1ρ1（X-X0）2（X-X0）x，
（X-X0）≤ρ
0，（X-X0）>ρ（6）在传统人工势场法中，障碍物被认为是高势能点，目标点是低势能点.在机器人路径规划中，一个机器人从高势能点走向低势能点［2］.基本步骤如下：（1） 设定一个与到目标点距离有关的势场函数Φ=1D，D为机器人到目标点的距离.（2） 利用算法确定一个最小势能点.（3） 利用人工势场法引导机器人沿势场走到最小势能点.（4） 重复步骤（2）和（3）步直到机器人到达目标点.1.2优缺点分析人工势场法实际上是使障碍物的分布情况及其位置等信息反映在环境中的势场值中，也即势场反映了环境的拓扑结构.由于机器人的运动是由其当前位置所承受的势场及其梯度方向确定的，所以，与全局规划相比具有计算量小、实时性等优点.势场方法虽能以高效的方式找到一条通往目标的路径，但势场中有许多能够使机器人落入圈套的局部极小，即零势点.所有的障碍物与目标在这些点上形成的抽象力之和为零.从而机器人受到零控制力而停止移动达不到目标，当环境中的障碍物非圆时，由于障碍物的形状比较复杂，非圆对称的排斥力场与圆对称的吸引力场迭加后更容易出现局部极小，如图2所示.机器人很早就停止移动而不能达到目标. 第3期孔伟，等：基于遗传算法的自主机器人避障方法研究
武汉工程大学学报第30卷
图2机器人寻找目标过程
Fig.2Robot search for the target2改进算法在APFF中，通过对目标点距离，到障碍物的距离，转角大小（路线光滑的判定），三个评判函数来判定，通过实验表明，对于单个障碍物来说实现起来比较成功，效果很理想，但是对于多障碍物，效果不是很好，因此，利用遗传算法并借用模拟退火算法（simulated Annealing Genetic Algorithm, SAGA）［3］使机器人避免局部极小(即零势点)，对其进行优化寻求最优路径.2.1模拟退火算法定义及应用模拟退火算法是一种跳出局部极值的有效方法［4］.模拟退火算法是Kirkpatrick［3］等将固体退火思想引入组合优化领域，其原理为先将固体加热至融化，然后徐徐冷却使之凝固成规则整晶体的热力学过程.统计物理学观点看，随着温度的降低，物质的能量将逐渐趋近于一个较低的状态，并最终达到某种平衡［5］.模拟退火算法在某一初始温度下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解时能概率性地跳出并最终趋于全局最优解. 模拟退火算法是依据Metropolis［6］接受准则来选取新解的，具体而言，在温度t，由当前状态i产生新状态j，两者的能量分别Ei和Ej，Metropolis准则对应的转移概率Pk为
Pk（ij）=1,E（i）≤E（j）
expE（i）-E（j）t,E（i）>E（j）（7）模拟退火算法依据式（7）计算的概率接受新解，因此除接受优化解外，还在一个限定范围内接受恶化解，这是模拟退火算法与局部搜索算法的本质区别所在.开始时t值大，可能接受较差的恶化解；随着t值的减小，只能接受较好的恶化解；最后在t值趋于零值时，就不再接受任何恶化解.这就使模拟退火算法既可以从局部最优解中跳出，更有可能求得优化问题的全局最优解，又不失简单性和通用性.这是出现在多个障碍物情况下怎样避免局部最小的关键所在,在与人工势场相结合时可以解决多障碍物问题.2.2适应度函数选择适和适应度函数在遗传算法中是相当重要的，它的选取直接影响到遗传算法的收敛速度与成功与否［6］.另由于机器人运动特性，还要考虑转角大小（路线光滑的判定），所以适应度函数取
Fit（p）=k1dist（p）+k2·Φ（p）（8）
式（8）中，k1,k2分别是适应度函数两个部分的权值，为适当大的实数值.dist(p)表示路径的总长度.
dist（p）=∑n-1i=1d（mi,mi+1）
其中,d（mi,mi+1）表示相邻节点mi和mi+1之间的距离.取水平或垂直方向为1，斜线方向距离是2.Φ（p）={1，或0}用来描述曲线的平滑程度.当为延前进方向或向上向下时取1，当反方向，该适应度值取0，即为无意义的值.2.3遗传操作遗传算法在运行早期个体差异较大，当采用经典的轮盘赌方式选择，后代产生个数与父个体适应度大小成正比，因此在早期容易使中坚力量好的个体的后代充斥整个种群，造成早熟(premature)；在遗传算法后期，适应度趋向一致，优秀的个体在产生后代时，优势不明显，从而使整个种群进化停滞不前（stalling）.因此对适应度适当地拉伸（scaling or stretching）是必要的.这样在温度高时（遗传算法前期），适应度相近的个体产生的后代概率相近；而当温度不断下降后，拉伸作用加强，使适应度相近的个体适应度差异放大，从而使得优秀的个体优势更明显. 交叉操作是遗传算法中最主要的遗传操作，它在遗传算法中起着关键作用［7］，是产生新个体的主要方法.变异操作的作用是保持群体中基因的多样性，以防止出现未成熟收敛.2.4算法实现过程由于模拟退火算法的概率突跳特性在解空间中随机寻找目标函数的全局最优解，为了避免恶化解导致的早熟现象，采用适应度拉伸算法［8］对其拉伸是必要的.该算法如下：
fi=efi/T∑Mi=1efi/T(9)
T=T0×0.99g-1(10)
式（9）、（10）中fi为第i个个体适应度，M为种群大小，g为遗传代数，T为当前温度，T0为初始温度.算法设计过程如下：（1） 利用栅格法建立机器人运行空间模型，机器人的初始位置、球的位置和障碍物的位置任意摆放.（2） 取可能出现零势点的位置产生一定规模的初始种群.（3） 计算种群的适应度，并进一步向下执行判断收敛准则.（4） 执行算法的收敛准则，如果符合要求，输出最佳个体及其代表的最优解.否则，往下继续执行.（5） 对种群执行遗传算法操作，进行选择、交叉、变异生成下一代种群.（6） 对种群各个体进行模拟退火操作.（7） 由模拟退火操作拉伸后产生的新一代种群，返回到第三步.算法流程如图3所示。图3遗传模拟退火算法流程
Fig.3Genetic algorithm and SAGA process通过以上流程，可以输出最佳个体代表的最优解，解决了因出现局部极小导致的零势点问题，再通过人工势场的避障方法，就可以顺利的寻找出一条到达目标球点的路径，进而绕过多个障碍物.3实验仿真为验证算法的可行性及实用性，取MATLAB7.0环境下对算法进行仿真实验，栅格维数取20×20取初始位置为坐标为（0,0）,目标位置为（19,19），障碍物位置为（5,6）,（7,7），（15,12）初始种群的规模取50，适应度函数的参数中k1=1、k2=1，交叉概率为0.75,变异率取0.01，实验结果的历代适应度曲线如图4所示。图4历代适应度曲线
Fig.4History fitness curve4实验测试将本方法应用到FIRA全自主机器人比赛3vs3中，取小球的位置为目标点，令避障机器人在远离球的另外一端，它们之间存在其它机器人作为障碍物，得到的机器人移动路径如图5所示.图5机器人的避障轨迹
Fig.5Robot obstacle avoidance track5结语以上讨论了基于遗传算法的人工避障方法.利用遗传算法与模拟退火算法相结合的混合遗传算法对传统势场进行了优化改进，可以防止遗传算法早熟现象的发生，并增强了其局部寻优的能力.因为在全自主机器人比赛中，机器人移动速度较慢，障碍物为对方与已方机器人，在避障过程中基本满足了实时性要求.