基于正反馈自适应遗传算法的机器人路径滚动规划.pdf

第27卷第6期
计算机应用研究
Vo].27No.6
2010年6月
Application Research of Computer
Jun.2010
基于正反馈自适应遗传算法的
机器人路径滚动规划
胡喜玲,国海涛
(鲁东大学信息科学与工程学院,山东烟台264025
摘要:针对传统遗传算法求解机器人路径规划问题存在的收敛速度較慢的缺陷,将妈蚁算法、模拟退火算法、
滚动规划和传算法相结合,提出了一种新颖的基于正反愤自适应遗传算法的滚动规划。仿真实验表明,即使
在复杂的未知境下,利用本算法也可以规划出一条全局优化路径,且能安全選碰。
关键词:路径规划;遠传算法;滚动规划;自适应
中图分类号:TP242.6文献标志码:A文章编号:1001-3695(2010)06-2037-03
doi:10.3969/j.issn.1001-3695.2010.06.011
Robot path planning based on
positive feedback adaptive genetic algorithm
HU Xi-ling, GUO Hai-tao
College ofinformation Science &Engineering, Ludong University, Yantai Shandong 264025, China
Abstract In order to improve the convergence speed of traditional genetic algorithm for path planninn of robot, presented a
new robot path planning based on positive feedback adaptive genetic algorithm by integrating ant algorithm, simulated annea
ling algorithm, rolling planning and genetic algorithm. Computer experiment results demonstrate that the proposed algorithm can
be used to solve the path planning for mobile robot even in the complex unknown environment, and achieve the successful ob-
stacle avoidance
Key words: path planning; genetic algorithm; rolling planning; adaptive
机器人路径规划是指移动机器人在工作空间中搜索一条径前进一步。每前进一步,都重复这一过程,因此,机器人在动
从起点到目标点的最优或近似最优的无碰路径。由于它是研态局部优化路径引导下,可沿一条全局较优的路径安全地到达
究机器人控制的础问题,得到广泛的研究和关注。如何保证终点。仿真实验结果表明,即使在障碍物非常复杂的地理环境
在复杂环境下规划出的机器人路径是全局最优或棊本最优一中,用本算法也能迅速规划出一条优化路径,且能安全地到达
直是这一领域的一个研究难题。已有不少学者提出了解决未终点,效果十分令人满意
知环境下机器人路径规划的方法和策略,如基于滚动窗口的规
划方法、蚁群算法2、粒子群算法等。其中遗传算法是通1环境描述
过模拟生物的进化过程而实现的一种最优化方式。遗传算法
由于具有优良的全局寻优能力和隐含的并行计算特性,保证了
机器人路径规划就是在工作环境中寻找一个从起始点到
该方法应用于机器人路径规划的可能性和有效性,因此有目标点的序列,这些点及相邻点之间的连线不与环境中障碍物
许多学者将遗传算法应用到机器人路砼规划中6)。但息山相交,且在所有这样的序列中,该序列的代价(如路径长度、费
于遗传算法从概率上来说群体中的优秀个体和全局最优解之月等)最小。机器人的工作环境在坐标系XOY中,sar为机器
间的亲和度要大于群体中其他个体和全局最优解之间的亲和人的出发点,goal为目标点,黑色实心物体表示障碍物,机器人
度:而且,与优秀个体有较大亲和度的个体也应有较高的适应路径规刘即是寻找一个点的序列P
度。优秀个体所体现的特征信息能否被充分利用将是决定该
P=i start, P, 2, ,P,, goal
算法优化能力的一个重要因素。简言之,遗传算法对系统中的其中P(j=1,2,…,n)不为障碍物点,其与相邻点的连接不与
反馈信息没有充分利用,往往导致无为的冗余法代,造成求环境中的任何障碍物相交,且满足路径代价最小(路径规划中
解效率不高。基于此,借鉴蚁群算法,在交叉与变异算子中引对障碍物作相应膨胀处理)。在机器人的工作环境中以star
入正反馈机制,可以提高遗传算法的收敛速度。根据研究现goal作为X轴,以etar作为原点新建一个坐标系XO'Y,如图
状及不足,本文研究了一种全新的基于遗传算法的移动机器人1所示。将线段star-goal进行n+1等分,在每一个等分点作
路径滚动规划算法。该方法首先将目标点映射到机器人视野"的垂线,得到一组平行Y的线{ム、互,…,Ln,机器人路径与
域内侧边界处,由机器人探浰环境,利用正反馈遗传算法完成此组并行线的交点即是机器人路径序列。这样优化路径就简
机器人静态局部最优路径的搜索,机器人根据规划好的局部路化为一维的y坐标编码优化间题。在初始化种群时每一条路
收稿日期:200-1-1;1修回日期:200.-12-29基金项目:国家自然科学基金资助项目(60673102)
作者简介:胡喜玲(19%3-),女,山东蒙成人,副教授,主要研究方向为人工智能、智能控制(hdld@126.com);国海涛(1980-),另,山东梁山
项士,主要研究方向为人工智能、智能控
万方数据