基于时间最优的足球机器人路径规划

基于时间最优的足球机器人路径规划郭路生 吕维先 杨林权中国地质大学 信息工程学院人工智能研究所,湖北武汉430074摘要：首次提出了一种基于时间最优的足球机器人的路径规划的方法。该方法用平滑的Bezier曲线代替传统的折线作为路径的描述，能满足移动机器人的非完整性约束方程，并能使机器人获得较大的运动速度，然后用遗传算法对代表路径的Bezier曲线控制点进行时间寻优。遗传算法的适应值函数充分考虑了影响机器人运动时间的三个因素：路径的安全性、长度和平滑度。仿真结果和实际比赛表明了该方法的有效性。关键字：时间最优 路径规划 Bezier曲线 遗传算法A path planning approach to soccer robot based on time optimizationAbstract: This paper presents a path planning approach to soccer robot based on time optimization for the first time. In order to improve the speed of robots movement, the path is described with a smooth Bezier curve instead of traditional broken lines, then the control points of Bezier curve presenting the path is optimized by genetic algorithm. The fitness function of the genetic algorithm takes full consideration of three factors which affect the time of robots movement: security, length and smoothness of the path. Results of the experiments and real match show the efficiency of the method. Key word: time optimization; path planning; Bezier curve; genetic algorithm1 引言足球机器人系统是一个典型的且非常具有挑战性的多智能体系统1,是一个实时、动态的复杂环境。足球机器人的路径规划是机器人导航的关键问题，是建立足球机器人决策系统的基础。所谓足球机器人的路径规划，就是要使机器人在它的活动区域内找到一个最安全最有效的路径到达目标位置。一般来说有许多路径可供机器人执行指定的工作,可事实上需要机器人找到一个最优路径,即以最小的消耗(如时间或能量等)到达期望的位置。机器人路径规划是一个困难的非线性问题。国内外在移动机器人路径规划方面已经做了大量的研究工作，常用的有人工势场法和可视顶点图法,也有人把一些遗传算法2等智能算法引入到路径规划中来，但这些方法基本上都是基于路径最短的路径规划。在机器人足球充满对抗的系统中，要求机器人以最快的时间到达目标点，因此这是一类时间最优345的路径规划问题。足球机器人一般都是采用双轮驱动移动机器人小 基金项目:中国地质大学研究生学术创新与探索基金项目作者简介:郭路生(1972-), 男, 硕士. 吕维先(1947-), 女，教授车，是一类典型的受非完整约束的系统，因此距离最短并非时间最优，从时间最优的观点而言，在满足约束条件和避开障碍物的前提下，我们不仅要考虑路径长度的问题，还在考虑速度问题。本文提出了一种基于时间最优的足球机器人路径规划算法，用平滑的Bezier曲线6作为路径的描述，然而用遗传算法对路径进行寻优，仿真实验表明了算法的有效性。2 问题的描述2.1 Bezier曲线的定义和性质2.1.1 Bezier曲线的定义给定空间n +1个点的位置矢量Pi（i=0，1，2，n），则Bezier参数曲线上各点坐标的插值公式是： (1) 其中，Pi构成该Bezier曲线的特征多边形，Bi,n(t)是n次Bernstein基函数： (2) (i=0,1,2n 0 =1, 0!=1)Bezier曲线实例如图1所示。图一 三次Bezier曲线Fig1: three-order Bezier curve2.1.2 Bezier曲线的性质a)端点性质Bezier曲线的起点、终点与相应的特征多边形的起点、终点重合。即曲线的起点和终点刚好与机器人运动的起点和目标点重合。b)连续性Bezier曲线的一阶导数和二阶导数都是连续的，这表明Bezier曲线是光滑的。c)变差缩减性 在平面内任意直线与Bezier的交点个数不多于该直线与其特征多边形的交点个数，这一性质叫变差缩减性质。此性质反映了Bezier曲线比其特征多边形的波动小，更光顺。2.2 路径的描述在一个区域里,可通往目标点的路径很多,这些路径可以由折线组成,也可以由光滑的曲线组成。为了保证时间最优,机器人应以最快的速度运行,显然折线是不能满足的,因此应该选择光滑的曲线来作为机车的路径。从Bezier曲线的性质可以看出，选择Bezier曲线作为我们的路径描述是可行的。我们把控制Bezierr曲线的一系列控制点作为路径的参数。2.3 问题的描述时间最优路径搜索问题可以表述为,在一个区域由控制点形成路径的组合系列问题,用数学表达式表示如下: (4) 其中路径的控制点系列;()在考虑机器人的物理限制下,每条路径的最优移动时间。我们用遗传算法来对控制点进行寻优。3 问题的求解3.1 障碍物的描述与检测我们的问题是从机器人的当前点到目标点寻求一条无碰撞的时间最优的Bezier曲线路径。由于机器人足球系统是一个实时动态的复杂环境，为了缩小搜索空间,提高搜索速度,搜索范围确定为:目标点为G,避障机器人R,R到G的距离为L,以L为长,以L/2为宽做一矩形,在矩形范围内的任何机器人(R除外)都视为是障碍,那么比赛场地中就存在一个障碍物的有限集合(由对方机器人ER以及我方的除避障机器人以外的另两个机器人R组成,用O表示)O=OR1,OR2ORq其中q为搜索范围内的障碍物个数.障碍物的表示ORi(x(i),y(i) ORi(x(i),y(i),i=0,1,2q;:为避障区域,如图2所示。为方便起见,我们对球场坐标进行转换，把机器人的当前位置作为新的原点，把当前位置到目标位置的连线作的X轴，建立新的直角坐标。在此坐标系下，障碍物的检测变得异常简单即：横坐标在（0，L）之间且纵坐标在（-L/2，L/2）之间的所有机器的都认为是障碍物。图二 障碍物描述示意图Fig.2Sketch map of obstacles description3.2 路径控制参数的编码在遗传算法中,首先必须把待优化问题的元素编码成染色体的形式。因此这里首先要把路径参数编码,对次Bezier曲线而言,由Bezier曲线的性质1知起点位置矢量0和终点位置矢量都已经确定,因此控制该曲线的点就是1,-1,所以我们的目的就是对这些控制点进行编码。这里选择直接对控制点的直角坐标,分别进行编码,这样每确定一条次Bezier曲线,需要对2(-1)个参数编码。3.3 适应度函数由于遗传算法的每种操作都是根据适应值的信息对群体进行遗传操作和逐代更新的,因此适应值函数的选取将直接影响到遗传算法收敛速度的快慢和算法的成败,此外适应值函数的选择还应该考虑到具体问题的特征,即时间最优并且能够避开障碍物,由v=s/t知要想时间最优必须路径最短和速度最大，而在机器人的机械性能一定的情况下主要受路径平滑度的影响，平滑度越好速度的可能值越大，因此我们的适应度函数应该由三部分组成。3.3.1 路径长度适应度函数用来描述路径的长度。我们只要对Bezier曲线进行曲线积分即可。 (5)3.3.2 路径安全性适应度函数描述机器人的避障程度。一般认为如果路径穿越了障碍就不能到达目标点,在这种情况下,个体的适应值应该为0。但是在遗传进化过程中,当适应值完全变成0时,该个体的所有信息(包括有用的和无用的)都将被丢掉,且不能遗传到下一代,这样在迭代繁殖后代操作的过程中就丢失了一些有用的信息,从而会降低收敛速度。因此需要建立一个新的考虑穿越障碍物的路径的避障适应度函数。为了求解的方便，我们把避障机器人缩小为质点，相应把障碍物进行放大，并设定一个安全半径R，安全半径应大于D（D为机器人的边长）。当路径穿越障碍物时给予一定的惩罚，罚值描述如下:当一条路径穿越一个障碍物区域进时,将该区域分成两个小区域,将其中较小的区域定义为1并把整个障碍物区域定义为2。我们构造的适应度函数如下： (6)罚值函数表述表明了当路径越靠近禁止区域的中心穿越,罚值越大,适应值越小。在实际的计算中，由于要求解Bezier曲线与障碍物相交而分割的面积是比较因难的。在机器人足球系统中，由于障碍物区域比较小，我们可以近似认为穿越障碍物是一直线，这样我们只要弓形的面积即可。3.3.3 平滑度适应度函数描述曲线的平滑度。在机器人由当前点运动目标点的过程中，我们认为机器的是一直向前运动的。如果出现向相反方向运动，显然是与我们的意愿相违背的，这时的曲线也必然出现拐点。在Bezier曲线中只要保证控制点序列是前向性的就可以保证Bezier曲线是光滑的。可以如下表示： 1 (PiPi+1)3.3.4 综合适应度函数综合适应度函数应该是能够避障，这是主要的，在此基础上应该让路径的长度较短,同时还要考虑路径的平滑度，以便获得较大的速度,这样才能保证时间最优。可表示如下： (8) k1、K2、K3分别是适应度函数三个部分的权值，调节K1，K2，K3就可分别调节路径长度影响度、避障程度和路径的平滑度。3.4 遗传操作3.4.1 选择算子初始种群作为优化过程的开始,由算法本身随机产生,为群体规模,即随机生成路径(=1,2,),同传统复制算子一样,采用与适配值成比例的概率来选择个体.具体做法是:1) 计算个体适配值:(=1,2,).2) 计算选择复制的概率:/.3) 按概率复制3.4.2 交叉算子第一步是将复制产生的个体随机两两配对;第二步是随机地选择交叉点,对匹配的个体按一定的杂交概率(一般在0 .7左右)进行交叉繁殖,产生一对新的个体.3.4.3 变异算子变异是对群体中的元素(基因)加入随机扰动.对于群体中的每一个元素,变异的概率为(一般在0.010.3),变异有节制地和交叉一起使用,是一种防止过度成熟而丢失一些重要遗传信息的保险策略,但变异多保持低概率,以避免严重损坏下一代个体的结构.4 仿真实验实验在SimuroSot 5v5平台上进行。路径采用3次Bezier曲线近似,仿真过程中遗传算法使用的遗传算子为:复制采用保存最优个体的轮盘赌模型,交叉采用两点随机交叉,变异采用随机一点变异。使用的参数为:种群规模=40,交叉概率=0.8,变异概率=0.2。（注：这里变异概率取得比较大是为避免算法陷入早熟。）因为每条路径有两个控制点,所以共有4个待编码的未知参数。将每个参数采用实数编码,参数范围为机器人到目标点的距离。运行16代以后,得到路径如图四所示,。实验数据记载在下表中。（我们也用四次Bezier曲线近似进行了仿真实验，在障碍物较少（4个以内）时结果跟三次差不多，在障碍物较多时如（11vs11），算法收敛更快，但平滑度不如三次Bezier曲线）。次数123起始点36.692743,41.45075633.157630,38.49686832.700797,39.909668目标点66.653778,41.69760970.472038,40.93060753.030960,46.302879障碍物158.641723,44.59301055.448612,41.74040348.023348,42.068897障碍物244.698213,38.80177644.566250,47.85224946.870680,49.513710障碍物350.245826,46.59000844.709438,35.569275控制点148.241841,50.74457344.024988,50.56002649.543924,35.510480控制点253.254995,31.4297353.257189,25.64296454.669556,36.474455图表三 仿真实验数据 Fig.3 Data. of simulated experiment图四（a）图四（b）图四（c）Fig4: Result of simulated experiment5 结论机器人足球是一个充满对抗的系统，要求机器人以最快的时间到达目标点，这是一类时间最优的路径规划问题。本文提出一种基于时间最优的足球机器人路径规划的算法。该算法用平滑的Bezier曲线进行路径的描述，然后用遗传算法进行寻优。算法实破了传统的用折线作为路径最短算法中的路径描述的方法，能满足移动机器人的非完整性约束方程，在路径较短的情况下能获得最大的运动速度，从而达到时间最优。遗传算法用于时间最优路径规划是可行而且是有效的。由于遗传算法的全局搜索性和全局收敛性,使得能在有障碍物存在的情况下,尽快地搜索出一条绕过障碍的时间最优路径,从而达到目的。在用遗传算法进行寻优的过程中充分考虑了路径的安全性、路径的长度和路径的平滑度（速度因素）这三个影响时间最优的因