基于免疫遗传的机器人路径规划【开题报告】

1、毕业设计开题报告电气工程与自动化基于免疫遗传的机器人路径规划一、选题的背景与意义机器人是一个集环境感知、动态决策与规划、行为控制与执行等多功能于一体的的综合复杂系统。它集中了计算机工程、机械工程、人工智能、控制论以及仿生学等多学科的科研成果，代表着机电一体化的最高成就，同样也是20世纪自动控制最具有说服力的成就，是当代最高意义上的自动化。自从1959年，机器人之父约瑟夫？恩格尔伯格推出第一款机器人以来，出现了各种各样的机器人，机器人性能也不断的在完善，它们在农业、工业、航天以及空间探测等许多领域发挥着非常重 要的作用。先进机器人技术的发展代表着一个国家的综合科技实力和水平，目前许多发达国家，甚

2、 至一些发展中国家都已将机器人技术列为二十一世纪高新技术发展计划。移动机器人是一种具有自规划、自组织和自适应能力并能够在复杂环境下正常完成所要求工作的机器人。导航技术是反映移动式机器人自主能力的关键问题之一，也是其实现真正智能化和完全 自主移动的关键技术。实质上我们可将导航问题描述为这样三个问题：“我现在在哪里、“我要去哪里”以及“应该用什么方法去我想去的地方”。而这三个问题可由两级规划完成，即局部规划和全局规划。其中第一个和第三个问题，即机器人目标制导和路径跟踪问题，可由局部规划解决。第二个 问题，即将全局大任务分解成局部子任务，通过不断完成这些子任务最终达到全局目标的问题，可 由全局规划完

3、成。全局规划一般是建立在已知环境信息的基础上，适应范围相当有限；局部规划能 适应于不确定环境的情况，但其对规划系统的品质要求较高并且具有有时反应不及时的缺点。通过上述描述可知，机器人路径规划是机器人导航技术中不可或缺的重要组成部分，它要求机器人根据给予的指令及周围环境信息在满足某个或某些性能指标（如距离、时间、能量、工作代价 等）条件下，自主选定一条从起始点到达任务目标点的无碰障最优或次路径。它是移动机器人完成 任务的安全保障。传统的路径规划方法在解决机器人路径规划问题时缺乏自适应性和鲁棒性，计算量大且复杂， 很难得到最优路径。遗传算法由于其并行随机搜索的特点，在解决路径规划问题时有独特的优势

4、， 取得了一定的成果。但其仍存在缺乏指导性，易产生无效路径，收敛速度慢，易早熟等问题，无法 有效保证路径规划的计算效率。为了进一步提高遗传算法在路径规划中的搜索精度和收敛速度，应用基于免疫遗传算法的路径规划方法去解决已有成果的缺陷，同时亦尝试对一般免疫遗传算法进行适当的改进，以期能够在路 径规划中得到好的效果二、研究的基本内容与拟解决的主要问题：（一）研究的基本内容1、查找文献数据，了解机器人路径规划传统方法，并了解遗传免疫算法；2、用MATLAB完成遗传免疫算法对典型多峰测试函数的搜索；3、用遗传免疫算法完成机器人在栅格环境下的搜索；4、对搜索策略进行分析评价。5、要求能在文献阅读的查找基础

5、上完成基本的遗传免疫算法的编程，建立栅格环境，用遗传 免疫算法进行搜索，达到预期的规定要求。（二）要解决的关建问题1、用栅格法建立环境模型。2、在遗传的基础上建立 MATLAB函数，并对多峰测试函数进行验证。3、设置障碍物，并确定适应度函数模型。三、研究的方法与技术路线：到目前为止，机器人的发展仍处于初始阶段，但是机器人路径规划的方法已经层出不穷了。根 据规划体对环境信息的认知程度，机器人路径规划方法可分为基于已知环境模型的全局路径规划和 基于传感器信息的局部路径规划。对于环境已知条件下的离线全局规划方法，已取得大量结果。下 面将主要研究全局路径规划。移动机器人运动环境模型的建立环境建模是机器

6、人路径规划的重要环节，目的是为了建立一个便于进行路径规划使用的环境模 型。合理的环境模型要求是便于计算机存储、处理、更新和使用。当然在实际应用中，这些要求有 可能会有冲突。移动机器人的工作环境一般可简化成二维模型，用地图来表示环境的信息情况。关 于环境地图的创建，有三个基本问题需要解决：如何表示环境地图；如何获取环境信息；如何实时 更新地图。目前地图创建的方法很多，大致可以分为栅格法、特征法和拓扑法这三类。特征法建立的模型虽然易于用计算描述和表示，但其需要特征提取的办法处理过程，对传感器 噪声非常敏感，只适于高度的结构化的环境。拓扑法在前面我们就说过，当障碍物增加时，实时更 新及其困难。而栅格

7、法建立的模型以为计算机存储、操作、显示与维护，并且易于扩充、修改，直 观性强，特别是易与遥感影像的联合处理。鉴于此，本人将使用栅格法建立环境地图。在使用栅格法创建地图时，需要做以下几个假设：（1）机器人的运动是在二维空间中;(2)用尺寸相同的栅格对工作环境进行划分。若栅格包含有障碍物，则称为障碍栅格，并用数字“1”标示；否则，称之为自由栅格，并用数字“0”标示；(3)由于环境是静态的，所以机器人在运动过程中障碍物的大小和位置都是不变的。在大多数文献中，对栅格进行标识时要么使用直角坐标法，要么使用序号法。而此处，将会使用两者结合一起来标识。因为相比坐标法，序号法占有的内存很少，便于在遗传操作中使

8、用。另一 方面，直角坐标法在描述栅格之间的相对位置，计算路径长度及检验路径可行性方面有着巨大的优 势。下面给出直接坐标法和序号法转换关系：X = N%niY = N /n2上式中，X和Y分别表示指定栅格的横坐标和纵坐标，N表示该栅格的序号，ni和n2分别指横坐标和纵坐标的栅格数。建模后的10*10机器人工作环境如下图所示。0123456789 XS(O)123 1415678g011121311415Id17IS1920212223124252627，2829303 口3233 J34，3536373839404口4243144，454d474g4950515253545556575S5960

9、61626364656667施】6970711173，74 1757677 17879SOS1S283S4S5S687SS8990919293，9495期97E(W图序号法和直鬲坐标法建立例机翳入空间模型全局路径规划全局路径规划的作业环境信息是完全已知的，故又称为静态路径规划，其主要包括环境建模和路径搜索策略两个子问题。典型的全局路径规划方法有栅格法、拓扑法、可视图法、概率路径图法、广度优先搜索方法等。栅格法栅格法是当前研究最广泛的路径规划之一，该方法Hovoden于1968年提出。栅格法的主要思想3是将机器人的工作环境划分成一系列具有二值信息的网格单元，障碍物和自由空间分别被不同的数 值所标

10、示（如0表示自由栅格，1表示障碍物栅格）。这些栅格构成了一个连通图，在这个连通图上 搜索一条从初始位置到目标栅格的路径。在栅格法中，栅格的大小是由机器人行进的区域的可视度所决定的，其直接影响着环境信息存 储量的大小和规划时间的长短。栅格选的小，环境的分辨率就高，在密集障碍物或狭窄通道中发现 路径的能力强，但环境信息的储存量大，规划时间长，降低了系统的实时性；栅格选的大了，环境 信息储存量小，决策速度快，抗干扰能力强，但环境的分辨率低，在相应环境中发现路径的能力变 差。因此合理选择栅格的大小是栅格法的重要问题。在某个局部栅格中，所有的参考点（也即机器人穿行环境时收集的传感器数据）应该是互相可 见

11、的。这就意味着在空旷的区域同一时间能够有更多的参考点是可视的，由此一个有着粗糙解析的 大栅格就可以将此区域描述出来。相反的在混乱区域，当机器人围绕障碍物转向或穿过门时，它容 易很快的丢失掉其他参考点的视线。描述这些区域的栅格就应当较小而且要有一个较好的解析。这 也就使得机器人在障碍物间或狭窄走廊中的机动行进成为可能。另外，栅格越小，就更容易做到路 径的实时再规划。虽然这种方法不能保证所有可能的路径都能够被发现，但是它提供了一种对环境 本能和实践的描述，使得机器人更加人性化，“正如机器人能够自主看见一样”。区域中的栅格通过那些重叠在不同栅格上的参考点相互连接在一起。这样整个机器人的路径规划问题也

12、就分解成了如何规划从一个参考点运行到下一个参考点最优无碰路径问题。免疫遗传算法与一般免疫算法一样，免疫遗传算法将待求解的问题对应为抗原，问题的解对应为抗体，在许 多方面表现出超越遗传算法和免疫算法的优点。其具有下述功能：克服通常遗传算法收敛方向无法 控制的缺陷，把目标函数和制约条件作为抗原，这就能保证所生成的抗体直接与问题相关联，收敛 方向能够得到控制。生成的抗体能够有效的排除抗原也就相当于求得了问题的最优解。对于抗原亲 和力高的抗体进行记忆，能促进快速求解，即当遇到同类抗原时可以快速生成与之对应的抗体。一般免疫遗传算法组成免疫遗传算法的流程图：抗原输入初始抗体产生计算适应度计算抗体浓度 计算

13、选择概率抗体产生(、交叉,变异，装 样性保持)遗传操作结束图1.免疫遗传算法流程图(1)抗原输入，即将目标函数和各种约束作为抗原。(2)初始抗体的产生，即生成初始解。一般都是根据问题的特征随机生成一组初始化解。(3)亲和度计算。亲和度指两者的关联性。生物体内，亲和度分为抗体一抗原间亲和度以及抗 体一抗体间亲和度这两类。前者即相当于遗传算法中的适应度，后者体现了不同抗体之间 的相似度，是构造群抗体浓度必须的量。(4)抗体的抑制/促进。与抗原亲和度高的抗体在算法中显然受到促进，会以较高的概率进入下 一代抗体群。这样做往往会使种群过于单一，易陷入局部最优。因此要引入必要的抑制策 略以保持种群中抗体的

14、多样性，这可以通过构造抗体的选择概率时加入抗体浓度因素来实 现，也即抗体间相似度高的抗体，应受到抑制。(5)遗传操作。当前种群中通过抗体的抑制/促进，抗体交叉、变异生成新一代抗体，进入下一代。算法通过综合考虑抗体适应度和其在种群中的浓度，构造选择概率对其进行选择，对 选择出来的抗体群进行遗传操作(交叉、变异)，产生新一代抗体。既确保抗体群整体朝着适应度高的方向进化，又维持了种群中抗体的多样性。本人在基本框架的基础上，对算法的具体步骤进行改进，增加精英选择策略等以其能够获得高效的效果。个体编码个体表示移动机器人在其工作空间中的一条运动路径。机器人由其起始位置 S g路径运动到终点位置E,即为1个

15、个体。该个体用直角坐标形式可表示为：(0 , 0), (0, 1), (0, 2), (1, 3), (2, (3 , 5) , ?, (9 , 9)。若每一位坐标用4位二进制数表示，则同一个体可表示为：0 000, 0 000,0 000, 0 001 , ?, 1 001 , 1 001。若用栅格序号表示，则同一个体可表示为：0, 10, 20, 31,42, 53,，99。由此可见，个体采用栅格序号编码较直角坐标或二进制编码长度短、简明、直观。种群初始化初始群体是遗传算法迭代运算的起点，它由一定数目的个体组成，在机器人运动的起点到终点之间，用一系列随机选择、自由、不一定连续的栅格序号连接

16、起始点和终点。在种群初始化过程中，确保个体基因位上填充的都为自由栅格，并且初始种群中的每个个体的长度大于3,再经过插入、删除操作生成一系列不问断无障碍路径。采用这种操作方法有利于种群初始化。个体适应度函数个体的适应度函数与免疫算法的计算时间和效率密切相关。这里所讨论的问题是求从起始点到终点的1条最优路径，且该路径不能与障碍物相交，以确保机器人按这条路径运动时不与障碍物发生碰撞。选取如下个体适应度函数：1精英选择策略精英选择策略是由 de.K.A.Jong提出的，其主要是为了解决遗传算法不能收敛到全局最优解这个缺陷。其主要思想就是，将当前群体中迄今出现的最佳个体作为精英个体不进行任何操作而直接复

17、制到下一代中。定义描述即为，假设免疫遗传算法进化到第t代时，群体中的最优个体为a(t),且新一代群体为A(t+1),若a(t)不属于A(t+1),则将a(t)作为精英个体复制到 A(t+1)中，作为其的个体。 此种免疫遗传算法，其具体步骤如下：进行个体免疫遗传编码，随机产生初始种群；按照设计的适应度函数，确定种群中每个个体的适应度值，并且将适应度最大抗体作为精英抗体保存在一个专有变量中；若种群为第一代抗体群，则转到第五步，否则，继续；再次确定抗体群中每个个体的适应度值。若当前种群中没有个体的适应度值比精英抗体适应度值大，则将该精英抗体复制到抗体群中，并将抗体群中适应度最小的抗体淘汰掉；或者若当

18、前群体中有个体适应度值大于精英抗体的适应度值，则将此作为新的精英抗体保存到专有变量中。否则，继续；计算抗体浓度，对抗体执行选择和复制操作；对抗体群实行交叉和变异操作；判断设置条件是否得到满足。若满足，算法终止；否则，回到第四步继续。四、研究的总体安排与进度：2010.11.30-12.30:查找文献资料，了解路径规划，遗传免疫算法，完成开题报告的撰写，2011.1.1-1.30:熟悉MATLAB的编程语言，完成算法的编写。2011.2.1-3.30:进行系统软件的调试。2011.4.1-4.30:对结果进行分析评价，撰写毕业论文，并进行答辩。五、主要参考文献：1袁曾让，高明.在动态环境中移动机

19、器人导用和避碰的一种新方法.机器人,2000,22(2):81-882曹雁军.机器人路径规划研究.河北工业大学硕士论文，20083莫宏伟，左兴权.人工免疫系统.科学出版社，2009:3-284李爱萍，李元宗.机器人路径规划方法的研究.机械工程与自动化,2009(5):194-1965王醒策，张汝波，顾国昌.基于势场栅格法的机器人全局路径规戈IJ.哈尔滨工程大学学 报,2003,24(2):170-1746于洪斌，李孝安.基于栅格法的机器人快速路径规划.微电子学与计算机.2005,22(6):98-1007陈曦，谭冠政，江斌.基于免疫遗传算法的移动机器人实时最优路径规划.中南大学学报(自然版)，2008,39(3):577-5838孙树栋.遗传算法在机器人路径规划中的应用研究.西北工业大学学报，1998,16(1):79-83.9李擎，冯金玲，柳延林等.自适应遗传算法在移动机器人路径规划中的应用.北京科技大学学报，2008,30(3):316-323J.Timmis, A.Hone, T.Stibor,etc. Theoretical advances