（机械电子工程专业论文）微型足球机器人决策系统的研究和开发.pdf

天津大学硕士学位论文 中文摘要 近年来，随着机器人a g e n t 模型在多机器人协调中的应用，基于多智能体 ( m a s ) 理论的多机器人合作已经成为机器人学领域的研究热点。毫无疑问， 足球机器人系统本身是一个典型的多智能体系统。足球机器人是一个新兴的交 叉学科项目，它涉及到机器人学、人工智能以及智能控制多个领域，同时为这 些领域的理论研究和模型测试提供了一个标准的实验平台。本课题在天津市自 然科学基金和8 6 3 机器人项目组资助下，对足球机器人决策系统进行了详细的 研究并且提出了可行的设计理念和方法。 首先，本文针对机器人足球比赛的特点归结出了简单有效的决策推理过 程，并在其启发下，确定了决策系统的分层递阶式的体系结构，此结构对整个 系统的构建具有全局性的指导意义；然后提出了小车运动学方程，并以它为基 础采用了两种互为补充的路径规划方法来引导机器人小车完成任务：紧接着以 人类足球队员的技术动作为参照，完成了足球机器人基本动作的设计任务，在 设计中采用了分层的原则，进一步增加了系统的扩展性：最后，本文利用知识 映射表的方法解决了在逻辑推理过程中的实时性难题；在结尾部分，总结了本 文的工作成果，并提出了需要迸一步完善的地方。 关键词：人工智能多智能体足球机器人决策系统 体系结构路径规划基本动作知识映射表 天津大学硕士学位论文 a b s t r a c t a l o n gw i t ht h ea p p l i c a t i o no fa g e n tm o d e l i nt h em u l t i r o b o ts y s t e mi nr e c e n t y e a r s ，m u l t i r o b o tc o o p e m f i o i l ，b a s e do n t h et h e o r ym a s ( m u l t i a g e n ts y s t e m ) ，h a s b e c o m eah o tp o i n ti nt h ed o m a i no fr o b o t i c s i ti sn od o u b tt h a tt h es o c c e rr o b o t s y s t e m i sa t y p i c a lm o d e l o f m a s i ti san e w i n t e r d i s c i p l i n a r y r e s e a r c ha r e a ，r e f e r r i n g t od i v e r s ef i e l d sl i k e ，r o b o t i c s ，a r t i f i c i a li n t e l h g e n c e ，i n t e l l i g e n tc o n t r o l ，e t c f i a n c e d b yt i a n j i nh i g h e d u c a t i o nd e v e l o p m e n tf o u n d a t i o na n dt h e8 6 3h i g h - t e c h p r o g r a m s ， ad e e pr e s e a r c hw 鼬e x e c u t e do nt h es o c c e rr o b o ta n daf e a s i b l e p r i n c i p e w a s p r e s e n t e d f i r s t l y ，a i m i n ga tt h ec h a r a c t e r i s t i c so f t h es o c c e rr o b o tg a m e ，t h ep a p e r g o tt h e s i m p l e a n de f f e c t i v e l o g i c a lr e a s o n i n gm o d e l ，a n d e s t a b l i s h e dt h e s y s t e m s a r c h i t e c t u r e ，w h i c hc o n d u c t e dh o wt o s e t u pt h es y s t e m s e c o n d l y ，t h em o t i o n e q u a t i o no f w h e e l e dm o b i l er o b o tw a sp r o v i d e d ，a n db a s e do nt h ee q u a t i o nt h ep a p e r a d o p t e d t h et w ow a y st op l a nr o b o t sp a t h s ，w h i c hw o u l d p i l o tt h er o b o t st of i n i s ht h e v a r i o u st a s k s t h i r d l y ，t h eb a s i ca c t i o n s ，w h i c hi m i t a t e dh u m a ns o c c e rp l a y e r ss k i l l s ， w a s d e s i g n e d ，a n d t om a k ei te a s i e rt oe x t e n dt h ea c t i o n s ，t h eh i b e r a r c h yw a s a d o p t e d t h e nan e w m e t h o d - k n o w l e d g em a p p i n gt a b l e ，w h i c h t oag r e a te x t e n te n h a n c e dt h e s y s t e m s r e a l t i m e ，w a sg i v e nd u r i n gd e s i g n i n gt h eh i g h - l a y e rl o g i c a lr e a s o n i n g m o d u l e f i n a l l y ，a l lm a i n c o n c l u s i o n si nt h ed i s s e r t a t i o na n df u r t h e rs u g g e s t i o n sw e r e g i v e n k e yw o r d ：a r t i f i c i a li n t e l l i g e n c e ，m u l t i - a g e n ts y s t e m ，s o c c e r r o b o t ，s t r a t e g ys y s t e m ， a r c h i t e c t u r e ，p a t hp l a n n i n g ，b a s i ca c t i o n ，k n o w l e d g em a p p i n g t a b l e 独创性声明 、本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得墨生盘茎或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的浇明并表示了谢意。 学位论文作者签名糊签字r 期：甜哆年f 月，汨 学位论文版权使用授权书 本学位论文作者完全了解盘壅盘堂有关保留、使用学位论文的规定。 特授权墨鲞盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名赫吨j 导师签名：枣茬 签字日期：驷3 年月j 胡 签字日期：2 0 哆年1 月2 日 第一章绪论 第一章绪论 1 1 引言 1 1 1 足球机器人的发展历史及其特点 训练机器人进行足球比赛的设想首先是由加拿大不列颠哥伦比亚大学的教 授a l a nm a c k w o r t h 在1 9 9 2 年的论文( o ns e e i n gr o b o t s ) ) 中提出的，旨在推动 人工智能学科的发展，为智能机器人提出一个新的具有标志性和挑战性的课 题。随后，1 9 9 2 年1 0 月在东京召开的关于“人工智能领域的巨大挑战”学术 讨论会( w o r k s h o po ng r a n dc h a l l e n g e si na r t i f i c i a li n t e l l i g e n c e ，o c t 1 9 9 2 ，t o k y o ) 上，与会的研究人员对制造和训练机器人进行足球比赛以促进相关领域研究进 行了探讨。在一些学者的积极倡导和s o n y 公司的大力支持下，成立了由国际 人工智能学会组织的国际机器人足球协会( r o b o c u p ：t h er o b o tw o r l dc u p i n s t i t u t e ) ，并于9 6 年在日本举行了次表演赛，获得了很大地成功。受 r o b o c u p 成功的启发，为了推广机器人足球比赛，韩国学者金钟焕发起了国际 机器人足球协会联合会( f i r a ：f e d e r a t i o no fi n t e r n a t i o n a l r o b o ts o c c e r a s s o c i a t i o n ) ，并于1 9 9 7 年举办了第一届机器人足球世界杯赛( f i r ar o b o t s o c c e rw o r l dc u p ) ，简称f i r ar w c 【l j 。目前，f i r ar w c 有许多种比赛项 目，我们所参加的为m i r o s o t 类型的比赛，它采用集中视觉，机器人尺寸限 制为7 5 7 5 7 5 e m ，场地大小为1 5 0 1 3 0 e m ，队员数为3 3 ，比赛用球为 高尔夫球。 在足球机器人比赛系统中，每个足球机器人是一个分布式的自主智能系统 ( a i s ：a u t o n o m o u si n t e l l i g e n ts y s t e m ) ，之所以说它是分布式的是因为构成机器 人的各个功能模块处于不同的物理空间。a i s 是一个模仿人类智能和行为的高 度自动化系统，在无人干预下，它能够在复杂多变的未知环境中自动地执行预 定任务：能通过环境的感知，决策规划，有计划、有目的地产生智能行为，以 适应环境，改变现状，从而达到预定的目标。由于自主式智能系统十分诱人的 应用前景，所以引起了许多学者的重视。其中自主式地面车辆系统 a l v ( a u t o n o m o u s l a n d v e h i c l e ) 得到了科学界的一致公认，并且也对我们构建足 球机器人系统有某种借鉴意义。a l v 是2 0 世纪8 0 年代美国国防部高级研究计 划署( d 越冲a ) 制定的“战略计划”中的主体研究课题之一【2 】。 在研究a i s 系统的过程中，人们发现以一个功能上面面俱到的、最大程度 地模仿人的a i s 产品，无论是在成本上还是在构造风险上都是不适宜的，再加 第一章绪论 上计算机网络、计算机通信和并发程序设计等技术的促进作用，多主体系统 r m a s ：m u l t i a g e n ts y s t e m ) 成为了一个新的研究热点。而足球机器人比赛系统 正是由若干个a i s 系统构成的一个多主体系统，它可以具体描述为：活动在一 个实时、存满噪声以及对抗性的复杂环境下，通过协作、配合以完成一个共同 任务的多主体系统。随着信息技术的飞速发展，多机器人的应用需求不断地增 加，多主体系统在不可测环境中的问题求解逐渐成为信息自动化领域基础研究 和应用研究的重大挑战性课题。虽然这一挑战性课题得到各国学者的重视，但 由于受到各种的限制，在基础研究和实际应用之间还存在着巨大的差距。机器 人足球正是在多机器人( 主体) 系统的理论研究和实际应用之间起桥梁的作用。 足球机器人系统是个庞大而复杂的系统。作为一个跨学科跨专业研究课 题，它涉及到无线电通信、机电一体化、人工智能等许多方面。从系统的整个 结构来看，系统分为四个子系统：小车、视觉、决策和通信子系统，而本论文 针对决策子系统做了一些研究工作。 1 1 2 决策子系统的任务 在足球机器人系统中，决策子系统的任务就是根据当前球场上的比赛形 势，经过分析，做出有规划的部署，给队员发出指令，使机器人小车能象真正 的足球运动员一样，做出各种动作，或者进攻得分或者瓦解对方进攻。 通常人们在体育比赛中以形象思维为主，对球场信息的处理通常是在模糊 概念基础上的，如：远、近、快、慢，用自然语言进行推理、决断，显 然，这种思维过程必然处在一种千变万化的动态环境之中。而足球机器人决策 子系统使用精确的数据和刻板的程序语言。如何将人的决策思维形式化、规范 化，并用计算机语言表现出来，属于知识工程的范畴，这也是机器人足球比计 算机下国际象棋更具有挑战性的要点所在，也是决策子系统的难点所在。 1 2 3 决策子系统涉及的相关学科 作为一个足球机器人比赛系统的关键组成，决策系统所要求的知识主要来 源于计算机学科中的人工智能技术。 广义地讲，人工智能是关于人工制造的智能行为的研究，而智能行为包括 知觉、推理、学习、交流和在复杂环境中的行为翻。人工智能的主要任务就是 应用和研究人工智能各种方法和技术，并用计算机语言实现它们，最后的生成 高效的程序代码，它为搭建多主体系统提供了几种十分有用的技术，其中，在 决策系统的开发过程中要用n - 1 ) 基于知识的世界模型建模方法 2 第一章绪论 自主式智能系统和多主体系统常常要在非结构化的环境中工作，而这些环 境的变化机理通常很难用数学方法来建模，但专家知识模型可以很好地解决这 类问题。 2 ) 基于推理的问题求解方法 这种方法为智能系统提供了拟人的思维工具，从而加强了处理复杂问题和 情况的能力，提高了智能水平，有助于进行问题求解和环境应变。 目前，人工智能的研究重点主要集中在专家系统、模式识别、自然语言理 解、机器人学、自动定理证明等方向上【4 】。自从八十年代以来，随着计算机网 络、计算机通信和并发程序设计技术的发展，分布式人工智能a j ： d i s t r i b u t e da r t i f i c i a l i n t e u i g e n e e ) 逐渐成为人工智能领域的另一个新的研究热点 睁j 。人们在研究人类智能行为中发现，大部分人类活动都呈现有多个人，多团 体的协作特点，“协作”是人类智能行为的主要表现形式之一，在人类社会中 普遍存在。分布式人工智能正是为了适应这种需要而兴起的，主要研究在逻辑 上或物理上分散的智能动作者如何协调其智能行为( 知识、技能和规划) 、求解 单目标或多目标问题，它为设计和建立大型复杂的智能系统或计算机协同工作 项目提供了有效途径。一般地，分布式人工智能的研究可分为两大方向【6 】：分 布式问题求解( d p s ：d i s t r i b u t e dp r o b l e ms o l v i n g ) 和多主体系统( m r s ：m u l t i a g e n ts y s t e m ) 。足球机器人系统正是一个典型的多主体系统，一个优秀的分布 式智能研究模型和平台，而它其中的决策子系统目标就是理论上研究和软件上 实现此多主体系统。 此外，自动化学科中的一些自动控制技术也将应用于此系统，它主要在机 器人小车的底层控制当中得到应用。 1 2 研究的意义 足球机器人系统作为研究多主体系统的典型课题，它的智能性主要体现在 决策系统中，足球机器人智能水平的高低主要取决于决策系统的先进性、合理 性和实时性。决策系统在整个足球机器人系统中，处于非常重要的地位，就好 比人脑对于人这个系统一样，决策系统的优劣将直接关系到比赛的结果，关系到 整个系统的成败。最为重要的是，对决策系统的深入研究有重大的理论意义和 现实应用价值。 在理论上，利用足球机器人这个优秀平台，决策子系统的开发者，可以最 大程度地把当前人工智能和智能控制领域的新方法和新理论应用于系统开发过 程中，从而检验所采用方法的有效性，这对理论研究有很明确的指导意义。决 策系统的开发过程本身就是诸如任务的描述、分解与分配，a g e n t 问的交互及 第一章绪论 通讯，一致性及协调性等多智能体系统的基本问题的求解过程。 在现实中，足球机器人的决策系统的研究成果，将带来巨大的应用价值。 例如，在军事领域，系统中的协作控制和决策技术，就可以用于无人作战平台 群的协作控制，诸如无人驾驶飞机群的编队控制及与敌方的辅助攻防对抗、海 军舰队的编队与辅助协同作战、以及未来战场上机器人部队的组成等。在制造 领域，引入智能体技术大大增加制造系统的柔性、智能性和可重构性【7 j 【“，并为 解决动态问题的复杂性和不确定性提供新的思路。此外这些研究成果还可以运 用到交通控制9 1 、软件开发、网络管理和信息处理 1 0 l 、商业管理等众多领域 当中。 综上所述，机器人足球比赛不仅成为研究多智能体系统的典型问题，而且 还可成为检验对抗双方多智能体协调策略优劣程度的标准试验平台。机器人足 球比赛将研究对象从过去计算机象棋的单智能体发展到分布式多智能体，将研 究环境从静态环境发展到动态环境，并且将非实时知识处理发展到实时处理， 有巨大的理论价值。最重要的是，这些研究成果将对相关的领域的发展有巨大 的推动作用。因此可以说，机器人足球比赛是继计算机象棋后出现的人工智能 发展的第二个里程碑【1 2 】，它将人工智能技术发展到新的境界。 1 3 本论文的研究重点 多主体系统m a s 是计算机技术、控制理论、人工智能应用等多学科交叉 融合的前沿研究热点，作为m a s 领域的典型课题，足球机器人主要涉及到以 下研究问题【1 3 】【1 4 】：机器人的机械、硬件设计；m a s 的体系结构；m a s 的知识 机构：m a s 的通信机制和协调冲突问题；a g e n t 的规划和避碰；a g e n t 感知与 学习。本文主要是以决策系统为研究方向的，而且为了简化系统的实现难度， 因此我们将有针对性地对以下议题进行深入细致的讨论： 1 m a s 的体系结构 m a s 体系结构可以定义为【l5 】：系统中a g e n t 之间的信息关系和控制关系以 及问题求解能力的分布模式，它是结构和控制的有机结合，通过对角色、行为 预测和控制关系的定义提供a g e n t 活动和交互的框架。 从控制方式的角度分析，m a s 的体系结构可分为集中式控制结构和分布式 控制结构，集中式结构比较适合紧密协调工作环境，而分布式结构比较适合松 散协调工作环境，具有较高的智能和自治力；从结构方式的角度分析，m a s 的 体系结构可分为同构体系与异构体系，同构体系中，每个a g e n t 的能力是一样 的，异构体系中每个a g e n t 的能力是不等的，任务按个体的能力进行分配；从 a g e n t 的知识粒度分析，m a s 的组织结构可分为完全自主型、半自主型和无自 4 第一章绪论 主型三种。完全自主型系统中，各a g e n t 的知识水平较高，智慧集中，相互独 立。半自主型系统中的各a g e n t 在某种程度上具有一定的决策能力，但知识粒 度有限，系统的战略战术及各a g e n t 之间的相互协调均由高层主a g e n t 负责处 理。无自主型系统中的a g e n t 只有行为，没有智慧，完全由高层a g e n t 控制。 采用何种m a s 的结构，必须视具体情况而定，环境的复杂性和不确定性是决 定组织结构的重要因素。我们的系统可以认为是具有异构的、集中控制的、半 自主式的m a s 系统。 2 障碍回避及路径规划问题 大多数的机器人均是在空间完成一定的动作，如在地面行走或在空间抓取 物体，这就涉及到二维或三维空间中的最佳运动轨迹的设计问题，即路径规 划。在类似于足球机器人小车的自主车的研究中，路径规划尤为重要。由于研 究侧重点不同、个人喜好不同，甚至对于相同的自主车空间环境都可能有不同 空间表示方法，这样导致了名目繁多的路径规划方法。例如，在结构化的道路 交通地图上，可用图论中的方法来实现规划目标；而对用网络表示【1 6 1 的障碍空 间，搜索通道则需要一系列的变换或采用其他方法，如势场法等来实现。此外 一些诸如遗传算法和神经网络【i7 】等智能算法也在机器人路径规划中的到了应 用。 3 简洁的知识表达和实时的知识推理问题 知识处理是人工智能的核心和最终目的，为了研究如何用计算机处理知 识，必须首先研究知识的表达方法，接下来才能利用计算机所能识别的知识来 进行诸如推理、分析的知识处理，因此知识表达的优劣，往往直接影响到系统 的知识处理能力和问题求解的效率。迄今为止，在人工智能领域已有许多种知 识表达方式，如谓词逻辑、命题逻辑、产生式系统、语义网络、框架、脚本等 等。在实际工作中，大多数成功的案例都采用了综合的知识表达方法，以表达 不同种类型的知识。在本课题中，我们就采用了命题逻辑和产生式系统来设计 基于规则的专家系统。文献 1 8 】也采用了类似的技术建造了类似的基于规则的 足球机器人专家系统，所不同的是知识的表达方式，它利用所谓“控制域 f c o n t r o l l a b l ez o n e ) ”的概念来提取和归结赛场信息。 从知识的角度来讲，推理指的是从已有的知识推导出蕴含着的未知知识或 发现新的知识。一般来说，大多数的推理方法都涉及到前提与结论之间的关 系，而知识推理技术实际上就是如何从给定的一组前提或假设推导出某种结 论，或在要求的某种结论的情况下，去寻找什么样的前提才能导致给定的结 论。很明显，在足球机器人的决策系统中，我们的推理决策属于前者。 综上所述，这些问题是我们构建决策系统中不可回避的问题，也是关键所 第一章绪论 在。在本论文后面几章，我们将针对性的分别对它们进行深入细致的讨论。 1 4 论文结构和主要内容 本论文的主体部分由四部份构成： 第二章：通过对足球机器人系统特点的分析，将提出系统的推理模型，并 在此基础上通过分析三种典型的自主式智能系统体系结构，力图得到本系统的 体系结构，此体系结构将对整个项目的开发具有全局性的指导意义； 第三章：在这一章将讨论路径规划技术，它的任务是解决足球机器人的底 层控制问题。在此部分，将提出满足项目要求的路径规划方法，并通过对其深 入分析，力图得到一些具体控制变量和参数的设定方法； 第四章：这一章首先将分析人类足球运动员的技术动作，以得到适合足球 机器人的基本动作集，然后把此动作集分解为便于利用所采用的路径规划技术 的元动作集，接下来的重点工作是设计几个重要基本动作： 第五章：此章讨论的问题应归属于逻辑推理的范畴，它的任务是实现具有 逻辑推理特性的高层模块。在此部分，首先将讨论能够解决类似足球机器人较 复杂的推理系统的一般方法一人工神经网络和专家系统，然后为了满足系统反 应的实时性，提出一种称之为知识映射表的推理方法，以此为基础，我们将实 现各个高层推理模块。 6 第二章系统概述 第二章系统概述 2 1 足球机器人的实现方案 2 1 1人类踢足球分析 足球机器人是对人类足球队员的模拟和仿真，因此有必要对人踢足球运动 进行认真的剖析。人踢足球是头脑和四肢相互协调的结果，就单人而言，首先 要看到球和球门或接应队员，再想怎么跑动，然后发力完成相应的动作；如果 多人踢球，则还要沟通信息，实现配合。上述的过程可以通过图2 - 1 表达。并 且可以进一步地归纳为：主动感知就是确定场上实体位姿，寻找目标，发现障 碍；思维决策则是判断事态，明确角色，规划动作；信息沟通便是通过手势， 语言，甚至眼色达成默契；而动作实现则包括跑动、踢球、拦截、射门等。 2 ，1 2 球机器人分类 图2 - 1 人类踢足球过程 文献【1 9 】根据感知系统实现方式和策略决策所在位置( 是在主机上，还是在机 器人上) ，把足球机器人系统划分为如下工作模式： 1 基于视觉的遥控足球机器人系统( v i s i o n b a s e dr e m o t eb r a i n l e s ss o c c e r r o b o ts y s t e m ) 。 2 基于视觉的有智能的足球机器人系统( v i s i o n b a s e db r a i n o n - b o a r ds o c c e r r o b o ts y s t e m ) 。 3 基于机器人的足球机器人系统( r o b o t b a s e ds o c c e rr o b o ts y s t e m ) 。 我们研究的足球机器人系统属于基于视觉的遥控足球机器人系统，或者称 为集中控制式( 集控式) 系统，文献【2 0 】讨论了类似控制结构的一个多机器人系 统。此系统中，机器人小车( 物理机器人) 的感知和决策处理在主机上完成，可 7 第二章系统概述 以将主机上的处理软件抽象为自主式智能代理( a t a ：a u t o n o m o u si n t e l l i g e n t a g e n t ) i2 1 】，它是一种工作在信息世界中的自动机，由驱动程序屏蔽物理机器人 ( p a ：p h y s i c a lr o b o t ) 。所有的决策只是针对代理而言的，而物理机器人能够接 受指令，实现运动，它仅仅是一个执行机构。大部分参加f i f a 微型机器人足 球赛的队伍都采用此结构。 2 2 足球机器人决策子系统分析 足球机器人的决策子系统的任务实际上就是如何建造一个多主体的自主式 智能代理系统。一个自主式智能系统，一般要遵循“感知一思维一行动”的基 本规律，足球机器人的决策系统在功能上主要要实现的是：思维和行动，而感 知由视觉处理子系统来实现。 2 2 1系统特点 决策系统是一个有如下i o 关系的知识性系统： 0 = ，( ，) 其中，i 是视觉输入，o 是决策的结果，即我方每个小车的左右轮速设定。可以 看出，此i ，o 关系是复杂的、非线形的和非结构化的。作为人类球员和教练 员，他们的主要通过形象思维的方式来分析比赛情况，而作为足球机器人的决 策系统必须把人类队员和教练员的思维过程形式化，以便于计算机推理判断。 决策系统的任务就是构建这个复杂的函数模型，这主要要利用人工智能领域的 相关技术，诸如：知识表示和知识推理。 2 2 2 系统模型分析 纵观整个足球机器人系统， 决策系统所能得到的信息仅仅是 由视觉系统传递来的球的位置以 及球员的位置和方向信息，而决 策系统传输给小车的信息仅为小 车的左右轮速。我们来分析一下 绿茵场上教练员的决策过程，如 图2 2 所示，假设我方向右进攻， 图士2 决策分析 当教练员看到这种场上形势，首先判断出我方应该采取进攻策略，继而看出小 车2 追球，小车1 进行接应较合理，然后各个小车采取各自的动作来完成整个 第二二章系统概述 策略。我们再仔细分析一下这个决策过程：看到图2 2 所示场上形势，教练员 首先直接看出球员2 离球近，球员1 离球远，然后就赋予球员1 、2 不同的任 务。然而不幸的是，在足球机器人决策系统中，由人们形象思维完成的这一过 程，必须转化为计算机的逻辑运算过程。为了对上述教练员的决策过程进一步 抽象，文献【2 2 提出了如下的六步推理模型：( 1 ) 输入信息预处理( 计算有关实 体速度、相对距离等) ；( 2 ) 态势分析与策略选择；( 3 ) 队形确定与角色分配；( 4 ) 目标位置确定；( 5 ) 运动轨迹规划；( 6 ) 轮速确定。根据六步推理模型，可以得到 如下推理过程：( 1 ) 态势分析；( 2 ) 队形选择；( 3 ) 角色分配：( 4 ) 动作选择；( 5 ) 动 作实现。足球机器人决策系统的体系结构就是根据此推理过程设计的。 2 3 足球机器人决策系统的体系结构 2 3 1 智能系统的体系结构技术 体系结构源于英语a r c h i t e c t u r e ，主要指建筑学上的结构框架。显然，在具 备了各种建筑材料的基础上，体系结构对建筑大厦从整体上形成什么样的风格 和具有什么功能起到关键作用。足球机器人决策系统作为一个自主式智能r 代理) 系统，如何把感知、规划、决策、行动等各种模块有机地结合起来，从而形成 具有一定特色的智能系统，是其主要任务之- - i 州。体系结构是决策系统的主心 骨，它的设计好坏直接关系到决策系统整体性能的发挥和智能水平的高低。在 设计决策系统的体系结构的过程中要考虑以下几点： 1 基本模块的选择； 2 模块之间的关系和数据控制流的确定； 3 全局性的信息资源的管理； 4 总体调度机构； 5 与外界( 足球机器人的通信模块) 通信的协议和规范。 上述几点中，模块间的关系意味着信息的加工次序和流程，它涉及到系统的 性能和效率。虽然足球机器人要遵循“感知一思维一行动”的基本规律，但各 个模块的相对关系不同，会产生许多不同结构流派。目前，构造智能系统的体 系框架主要有以下三种方法： 1 分层递阶式结构。 2 包容式结构。 3 由于网络技术的发展导致的分布式结构。 在上一章我们已经提到了，足球机器人系统是个典型的多主体系统，进 攻和防守不仅要求单个机器人的智慧，它更要注重集体的智慧力量。因此，分 9 第二章系统概述 布式的体系结构是很合适的，但是难度很大。为此，我将重点考虑前两种方 法。但是作为一个多智能体系统， 的能力是必须应改考虑的。 分层递阶式结构是把各种模块 安排成若干个层次，在不同层次 上的模块具有不同的动作性能和 操作方式。一般来说，位于高层 的模块负责复杂的判断和推理操 作，其智能化程度高：而较低层 次的模块用于与外界交互，其智 能化程度低。分层递阶式结构最 有代表性的是由s a r i d i s l 2 3 l 提出的 三级模型，他把整个结构按功能从 低到高分成三个层次：执行级、 在系统的实现过程中，任务协调和消除冲突 人员 环境和控制对象 图2 - 3 分层递阶式结构的三级模型 局管理 执行 驱动 协调级和组织管理级。如图2 - 3 所示。在此结构中，底层的执行级用于与控制 对象和环境交互( 通过传感器和行为发生器) ；最高层用于组织管理，中间层连 接上下两层，进行操作行为的协调。需要指出的是图中的三级模型仅仅是一个 概念模型，实际的物理结构可以多于或少于三级。由图可以看出，此结构有两 条数据流：一条是从低向上的外界采样信息：另一条是从上向下的命令控制信 息。文献2 4 所建造的足球机器人的决策系统就是典型的分层递阶式三级模 犁。 分层递阶式结构合乎人类由总到 分的问题逐步分解的思维方式，构造 正常作业 简单，应用范围广是它的主要特点。 传感器建立地图动作 但是它也有一些不尽人意的地方，其卜= = 一卜 中一个致命的问题就是它的反应性二= 一 差。因此，麻省理工学院的 壁障 r b r o o k s i 2 5 l 提出了包容式体系结构， 如图2 4 所示，实际上它是一种水平 图2 - 4 包容式体系结构 分片式结构，它强调了单元的独立，平行工作，缺少全局的指导和协调，虽然 在局部行动上可以显示很灵活的反应能力和鲁棒性，但对于长远的、全局性的 目标跟踪显得缺少主动性，目标性较差。而且人的经验、启发性知识难以加 入，限制了人的知识的应用。 1 0 第二章系统概述 2 3 2 决策系统的体系结构 上面分析了智能系统的两种典型的体系结构，现在的问题是，如何设计足 球机器人的决策系统的体系结构，以满足比赛要求。通过仔细分析，我认为分 层递阶式结构是合适的、可行的。由于足球机器人系统采用的是集中视觉的方 式，这样所采用的分层结构，对于决策系统来说仅仅有一条数据流，即至上而 下的命令控制信息流，这样可以在某种程度上增加系统的反应速度。如果再设 计较少的分层层数，那么它的反应性将能满足要求。为此，根据上面得到的推 理模型，我们设计了如2 5 图的分层递阶式体系结构。此体系结构有如下特 点： 视觉 信息 li 雾委i |唪牵囊 母 瘫羹 l i 动作执行l 底层运动控制算 小车 图2 - 5 足球机器人决策子系统体系结构 1 每个模块执行一个任务，体现了“分而治之”的原则。 2 模块的工作范围越来越小。高层的模块考虑全面的大范围的问题，而底 层模块往往只考虑专门范围内的局部问题，这有利于把问题转化为小范围内相 对简单的问题而得到有效地求解方法。 3 问题求解的精度越来越高。在上层，由于问题范围较大，它的结果是抽 象的、定性的；而在底层可以利用小车的运动学模型，给出定量的控制指标f 左 右轮速1 ，有一定的精度。 4 从人工智能推理方法发展到数值计算。高层模块要使用知识工程的方 第二章系统概述 法，进行逻辑推理，而底层，则明显地需要精确和高速的数值计算，即它是基 于数值计算的计算系统。 总之，为决策系统所设计的体系结构符合s a r i d i s 提出的著名原则层次 向上，智能增加，但精度降低；层次向下则相反。它可以完全满足设计要求。 1 2 第三章足球机器人路径规划 3 1 概述 第三章足球机器人路径规划 足球机器人小车属于自主式移动机器人，其中路径规划技术是此领域的核 心技术之一。路径规划的目的是使机器人或其他智能体能够按照存储在其内部 的地图信息，或根据外部环境提供的引导信号( 即通过对外部环境的实时探测所 获得的信息1 规划出一条较优的避碰路径，并能够沿着该路径在没有人工干预的 情况下，移动到预定目标点。由于具有广泛的理论研究和应用价值，因此对它 的研究j 下在成为人工智能和智能控制领域一个很重要的研究热点【2 。大量的文 献提出了各式各样的路进规划方法，下面我们将作重点讨论。路径规划技术作 为实现足球机器人基本动作的基础，在足球机器人决策系统中占有很重要的地 位，所采用的规划方法不同，那么基本动作实现方式也将不同。在本课题中， 我们将采用能满足足球机器人比赛要求的路径规划技术，力求为小车基本动作 的实现打下一坚实的基础。 控制小车在规划好的路径上移动，必须依靠小车j 下确的运动模型，因此建 立小车的运动学模型也是这一章的重点工作。 本章的目标： 1 创建小车运动学模型； 2 提出有效的路径规划方法。 3 2 足球机器人运动模型 3 2 1 坐标系定义及齐次坐标变换 要对机器人的运动和动作进行研究，首先要描述其位置和姿态f 统称位 姿1 。在工业机器人中，常常以固联在机器人末端执行器上的坐标系f 称工具坐 标系) 的原点，在基础坐标系中( 一般固联在基坐上) 的位置表示机器人的位置， 利用工具坐标系在基础坐标系下的投影来表示机器人的姿态。这需要一个3 维 矢量来表示空间内任意一点的位置，而在m i r o s o t 类足球机器人比赛中用垂 直悬挂的摄像机获取平面场地的图像，用2 维直角坐标系就可以描述机器人的 位置。为此我们定义以下几种常用的坐标系： 1 球场坐标系 用o x y 表示，它的坐标原点位于球场的左上角，x 轴正向向右，y 轴正向 向下，这主要是考虑与计算机默认坐标系一致。机器人小车在此坐标系内作平 第三章足球机器人路径规划 面运动，它的质心坐标( x ，y ) 代表它的位置，前向与o x y 坐标系的x 轴的央角 0 表示它的姿态。因此定义机器人的姿态为： p ，by8 7 2 机器人直角坐标系 表示为d ，x ，r ，它以机器人质心为坐标原点， 向，r 轴正向为x ，轴f 向逆时针转9 0 度得到的。 3 机器人极坐标系 为了计算方便，还定义了以机器人极坐标系 点，x 轴为极坐标的起始轴。 如3 - 1 图，描述了这三个坐标系的关系。 以机器人前向为盖，轴正 它以o ，x ，r 的坐标系为原 一一 - vl 、 旁、 。 ijr 、 e fj 一器ji5l 厂l 图3 1足球机器人的坐标系定义 在路径规划、运动控制及决策分析当中，要频繁地在这三个坐标系中转 换，尤其是在球场坐标系o x y 和机器人坐标系o ，x ，r 之间更是如此。下面， 我们将利用在工业机器人领域内，有广泛应用的齐次坐标变换工具来解决足球 机器人的坐标变换问题。 设在o x y 中，机器人的位姿为p 【ab 日】7 。从o x y 到0 ，x ，r 的平移 变换矩阵t 和旋转矩阵r 分别为： r 。阱玑r 。阢- c 8 0m 【0 01 j【0 0 1 j 推出两坐标系间的齐次变换矩阵：爿= t r = l c o s o s o c o 一 l 00 1 4 第二章足球机器人路径规划 3 2 2 运动学模型 一般的移动机器人都为轮式移动机器人( w m r ：w h e e l e dm o b i l er o b o t s ) ， 根据车轮数分类，可以把它们分为：2 轮车、3 轮车、4 轮车和全方位移动车。 其中，4 轮车由于机械结构和数学模型简单，因此的到了广泛的应用。文献 2 7 1 在理论上对各种类型的w m r 作了相当深入仔细的分析，它根据运动自由度 f d o m ：d e g m e o fm o b i l i t y ) 和舵性自由度( d o s ：d e 伊e eo fs t e e r i b i l i t y ) 对w m r 作t ( d o m ，d o s ) 形- 式上的分类。 在我们的足球机器人系统中，我们采用了双驱动轮、双辅助轮的四轮车结 构，它属于( 2 ，o ) 类型，即运动自由度为2 ，舵性自由度为0 。它的旋转半径范围 可从零( 原地打转) 到无限大( 直线运动) 。为了简化模型和降低难度，在理论分析 过程中，我们作了如下的假设： 1 假定小车轮子和地面没有滑动，沿直线作纯滚动运动； 2 轮子侧向没有滑动，即它受到t s i n 0 9 c o s 0 0 的非完整约束 ( n o n h o l o n o m i cr e s t r i c t i o n ) 。 如图3 2 机器人小车模型 如图3 2 所示，机器人在x o y 平面内作平面运动，为了简化分析，我们选 择轮轴中点c 为基点，这样，我们可以得到小车的运动学方程： i 。j 一：j l c o s 0 as i n 0 ( 3 1 ) l= 0 、 式中： v 为基点c 的瞬时线速度，因为速度瞬心位于轮轴线上，因此v 的方向始终 垂直于轮轴，即v 的正向方向与小车的正向标线重合； 为小车的角速度，它的正向设定如图所示； ( x ，y ) 为c 点坐标； 0 为小车正向标线与o x 轴的夹角。 第二章足球机器人路径规划 小车速度向量u 定义为： u = “笼圳1 p 叫, 1 小车运动轨迹的曲率半径为： p 一- 工”( v ，叫) 其中： l 为1 2 机器人左右轮距。 v ，v ，分别为小车的左右轮速，方向始终垂直轮轴线，由左右电机给定 p ，的方向相同，都定义为逆时针为正。 3 3 路径规划综述 ( 3 2 ) ( 3 - 3 ) 路径规戈t j ( p a t hp l a n n i n g ) 为自主式智能系统的空间规划技术，它是自主式智 能系统的核心技术之一。空间规划原来是计算几何学的传统研究课题，由于智 能机器人研究的需要，7 0 年代中期以后，这个问题在人工智能领域越来越受到 重视。因为无论是离线编程的装配机器人，还是能自动躲避障碍的移动机器 人，都需要空问规划技术。此外，空间规划中所涉及的几何物体表示以及物体 的空间关系等也是人工智能领域推理和判断所关注的问题。 人工智能中的路径规划，有时也称为无碰路径规划( c o l l i s i o n f r e ep a t h p l a n n i n g ) ，主要指的是机器人的运动规戈r j ( m o t i o np l a n n i n g ) ，即给定机器人的工 作环境以及其起始和目标的位姿，为机器人寻找一条从起点到目标点，且不与 任何障碍相碰的路径。有的文献中也把此问题称为寻找路径( f i n d p a t h ) ，或避碰 ( c o l l i s i o na v o i d a n c e ) f n 题。路径规划包括全局路径规划和局部路径规划，有的 文献分别称之为基于模型的路径规划细o d e l b a s e dp a t h p l a n n i n g ) 和基于传感器的 路径规划( s e n s o r b a s e dp a t h 。p l a n n i n g ) i ”】。前者是根据先验环境模型( 地图) 来规划 路径，它涉及的基本问题是世界模型的表示和搜索策略。世界模型的表示主要 有轮廓空间法，自由空间法，网格表示法，等高线法等：搜索策略常用的有a 算法，动态规划等。局部路径规划技术是利用环境传感器f 如超声波传感器、激 光测距仪、视觉传感器1 提供的机器人周围的局部环境信息产生的下一刻机器人 位姿信息的技术，目前主要有人工势场法、道路查找法等。有些规划技术，不 能绝对地归为全局的或者局部的，在具体情况下它们可能既有全局的特点又有 局部的特性。全局路径规划不适合用于解决在复杂和动态变化的环境中的机器 人导航问题，因为未知的障碍物有可能出现在规划好的路径上。足球机器人所 处的环境是一个典型的动态环境，但考虑到获得的视觉信息的全局性及一些诸 如球门、边界等场地特性的非动态性，因此全局和局部路径规划技术都将得到 1 6 第三章足球机器人路径规划 应用。下面我将简单介绍一下几种典型的路径规划技术。 3 3 1 全局路径规划技术 一一种基础的全局路径规划技术 之所以称之为基础，是因为很多方法都是在其基础上作得改进，它为人们 提供了一种路径规划的思路。此方法顺序上可分为三步： 1 规划空间的表达 在规划过程中，可能出现多种规划结果，这所有可能的规划结果的全体即 为规划空削，如图3 3 所示。考虑机器人所在的物理空问s ，障碍物的有限集 o = d