基于可拓遗传算法的机器人路径规划

发布时间：2012-6-29 10:53 发布者：1770309616

目前，国内外对机器人路径规划方法的研究主要有两大类，传统方法与智能方法。传统方法主要包括：梯度法、栅格法、枚举法、人工势场法、自由空间法、A*等图搜索方法及随机搜索法等。其中梯度法易陷入局部最小点，图搜索法、枚举法不能用于高维的优化问题，势场法则存在丢失解的部分有用信息的可能。用于机器人路径规划的智能方法主要有模糊逻辑、神经网络、遗传算法等，而模糊方法主要用于在线的规划中，自适应性较差。神经网络方法对于环境复杂的情况，规划能力较差，遗传算法则是目前应用较多的一种方法，受到了广大研究者的重视．但是，用遗传算法进行机器人路径规划时，随机产生初始种群，种群规模大导致搜索空间较大，删除冗余个体能力较差，大大影响了路径规划的速度，特别是环境复杂或多机器人路径规划时，这种缺点更是明显。笔者在原有基于遗传算法的机器人路径规划方法的基础上，引入了可拓学理论，对遗传算法进行了改进，以提高机器人路径规划的速度和能力。
　　1 基于栅格的可拓遗传算法路径规划
　　可拓学是1983年由我国学者蔡文提出的一门原创性学科，主要研究不相容问题的转化与解决的规律。经过二十年的发展已经形成了它的理论框架，并且在信息、知识生成、管理、营销、策划、控制、数据挖掘等许多领域得到了应用。可拓学现在已经成为人工智能领域中一个新的学术研究热点。
　　本文将可拓理论应用到遗传算法中解决路径规划问题。
　　（1）采用可拓物元的表示方法来表示机器人的位置信息；
　　（2）将可拓学中的主要概念――关联函数作为遗传算法的适应度函数；
　　（3）采用可拓工程方法中的三种可拓变换形式，丰富了遗传算法的变异方式。
　　1.1 栅格表示模型
　　为了模拟机器人的工作环境需要对其工作空间建立模型，只考虑机器人工作空间的平面状况，在二维空间中采用栅格法来建立机器人的工作空间模型，按照机器人及工作空间的大小来确定栅格的数目，以保证机器人可以在其中自由移动。用直角坐标法在矩形的工作空间中建立多个等值大小的小栅格(以10×10的栅格为例)。将直角坐标法同序号法相结合使用，根据条件的不同按照映射关系进行变换。自由空间和障碍物均可表示成栅格块的集合。划分后的机器人工作空间如图2所示，图中阴影区为障碍物。

浏览全文: