２０１５．１２ 岳工自动化 Ｏｒｄｎａｎｃｅ Ｉｎｄｕｓｔｒｙ Ａｕｔｏｍａｔｉｏｎ ３４（１２） 基于遗传算法的机器鱼水中路径规划 李连鹏 ， ，一，苏 中 ， ，一，解迎刚１，２，３，刘福朝 ， ，３ （１．北京信息科技大学，北京１００１９２；２．高动态导航技术北京市重点实验室，北京１００１０１； ３．智能控制研究所，北京ｌＯ０１０１） 摘要：针对机器鱼水中路径寻优的具体要求，提出一种以遗传算法为基础的机器鱼路径规划方法。通过介绍遗 传算法的３种基本操作，将遗传算法应用到试验场景中规划出最优路径，分析研究了一种根据目标点与机器鱼的距 离变化而改变机器鱼运动速度的策略，并进行仿真分析和实验。仿真结果表明：采用遗传算法的水中救援路径规划 可将救援时间缩短３０％ｖ；Ｚ上，提高了寻优效率。说明遗传算法对机器鱼的路径规划具有积极效果和快速寻优特性。 关键词：机器鱼；遗传算法；水中救援；路径规划 中图分类号：ＴＰ２４２．６ 文献标志码：Ａ Ｐａｔｈ Ｐｌａｎｎｉｎｇ ｏｆ Ｒｏｂｏｔ Ｆｉｓｈ’Ｓ Ｂａｓｅｄ ｏｎ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ Ｌｉ Ｌｉａｎｐｅｎｇ ’ ’ ，Ｓｕ Ｚｈｏｎｇ ’ ’ ，Ｘｉｅ Ｙｉｎｇｇａｎｇ ’ ’ ，Ｌｉｕ Ｆｕｃｈａｏ ’ ’ （１．Ｂｅｉｊｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ＆Ｔｅｃｈｎｏｌｏｇｙ Ｕｎｉｖｅｒｓｉｔｙ，Ｂｅｉｊｉｎｇ １００１９２，Ｃｈｉｎａ；２．Ｂｅｉｊｉｎｇ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆＨｉｇｈ Ｄｙｎａｍｉｃ Ｎａｖｉｇａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ １Ｏ０１０１，Ｃｈｉｎａ；３．Ｉｎｓｔｉｔｕｔｅ ｏｆＩｎｔｅｌｌｉｇｅｎｃｅ Ｃｏｎｔｒｏｌ，Ｂｅｉｊｉｎｇ １Ｏ０１０１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａｉｍｉｎｇ ａｔ ｒｅｑｕｉｒｅｍｅｎｔｓ ｏｆ ｔｈｅ ｒｏｂｏｔ ｆｉｓｈ ｗａｔｅｒ ｐａｔｈ ｓｅａｒｃｈｉｎｇ，ａ ｎｅｗ ｍｅｔｈｏｄ ｏｆ ｒｏｂｏｔ ｆｉｓｈ ｐａｔｈ ｐｌａｎｎｉｎｇ ｂａｓｅｄ ｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ｐｒｏｐｏｓｅｄ。Ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ３ ｂａｓｉｃ ｏｐｅｒａｔｉｏｎｓ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｔｈｅ ｔｅｓｔ ｓｃｅｎｅ ｔｏ ｐｌａｎ ｔｈｅ ｏｐｔｉｍａｌ ｐａｔｈ，ａｎｄ ａｎａｌｙｚｅｄ ａ ｓｔｒａｔｅｇｙ ｔｏ ｃｈａｎｇｅ ｔｈｅ ｓｐｅｅｄ ｏｆ ｔｈｅ ｒｏｂｏｔ ｆｉｓｈ．Ｓｉｍｕｌａｔｉｏｎ ａｎａｌｙｓｉｓ ａｎｄ ｅｘｐｅｒｉｍｅｎｔ ａｒｅ ｃａｒｒｉｅｄ ｏｕｔ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｕｓｅ ｏｆ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｎ ｔｈｅ ｗａｔｅｒ ｒｅｓｃｕｅ ｐａｔｈ ｐｌａｎｎｉｎｇ ｃａｎ ｓｈｏｒｔｅｎ ｔｈｅ ｒｅｓｃｕｅ ｔｉｍｅ ｏｆ ｍｏｒｅ ｔｈａｎ ３０％，ｉｍｐｒｏｖｉｎｇ ｔｈｅ ｓｅａｒｃｈ ｅｆｉｃｉｅｎｃｙ．Ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｆｔｈｍ ｈａｓ ｐｏｓｉｔｉｖｅ ｅｆｆｅｃｔｓ ｏｎ ｔｈｅ ｐａｔｈ ｐｌａｎｎｉｎｇ ｏｆ ｔｈｅ ｒｏｂｏｔ ｆｉｓｈ ａｎｄ ｔｈｅ ｆａｓｔ ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｒｏｂｏｔｉｃ ｆｉｓｈ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｔｈｅ ｗａｔｅｒ ｒｅｓｃｕｅ；ｐａｔｈ ｐｌａｎｎｉｎｇ Ｏ 引言 随着近年来机器人技术、控制技术、人工智能、 水动力学以及新型材料、传感器和执行机构的发展， 各式各样的水下机器人将以更快的速度发展起来。 未来的仿生机器鱼将在水下环境中进行海底勘探、 改变机器鱼速度来改变冲击力量的策略，配合遗传 算法规划处的最优路径，从而在最短的时间内完成 救援任务。 １ 遗传算法描述 １．１ 遗传算法介绍 海洋生物观察、水下施工和军事侦察、水中救援等 艰巨工作，这也吸引了越来越多的科研工作者进行 仿鱼型机器人的研究 Ｊ。 由于水下情况复杂，环境恶劣，水上事故频发， 水中机器人救援成为近年来研究的热点。在救援过 遗传算法是一种模拟自然生物进化过程的全局 随机搜索算法，由美国Ｍｃｉｈｉｇｎａ大学的Ｈｏｌｌｎａｄ教 授于２０世纪６０年代提出。它将计算机科学与进化 论思想有机结合起来，借助生物进化机制与遗传学 程中，怎样在最短的时间内完成救援任务显得尤为 重要；因此路径规划成为水中救援研究的重中之重。 在现有的水中救援赛中，没有明确的路径规划 方法及策略，仅凭人的判断进行规划不能充分利用 原理的根优胜劣汰和适者生存原则，通过模拟自然 界中生物群体由低级、简单到高级、复杂的生物进 化过程，使所要解决的问题从初始解逐渐逼近最优 解或准最优解 ］。作为一种新的全局优化搜索算法， 遗传算法简单易用，对很多优化问题能够较容易地 解出令人满意的解，且适用于并行分布处理，已在 时问完成救援任务。作为一种新的全局优化搜索算 法，遗传算法（ｇｎｅｃｔｃｉ ａｌｇｏｒｔｉｈｍｓ）因其简单易用，适 科学研究和工程最优化领域中展现出独特魅力 Ｊ。 １．２遗传算法的３种基本操作 用于并行分布处理等特点，得到了深入发展和广泛 应用。笔者将遗传算法应用于路径寻优，充分利用 距离判断，在众多可选择路径中，选择最短救援距 离，并且针对救援目标的重量问题提出了一种通过 １．２．１ 选择 选择即是在种群中选择一个个体，它是随机映 收稿日期：２０１５－０８—２２；修回日期：２０１５－０９—２９ 基金项目：国家自然基金（６１２６１１６０４９７）：北京市科技计划课题（Ｚ１３１１００００５３２３００９）；研究生教育质量工程（５１１１５２４１０２） 作者简介：李连鹏（１９９１一），男，河北人，硕士，从事高旋载体姿态角解算、救援机器人研究。 ・９６・ 兵工自动化 第３４卷 上，充分体现了此方法的高效性和合理性，验证了 图６最优路径选择 在比赛中，待救援目标的位置坐标是一定的。 图４为坐标点分布图，图５给出了一张随机选择的 路径，图６是经过遍历比较得到的距离和最短的路 径即最优路径。机器鱼按图５所给路径完成救援所 走过的路程为７．５０６ ｍ，按图６所给路径完成救援 所走过的路程为５．８２８ ｍ。不仅路程差距较大，而 且选择最优路径完成救援所用时间也较短。仿真结 果清楚地显示出基于遗传算法对路径的规划有积极 效果和快速寻优特性，是最优的路径。 ３．２实验结果分析 为了检验仿真结果的可靠性，进行了如下实验 操作： １）按照水中救援比赛待救援目标的标准位置 进行实验，分别按图５和图６所给的路径进行救 援，记录时间。 ２）改变待救援目标的位置，通过平台得到５ 点的坐标，输入到程序中，仿真出最优路径。记录 随机选择一个路径和规划的最优路径完成水中救援 的时间。 ３）重复２）６次。部分实验结果如表１。 实验结果表明，基于遗传算法的水中救援的路 径规划方法在比赛中有重要应用。机器鱼按照遗传 算法规划出的路径完成救援任务所用的时间要小于 随机选择路径所用的时间，救援时间缩短了３０％以 仿真的结果。 表１ 实验结果 １３０ ｌ８４ ５４ ４１．５ ｌｌ５ ｌ７３ ４８ ４１．７ １２３ １３２ ９ ７．３ １４８ ２０８ ６０ ４０．５ １４２ １９１ ４９ ３４．５ １２１ １６ｌ ４０ ３３．１ ４ 结束语 实验结果表明：笔者提出的基于遗传算法的机 器鱼水中路径规划，在机器鱼完成水中最短路径寻 优中发挥了重要的作用，极大地缩短了目标点寻优 时间，提高了寻优效率。另外，笔者提出的基于距 离改变机器鱼摆尾幅度的控制方法在场景实验中也 起到了积极的效果。然而在实际的应用中，机器鱼 所处环境是非线性、动态变化的，无法建立精确的 数学模型，有待做进～步分析和研究。 参考文献： ［１］许允喜，蒋云良，陈方．基于点线对应的多摄像机全局 位姿估计迭代算法Ⅲ．光子学报，２０１０，３９（１０）： １８８１—１８８８． ［２］葛继科，邱玉辉，吴春明，等．遗传算法研究综述［Ｊ］． 计算机应用研究，２００８ｆ１０１：２９ｌ１－２９ｌ６． ［３】李华昌，谢淑兰，易忠胜．遗传算法的原理与应用［Ｊ】． 矿冶．２００５（１）：８７—９０． ［４］陶金，孔峰，谢广明．基于动作决策的机器鱼顶球算法 ［Ｊ］．兵．Ｙ－自动化，２０１０，２９（１１）：７０—７３． 【５］肖权，孔峰，谢广明．基于动态角色的多机器鱼协作顶 球研究［Ｊ］．机械科学与技术，２０１２，２９（７）：２４—２８． ［６］孙凯．机器鱼２Ｄ游动的动力学建模与仿真［Ｄ］．北京： 北京大学，２０１０． 【７］俞经虎，竺长安，邱欲明，等．仿生机器鱼的动力学仿 真［Ｊ］．机器人，２００３，２５（３）：６１０－６１３． （８］肖洋，蒋玉莲．三关节机器鱼的动力学建模及其关键运 动参数的研究［Ｊ］．西南民族大学学报（自然科学版）， ２０１ １（Ｓ１）：２４７～２５０， ［９】王晨，谢广明，王龙．基于全局视觉的机器人水球比赛 ｆｃ】＼＼中国自动化学会智能自动化专业委员会、江苏省自 动化学会．２００９年中国智能自动化会议论文集ｆ第二分 册）．中国自动化学会智能自动化专业委员会、江苏省自 动化学会，２００９：７． ［１０】陈言俊，李果，陈宏达，等．仿生机器鱼水球比赛策略 系统的初步探究［Ｊ］．机器人技术与应用，２００９（４）： ２９—３２． 【１ １］Ｙｕ Ｊｕｎｚｈｉ，Ｗａｎｇ Ｓｈｕｏ，Ｔａｎ Ｍｉｎ．Ｓｉｍｐｌｉｆｉｅｄ ｐｒｏｐｕｌｓｉｖｅ ｍｏｄｅｌ ｆｏｒ ｂｉｏｍｉｍｅｔｉｃ ｒｏｂｏｔ ｆｉｓｈ ａｎｄ ｉｔｓ ｅｘｐｅｒｉｍｅｎｔａｌ ｖａｌｉｄａｔｉｏｎ［Ｊ］．２００５，１１（４）：１３５ １３９．
