基于遗传算法的足球机器人动态避障路径规划

硕士学位论文

THESIS OF MASTER DEGREE 论文题目:基于遗传算法的足球机器人动态避障路径

规划

(英文:Genetic Algorithm Based Dynamic Obstacle Avoidance And Path Planning For A soccer Robot

作者:方惠蓉

指导教师:杨楠、副教授

2009年 12月 20 日

论文题目:

(中文 基于遗传算法的足球机器人动态避障路径规

划

(外文 Genetic Algorithm Based Dynamic Obstacle

Avoidance And Path Planning For A Robot 所在院、系、所 :信息学院

专业名称 :计算机应用技术

指导教师

姓名、职称 :杨楠、教授

论文主题词:足球机器人;路径规划;遗传算法;

障碍物;自适应度函数 学 习 期 限 : 2006年3月至2009年12月 论文提交时间: 2009年12月 20 日

独创性声明

本人郑重声明:所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写的研究成果,也不包含为获得中国人民大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献已在论文中作了明确地说明并表示了谢意。

签名:方惠蓉日期:2009.11.16

关于论文使用授权的说明

本人完全了解中国人民大学有关保留、使用学位论文的规定,即:学校有权保留送交论文的复印件,允许论文被查阅和借阅;学校可以公布论文的全部或部分内容,可以采用影印、缩印或其他复制手段保存论文。

签名:方惠蓉导师签名:杨楠日期:2009.11.16

摘要

移动机器人越来越多地应用到各个行业中,移动机器人具有高度自规划、自组织和自适应能力,适合于工作于复杂的非结构化环境中,路径规划是机器人技术研究领域中的核心问题,它的任务就是在具有障碍物的环境中,按照一定的标准(路径最短、时间最快或能量消耗最少等,寻求一条从已知点到已知终点的具有最低代价的无碰(较优路径。

本文以RoboCup 小型组机器人足球系统为研究平台,探索行之有效的方法来解决实际中的路径规划问题。

首先,总体介绍了足球机器人系统的体系结构及相关技术,包括视觉子系统、决策子系统、通讯子系统和机器人小车子系统。

然后,讨论了足球机器人路径规划方法,包括全局的路径规划和局部的路径规划方法,结合多种理论各自特点进行路径规划是今后研究的一个主要方向,在对各种路径规划方法进行优缺点比较后,选择遗传算法来解决移动机器人的路径规划问题,并对算法的各个环节进

行分析,包括环境建模,染色体的编码、适应度函数的设计和遗传操作算子的设计。

最后,本文提出一种多个移动机器人在动态环境下进行路径规划的新方法,即基于遗传算法的行为控制的机器人路径规划方法,包含奔向目标行为、保持队形行为、避免与静态障碍物碰撞行为、避免与其他机器人碰撞这四种行为控制的机器人路径规划方法,用行为来描述机器人在达到目标点时所要执行的任务,再用遗传算法对机器人的行为控制参数进行优化,适应度函数是由路径最短和能够动态避障的评价函数进行加权求和来确定。

通过对算法进行实验访真,结果表明提出的动态路径规划方法是正确和有效的。能够很好地解决动态环境下移动机器人的路径规划问题,对移动机器人路径规划的进一步研究具有很深远的现实意义。

关键词:足球机器人;路径规划;遗传算法;障碍物;自适应度函数

Abstract

Recently mobile robot has been introduced in many application situations. Autonomous mobile robot has the ability of self-planning, self-organization and adaptability. It can work in many complex situations. Path Planning is a kernel problem of robot technology area, the main task of planning is figuring ort a collide –free path at least cost from the known start position to known goal position in the robot environment.

Based on the research platform of RoboCup, this paper tries to find effective

schemes to solve the path –planning problems in practice,

Firstly, the architecture of soccer robot system and its key technologies are reviewed. In functions it included the visual system, decision-making sub-system, communication sub-system and subsystem robot car.

, Secondly, The paper studies the elementary theory of genetic algorithm include global planning method and local planning method. One great research tendency is to path plan with several theories’ virtues. And then presents the path planning method of the robot based on the genetic algorithm which combines the feature of the path planning problem. With the evolution operation such as selection, mutation and recombination, the optimal solutions can be obtained.

Finally, the paper proposes a new method of collision avoidance planning for multi-robots in dynamics environment where multiple obstacles are moving around. Four primitive behavior which called move-to goal, keep –formation, avoid-static –obstacle and avoid –robot behaviors describe acts that the robot go to the end point, then the GA optimize behavior’s parameters, the weighted sum of the evaluation function that the shortest path and dynamic obstacle avoidance determine fitness function.

The simulation result shows that the proposed method is correct and

efficient. The genetic algorithm can solve the path planning problem of mobile robot in the dynamic environment. It is highly significant to the study of autonomous soccer robot path planning.

Key Words robot soccer; path planning; GA; dynamic obstacle avoidance;

:

fitness function

目录

第1章 绪论 (1

1.1引言 (1

1.2足球机器人概述 (1

1.2.1 足球机器人的起源与发展 (1

1.2.2 足球机器人的研究难点 (2

1.2.3 足球机器人技术的发展趋势 (3

1.2.4 足球机器人的技术应用 (3

1.3研究本课题的目的和意义 (4

1.4机器人的路径规划 (6

1.4.1 路径规划的含义 (6

1.4.2 路径规划问题的方法及现状 (6

1.5论文的主要内容 (8

第2章 机器人足球比赛系统 (10

2.1引言 (10

2.2足球机器人比赛系统的组成 (10

2.2.1 小车子系统 (12

2.2.2 视觉子系统 (13

2.2.3 决策子系统 (14

2.2.4 通讯子系统 (16

2.3小结 (17

第3章 足球机器人路径规划方法 (18

3.1引言 (18

3.2全局路径规划常用的方法 (19

3.2.1 栅格法 (19

3.2.2 可视图法 (20

3.3局部路径规划常用的方法 (21

3.3.1 人工势场法 (21

3.3.2 遗传算法 (22

3.3.3 神经网络法 (25

3.4基于行为的路径规划方法 (27

3.5动态环境下的路径规划方法 (28

3.6各种方法综合分析 (28

3.7本章小结 (29

第4章 基于遗传算法的足球机器人路径规划 (30

4.1引言 (30

4.2遗传算法概述 (30

4.3遗传算法基本原理 (32

4.4遗传算法的设计步骤 (32

4.5利用遗传算法进行路径规划 (37

4.5.1 环境建模 (37

4.5.2 编码 (38

4.5.3 种群初始化 (38

4.5.4 适应值的计算 (38

4.5.5 遗传算子的操作 (38

第5章 基于遗传算法的行为控制路径规划方法 (41

5.1引言 (41

5.2足球机器人路径规划的行为方法描述 (41

5.2.1 向目标点前进的行为 (43

5.2.2 避开静态环境障碍物的行为 (44

5.2.3 躲避本方和对方机器的行为 (44

5.2.4 保持队形的行为: (45

5.2.5 最终行为合成策略: (45

5.3行为控制的遗传算法实现 (46

5.3.1 参数编码 (46

5.3.2 适应度函数的设计 (47

5.3.3 操作函数的设计 (48

5.3.4 终止条件 (51

5.4仿真实验及实验结果分析 (52

5.5小结 (56

第6章 总结 (57

6.1总结 (57

6.2展望 (57

参考文献 (59

致 谢 (62

图表索引

图2.1(A足球机器人比赛环境 (11

图2.1(BR OBO C UP小型组机器人足球系统的示意图 (11

图2.2小型足球机器人系统结构图 (12

图2.3决策子系统流程图 (15

图2.4通讯子系统流程图 (16

图2.5各子系统的相互关系 (17

图3.1栅格法表示的机器人活动场地即搜索到的路径 (20

图3.2遗传算法简单流程图 (24

图3.3神经元形式化结构模型图 (26

图3.4神经网络基本结构图 (27

图4.1遗传算法运算流程 (33

图4.2移动机器人所处环境 (37

图4.3“轮盘赌”示意图 (39

图5.1足球机器人实物图 (52

图5.2最大适应度函数值与平均适应度值的进化曲线图 (53

表1.1视觉子系统输出数据矩阵 (14

表5.1第四代算法的收敛情况 (54

表5.2第九代算法的收敛情况 (54

表5.3适应度函数的权系数 (54

表5.4行为控制参数 (54

基于遗传算法的足球机器人动态避障路径规划

第1章绪论

1.1 引言

机器人技术与系统经历了50多年的发展,已取得实质性的进步和成果,机器人系统逐步向更主智能化和与人类社会更密切的融合方向发展。机器人足球系统的研究融入了机器视觉技术、机电一体化技术、无线通讯技术、嵌入式计算机技术、人工生命学技术、战略战术技术、智能控制等多学科的研究成果,不仅能反映出一个国家信息与自动化技术的综合

实力,而且也能作为展示高科技水平的生动窗口以及促进科技成果实用化和产业化的有效途径。

随着机器人应用领域的不断拓展,机器人工作环境复杂度及任务的加重,对机器人的要求不再局限于单个机器人,对机器人的研究已经成为机器人学研究的一个热点,制造和训练机器人进行足球比赛,也已成为人工智能与智能机器人研究领域中一个十分令人注目的热点。一些发达国家已把智能机器人比赛作为创新教育的战略性手段。智能机器人集成了数学、力学、机械、电子、自动控制、传感器、通 信、计算机、人工智能,是众多领域的高科技,能有效培养学生的动手能力、创造能力和协作精神。

1.2 足球机器人概述

1.2.1 足球机器人的起源与发展

机器人世界杯足球赛(RoboCup是以Multi-agent系统(MAS与分布式人工智能(DAI为主要研究背景的,其主要目的就是通过提供一个标准的、易于评价的比赛平台,促进DAI与MAS的研究与发展,涉及的研究领域包括:智能机器人系统、智能体结构设计、传感器融合技术、多通知体系统、实时规划等。机器人足球可以描述成一个先进的机器人技术在密闭空间内的竞争,它提供了一个挑战性的舞台。

机器人足球赛自成立以来就确定了良好的游戏规则[1],在足球机器人世界杯

基于遗传算法的足球机器人动态避障路径规划

中,分成几类,其中包括微型足球锦标赛(机器人比赛,模拟足球人足球锦标赛(SimuroSot和类人型机器足球锦标赛(HuroSot,第一届国际RoboCup比赛是1997年在日本Nagoya举办的[2],当时参加RoboCup小型组比赛的共有四支队伍,最后获得冠军的是美国Carnegie Mellon大学的CMUnited,此后,CMUnited 蝉联了1998年的世界冠军。而接下来的几年中,美国Cornell大学的Big Red表现出众,分别于1999, 2000, 2002, 2003年四次获得世界冠军,而2001年的世界冠军被来自新加坡南洋理工的LuckyStar-2获得,2004和2005年,来自德国Freie大学的FU-Fighters连续两年获得世界冠军,2006年,RoboCup世界杯创建10周年之际,参加小型组比赛的球队达到了20支,而老牌强队CMDragons(前CMUnited再次以超强实力夺冠。此外,来自澳大利亚Queensland大学的RoboRoos曾经多次获得世界亚军,也是一支传统强队。在10年的发展历程中,这些球队的研究和开发人员做了许多研究工作,在分布式人工智能、模式识别、图像处理、电路控制及机械结构等各个领域取得了很多研究成果。

与国际上这些强队相比,国内在RoboCup 小型组机器人足球方面的研究尚处于1.2.2 足球机器人的研究难点

必须制定使用人工智能(AI[2], RoboCup小型组机起步阶段,首届全国机器人足球比赛于1999在哈尔滨工业大学成功举行,中科大、浙江大学和上海大学等学校在进行机器人足球相关研究的同时,都开发了自己的小型足球机器人队伍,其中科大的蓝鹰小型机器人足球队是国内的传统强队,曾经多次获得全国比赛的冠军并多次参加了机器人足球世界杯的比赛。近几年,以中科大、浙大为代表的国内球队在RoboCup 小型组机器人足球比赛方面取得了可喜的进步,但与国际水平相比还有很大差距,还有很多方面需要改进和提高,RoboCup 的比赛水平直接反映了机器人与智能控制技术的研究水平,同时其产生的国

际影响又大大促进了机器人与智能控制技术的研究与发展。

在机器人比赛中,参加者器人足球的特点可以用12个字概括[3]:“实时采集,实时控制,实时行动”。这3个“实时”是机器人足球的难点所在,也是机器人足球的魅力所在。相比于RoboCup模拟比赛,RoboCup小型组足球机器人更加强调实物,许多仿真环境下假设的理想状态,在实际的小型组比赛中,需要机器人足球运动员进行合作

基于遗传算法的足球机器人动态避障路径规划

和自主协调,关键在于打败对手赢得比赛。

RoboCup 小型组的规则中明确规定不能同对方机器人发生剧烈冲撞,否则会受到消失了,因此,减少场外处理1.2.3 足球机器人技术的发展趋势

越来越多的机器人保姆、机器人司机、机器人秘1.2.4 足球机器人的技术应用

背景极其广阔, RoboCup 小型组足球机器人主要在于究和应用涉及多个课题,如机器人体系结构、机构、控制、智能黄牌警告甚至直接罚出场外,这样,在进行RoboCup 的路径规划时,障是必须考虑进去的,这样也增加了路径规划的难度。

小型组的比赛强调以快制胜,机会往往在瞬间就的时间(视觉处理和决策处理,缩短机器人执行命令的时延,是小型组的研究难点。

人类必须会与机器人打交道,书、机器人节目主持人以及网络机器人、虚拟机器人、

人形机器人、军事机器人等将推广应用,成为机器人学新篇章的重要旋律。路径规划问题是机器人足球导航的基本环节之一,为了能实现“到21世纪中期[2],一个全自主类人型机器人足球队将与人类足球世界杯冠军队比赛并获胜”的研究目标,机器人足球系统的研究方向将不可避免地向着分布式自主机器人球队方面发展,小型组机器人足球系统也不例外。国外同行预言[4],2010年的机器人足球比赛,将全是分布式自主机器人球队间的比赛。因此,我们更应加强机器人足球系统的研究力度和研究进度,才能在人工智能和多智能体协同控制研究领域,跟踪和赶上国际发展趋势。

机器人足球的研究和应用研究在动态环境下使用一个集中或者分布的系统如何控制多智能体以及如何完成它们的协作,是多智能体集中控制方法的良好的测试平台,其研究成果可推广应用于很多领域,具有典型的研究意义,最直接的应用就是智能机器人和多机器人系统。

智能机器人的研、视觉、触觉、力觉、听觉、机器人装配、恶劣环境下的机器人以及机器人语言等,智能机器人已在各种工业、农业、商业、旅游业、空中和海洋以及国防等领域获得越来越普遍的应用。

基于遗传算法的足球机器人动态避障路径规划

多机器人系统的研究始于20世纪70年代,多机器人系统的研究分为多机器人1.3 研究本课题的目的和意义

随着机器人系统不断向智能化发展,已经从在工业领域的应用,进入到探索宇动机器人

中一种典型,它能合作(multi-robot coordination 和多机器人协调(multi-robot cooperation两大类,主要在给定一个多机器人系统任务后,如何组织多个机器人去完成任务,如何分解和分配任务以及如何保持机器人之间的运动协调一致,例如家用机器人、军用机器人(如美正在研究的无人驾驶战斗机机群、工业机器人、救援机器人和太空机器人(如火星车等等。对于多机器人系统的研究背景与网络“信息代理”有关,这些所谓的代理即网络空间中的“信息机器人”(事实上,最早从事“信息代理”研究的学者中就有一批机器人专家。另一方面还涉及各种“软件自主体系统”,即由一些自主的计算实体(类似于机器人足球队中的队员通过合作的方式形成得到软件系统,这种系统有可能成为下一代软件工程主流技术的一个关键部分。多机器人的协调控制机制是研究的重点,最基本的问题是多机器人之间信息的传递,多机器人之间通过必要的信息交流实现多机器人的同步和协调。多主体系统、信息代理和软件自主体被认为是未来信息产业(特别是电子商务的主要理论基础和技术手段。

宙与外星球等特殊行业,机器人将成为代替人在繁重、危险、恶劣、外太空环境下作业的必不可少的工具,它将成为代替人类完成与深海作业、精密操作、高温作业、基础设施建设工程等的关键技术装备。

移动机器人是机器人中常见一种,

足球机器人也是移实时自主运动,是一种集环境感知、动态决策与规划、行为控制与执行等多项功能于一体的高智能化机器系统。足球机器人路径规划是机器人应用中的一项很重要的技术,它必须要求机器人根据给予的指令及环境信息决定路径,避开障碍物,实现任务目标。路径规划是机器人完成任务的安全保障,同时也是移动机器人智能化程度的重要

标志。采用良好的机器人路径规划技术可以节省大量的机器人作业时间、减少机器人磨损,同时也可以减少资金的投入,为机器人在多种行业中的应用奠定了良好的基础。

基于遗传算法的足球机器人动态避障路径规划

足球机器人的研究重点之一就是路径规划,路径规划的环境分为静态和动态,个动态竞技项目,机器人在运动过程中小车车体可能会最短机器人足球赛平台,以高适应性的移动机种导航方式,移动针对障碍物的状态,障碍物静止的状态称为静态,相反,障碍物可以运动,使环境信息不断的变化,则称为动态环境。在机器人足球比赛中为了组织起有效进攻,或者在防守中抢占有利的位置,精确地避开障碍物,需要对机器人进行运动路线的规划。动态环境中的路径规划比静态环境下的规划复杂得多,动态环境下的路径规划是足球机器人系统研究中的一个重要课题,其重要性主要表现在以下几个方面[5]:

(l 机器人足球赛是一与周围的环境发生碰撞,也可能与来自对方的球员产生碰撞,而机器人车体造价比较高,如果没有设计相应的避障行为,经过多次相撞后将会损坏车体;

(2 在比赛中,为取得较好成绩,需要对路径进行规划,使得机器人能以时间到达目的地,完成相应动作;

(3 可以促进人工智能的发展,利用器人控制技术,真实环境下的规划技术,对各种智能算法进行研究和检验,开展更高层次的研究,可以促进相关学科和人工智能的发展;

(4 机器人足球赛系统是一个动态的复杂环境,不论采用何机器人主要完成路径规划、定位和避障等任务,对机器人路径规划这个课题研究的时间比较长,随着科技的发展和人类

探索领域的不断拓宽,对机器人的研究不断的深入,要求也不断地提高。路径规划属于一种作业环境未知且动态的路径规划,以足球机器人为研究平台,可以应用到其他机器人应用环境,促进了移动机器人学多种研究方向的出现。随着科技的发展,多机器人系统的应用领域将逐渐向工业、军事领域发展,足球机器人系统环境是一个很典型的具有动态性、不确定性、实时性的环境,这样的环境正好符合当前机器人路径规划的研究方向。对于多个移动机器人的系统,各个机器人的协调无碰撞运动路线是对它的一项基本要求,所以本文选择从动态环境下的行为控制角度对足球机器人系统进行研究。

基于遗传算法的足球机器人动态避障路径规划

1.4 机器人的路径规划

1.4.1 路径规划的含义

路径规划问题是机器人足球导航的基本环节之一[2],它是依据某一性能指标,某一些优化准则(如工作代价最小、行走路线最短等,在机器人工作环境中搜索一条从起始状态到目标状态的最优或近似最优的、能避开障碍物的最优运动路线。机器人足球系统是一个实时动态的不确定的复杂环境,规划方法关心的是在环境表达的基础上,采用有效的方法规划路径并且进行优化。由于路径规划问题的复杂性,不同的研究者从不同的角度研究某一方面的问题,对具体问题的提法也不完全相同,一般情况下,路径规划问题的研究涉及到环境表达、规划方法、路径执行。

动态环境中机器人的路径规划依赖于障碍物可能出现的位置,对每个机器人进行路径

规划,要考虑多方面的因素,比如路径的起始和终止位置、机器人周围环境信息的不完整性、不可预知性、近似性以及缺少相关数据信息等缺点,还要综合考虑该机器人的行动意图。在进攻态势下,为了加大进攻力度,只要有机会接触到球,机器人最好将球踢到对方半场,所以小球的位置就是路径的终点,这个目标是动态的不断变化的。

1.4.2 路径规划问题的方法及现状

动态环境下的路径规划随着机器人技术的发展已成为急待解决的问题,难度在于既要有充分的环境信息并和环境形成闭环,又要求处理速度快,以满足实时性要求,它需要在状态空间进行规划,不仅要考虑机器人本身的因素,还要结合周围动态的环境和障碍物,动态障碍物的出现存在随机性和不确定因素;而且机器人运动过程中路径性能要求存在多种目标,如路径最短,时间最优,安全性能最好,能源消耗最小,但它们之间往往存在冲突。需要连续不断地解决路径规划和速度规划问题。

研究机器人的路径规划,对于足球机器人来说就是其他机器人的运动状态。机器人各因素可以归为以下几种情况:

已知环境下的静态障碍物、已知环境下的动态障碍物、未知环境下的静态障碍物和未知环境下的动态障碍物,并且机器人比赛像真正的足球比赛一样,

基于遗传算法的足球机器人动态避障路径规划

要求各个机器人动作准确、敏捷,战略战术灵活多变。它有以下特点[6]:

(1既有本方的机器人又有对方的机器人和球场四周;

(2既有动态的障碍物(包括本方的和对方的又有静态的障碍物(球场的四周;

(3既有本方机器人与本方机器人相撞,又有本方机器人与对方机器人相撞;既有无意相撞,又有故意相撞等;

对于路径规划目前有很多有效的解决方法,有应用范围很广的,也有应用范围极其有限的,它们之间各有优缺点,也不会互相排斥,所以一般结合起来共同实现路径规划。根据机器人对环境信息知道程度不同,可分为两种类型:环境信息完全知道的全局路径规划和环境信息完全未知或部分未知,通过传感器对机器人的工作环境进行探测,以获取障碍物的位置、形状和尺寸等信息的局部路径规划。

全局规划方法依照已获取的环境信息,给机器人规划出一条路径,规划路径的精确程度取决于获取环境信息的准确程度,全局路径规划包括环境建模和路径搜索两个子问题。环境建模的主要方法有:可视图法、自由空间法和栅格法等;路径搜索策略主要有:A*算法、D*最优算法。全局路径规划方法通常可以寻找到最优解,但是需要预先知道关于环境的所有信息,根据环境进行路径规划,并产生一系列关键点作为子目标点传达给局部路径规划系统,而且计算量很大。

局部规划的主要方法有:人工势场法、遗传算法和模糊逻辑算法等,这种方法侧重于考虑距离机器人较近的局部环境信息,让机器人具有良好的避碰能力。和全局规划方法相比较,局部规划方法更具有实时性和实用性,缺点是仅仅依靠局部信息,有时会产生局部极点,无

法保证机器人能顺利到达目的地。

从机器人工作环境的角度区分规划方法,可以分为静态确定环境规划方法和动态改变环境规划方法,在动态环境下的规划问题已经引起了人们的重视,并且已经取得了一些成果,这将是今后的一个发展方向。

为了使机器人能够在未知环境中实现自主导航,就需要给它更多智能以及增加它的自主性,采用有效的路径规划算法[7]是当前足球机器人系统进行智能研究的重要问题,目前国内机器人足球比赛中采用的路径规划方法很多,有经典的路径规划方法,包括:人工势场法、模糊逻辑法、可视顶点图法、遗传算法、

基于遗传算法的足球机器人动态避障路径规划

神经网络方法等,本文通过对动态环境下要解决的避障问题进行研究,最终采用基于遗传算法的行为控制方法来解决路径规划问题。

1.5 论文的主要内容

足球机器人作为一个典型的多智能体系统,是一个实时动态的复杂环境,机器人的行为和动作的有效性完全基于对将要行走路径的准确预测和合理的规划以及机器人与足球碰撞时位置的调整。足球机器人的路径规划问题,作为足球机器人智能的一个因素显得尤为重要,其主要目的是为了在充满竞争和对抗的赛场上规划出一条满足某项评价指标(时间最优、路径最短等的无碰撞路径。作为足球机器人基本动作实现的基础,路径规划的优劣直接影响动作的实时性和准确性,因此,这是研究足球机器人的一个重点。本文共分六章,组织

结构如下:

第一章:阐述了机器人足球的起源与发展,说明了研究机器人足球赛和研究路径规划的重要意义,足球机器人国内外研究现状及发展趋势,及本课题的主要研究内容。

第二章:介绍了足球机器人比赛系统的体系结构及相关技术,包括了视觉子系统、决策子系统、通讯子系统和机器人小车子系统,描述了足球机器人路径规划的总体思想,分析了路径规划在机器人系统中的重要性。

第三章:分析用于FIRA微足球机器人路径规划的几种典型方法,重点对人们研究比较多的几种方法进行深入研究与分析,包括可视图法、栅格法、人工势场法、遗传算法、神经网络法等;讨论它们在足球机器人系统中的应用可行性,分析其优缺点和适应条件,并对各种方法进行了综合分析论述。

第四章:根据机器人当前的位置和要到达目标点的位置所要采取的避障行为,提出了改进的遗传算法,在操作算子的设计中增加了插入算子和删除算子,该方法具有进行整体搜索和全局最优计算功能,遗传算法所具有的全局寻优能力和隐含并行性,保证了该方法应用于机器人路径规划的可能性和有效性。

第五章:在动态环境中,对遗传算法加以改进,结合机器人在动态环境下要达到的目标以及根据周围环境进行实时的避障问题,提出基于遗传算法的行

基于遗传算法的足球机器人动态避障路径规划

为控制的足球机器人动作实现路径规划方法,使用行为控制参数进行优化,适应度函数是由路径最短和能够动态避障的评价函数进行加权求和来确定,通过把算法推广到动态环境中,取得了不错的效果,仿真表明此方法的高效可行性。

第六章:对本文进行总结,同时展望机器人路径规划的发展。

基于遗传算法的足球机器人动态避障路径规划

第2章机器人足球比赛系统

2.1 引言

机器人足球所涉及的技术非常广泛,融入了机器人学、机电一体化技术、通信与计算机技术、机器人视觉与传感融合技术、决策与对策、路径规划、智能控制等多学科高新技术。机器人足球赛有利于将人工智能理论研究与实践相结合起来,检验新思想、新技术,促进相关科技的发展。

本论文中使用的足球机器人属于集中视觉的遥控无脑多机器人系统,这种比赛是半自主型的。在系统决策程序的控制下,足球机器人通过自己的前进、后退、转身、停住等动作,实现符合比赛规则的传球、带球、过人、射门、跑位等攻防技术动作。计算机统一对场上信息进行分析、决策,然后分配本方机器人攻守和行进任务,达到遥控场上各机器人运动的目的,属于集中控制类型的系统。

机器人足球赛所催生成熟的一系列高新技术,机器人足球既是一种前沿研究的竞争和

高技术对抗活动,又具有与足球类似的娱乐性、观赏性和刺激性。可以预料,这一活动将产生极大的市场需求和新的产业机会,带来不可估量的经济和社会效益。

2.2 足球机器人比赛系统的组成

足球机器人比赛系统的体系结构,首先在于它是多机器人系统,作为多机器人系统研究的一个重要课题,参加比赛的多个机器人要实现相互之间的合作就必须确定机器人逻辑上和物理上的信息和控制关系,以及问题求解能力如何颁等问题。合理的体系结构可以使多机器人之间进行有效的合作。足球机器人的体系结构可以分为集中式和分散式两种。本文采用集中式结构,它的优点在于:实现起来比较直观。在这样的系统中,通常由一个主控单元掌握全部环境信息及各受控机器人的信息,运用规划算法和优化算法,主控单元对任务进行分解和分配,向各受控机器人发布命令,并组织多个受控机器人共同完成任务。

基于遗传算法的足球机器人动态避障路径规划

在机器人足球比赛中(如图2-1所示,球场上方(2m悬挂的摄像头将比赛实况传入控制主机,由预装的软件作出恰当的决策和对策,然后通过无线通信方式将最终的决策指令传给机器人。同时,在比赛场上,机器人协调作战,双方对抗,各有攻防,从而形成一场激烈的比赛。

图2.1 (a 足球机器人比赛环境

图2.1(bRoboCup小型组机器人足球系统的示意图

基于遗传算法的足球机器人动态避障路径规划

RoboCup小型足球机器人包括三个机器人小车构成的机器人小车设备;一个位于球场正上方约2米的摄像机、图像识别系统组成的视觉子系统;由一个至少两个频道的无线电发射盒组成的通讯设备;为各个机器人提供各种动作的计算机设备。在功能方面包括机器人小车子系统、视觉子系统、决策子系统和通讯子系统。这四个子系统构成一个大的闭环系统。图1-2给出的就是足球机器人系统硬件组成框图。下面分别介绍各部分的组成,及系统对各部分的要求。

图2.2 小型足球机器人系统结构图

2.2.1 小车子系统

小车在比赛场上就是各个动作的执行者,它在场中的表现[8]直接体现了整个足球机器

人系统的好坏,车体的机械结构包括车轮、踢球器、控球器、带球器、挡板及其他;根据比赛规则,为保证小车具有良好运动灵活性的要求,车体的走行机构采用轮式机构,整个车体采用对称结构,使车体的重心位于车的中心,尽量降低车体重心的高度;为满足车体应具有抗冲击性和可靠性的要求,车体框架应选取强度大的材料,即质量轻、强度高的材料;为满足车体应具有可维

基于遗传算法的足球机器人动态避障路径规划

护性的要求,车体的结构设计要尽量简单、合理。在设计小车时应考虑到微处理器的选择、小车的机械结构和电机速度的控制三个方面。

选择CPU是为了实现高智能、运算速度快。它是小车的核心部分,车载子系统的任务是准确接收来自主机计算机的运动指令,并能根据指令要求迅速、准确地完成决策子系统所要求的动作(如带球、传球、截球、防守、射门等动作。

机器人小车的机械结构对整个机器人的灵活性起着重要作用。两轮驱动的机器人的运动轨迹是由圆弧和圆弧的切线组成的是非完整性约束系统,为得到较好的机动性和灵活性,采用三轮方向轮驱动,这样的机器人不存在非完整约束,它可以向任意方向做直线运动而不需要事先作旋转运动,并且在以直线运动到达目标点的过程中同时可以做自身旋转运动调整机器人的姿态,从而达到终态所需的姿态角。这样,就使得全向移动机器人在比赛中表现出运动快速灵活,易于控制,进攻性强等优点。随着RoboCup比赛的发展,机器人的灵活性也越来越凸现其在比赛中的重要性。因此,目前全向移动机器人已逐渐成为各个球队设计发展的趋势。

机器人小车要具有良好的性能,电机的选择对其有明显的影响,一般采用直流电机来保证足够的速度。电机的控制包括电机的驱动和转速检查两部分。对于控制值和实际转速之间的误差,可采用同步补偿的方法来解决[6]。由于受到机器人尺寸的限制,选择一个在功能、尺寸、能量消耗适合的CPU是很重要的。在硬件结构的设计上,硬件的设计应保证便于安装测试和检修,同时机器人控制电路具有较好的坚固性,保证在激烈碰撞下电路元器件不发生损坏,电缆接口插件不发生松动,特别是电源插件要得到保证。软件应采用模块化结构设计,便于调试,纠错及升级;机器人应具有高度的机动性和灵活性,控制算法应保证机器人有良好的运动性能,除此之外,设计时需考虑到经济性。

2.2.2 视觉子系统

机器人足球的视觉子系统是整个系统的检测机构,它包括3个过程:图像获取、图像处理和图像理解。图像获取通过视觉传感器将三维环境图转换为电信号;图像处理是指图像到图像的转换,如特征提取;图像理解则在处理的基础给出环境描述。视觉子系统的主要任务[9]是以一定的周期、快速、实时采集赛场上的图像,处理并辨识,得到场上球的位置、以及识别己方和对方机器人小

基于遗传算法的足球机器人动态避障路径规划

车(包括10个机器人小车和1个足球的位置和运动情况(如表1.1所示,在此只列出双方3个机器人小车。然后,对赛场上获取的所有图像信息进行迅速的处理,并传给主机作为决策依据。比赛规则规定,每队都有自己的队标(黄色和蓝色,每个机器人也有自己的队员标志(除了队标和球之外的颜色。在机器人足球比赛过程中,摄像头固定,视场固定,光线充足,

机器人小车和小球的颜色鲜明、轮廓清晰等。这些特点给视觉系统的设计和实现带来了一些便利条件。但由于小车运行速度快,场上形势瞬息变化,视觉系统必须实现每秒数十幅彩色图像的辨识,并给出各个实体精确的位置坐标与朝向角,这种快速性、精确性要求又使视觉系统的设计与实现变为十分艰巨的任务。由于比赛时通常光照并不均匀,还可能出现各类光色干扰。为使系统可靠工作,视觉系统设计时还应考虑抗干扰措施。

表1.1 视觉子系统输出数据矩阵

机器人坐标x 坐标y 运动方向角度α

机器人A1 机器人A2 机器人A3 X1

X2

X3

Y1

Y2

Y3

1

α

2

α

3

α

机器人B1 机器人B2 机器人B3 X1

X2

X3

Y1

Y2

Y3

θ1

θ2

θ3

球X Y Φ

小型组足球机器人本身不含任何视觉传感器,所以视觉子系统是决定系统总体性能的关键因素。比赛过程中场上的信息通过固定在比赛场地上方的摄像头获取的,因此视觉子系统对于整个系统的重要性不言而喻,视觉系统性能优良的机器人足球队就把握了比赛取胜的先机。

2.2.3 决策子系统

决策子系统决策子系统在比赛进行过程中充当“大脑”的角色。在人类的足球比赛中,教练和球员的思维决策包括形象思维和逻辑思维两部分,在机器人比赛中,虽然他们决策方式不同,但是决策过程是类似的,决策子系统是整

基于遗传算法的足球机器人动态避障路径规划

个比赛的指挥机构,主机根据视觉子系统提供的数据,应用专家系统、模糊控制、神经网络等技术,判断场上攻守态势,确定机器人攻守策略,完成机器人角色分配。对于采用共轴平行的两轮独立驱动的移动机器人,决策子系统的输入信息是视觉系统获取的环境信息,包括球的位置,己方和对方机器人的位置及方向等,输出信息是本方5个机器人的左右轮轮速和击球控球命令。在足球机器人系统[10]中,决策是受视觉调用的。当决策子系统收到视觉

输入信息后,对其进行预处理,根据球和本方机器人的位置,对场上攻防形势进行分析,并将所作的决策分解为各个任务——这是决策的第一层。根据分解完的任务从队形库中为本方机器人确定一个队形——这是决策的第二层。根据队形所需的角色以及我方机器人的位置,将每个角色分配给具体的机器人——这是决策的第三层,之后通过机器人管理函数将左右轮速发送给对应的每个机器人。

图2.3 决策子系统流程图

决策子系统是机器人足球比赛的核心,主要解决足球机器人多智能体协作和运动控制问题。决策子系统上接视觉子系统,下接通信子系统,它的任务是根据视觉子系统送到的目标信息,即当前球场上的比赛形势(场上机器人和球的位置坐标和方向角,作出决策部署,产生机器人运动控制指令,给队员发出指令,通过无线通信子系统发送给各个机器人担负起教练员的职责。对于足球机器人而言,教练员是个盲人,他不是用眼睛看到比赛场景,反映到大脑进行

基于遗传算法的足球机器人动态避障路径规划

形象思维,而是根据队员在比赛场上的位置和球位置的精确数据对比赛场上的形势进行分析,所以更多的是依靠逻辑思维来完成推理过程。在每个控制周期内,决策子系统能像真正的运动员一样,做出各种动作,尽可能完成进球这个目标。

决策子系统是由决策模型和机器人行为控制两部分组成,决策模型主要完成攻防势判断、队形确定、角色和任务分配;机器人行为控制则包括动态避障和运动控制[11],决策系统实际上是由基层到高层逐步构造的一个设计过程。文中使用FIRA微型足球机器人的整个决策系统分为六个类,运算函数类、基本动作类、技术动作类、组合动作类、决策类,它们依次从基层到高层并且高层可以继承基层,但是基层不能继承高层,系统要求具有较高的实时性和灵活性,其灵活性指实现攻防策略,阵型变化、战术配合及足球机器人运动,使机器人的运动流畅。

2.2.4 通讯子系统

FIRE微足球机器人足球系统的通讯模块选用的是RF(射频通信模块,通过主机串口将命令传给发射装置,通过小车上的接收模块与场上各机器人建立无线通讯联系。命令字符串由机器人标识符、动作指令及指令数据等组成。 采用全局视觉集中控制的小型组机器人足球系统的通讯需求主要是主机向每个机器人发送数据,通常机器人不用向主机发送数据,机器人之间也不进行通讯。因此,一般采用应答式无线通讯方式,也可以采用无线局域网的方式。

由FIRA微型足球机器人的比赛规则决定了主机和机器人小车是无线的方式进行通讯的,一般采用的是无线射频通讯方式。

图2.4 通讯子系统流程图

无线通讯子系统包括两部分[12]:无线发射盒和无线接收模块,如图2.4所示。无线发射盒与主机相连,而接收模块则装在足球机器人小车上。主机中的指令数据通过计算机的串行口送到无线通讯模块,经过调制后以射频的方式发

基于遗传算法的足球机器人动态避障路径规划

射出去,由机器人小车的通讯装置接受信号并进行解调,然后传送给车载微处理器。主机和足球机器人小车之间的通讯是单向的,而且是一对多的形式。主机发给各个机器。

图2.5 各子系统的相互关系

从控制理论的角度上讲,这四个系统组成一个大闭环,各子系统的相互关系见图2-5。

如果将机器人比作人的话,那么视觉子系统相当于人的眼睛,决策子系统就相当于人的大脑,无线通讯系统就相当于人的神经系统,而机器人就相当于人的躯体。显然,4个子系统必须全部正常运行才能保证系统的有效运行,而系统性能的提高也是依赖于每个子系统性能的提高。

2.3 小结

本章首先对机器人足球赛的起源和发展进行了介绍,系统分析和研究足球机器人系统的体系结构及相关技术,介绍了组成足球机器人比赛系统的四个子系统。其中决策子系统中就包括了路径规划的策略,为本文进行足球机器人路径规划研究奠定必备的基础。

基于遗传算法的足球机器人动态避障路径规划

第3章足球机器人路径规划方法

3.1 引言

移动机器人路径规划技术是智能机器人领域中的核心问题之一,也是机器人学中研究人工智能问题的一个重要方面,机器人路径规划是在信息环境的基础上,针对某个特定的问题状态出发,寻求一系列行为动作,并建立一个操作集合,该集合具有时间的序列关系,直到目标状态为止。机器人的运动规划一般由两级规划组成:即全局规划和局部规划,全局规划主要解决机器人到哪里去的问题,而局部规划是解决机器人的定位和如何到达目标位置的问题,机器人处在复杂多变的环境中,如何找到没有冲突高效的路径是个复杂的问题,所以机器人的路径规划成为路径规划的研究重点[12],它被描述成:依据某一个或某一些优化准则(如

工作代价最小、行走路线最短等在根据一定的任务要求其工作环境中找出一条从起点到终点的能避开障碍物的移动机器人路径轨迹,即最优或次优的行走路径线。

移动机器人路径规划可以采用目前研究移动机器人路径规划的一个基本方法——构型空间法,其基本思想是用构型空间中的一个点来表征移动机器人的位置与方向。目前,最常用的方法是可视图法,即在一个无向图中,将移动机器人的起始点与终止点以及移动机器人运动环境中各障碍物的顶点表征点的形式,从而移动机器人的有效路径就是这样的一些点之间与障碍物不相交的相互连接的线段。

对于移动机器人的路径规划研究,设定移动机器人执行如下任务:由于移动机器人所处环境中各障碍物顶点处有物品需要搬运,要求移动机器人从起始点出发绕开障碍物,以较短的时间经过较多的障碍物顶点,最后到达终止点。

在足球机器人中,路径规划是实现机器人智能的关键技术,其目的主要是为了在充满对抗的赛场上规划出一条满足某项评价指标的无碰路径。路径规划主要应用于机器人底层策略中,作为足球机器人基本动作实现的基础,他的优劣将直接影响动作的实时性和准确性,因此对于足球机器人路径规划问题,国

基于遗传算法的足球机器人动态避障路径规划

内外的学者做了不少研究和实验,提出了很多方法和理论。随着科技的发展和问题的深入,原来已有的栅格法、人工势场法还有遗传算法、神经网络法等智能的方法已经不能很好的解决许多路径规划中的复杂的问题。这是因为有的方法应用范围很广,另一些方法

应用范围则极为有限。他们之间不是互相排斥的,各有优缺点,因而常常把这些方法结合起来共同地实现路径规划。

3.2 全局路径规划常用的方法

3.2.1 栅格法

栅格法(Grids是由W.E.Howden在1968年提出的,是目前研究较广泛的静态路径规划方法。栅格法[13]将机器人工作环境分解成一系统列具有二值信息的网络单元,工作这僮中障碍物的位置和大小一致,并且在机器人运动过程中,障碍物的位置和大小不会变化。该方法[14]将机器人的工作空间分解为多个简单的区域,一般称为栅格。栅格大小的选取直接影响着路径规划算法的性能。栅格选得过小,环境分辨率高,但抗干扰能力弱,环境信息存储量大,决策速度慢;栅格选得过大,抗干扰能力强,环境信息存储量小,决策速度快,但分辨率下降,在密集障碍物环境中发现路径的能力减弱。某一个栅格范围内不包含任何障碍物,则称此栅格为自由栅格;反之,称为障碍栅格。由这些栅格构成了一个连通图,在这个连通图上搜索一条从起始栅格到目标栅格的路径,所示该路径均由自由栅格构成,用栅格的序号来表示的。最后把栅格序号转换成机器人空间实际坐标,令机器人按此路径运动[16]。栅格的标识方法有两种:直角坐标法和序号法,多采用四叉树或八叉树表示工作环境,并通过优化算法完成路径搜索。

利用栅格法进行路径规划如图3.2所示:

基于遗传算法的足球机器人动态避障路径规划

图3.1 栅格法表示的机器人活动场地即搜索到的路径

根据机器人起始点和目标点的位置划定规划区域,即按照机器人活动场地

的大小进行栅格的定义和划分。然后将该区域用网格表示,每个网格就是一个

小矩形栅格,以保证机器人可以在其中自由移动。然后对划分好的栅格进行编

号,这里采用序号法[14]对每个小栅格进行编号,栅格序号将代表栅格所在的位

置。具有小方块的栅格表示可能有障碍物,障碍物为规格相同的其它机器人小

车。针对每个栅格位置的不同,将栅格分为两大类:边界栅格和中间栅格。

搜索无碰撞最优路径:就是选定一种搜索方法寻找一条从出发点到目标点

的连续自由栅格序列。

3.2.2 可视图法

可视图法把足球机器人处理成点。以机器人、运动目标点和动态出现的多

边形障碍物的各顶点进行组合连接,要求机器人和障碍物各顶点之间,目标点

和障碍物的各顶点之间以及各障碍物顶点与顶点之间的连线,都是可见的,即

都不能穿越障碍物,可视图法把搜索最优路径的问题转化为从起始点到目标点

经过这些可视直线的最距离问题。但是这样的连线会使的搜索变得更加复杂。

可以使用优化算法,删除一些不必要的连线以简化视图,缩短搜索时间。

基于遗传算法的足球机器人动态避障路径规划

3.3 局部路径规划常用的方法

3.3.1 人工势场法

在已知环境中进行运动规划,是机器人足球运动规划的基本问题,当足球机器人运动空间中存在一条期望路径时,全局方法可保证找到这条路径,但是随着机器人自由度数的增加,其计算机量呈指数增长,计算机的巨大复杂性限制了这类方法在实时控制中的应用,局部方法则大部分基于所谓的人工势场法,可在任务空间或操作空间完成。

人工势场法[15]最初由Khatib于1985年提出,在他的博士论文中首先将这种方法用于机器人操作臂的避障运动规划上,实现了机械臂的实时避障。这种方法同样使用于移动机器人的路径规划。

在人工势场[16]中,障碍物被看作斥力场,而目标被看作引力场,这种方法的计算机量远小于全局法,因此可以方便用于实时控制。每种机器人运动规划都具有自身的优点和缺点,相比于许多其他方法,人工势场法同时考虑了机器人的避障和轨迹规划,而且也考虑了机器人的动态运动性能,使机器人运动更加自然和具有柔顺性。它将物理学中场的概念引入到规划环境的表达当中,其基本思想是人工势场法的思想是把机器人在环境中的运动视为一种在抽象人造受力场中的运动,类似于电子在正负电荷产生的电场中运动,“同性相斥,异性相吸”, 引入一个称做人工势场的数值函数来描述空间结构,通过势场中的力来引导机器人到达目标。机器人沿吸引场和排斥场产生的合力方向运动,构造一个被称做势场函数的标量函数,搜索势函数的下降方向来寻找无碰路径,目标点对移动机器的产生引力,障碍物对机器的产生斥力,结果是使机器人沿“势峰”间的“势谷”前进。利用势函数完成运动意味着机器人运动轨迹是未知的或计算过于复杂,需要机器人自动选择合适的路径来达到目标,文献[17]提出的势函数表现出局部收敛的缺陷,这样,不论机器人处于自由空间的任何位置,只要有路径存在,它都能通过势能值的负梯度方向找到目标位姿,对应于障碍物区域有较大的值,可以保证生成路径的无碰性。如上所述,势场分为两种,即目标位姿产生的吸引势和障

碍物产生的排斥势。吸引势使机器人向目标位姿靠近,排斥势使机器人绕开障碍物,二者的叠加构成机器人运动的无碰运动。

基于遗传算法的足球机器人动态避障路径规划

人工势场法的优缺点:

优点:

(1结构简单,使用方便,便于底层的实时控制;

(2具有明显的柔顺性和自适应性,表现出了某种智能特征,是更加自然的控制方法;

(3具有较高的控制精度和处理未定因素的能力。

缺点:

(1是一种局部寻优方法,注重得到一条能够避障的可行路径,对路径是否最优并未加以考察;

(2对简单环境很有效,对于复杂的多障碍物环境,不合理的势场数学方程容易导致机器人在到达目标位置前由于陷入局部极小点而无法到达目标位置。

势场角度不易控制,会因为机器人或者障碍物等位置的稍微改变而发生较大变化,出现

在障碍物前震荡等现象,比如机器人在断墙之间。

为克服上述缺点,有很多人对人工势场法进行了改进,胡志华等[18]采用极点配置的PID控制器,采用渐消记忆对参数进和辩识,动态改变控制规律。金勇等[15]使用遗传算法优化势场函数,设计了基于进化势场的足球机器人路径规划系统,当障碍物间相距较近,机器人[19]受到的排斥力远大于目标对它的吸引力,造成机器人不能发现相近障碍物间的路径。

3.3.2 遗传算法

20世纪60年代末70年代初期,美国Michigan大学的John Holland与其同事、学生们在细胞自动机(Cellular Automata的研究过程中,从自然系统中生物的复杂适应过程入手,模拟生物进化的机制构造了一个人工系统的模型,并形成了一种较完整的理论和方法,称之为遗传算法(Genetic Algorithm,GA。而后Michalwicz将不同编码策略与遗传算法的结合称为演化算法(Evolutionary Algorithm,EA。随后经过30余年的发展,取得了理论研究上的进展和丰硕的成果,被广泛的应用于机器人系统、神经网络的学习过程、模式识别、图像处理、工业优化控制、自适应控制、遗传学,以及社会科学等领域。

基于遗传算法的足球机器人动态避障路径规划

遗传算法(GA[20]是以自然遗传、遗传选择和自然淘汰的生物进化过程的计算模型,它采用简单的编码技术来表示各种复杂的结构,采用从自然界选择、遗传操作中抽象出来的几个算子,对一组参数编码的字符串编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向,构造了一种仿生搜索算法,它使用群体搜索技术,种群代表一

组问题解,通过对当前种群施加选择、交叉和变异等一系列遗传操作,从而产生新一代的种群,并逐步使种群进化到包含最优解或近似最优解的状态。这个算法在进化过程中可以并行地对解空间的不同区域进行搜索,可使搜索趋于全局最优解而不会陷于局部极小解。遗传算法作为一种新的全局优化搜索算法,以其简单通用、鲁棒性强、适合于并行处理以及应用范围广等显著特点,奠定了它作为21世纪关键智能计算方法之一的地位,从而被引入到需要进行优化的机器人路径规划领域之中。遗传算法的操作算法有:

复制或选择、交叉和变异是遗传算法的三个主要操作算子,它们构成了所谓的遗传操作,使遗传算法具有了其他传统方法所没有的特性,遗传算法中包含了如下五个基本要素:①参数编码;②初始群体的设定;③适应度函数的设计;④遗传操作设计;⑤控制参数设定(主要是指群体大小和使用遗传操作的概率等。

遗传算法是一种通过模拟自然进化过程搜索最优解的方法,属于改进式启发算法,在机器人路径规划方面属于智能算法。

遗传算法采纳了自然进化模型[21],如选择、交叉、变异、迁移、局域和领域等。如图3.6基本的遗传算法的流程。

基于遗传算法的足球机器人动态避障路径规划

图3.2 遗传算法简单流程图

遗传算法的优点[11]:

(1基本的遗传算法是对参数集的有限长度编码进行操作,并为每一个编码产生一个适配值来评价该编码的好坏,通过编码和适配值使得算法不需要考虑问题的具体情况,从而容易适应各种情况,可以对具体问题进行编码操作,在二维结构化空间中应用遗传算法规划机器人运动路径,而在很难对问题进行编码时也完全可以直接对问题的参数集进行操作,即通过直接对已有路径点序列集编码而进行寻优操作。

(2实现全局最优路径的规划,采用群体方式对目标函数空间进行多线索的并行搜索,可同时对多个可行解进行检查,交叉算子、变异算子可以使可行

基于遗传算法的足球机器人动态避障路径规划

解之间交换信息从而产生新的可行解,不会陷入局部极小点。

(3只需要可行解目标函数的值,而不需要其他信息,对目标函数的连续性、可微性没有要求,因此使用方便。

(4解的选择和产生采用概率方式,因此具有较强的适应能力和鲁棒性。

缺点:

(1解的早熟现象、局部寻优能力差,保证不了对路径规划的执行效率和可靠性。

(2利用遗传算法解决机器人动态环境中路径规划问题,可以直接获得问题的最优解,避免困难的理论推导,但遗传算法速度不快,进化众多的规划要占用较大的存储空间和运算时间。

所以已有很多人把遗传算法与其他算法相结合进行路径规划上,如姜明洋[22]等提出在遗传算子的设计中,加入了平滑、插入和删除算子来补充基本算子的不足,使用变异率和交叉率的自适用调整方法对遗传算法进行优化;孟宪强等[23]提出基于量子遗传算法的足球机器人路径规划方法,通过对路径点进行量子比特编码,使一条遗传路径染色体可以表达多个态的叠加,并对路径适应度函数优化求解实现移动机器人的路径规划;杨长禹[24]提出新的自适应的隔离小生境遗传算法,还有将遗传算法与模拟退火、神经网络、模糊控制等相结合,如遗传算法负责搜索和优化,而模糊推理处理未知及不明确的状况,吸取双方的长处有效

地解决动态避障的问题。此外,还有蔡自兴[20]、周明及孙树栋等人的研究成果。

3.3.3 神经网络法

神经网络[19]是在现代神经科学研究的基础上提出的,反映了人脑功能的基本特征,神经网络模型用于模拟人脑神经元活动的过程,使机器人具有人脑那样的感知、学习和推理等智能。神经网络是模拟人类生理上的神经机制的计算模型,也是一种常用的学习方法,它用于全局路径规划,人工神经网络是根据人的认识过程而开发出的一种算法,它将控制系统处理成由输入到输出的建模和控制。如文献[28]所描述,神经网络是一个高度复杂的非线性动力系,其主要特征是它处理具有一般非线性系统的共性之外,还有自己的特点,如信息的分布存储和信息的并行协同处理。将它用于系统设计主要是针对系统的非线性、

基于遗传算法的足球机器人动态避障路径规划

不确定性和复杂性进行的,人工神经网络广泛应用于机器人控制领域,对机器人路径规划的研究尤为重要。

神经元是神经网络的基本构造,神经元是处理人体内各部分之间相互信息传递的基本单元,人们对生物神经系统进行研究,探寻和研究其工作机制,把神经细胞模型化,构造了神经元模型。文献[29]建立起更接近于工程的神经元数学模型,该模型是一个多输入单输出的非线性信息处理单元,从系统观点看,神经网络是由大量神经元通过极其丰富和完善的联接而构成的自适应非线性动态系统,如图3.5所示。神经网络具有高度并行的体系结构,神经元之间的信息的传播是双向的,每个神经元节点对应于离散化结构空间中的一个位置。其

中权值即代表神经元之间的连接强度,x 12

,,n x x K K x 是神经元的输入,兴奋的阈值为y θ,

输出信号是y ,神经细胞之间信息的传递效率用12,,n ωωωK K 表示,即神经元对12,,n x x K K x 的权系数,f(x为非线性转移函数。

图3.3 神经元形式化结构模型图

神经元网络的工作原理:

虽然单个神经元的结构和功能都很简单,但是当大量形式相同的神经元连接在一起组成神经网络时,就构成了一个高度非线性动力学系统,神经网络的动态行为十分复杂,用神经网络可以表达实际物理世界的各种现象,描述神经网络[30]的原理为:是一种前向网络,它有一个输入层,一个输出层和多个隐含层,同层节点(神经元间无关联,异点层节点间前向连接,其基本结构如图

3.6所示,隐层数越多,计算结果越精确,但是所需的时间也就越长,所以要根

基于遗传算法的足球机器人动态避障路径规划

据具体要求来设计网络层数。用神经网络对机器人进行路径规划,其目标是使整个路径的长度尽量短,同时又要尽可能远离障碍物。

输

出

层

图3.4 神经网络基本结构图

优点:算法简单,对被控制系统先验知识要求少,可任意精度逼近期望轨迹,控制器可自学习达到在线寻优[31]。

缺点:

从数学的角度看,神经网络算法是一个非线性优化问题,不可避免存在有局部极小值问题。

陈卫东等[32]提出:一种基于模糊回归神经网络的间接自适应控制方法,解决了一般无反馈模糊神经网络仅限于表态映射的缺陷,利用其动态记忆和模糊推理功能对系统模型进行全局逼进,获得良好的轨迹跟踪响应。黄磊等[28]提出采用神经网络模型对机器人所处的环境进行描述之后,利用神经网络建立遗传算法的适应度函数,使用遗传算法优化路径,又将遗传算法与模拟退火算法相结合构成遗传模拟退火算法。

3.4 基于行为的路径规划方法

基于行为的移动机器人路径规划方法是移动机器人路径规划问题研究中的一种新动向,就是把导航问题分解成许多相对独立的导航单元,即行为单元,

基于遗传算法的足球机器人动态避障路径规划

如避碰、跟踪、目标制导等,这些行为单元都是具有传感器和执行器的完整运动控制单元,具有相应的导航功能,彼此协调工作,完成总体导航任务,基于行为的控制方法具有较强的实时性、计算量小、能实现多种复杂功能,近几年得到了广泛应用。

行为控制[33]是一种重要的、全新的智能控制方法,它是将机器人所感知到的所有信息和知识库一起融合到一个全局的环境地图中,基本行为是感知和执行的单元。

在基于行为的机器人路径规划过程中,参与控制的是各种不同的、并有可能不兼容的

多个行为,每个行为负责机器人某一特定目标的实现或维护,如跟踪目标或避障等,多个行为往往可能产生互相冲突的控制输出命令,因而系统首先需解决的一个问题是多行为的协作,即通过构造有效的多行为活动协调机制实现合理一致的整体行为。

3.5 动态环境下的路径规划方法

近几年人们比较关注动态环境下的多个机器人路径规划问题,在机器人足球赛中,常常存在动态障碍物,静态环境下机器人的路径规划方法比较简单也容易实现,由于机器人周围环境信息具有不完整性、不可预知性以及缺少相关数据信息等缺点,导致动态环境下,对足球机器人进行路径规划难度加大,在实际的真人足球比赛中,当球员要往一个目标点前进的时候,我们只考虑在我们前进方向的障碍物(球员,而且还要考虑距离我们比较近的球员,因为每个球员都处在运动中,使得路径规划具有很在很多不确定性,所以一般的路径规划方法可以只考虑局部障碍物的情况,这种不确定性还存在于传感器测量数据以及计算过程中,本文的方法是将遗传算法与动态环境下足球机器人所要完成的行为控制相结合。

3.6 各种方法综合分析

前面介绍了可视图法、栅格法、人工势场法、遗传算法还有神经网络法,

基于遗传算法的足球机器人动态避障路径规划

并简单描述了这些方法在机器人路径规划中的应用。现在对这些方法进行比较分析[28]。

栅格法:简单的建模过程和灵活多变的搜索算法可以被各个领域和各个阶层的人接受和使用,而且只要问题的最优路径存在,设计合理的搜索算法一定能求出最优路径。但是当要规划的环境比较大时,将需要较大的存储空间,搜索效率也会下降;规划出的路径是一个折线,路线不够光滑,机器人在转角处的速度会很受影响,对于高速运行的机器人,这个问题将会更为突出。

人工势场法结构简单,使用方便,便于底层的实时控制,规划出的路径一般比较平滑并且安全,使机器人运动更加自然和具有柔顺性,但是人工势场法是一种局部规划算法,不一定能规划出全局最优路径,而且算法本身存在着一定的局限性,可能会出现机器人没有到达目标点时就停滞或者找不到路径的现象;当障碍物和目标点的位置很接近时会出现机器人在障碍物面前振荡甚至被障碍物推开的现象。

遗传算法和神经网络属于人工智能法,遗传算法是一种全局寻优算法,在求解最优路径问题中有很大的应用价值;神经网络是一种大规模并行处理算法,它模拟人类生理上的神经机制的计算模型,对环境有一定的容错能力。但这两种方法的共性就是算法比较复杂,在具体进行路径规划时的算法设计也是个比较复杂的过程,需要花费设计者较大的精力,二者都是迭代算法,可能会出现迭代次数较多的情况,不一定能完全满足实时性要求较高的环境。

3.7 本章小结

本章重点对解决机器人路径规划的全局路径规划算法、局部路径规划算法、基于行为的路径规划算法理论和它们在机器人路径规划中的应用进行研究,可视图法、栅格法、人工势场法、遗传算法和神经网络法,分析了每个方法的性能和特点,客观评价了各自的优点

和缺点,最后从各种方法的应用得出这些算法在解决机器人路径规划问题时存在的优缺点。

基于遗传算法的足球机器人动态避障路径规划

第4章基于遗传算法的足球机器人路径规划

4.1 引言

遗传算法是目前足球机器人路径规划研究中应用比较多的一种智能算法,遗传算法以自然遗传机制和自然选择等生物进化理论为基础,构造了一类随机化搜索算法,主要特点是采取群体搜索策略和在群体中个体之间进行信息交换,利用简单的编码技术和繁殖机制来表现复杂的现象,因为其并不要求待求解问题局限在某些特定的范围内,已经在移动机器人路径规划的结构优化和行动协调等方面得到研究和应用。无论对于单机器人静态工作空间,还是存在多机器人的动态工作空间,遗传算法及其派生算法都有取得了良好的路径规划效果,它是一种多点搜索算法,是一种求解全局最优解的较好方法。

4.2 遗传算法概述

20世纪60年代,Michigan大学[34]的J.H.Holland认识到生物的遗传和自然进化现象与人工自适应系统的相似关系,提出了遗传算法,遗传算法简称GA(Genetic Algorithm,在本质上是一种不依赖具体问题的直接搜索方法,生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种。遗传算法是近几年发展起来的,是根据生物进化思想而启发得出的一种崭新的全局优化算法。

遗传算法[13]的基本思想是基于Darwin进化论和Mendel的遗传学说的, Darwin进化论最重要的是适者生存原理,它认为每一物种在发展中越来越适应环境,物种每个个体的基本特征由后代所继承,但后代又会产生一些异于父代的新变化,在环境变化时,只有那些能适应环境的个体特征方能保留下来, Mendel遗传学说最重要的是基因遗传原理,它认为遗传以密码方式存在细胞中,并以基因形式包含在染色体内,每个基因有特殊的位置并控制某种特殊性质;所以,每个基因产生的个体对环境具有某种适应性,基因突变和基因杂交可产

基于遗传算法的足球机器人动态避障路径规划

生更适应于环境的后代,经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来。

在问题求解的过程中,它是从代表问题可能潜在解集的一个种群(population开始的,而一种群则由经过基因(gene编码(coding的一定数目的个体(individual组成。把搜索空间视为遗传空间,把问题的每一个可能解看作一个个体,个体里面有基因,所有的个体组成群体。遗传算法采纳了自然进化模型,如选择、交叉、变异、迁移、局域和邻域等,提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题的具体领域,对问题的种类具有很强的鲁棒性,所以广泛应用于许多学科。

遗传算法随着问题种类的不同以及问题规模的扩大,要寻求一种能以有限的代价来解决搜索和优化的通用方法,遗传算法正是为人们提供的一个有效的途径。遗传算法已在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到了成功的运用。此外,GA也在生产调度问题、自动控制、机器人学、图像处理、人工生命、遗传编程和机器学习等

方面获得了广泛的运用,它不同于传统的搜索和优化方法,主要有以下特点[22]:

(1遗传算法以决策变量的编码作为运算对象。

(2传统的优化算法往往直接利用决策变量的实际值本身,而遗传算法处理决策变量的某种编码形式,使得我们可以借鉴生物学的染色体和基因等概念,可以模仿自然界的遗传和进化机理。

(3遗传算法的本质并行性,遗传算法按并行方式搜索一个种群数目的点,而不是单点,具有隐含搜索特性,从而大大减少了陷入局部极小的可能性。并行性表现在两个方面:一是遗传算法是内在并行的,即遗传算法本身非常适合大规模并行;二是遗传算法的内含并行性,由于遗传算法采用种群的方式组织搜索,因而可同时搜索解空间内的多个区域,并相互交流信息。

(4遗传算法使用概率搜索技术,而非确定性规则。

(5遗传算法具有全局搜索能力,最善于搜索复杂问题和非线性问题。

无论对于单机器人静态工作空间,还是存在多机器人的动态工作空间,遗传算法及其派生算法都有取得了良好的路径规划效果,它是一种多点搜索算法,是一种求解全局最优解的较好方法,在人工智能研究中,现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样,都是对今后十

基于遗传算法的足球机器人动态避障路径规划

年的计算技术有重大影响的关键技术”。

4.3 遗传算法基本原理

遗传算法GA是一种迭代算法,它从某一随机产生的或是特定的初始解集出发,初代种群产生后,按照适者生存和优胜劣汰的原理,逐代(generation 演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness大小挑选(selection个体,并借助于自然遗传学的遗传算子进行组合交叉和变异,产生代表新的解集的种群,这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,末代种群中的最优个体经过解码(decoding,可以作为问题的近似最优解。

遗传算法GA采纳了自然进化模型,计算开始时,一定数目N个个体随机初始化,并计算每个个体的适应度函数,第一代即初始代就产生了,如果不满足优化准则,开始产生新一代的计算。为了产生下一代,按照适应度选择个体,父代进行基因重组而产生子代。所有的子代按一定概率变异,然后子代的适应度又被重新计算,子代被插入到种群中将父代取而代之,构成新的一代。这一过程循环执行,直到满足优化准则为止[21]。

4.4 遗传算法的设计步骤

基于遗传算法的移动机器人路径规划,算法具有良好的通用性,其设计步骤一般可分为参数的编码、初始化、确定适应度函数、算法参数选取、遗传算子的设计和确定算法终止条件六个部分,如图4.1所示:

基于遗传算法的足球机器人动态避障路径规划

图4.1 遗传算法运算流程

1、 路径编码

用遗传算法求解任何优化问题,最关键的步骤是对问题的潜在解进行编码,在遗传算法中如何描述问题的可行解,即把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法就称为编码。而由遗传算法解空间向问题空间的转换称为解码(或称译码,Decoding。遗传算法的编码就是解的遗传表示,它是应用遗传算法求解问题的第一步。用n个具有任意染色体的个体组成初始种群,其中最主要的是对参数的编码。由于遗传算法的优化过程不是直接作用在问题参数本身,而是在一定的编码机制对应的码空间上进行的,因此编码的选择是影响算法性能与效率的重要因素,常用的编码方式有二进制编码

和十进制编码。

二进制编码是将问题的解用一个二进制串来表示,该编码方式具有编译码操作简单和遗传操作便于实现等优点。但是存在着连续函数离散化时的映射误

基于遗传算法的足球机器人动态避障路径规划

差。当个体编码串的长度较短时,可能达不到精度要求;当个体编码串的长度较长时,虽然能提高编码精度,但却会使搜索空间急剧扩大。二进制编码的缺点是:二进制编码存在着连续函数离散化时的映射误差,个体编码串的长度较短时,可能达不到精度的要求,而个体编码串的长度较大时,虽然能提高编码精度,但却会使遗传算法的搜索空间急剧扩大;而有就是它不能直接反映出所求问题的本身结构特征。

为了克服二进制编码方法的缺点,人们提出了个体的十进制编码即浮点数编码方法。

首先,将移动机器人所处环境中的障碍物表示成多边形的形式,令所有障碍物顶点个数之和为n;然后对所有顶点用十进制进行任意编号,取值为[1,n]之间的整数。然后将移动机器人的路径编码成长度为n的十进制染色体串,串中非0位上的整数值表征移动机器人的路径经过了环境中相应编号的顶点,各非O 位在串中的顺序即相应编号的顶点在路径中的顺序,为避免路径经过重复的顶点,在同一串中非O值是不允许重复的[34]。

2、初始群体的产生

在遗传算法的初始化处理过程中,经常采用随机产生初始群体,这样可以达到产生方式

不依赖于问题的目的。因此从随机初始群体出发能更清楚地考察算法的行为和性能。进化群体的大小会影响遗传算法的收敛性,首先,种群由经典值100个个体组成,初始化时,设置这100个个体的每一位都是O;然后,每个个体的初始化由一个n次的循环来完成,每次循环对染色体串中的一位进行初始化,由于一条路径经过太多的顶点时,其与障碍物相交的机会比较大,因此每次循环均先以50%的概率决定该位的值是O还是一个非O的整数,以保证一个个体中有50%概率的位是0,这样就可以避免了一条路径经过太多的顶点而不利于有效路径的获得。

3、适应度函数

适应度函数是遗传算法与问题的接口,对遗传算法的收敛速度和结果影响很大,根据问题的特点而设计合适的适应度函数,能产生适宜于遗传算法处理的状态空间,能使算法快速有效地收敛。以移动机器人经过的不重复的项点数和移动机器人经过的路径长度的比例作为适应度函数P,如果某个体表示的路径是有效路径,定义该个体的适应度为lOP;如果某个体所表示的路径不是有效路

基于遗传算法的足球机器人动态避障路径规划

径,则定义该个体的适应度为O.1P,定义个体的适应度是因为移动机器人的路径规划就是要寻求一条满足性能要求的移动机器人有效路径。这样定义就增加了代表有效路径个体的适应度值。

对于非线规划问题,一般用函数值来评价解的好坏,这种方法是最直接,也是最方便的方

法。这也是本文使用的方法。

4、遗传算子

(1选择操作

选择算子的作用是繁殖、再生或复制,用来模拟生物界采用传统的赌盘选择方法,遗传算法使用选择算子(又称复制算子,Reproduction Operator来对群体中的个体模拟优胜劣汰操作,根据每个个体的适应值大小选择,适应度较高的个体被遗传到下一代群体中的概率较大;适应度较低的个体被遗传到下一代群体中的概率较小。这样就可以使得群体中个体的适应度值不断接近最优解。选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免有效基因的损失,提高全局收敛性和计算效率。选择算子确定的好坏,直接影响到遗传算法的计算结果。选择算子确定不当,会造成群体中相似度值相近的个体增加,使得子代个体与父代个体相近,导致进化停止不前;或使适应度值偏大的个体误导群体的发展方向,使遗传失去多样性,产生早熟问题。

(2交叉操作

交叉操作是模拟生物进化过程中的繁殖现象,能过两个个体的交换组合产生新的个体,具体的操作步骤是:

①在区配集中任选两个个体作为双亲个体;

②在双亲个体数字串中随机选择一点或多点作为交叉位置;

③交换双亲个体交叉点右边部分产生新的个体。

(3变异操作

遗传算法模仿生物遗传和进化过程中的变异环节。变异(Mutation是以较小的概率对个体编码串上的某个或某些位值进行改变,如二进制编码中“0”变成“1”,“1”变成“0”,进而生成新个体。遗传算法中,所谓的变异运算,是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换,从而形成一个新的个体。从遗传运算过程中产生新个体的能力方面来说,变异本身是一种随机算法,但与选择和交叉算子结合后,能够避免由于选

基于遗传算法的足球机器人动态避障路径规划

择和交叉运算而造成的某些信息丢失,保证遗传算法的有效性。交叉运算是产生新个体的主要方法,它决定了遗传算法的全局搜索能力;而变异运算只是产生新个体的辅助方法,但它也是必不可少的一个步骤,因为它决定了遗传算法的局部搜索能力。交叉算子和变异算子相互配合,共同完成对搜索空间的全局搜索和局部搜索,从而使得遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。

实施遗传算法步骤为:

对待解决问题进行编码,我们将问题结构变换为位串形式编码表示的过程叫编码;而相反将位串形式编码表示变换为原问题结构的过程叫译码。

随机初始化群体P(0:=(p1, p2, … pn。

计算群体上每个个体的适应度值(Fitness。

评估适应度,对当前群体P(t中每个个体Pi计算其适应度F(Pi,适应度表示了该个体的性能好坏。

按由个体适应度值所决定的某个规则应用选择算子产生中间代Pr(t。

依照Pc选择个体进行交叉操作。

仿照Pm对繁殖个体进行变异操作。

没有满足某种停止条件,则转第3步,否则进入9。

输出种群中适应度值最优的个体。

5、终止

就如同程序中循环无限地执行下去会导致死循环,对于遗传算法也不能无条件地执行下去,要在合理的时间内终止。

遗传算法通常用到的终止标准有:

① 收敛标准,算法执行到一定程度,群体中的个体字符串结构会很相似,再执行下去难以得到更好的个体了,这时认为算法收敛了。当然,判断收敛的标准可以是不同的。

② 时间标准,预先给定算法的执行时间,如给定要产生的个体的总数、循环的代数或者计算的时间长度。

③ 精度标准,当找到的个体的评价函数值的精度达到一定要求后,算法就可终止。

程序的停止条件最简单的有如下二种:完成了预先给定的进化代数则停止;

基于遗传算法的足球机器人动态避障路径规划

种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。

4.5 利用遗传算法进行路径规划

4.5.1 环境建模

所谓环境建模是指建立合理的数学模型来描述移动机器人的工作环境。路径规划算法有效性很大程序上依靠障碍物的描述,许多研究者采用栅格法、拓朴法、路径法等方法进行环境建模。在这里主要用栅格建模方法,用序号标注每个栅格,栅格大小以机器人能在其内自由运动为限。自由空间和障碍物都可表示成栅格块的集合。划分后的机器人工作空间如图4.2所示:图中阴影区为障碍物。

在工作空间中[22],障碍物可以用其所占据的栅格边界顶点来记录,当环境中出现了动态障碍物的时候,视其为一个质点,它不具备形状,但有一定的安全范围,即在安全范围之外都认为是可以避碰的,安全范围之内视为无法避碰,每个动态障碍物都有一定的运动轨迹。

图4. 2 移动机器人所处环境

基于遗传算法的足球机器人动态避障路径规划

4.5.2 编码

遗传算法中进化进程是建立在编码机制的基础上,编码对算法的性能有很大影响,如搜索能力和种群的多样性,进行足球机器人路径规划研究,在这里用十进制栅格序号表示路径

点,用栅格序列表示一条染色体,由于无法确定究竟要经过多少个栅格,所以这里的染色体用不定长染色体表示。

4.5.3 种群初始化

初始种群为在机器人工作空间模型中随机生成的从起点到终点的任意一条可能的路径,无论是从遗传算法的基础理论还是从算子的运算方式来看,交叉操作对初始化种群的依赖性较强,而遗传算法的搜索速度主要依赖于交叉计算,所以,初始化种群必须充分代表解空间的个体,在有限数量内最大限度地表示所有个体的信息。

由于路径的起始点和终止点已知,在种群初始化的过程中确定自由栅格(不含任何障碍物的栅格和障碍栅格(包含障碍物的栅格的序号,在初始化结束后得到的种群中应该不含有障碍栅格的序号。

4.5.4 适应值的计算

适应值的计算可以说是遗传算法与优化问题之间的接口,遗传算法评价一个解的好坏,不是取决于它的解的结构,而是取决于相应于该解的适应值。利用种群中每个个体的适应值来进行搜索,选择适应值函数将直接影响到遗传算法的收敛速度以及能否找到最优解。进行足球机器人的路径规划,就是要规划出一条最短的可行路径,约束条件是路径不与障碍物相交,且要求与障碍物有一定的距离。对路径优劣程度的评估就作为遗传算法中染色体的适应值。以路径最短为评价标准,选择适应值函数为

⎪⎪⎪⎪ ⎪⎪⎪⎪⎪⎪ ⎪

⎪-+=D n f 111/1 其中:n 表示该个体通过的栅格总数;D 表示该个体相邻序号间直线距离之和。

4.5.5 遗传算子的操作

定义了初始化群体和适应值之后,遗传算法可以通过交叉、变异等遗传算

基于遗传算法的足球机器人动态避障路径规划

子生成新个体,对采用浮点数编码的遗传算法来说,定义合理的遗传操作算子对提高算法性能非常重要。通过新个体的评估产生子代,不断进化,直到得到问题的最优解或达到算法终止条件而停止。

(1选择操作

用一定的算法从当前种群中选择同样数量的新一代群体。首先计算每个个体的适应值函数,本文采用一种被称为“轮盘赌”的方法,设群体的规模为N,

若某个体体i,其适应度为(i=1,(i x f N ,Λ,则第i 个染色体被选中的概率由

下式:被选取的概率表示为:

∑==N

j j i i x F x F P 1(/(

在选择一个染色体时,先转动轮盘,等转盘停下后,指针指向的格子所对应的i 就是被选中的个体。这样经过N 次“轮盘赌”之后,就得到规模为N 的种群。

图4.3“轮盘赌”示意图

(2交叉操作

交叉是以一定的概率,通常有单点交叉、多点交叉、均匀交叉等几种方法。

基于遗传算法的足球机器人动态避障路径规划

在变长的染色体中随机选择一个除起始点与目标点以外的转向点,这个转向点就作为交叉点,把整个路径分成两个路径段。然后选择两个父代染色体,相互交换交叉点后面的路径段,这样就产生了两个子代染色体。交叉后的子代染色体代替原种群的父代染色体,产生

新的种群。

(3变异操作

变异算子就是对某些染色体的某一处基因进行替换,对应于路径规划的局部随机搜索,与选择操作结合在一起,保证了遗传算法的有效性,使遗传算法具有局部的随机搜索能力,可以从个体中以一定概率选择一个起点和终点之外序号作为变异点,删除该点,或者用另一个随机产生的序号代替它,或者在个体中随机选择一个序号在变异处插入,在进化的初始队体段,变异的范围很大,但随着进化过程的进行,变异量逐渐减小。

(4优化操作

在机器人的路径规划中,还需要增加一些特殊的操作,以保证所得的路径能够避开障碍物,并达到最短的要求,常见的有插入和删除算子操作。

插入算子:由于交叉操作和变异操作可能产生不连续路径的情况,引入插入操作的目的就是把间断路径用自由栅格弥补,使之成为连续路径。具体方法是对于一条路径,统计穿越障碍物线段并记录下来,如果有线段穿越障碍物,则从中选择一段并在这一段之间增加一个点,否则随机选择路径中的一段,插入一个任意产生的转向点,要求新插入的转向点坐标在非障碍物区域内。显然,在不存在相交的地方是不需要施以插入操作的,所以插入操作是按不等概率进行的。

删除算子:插入自由栅格的操作可能会使路径中出现重复节点,删除操作的作用就是将个体中两相同序号之间的冗余序号,连同两个相同序号中的一个一并舍去,可以使得不可行

路径变为可行路径,以简化路径。

基于遗传算法的足球机器人动态避障路径规划

第5章基于遗传算法的行为控制路径规划方法5.1 引言

在高度结构化的比赛环境下,足球机器人都是执行预先规定的动作序列,由于缺乏灵活性和自主性,在新的环境下或遇到意外情况时,不能很好地完成任务。主要原因是现实环境是非结构化的,存在不确定性,具体体现在关于环境的先验知识通常是不全面的,不确定的和近似的;大多数机器人由于传感器自身的限制,感知信息存在不同程度的不确定性,直接使用感知信息很难得到准确的环境模型,现实的环境通常具有复杂和不可预测的动态特性[29]。

基于行为的方法是一种自底向上的“进化”方法,它将系统按照行为划分成不同的层次,本文采用基于行为的结构,能克服环境的不确定性,可以很容易地得出控制策略,可以实现分布式控制,可靠地完成复杂任务,且效率高,鲁棒性好。主要缺点是不能明确地定义群体行为,很难对其进行数学分析,并且不能保证队形的稳定性。

5.2 足球机器人路径规划的行为方法描述

在机器人研究中,对于环境的描述经常包含着不确定因素,不能将其直接归类到某一环境特征或采取某一明确的规则。路径规划可以分为三种类型:一种是基于环境已知的路径规划;另一种是基于传感器信息的不确定环境的路径规划;第三种是基于行为的路径规划方法。基于行为的方法是构造工作于动态环境中机器人的一种有效工具。该方法按照任务要求将机器人运动分解为一系列基本行为的集合,根据传感器信息和有关通讯信息对环境做

出快速反映,以便于更好的完成任务。基于行为的设计方法在机器人路径规划中也是一个很重要的方法,行为的选取是由机器人所要完成的任务决定的,任务不同,完成它就可能需要不同的行为。把复杂的任务分解成很多简单的可以并发执行的单元,每个单元有自己的感知器和执行器,构成感知动作行为。