基于自适应隔离小生境遗传算法的足球机器人路径规划

论文摘要

随着计算机网络技术的迅速发展,计算机快速转向开放的、网络平台的、协同工作方式。基于Agent理论和技术尤其是MAS（Multi-Agent systems）的理论和技术,给我们带来了设计和实现在分布与开放环境中运行的软件系统的一个全新模式。机器人世界杯足球赛（The Robot World Cup,简称RoboCup）,是典型的MAS,是MAS标准问题。在RoboCup中,路径规划的主要目的是为了在充满对抗的赛场上规划出一条满足某项评价指标的无碰撞路径。路径规划主要应用于机器人底层策略中,作为足球机器人基本动作实现的基础,他的优劣将直接影响动作的实时性和准确性,因此,每个足球机器人研究人员都把它作为一个研究重点。本文以机器人足球系统为研究背景,针对系统中的路径规划问题进行深入研究,通过对传统的机器人路径规划方法的分析与所存在问题的研究,提出了基于自适应的隔离小生境遗传算法（AINGA,Adaptive Isolation Niche Genetic Algorithm）的路径规划算法。本文的主要工作及创新点是:（1）本文在详细分析了遗传算法（GA）、小生境遗传算法（NGA）的基本理论及隔离小生境机制的基础上,对隔离小生境遗传算法进行了改进,引入了最优个体交换池,使其能够防止收敛于局部最优解,加快了算法的收敛速度。（2）通过对遗传过程的分析及传统自适应遗传算法的研究,设计了新的自适应交叉和变异算子,该交叉和变异算子与进化代数相关,能够加快收敛的速度。（3）基于以上两点,提出了新的自适应的隔离小生境遗传算法AINGA,并将其应用于RoboCup2D比赛中。通过与基于Q学习的方法相比较,可以发现在路径规划效率方面,本文的方法明显优于基于Q学习的路径规划方法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 问题的提出
• 1.2 课题的研究背景与意义
• 1.2.1 机器人足球概述
• 1.2.2 足球机器人路径规划特点
• 1.2.3 研究意义
• 1.3 国内外的研究现状
• 1.4 本文的研究内容及组织结构
• 1.4.1 本文的研究内容
• 1.4.2 本文的组织结构
• 第二章 足球机器人路径规划典型方法的研究
• 2.1 引言
• 2.2 路径规划典型方法的研究
• 2.2.1 基于人工势场法的路径规划
• 2.2.3 基于栅格法的路径规划
• 2.2.4 基于神经网络算法的路径规划
• 2.2.5 基于Q-学习的路径规划
• 2.2.6 基于遗传算法的路径规划
• 2.3 各种方法的综合分析
• 2.4 本章小结
• 第三章 自适应遗传算法的改进
• 3.1 遗传算法特点及流程
• 3.2 遗传算法的组成
• 3.2.1 编码
• 3.2.2 初始种群的产生
• 3.2.3 评价函数
• 3.2.4 遗传操作算子
• 3.2.5 算法的终止条件
• 3.2.6 算法参数设置
• 3.3 自适应遗传算法的改进
• 3.3.1 遗传算法存在问题
• 3.3.2 自适应遗传算法AGA的改进
• 3.4 实验结果
• 3.5 本章小结
• 第四章 小生境遗传算法的改进
• 4.1 小生境技术及实现方法
• 4.1.1 小生境技术
• 4.1.2 基于预选择的小生境实现方法
• 4.1.3 基于排挤的小生境实现方法
• 4.1.4 基于共享函数的小生境实现方法
• 4.1.5 基于隔离的小生境实现方法
• 4.2 隔离小生境遗传算法INGA的改进
• 4.3 AINGA算法描述
• 4.4 实验结果
• 4.5 本章小结
• 第五章 基于AINGA的足球机器人路径规划
• 5.1 足球机器人路径规划问题的多目标优化
• 5.2 足球机器人路径规划的多目标优化模型
• 5.2.1 运动模型
• 5.2.2 体力模型
• 5.3 AINGA中的遗传操作
• 5.3.1 染色体的表示以及种群的初始化
• 5.3.2 路径评价适应度函数
• 5.3.3 遗传操作
• 5.4 仿真实验结果及分析
• 5.4.1 仿真环境
• 5.4.2 仿真结果
• 5.4.3 结果分析及结论
• 5.5 本章小结
• 第六章 结论与展望
• 6.1 结论
• 6.2 今后的工作
• 参考文献
• 致谢
• 在学期间发表的论文