





























大学硕士学位论文图路径跟踪示意图实验以上算法在的仿真比赛平台上进行了实验。
球的位置坐标为,,射门方向角为,机器人的位置坐标为,,机器人的初始方向角为在试验中,取,产生的两个曲线控制点的坐标分别为,和,,沿曲线射门时记录机器人在运动中的各位置坐标及方向角,结果如图。
图显示了机器人在不同起始位置度角射向球门上角的实验图,图是当机器人在球与球门的异侧时的大转角射门实验图。
从这些实验来看无论机器人初始在什么位置什么角度都能很好按照指定的角度射门,效果很好。
图射门仿真实验郭路生足球机器人路径规划研究图不同起始位姿的度角射门实验图图异侧大转角射门实验图中国地质大学硕士学位论文本章小结本章首先详细的研究了曲线的性质和足球机器人动作的实现的特点及性能指标,分析了曲线作为路径描述的可行性和优点,然后提出了种基于曲线的路径规划算法,该算法用三次曲线进行路径规划,然后用带误差控制的算法就可以灵活跟踪。
该算法充分考虑了机器人的当前状态位置和方向,并能保证到达目标点的速度和方向。
仿真实验表明能满足速度性,准确性和连惯性的要求,其方向误差可控制在度之间。
调整控制点几乎可适合在任何情况下的射门,此算法也可用于射门传球等初始状态向目标状态转变的动作实现的路径规划。
该算法运用到机器人足球仿真比赛中,取得了良好的效果。
郭路生足球机器人路径规划研究第五章基于时间最优的足球机器人路径规划引言上章中,研究了基于动作实现的路径规划问题,本章研究足球机器人避障路径规划问题。
足球机器人系统是个典型的且非常具有挑战性的多智能体系统,是个实时动态的复杂环境。
足球机器人的避障路径规划是机器人导航的关键问题,是建立足球机器人决策系统的基础。
所谓足球机器人的避障路径规划,就是要使机器人在它的活动区域内找到个最安全最有效的路径到达目标位置。
般来说有许多路径可供机器人执行指定的工作,可事实上需要机器人找到个最优路径,即以最小的消耗如时间或能量等到达期望的位置。
机器人避障路径规划是个困难的非线性问题。
国内外在移动机器人避障路径规划方面已经做了大量的研究工作,常用的有人工势场法和栅格法,也有人把些遗传算法等智能算法引入到路径规划中来,但这些方法基本上都是基于路径最短的路径规划。
在机器人足球充满对抗的系统中,要求机器人以最快的时间到达目标点,因此这是类时间最优的路径规划问题。
足球机器人般都是采用双轮差驱动移动机器人小车,是类典型的受非完整约束的系统,因此距离最短并非时间最优,从时间最优的观点而言,在满足约束条件和避开障碍物的前提下,我们不仅要考虑路径长度的问题,还在考虑速度问题。
本章提出了种基于时间最优的足球机器人路径规划算法,用平滑的曲线作为路径的描述,然而用遗传算法对路径进行寻优,最后用仿真实验验证算法的有效性。
时间最优问题足球机器人系统中充满对抗的比赛系统,谁能先触到球,谁就在比赛中占据主动,因此要求机器人以最快的时间到达目标点,是类时间最优问题。
在个区域里,可通往目标点的路径很多,这些路径可以由折线组成,也可以由光滑的曲线组成。
足球机器人般都是采用双轮驱动移动机器人小车,是类典型的受非完整约束的系统,如要机器人跟踪折线路径,必然在经过加速起动,减速停止,转角,然后再加速,减速,再转角的过程,这样机器人平均速度就会大大降低,从而延长了时间。
为了保证时间最优,机器人应以最快的速度运行,显然折线是不能满足的,因此应该选择光滑的曲线来作为机车的路径。
从上章我们们研究的曲线的性质知道,曲线的阶导数和二阶导数都是连续的,曲线是光滑的,能满足非完整性约束方程,因些选择曲线作为我们的路径描述是可行的。
曲线是由系列的控制点来确定的,我中国地质大学硕士学位论文们把控制曲线的系列控制点作为路径的参数。
这样时间最优路径搜索问题可以表述为,在个区域由控制点形成路径的组合系列问题,用数学表达式表示如下其中路径的控制点系列在考虑机器人的物理限制下,每条路径的最优移动时间。
我们用遗传算法来对控制点进行寻优,下面我们先来介绍下遗传的基本原理。
遗传算法遗传算法是种有效的优化技术,具有简单通用鲁棒性强和适于并行处理的优点,广泛应用于优化控制图像编码机器人最佳运动轨迹规划等领域。
遗传算法原理遗传算法,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,它是由美国大学的教授于年在其开创性著作中首先提出的。
教授和他的研究小组围绕遗传算法进行研究的宗旨有两个,是抽取和解释自然系统的自适应过程,二是设计具有自然系统机理的人工系统。
后来和他的学生们将该算法加以推广并应用到优化及机器学习等问题之中,而且正式定名为遗传算法,遗传算法的通用编码技术及简单有效的遗传操作为其广泛的应用和成功奠定了基础。
的遗传算法常被称为简单遗传算法简称。
它是种基于自然选择和群体遗传机理的搜索算法,它模拟了自然界中的生存法则,将待求解问题的每个可能解编码成个染色体,若干个染色体又构成种群,同时构造了复制选择交叉和变异几种遗传操作。
在遗传算法开始时,先随机产生个种群即初始解,并根据定的评价函数对种群中的个体进行评价,产生相应的适应度值。
基于此适应度值,选择部分好的个体用来复制下代,然后对这些选择出来的个体进行交叉和变异操作,产生新代种群。
新的种群继承了上代的些优良特性,在性能上要优于上代,这样使进化逐步朝着更优解的方向前进。
因此,遗传算法可以看作是个由可行解组成的群体逐代进化的过程,是生产检测的迭代过程的搜索算法。
它的基本处理流程如图所示。
由图可见,遗传算法是种群体性操作,它模仿自然界中适者生存的原理,以适应度函数为选择的标准,以群体中所有染色体为对象,在问题的解空间作有向的搜索。
遗传算法的基本要素遗传算子选择,交叉和变异是遗传算法的主要操作算子,它们构成了所谓的遗传算子,使遗传算法具有了其他传统方法所没有的特性。
选择从群体中选择优良的个体并淘汰劣质个体的操作,适应度大的个体,被选择的复制到下代的可能性比较大。
郭路生足球机器人路径规划研究开始确定字符串的长度随机产生个初始个体满足终止条件否计算初始个体适应值计算群体中各个体适应值自左向右执行遗传操作根据适应值选择两个体交换执行交换根据适应值选择个体复制执行复制选择变异个体执行变异将复制结果添加新群体中将交换结果添加新群体中将变异结果添加新群体中输出结果结束图遗传算法流程图中国地质大学硕士学位论文交叉把两个父代个体的部分结构加以替换重组而生成新个体的操作。
目的在于产生下代的新个体。
这种操作使遗传算法的搜索能力得以提高,是获取新优良个体的最重要手段。
变异以很小的概率随机地改变群体中个体些基因的值。
变异操作使遗传算法具有局部随机搜索能力,保持群体的多样性,是种防止算法早熟的措施。
基本要素遗传算法中包含了如下的五个基本要素参数编码初始群体设定适应度函数的设计遗传操作设计控制参数设定主要是指群体大小和使用遗传操作算子的概率和收敛函数的设计。
这五个要素构成了遗传算法的核心内容。
由于遗传算法不能直接处理解空间的解数据,必须通过编码把它们表示成遗传空间的基因串结构数据。
遗传操作的对象是编码后的染色体,染色体的集合就是些初始解的集合,即初始群体因为初始群体中不定会包含要搜索的最优解,遗传算法想要收敛到最优解,就的靠选择,交叉和变异这三个遗传操作算子。
初始群体的规模将影响到算的收敛的速度和精度。
初始规模小收敛快,但不定能找到最优解,初始规模大,找到最优解的几率大,但收敛慢。
适应度函数的设计是遗传算法成败的关键。
因为在搜索进化的过程中,个体的生存能力取决于该个体的适应度。
适应度越高,该个体生存的机会越大,反之,机会越小。
这种选择机制,使遗传算法成为有向的搜索算法。
在自然界中生物进化过程中起核心作用生物遗传基因重组加上变异,同样,遗传算法中起核心作用的是交叉算子。
通过交叉,遗传算法的搜索能力得以飞跃提高。
简单的交叉可以分三步进行对配对库中的个体进行随机配对在配对个体中随机设定交叉处配对个体彼此交叉部分信息。
变异操作是按位进行的。
即把位的内容进行变异。
导入变异算子的目的有两个使遗传算法具有局部的搜索能力。
当遗传算法提高交叉算子己接近最优解时,利用交叉算子的这种局部随机搜索能力可以加速向最优解收敛。
使遗传算法维持个体的多样性,以防止出现未成熟的收敛现象。
遗传算法中交叉算子因其全局搜索能力而作为主要算子,而变异算子因其局部搜索的能力而作为辅助算子。
遗传算法采用交叉和变异这对相互配合而又相互竞争的遗传操作使其具备全局和具备局部搜索能力。
用遗传算法实现时间最优的路径规划郭路生足球机器人路径规划研究障碍物的描述与检测我们的问题是从机器人的当前点到目标点寻求条无碰撞的时间最优的曲线路径。
由于机器人足球系统是个实时动态的复杂环境,为了缩小搜索空间,提高搜索速度,搜索范围确定为目标点为,避障机器人,到的距离为,以为长,以为宽做矩形,在矩形范围内的任何机器人除外都视为是障碍,那么比赛场地中就存在个障碍物的有限集合由对方机器人以及我方的除避障机器人以外的另两个机器人组成,用表示,其中为搜索范围内的障碍物个数障碍物的表示∈为避障区域,如图所示。
为方便起见,我们对球场坐标进行转换,把机器人的当前位置作为新的原点,把当前位置到目标位置的连线作的轴,建立新的直角坐标。
在此坐标系下,障碍物的检测变得异常简单即横坐标在,之间且纵坐标在,之间的所有机器的都认为是障碍物。
图障碍物描述示意图路径控制参数的编码在遗传算法中,首先必须把待优化问题的元素编码成染色体的形式。
因此这里首先要把路径参数编码,对次曲线而言,由曲线的性质知起点位置矢量和终点位置矢量都已经确定,因此控制该曲线的点
