（机械制造及其自动化专业论文）基于聚类算法的群体机器人聚集运动协调性研究.pdf

硕士学 论文 摘要 群体机器人协作运动系统是群体机器人研究领域的一个重要课题，本论文 在查阅大量文献资料的基础上对群体机器人协作系统研究内容和研究现状进行 了分析总结。 以基于组合式框架聚类算法、意愿强度磋商策略、k m e a n s 聚类算法的智 能理论为基础，深入探讨了群体机器人协作系统的基本原理，建立群体机器人 聚集队形路径规划的数学模型、运动控制模型。采用磋商和意愿强度策略，建 立合作式的宏观调控机制，解决群体机器人协作系统的冲突问题。建立复合体 体系结构，在此结构下机器人将产生四种控制行为函数，以避免机器人在运动 过程中的碰撞，使机器人有效躲避障碍物并保持队形。 以p i c 单片机为主控制芯片、红外对管传感器为系统输入，直流电机p w m 信号为系统输出，开发个体机器人硬件系统，并以智能理论为基础，以面向对 象的可视化编程软件为、f j 台，编写机器人硬件控制程序。 以k m e a n s 聚类算法为基础进行群体机器聚集队形仿真实验，基于已建立 的群体机器人实验系统为平台，进行物理实验，验证群体机器人协作系统的可 靠与稳定性，证明该方法运用到群体机器人协作系统平台具有良好的效果。 关键词：组合框架聚类算法；k m e a n s 聚类算法；磋商和意愿强度规则；群体 机器人系统：聚集队形 a s t r a c t g r o u pr o b o tc o o p e r a t i v es y s t e mi s a l l i m p o r t a n tt o p i ci nt h er o b o ts y s t e m r e s e a r c h i nt hi sp a p e r ，a l le x t e n s i v ei i t e r a t u r eo ng r o u pb a s e do nt h ei n f o r m a t i o n c o n t e n to fr o b o tc o o p e r a t i o ns y s t e ma n dt h ec u r r e n tr e s e a r c hw e r ea n a l v z e da n d s u m m a r i z e d b a s e do nt h ec o m b i n a t i o nf r a m e c l u s t e r i n ga l g o r i t h m ， i n t e n dt o s t r e n g t h c o n s u l t a t i o n ss t r a t e g y ，k - m e a n sc i u s t e r i n ga l g o r i t h mb a s e do nt h et h e o r y o ft h e i n t e l l i g e n c e ，t h eg r o u pd i s c u s s e dt h eb a s i cp r i n c i p l eo fr o b o tc o o p e r a t i o ns y s t e m ， e s t a b l i s hr o b o tp a t hp l a n n i n gg r o u pg a t h e r e df o r m a t i o no ft h em a t h e m a t i c a lm o d e l t h em o t i o nc o n t r o lm o d e l t h ec o n s u l t a t i o na n di n t e n dt o s t r e n g t hs t r a t e g ya n d e s t a b l i s h c o - o p e r a t i v e m a c r o c o n t r o lm e c h a n i s m ， s o l v e g r o u pc o n f l i c tr o b o t c o o p e r a t i o ns y s t e m b u i l dc o m p l e xs y s t e ms t r u c t u r e ，i nt h i ss t r u c t u r eo fr o b o t sw i l l b e f b u rc o n t r o lb e h a v i o rf b n c t i o n ，i no r d e rt oa v o i dt h er o b o ti n t h ep r o c e s so f c o l l i s i o ni ns p o r t s ，m a k er o b o t se f f b c t i v ee v a d e so b s t a c i e sa n d k e e pt h ef o r m a t i o n u s i n gp i cm c u b a s e d ， i n f r a r e ds e n s o r sf o r t h es y s t e mi n p u t ，d cm o t o r p w m c o n t r o l s i g n a l f b r t h e s y s t e mo u t p u t ， t h e d e v e l o p m e n to fg r o u pr o b o t a r c h i t e c t u r e ，a n dw i t hi n t e l l i g e n c et h e o r ya st h ef o u n d a t i o n ，t h e o b i e c t o r i e n t e d v i s u a l p r o g r a m m i n gs o f t w a r ef o rt h ep l a t f o r m ，a n dw r i t er o b o th a r d w a r ec o n t r o l p r o c e d u r e s t ok 。m e a n sc l u s t e r i n ga l g o r i t h mb a s e do ng r o u pg a t h e r e df o rt h em a c h i n et o f o r m a t i o ns i m u l a t i o ne x p e r i m e n t ， b a s e do nt h ee s t a b l i s h e ds y s t e mf o re x p e r i m e n t a l g r o u pr o b o tp l a t f b r m ，p h y s i c a le x p e r j m e n t ss h o wt h a tt h er o b o tc o o p e r a t i o ng r o u p s y s t e mr e l i a b l ea n ds t a b i l i t y ，a n dp r o v e st h a tt h em e t h o di sa p p l i e dt ot h er o b o t c o o p e r a t i o ns y s t e mp l a t f 6 r mg r o u ph a sg o o de f 琵c t k e y w o r d s ：c o m b i n a t i o nf r a m ec l u s t e r i n g c o n s u l t a t i o na n di n t e n dt os t r e n g t hr u l e s ； a l g o r i t h m ；k m e a n sc l u s t e r i n ga l g o r i t h m s ； g r o u pr o b o ts y s t e m ；g a t h e r e df o r m a t i o n 硕上学化论文 插图索引 图1 1c o l l e c t i v er o b o t i c s 系统4 图1 2t h en e r dh e r d 系统4 图1 3 自重构机器人系统4 图1 4 协作机器人系统5 图1 5m i r o s o t 5 i 訇1 6r o b o c u p 5 图2 1 输出h 枣k 个簇流程图1 4 图2 2 输出较优k 个初始质心流程图15 图2 3d s c a 算法过程1 6 图3 1 传统结构2 5 图3 2 包容式结构2 6 图3 3 反应式控制结构2 6 图3 4 复合基体结构2 7 图3 5 单机器人系统图2 8 图3 6 系统功能框图2 8 图3 7a t 8 9 s 5 2 型单片机2 9 图3 87 8 0 5 电参数3l 图3 9 电源电路3 1 图3 1oh 桥驱动模型3 2 图3 1 ll 2 9 8 实物图3 2 图3 1 2 电机驱动电路3 3 图3 13p w m 输出波形3 4 图3 1 4 传感器电路图3 5 图4 1 移动机器人运动模型3 8 图4 2 聚类运动的仿真过程4 9 图5 1 群体机器人习作实验系统5 0 图5 2 个体机器人5 2 图5 3 聚集队形控制算法流程框图5 4 图5 4 群体机器人横一队形排列5 9 图5 5 群体机器人三角形队形排列6 0 幕- r - 聚类算法的群体机器人聚审运动协调他研究 插表索引 表3 1 真值表3 4 表4 1 机器人行为控制参数产生函数中的参数4 8 i v 硕士学 _ 论文 第一章绪论 机器人作为人类2 0 世纪最伟大的发明之一，在短短的4 0 年内发生了同新月 异的变化。随着计算机技术、超大规模集成电路、控制理论、人工智能理论、传 感器技术等的不断发展，由许多学科交叉而形成的机器人学研究也进入了一个崭 新的阶端。近几年机器人己成为高技术领域内具有代表性的战略目标。从可编 程的、示教再现型的工业机器人到具有一定传感能力、一定适应能力的机器人， 再到配备多种先进传感器，具有较强的适应能力的智能机器人，机器人学的研究 工作经历了一个从简单到复杂，从功能单一到功能多样，从工业制造领域到军事 勘察、核工业、航空航天、服务业、医疗器械、基因工程等诸多领域的过程。机 器人技术的出现和发展，不但使传统的工业生产面貌发生根本性变化，而且将对 人类的社会产生深远的影响。可以预见，在不久的将来，机器人技术在各个领域 的应用将会更加广泛和深入。然而就目前的机器人技术水平而言，单机器人在信 息的获取、处理及控制能力等方面都是有限的，对于复杂的工作任务及多变的工 作环境，单机器人的能力更湿不足。于是人们考虑由多个机器人组成的群体系统 通过协调、协作来完成单机器人无法或难以完成的工作【2 1 。而各种机器人系统在 实际工作中的广泛应用又为机器入学提出了新的要求和新的研究课题。群体机器 人系统的研究就是在这些新的应用需求驱动下提出的【3 1 ，并且随着机器人学的不 断发展而逐渐成为机器人学研究的一个重要分支。 1 1 群体机器人研究背景 随着机器人应用领域的不断拓展、机器人工作环境愈加复杂，机器人任务随 之加重，单个机器人的能力难以完成复杂的任务。因此，在2 0 世纪7 0 年代兴起 了群体机器人系统的研究，并取得了许多重要的成果。近年来，随着群体机器人 系统规模的不断增大，为了实现个体之间的协作，许多系统采用了复杂通信机制 和任务指派机制，要求机器人个体必须具备复杂的通信和决策能力，以达到在群 体中进行信息交流和行为协调的目的，这就使得机器人个体变得越米越复杂，整 个系统的控制复杂度及机器人之间的通信量成指数倍地增加。并且在未知复杂环 境中所需要的环境决策信息通常不易直接获得。而传统群体机器人系统的理论和 方法很难解决这些问题。 在众多生物群体中，如编队迁徙的鸟群、结对巡游的鱼群、协同工作的蚁群、 聚集而生的细菌菌落等，不存在某个协调者来协调大量自主个体，但整个系统却 呈现协调有序的状态。群体机器人学受社会性昆虫及群居动物群体行为的启发， 基丁聚类茆注的群似：机器人聚震运动协调r ：研冗 主要研究如何使大量相对简单的机器人通过局部交互，涌现出智能群体智能行为。 所谓群体智能( s w a r mi n t e l l i g e n c e ) 指的是众多简单智能个体组成群体【引，通过 相互间的简单合作表现出智能行为的特征。在自然界中动物昆虫常以集体的力量 进行觅食生存，单个个体所表现的行为是缺乏智能的，但由个体组成的群体则表 现出了一种有效的复杂智能行为。科学家将这一理论应用到群体机器人的实践与 研究中，取得了显著的成效。多个简单的机器人组合在一起，组成群体机器人， 可以完成单个机器人无法达到的任务，提高工作效率。群体机器人系统比单机器 人系统具有更强的优越性，主要表现在以下几个方面1 5 j ： ( 1 ) 相互协调的n 个机器人系统的能力可以远大于一个单机器人系统的n 倍，群体机器人系统还可以实现单机器人系统无法实现的复杂任务； ( 2 ) 设计和制造多个简单机器人比单个复杂机器人更容易、成本更低； ( 3 ) 使用群体机器人系统可以大大节约时间，提高效率； ( 4 ) 群体机器人系统的平行性和冗余性可以提高系统的柔性和鲁棒性等。 此外群体机器人系统具有空间分布、功能分布、时间分布等特点，利用这些 特点可以达到以下目； ( 1 ) 通过群体机器人系统内在的特性提高完成任务的效率； ( 2 ) 通过共享资源( 信息、知识等) 弥补单机器人能力的不足，扩大完成 任务的能力范围； ( 3 ) 利用系统内机器人资源的冗余性提高完成任务的可能性，增加系统的 性能。 因此群体机器人系统的研究是机器人技术发展的必然趋势，必将对机器人技 术的发展带来划时代的变化。 1 2 国内外发展现状 群体机器人技术是机器人技术的一个崭新的发展方向，群体机器人系统是特 殊的多机器人系统，由许多无差别的自治机器人组成。经过二十几年的发展，群 体机器人系统的研究已在理论和实践方面取得较大的进展，并建立了群体机器人 仿真系统和实验系统。目前，国内关于群体机器人系统的研究刚刚起步，而国外 的研究则比较活跃，欧洲、日本、美国等地的研究机构在理论上和实践上已经取 得了较大的进展。 欧盟专门建立了一个进行多机器人系统研究的m a r t h a 课题“用于搬运的 多自主机器人系统( m u l t i p l ea u t o n o m o u sr o b o t ss y s t e mf ot r a n s p o r ta n dh a n d i n g a p p l i c a t j o n ) 【6 1 。 日本群体机器人系统的著名研究有a c t r e s s 系统和c e b o t 系统。a c t r e s s 倾j ：7 ：何论文 是由日本h a s a m a 等人提出的通过设计底层的通讯结构而把机器人、周边设备和 计算机等连接起来的自治多机器人智能系统，这个系统的主要特点是系统的单个 动作和合作动作的并存【7 1 。c e b o t 系统中的每个机器人可以自主的运动，没有全 局的世界模型，整个系统没有集中控制，可以根据任务和环境动态重构、可以具 有学习和适应的群体智能，具有分布式的体系结构。 瑞士联邦工学院的群体智能系统研究小组开发了群体智能机器人检测系统， 可用执行汽轮机喷漆涡轮叶片的检测任务。对于搜索遍历、导航定位、路径规划、 环境监测类型的任务，十分适合群体机器人系统来完成。 美国学者k j i n 和g b e n i 等研究了s w a r m 系统。s w a r m 系统是由大量自 治机器人组成的分布式系统，其主要特点是机器人本身被认为无智能，他们在组 成系统后，将标新出群体的智能。 相对于国外的群体机器人研究，我国起步较晚，目前已逐渐引起人们的重视， 上海交通大学，中国科学院，哈尔滨工业大学机器人研究所，东北大学等已先后 开发出各种形式的群体机器人系统。总体上说，国内外对群体机器人的研究已取 得了令人瞩目的进展，且所研究的群体机器人都具有如下系统特征【8 】： ( 1 ) 系统包含大量个体，规模应至少维持在1 0 2 0 个个体的水平； ( 2 ) 没有中心协调机制； ( 3 ) 个体种类较少，而每个种类中个体的数量较多； ( 4 ) 机器人个体的行为比较简单、能力有限、需要大量机器人的合作才能 完成任务； ( 5 ) 个体机器人只有局部感知与通信能力，以保证机器人间分布式的协调； 1 3 典型的群体机器人系统 随着群体机器人系统研究的深入d a l l i a n c e ，m a r t h a ，c e b o t ，s w a r m ， g o f e r ，a c t r e s s ，m r c a s 等实验仿真系统逐步建立起来，下面介绍几类有代表 性的群体机器人系统。 1 3 1 群体智能机器人系统 群体智能机器人系统是由许多无差别的自治机器人组成的分布式系统，它主 要研究如何使能力有限的个体机器人通过交互产生群体智能。在自然界的蚂蚁、 蜜蜂等昆虫群体中，个体的能力有限，但从他们的交互中却呈现出了智能行为。 群体智能机器人系统中比较有代表性的例子是加拿大的a l b e r t a 大学开发的 c o l l e c t i v er o b o t i c s 系统和美国u s c 大学开发的t h en e r dh e r d 系统。如图1 1 、 1 2 所示，该系统将许多简单的机器人组织成团队来完成出单个个体不能完成的 工作。 基于聚类算法的群体机器人聚集运动协调性研究 图1 1c o l l e c t i v er o b o t i c s 系统 图1 2t h en e r dh e r d 系统 1 3 2 自重构机器人系统 自重构机器人系统以一些具有不同功能的标准模块为组建，根据目标任务的 需要，对这些模块进行相应的组合，进而形成具有不同功能的系统。如图1 3 所 示。日本n a g o y a 大学的t f u k u d a 教授领导的研究小组在生物细胞结构的启发下 研究的c e b o t ( c e l l u l a rr o b o ts y s t e m ) 系统就是一个典型的示例【9 】。 图1 3 自重构机器人系统 1 3 3 协作机器人系统 协作机器人系统是由多个具有一定智能的自治机器人组成，机器人之间通过 通信实现相互间的协作以完成复杂任务10 1 。如图1 4 所示。美国o a kr i d g e 国家 实验室的l y n n e e p a r k e r 及其研究小组建立了协作机器人系统实验平台c e s a r 4 硕士学位论文 n o m a d s 是写作机器人系统典型实例之一。 图1 4 协作机器人系统 1 3 4 足球机器人系统 前述的几类机器人系统中，机器人之间的关系是合作的、互助的。而在机器 人足球赛中，不同球队的机器人之间的关系是对抗的、竞争的；同队的机器人之 间是合作的、互助的】。当今主要的足球机器人比赛有两个分支，一个是韩国 j o n g h w a nk i m 教授发起并每年举行一次的微型机器人足球赛m i r o s o t 。二是日本 的机器人足球锦标赛r o b o c u p 。如图1 5 、1 6 所示。 图1 5 m i r o s o t 图1 6 r o b o c u p 墟丁聚类算；主的群体机器人聚囊运动协调件研究 1 4 群体机器人系统主要研究内容 群体机器人系统的主要研究内容为：群体机器人系统的通信，群体机器人系 统的协作与控制，群体机器人系统冲突问题的解决。 根据系统中机器入功能结构的不同，可将群体机器人系统分为同构系统和异 构系统。同构系统就是系统中每个机器人的结构相同、功能相同；异构系统中每 个机器人的结构和功能不尽相同。对于同构群体机器人系统研究的主要问题是设 计正确的控制方案和通信机制，使之能正确完成给定的任务；而对于异构群体机 器人系统的研究主要是解决如何在它们之间进行有意识的合作问题，另外还有动 作选择问题、通信冲突问题的解决。不论是同构系统还是异构系统的研究对群体 机器人系统的研究都起着重要作用，下面以同构系统为主来讨论群体机器人的研 究。 1 4 1 群体机器人个体间的交互与通信 群体机器人个体间存在着交互，通信是个体交互的途径，而个体交互主要有 三种方式： ( 1 ) 通过环境实现交互。以环境作为交互媒介，机器人之间没有明确的通 信。机器人随着在执行任务的过程中改变环境，进而帮助其他机器人完成任务。 ( 2 ) 通过感知实现交互。在传感器的感知范围内，机器人可以相互感知对 方的存在，这利，感知是局部的交互，而不是明确的通信。这需要机器人具有一定 的环境识别能力。同时，由于机器人个体都具有自己的传感器，群体机器人系统 存在大量传感器信息。相关的信息融合是需要研究的课题。 ( 3 ) 通过明确的通信实现交互。通信是群体机器人动态运行的关键问题， 有研究表明通信方式更有利于提高群体机器人系统的运行效率。群体机器人的通 信可以是直接型通信或广播型通信，相关通信方式、通信协议以网络拓扑结构尚 在研究之中。 1 4 2 群体机器人系统的协作与控制 群体机器人系统通过协调个体动作以实现群体功能，对群体机器人系统协调 性的研究分为个体协作行为和群体协作行为两个层次。前者是后者实现的基础， 后者是前者的集成。因为群体机器人不存在全局的协作控制，群体协作行为表现 为群机器人系统的自组织。每个机器人个体都有自己的局部协作控制系统，因此 必须具备在各自的局部协作系统框架内定位相邻个体的能力，个体机器人对相邻 个体的快速准确定位是十分重要的。 机器人个体行为主要包括机器人个体对环境的感知、学习、响应以及自适应 动作的协调。机器人个体控制系统是实现个体行为的基础，机器人个体控制系统 6 埘! 十孑： j z 沦文 要求使个体表现出较强的协作性和自主性。自主性是指机器人具有一定的自主能 力、能够感知环境的变化并且能作用于环境。系统的协调行为在很大程度上依赖 于如何处理机器人的自主和协作之间的关系，机器人群体行为是机器人个体行为 的复杂合成。典型的群体行为研究有聚集行为、分散行为和编队行为等。根据机 器人群体结构分布的不同，相应的控制结构也不同，可分为集中式和分布式两种。 集中式控制由一个机器人或者p c 机对任务进行协调规划并集中调度；分散式控 制中任务分配通过机器人之间的交互来实现的，每个机器人基于自己的传感器信 息与内部状态来规划各自的行为，并通过协商等手段消解冲突。为研究机器人群 体的协作机制，以提高群体的协作能力，目前多采用下述控制机制，包括： ( 1 ) 基于信息资源库的共享； ( 2 ) 基于传感器信息共享的控制：依靠通信装置，每个机器人上的传感器不再 是私有的，而是其他机器人通过通信共享的： ( 3 ) 基于资源竞争规则的调度机制：资源包括作业空间、作业顺序、作业工具 等，该控制策略最基本的目标是解决死锁问题； ( 4 ) 基于任务与能量最佳匹配原则的动态组成、重构控制； ( 5 ) 并行规划算法。 1 4 3 群体机器人系统冲突问题的解决 在群体机器人系统中还有一个很重要的问题是系统巾冲突问题的解决。在群 体机器人系统中，冲突的形式是多种多样的。主要有任务冲突、路径冲突和空间 冲突等。群体机器人系统中的冲突很容易造成系统的混乱，严重影响了系统的总 体性能。解决冲突除了要有合理的控制结构和通信方式外，也需要相应的解决策 略。在群体机器人系统中，每个机器人都把其他机器人当作障碍物来处理，并通 过传感器探测障碍物的有无。同时机器人也根据定期接收到的信息来处理传感器 的不确定性，并区分机器人障碍物和非机器人障碍物，由此来选择不同的处理方 法。群体机器人系统冲突问题的解决办法有很多，最直接的方法是采用集中控制 器来决定所有机器人的无冲突路径，但是这种方法在实用性方面具有一定的缺陷。 另一种方法是主从控制法，在冲突的机器人中有一个作为主控，指挥别的机器 人以解决冲突问题。对于群体机器人系统的研究除了上述几个主要的方面外还有 群体机器人系统的学习问题、系统的组织结构问题和环境的观察问题等。 1 5 本文主要研究内容 群体机器人的协作是指多个机器人在完成一些集体活动时相互合作的性质。 群体机器人的协作主要包括两个方面的内容：机器人之间的“合作( c o o p r e a t i o n ) 和机器人之间的协调( c o o r d i n a t i o n ) 【12 1 。机器人的合作解决的主要问题是 基丁聚类算法的群体机器人聚集运动胁凋r ：研冗 如何组织多个机器人共同完成任务，是高层的组织与决策机制问题；机器人的协 调解决的主要问题是如何保持或实现群体机器人之间在执行任务的过程中动作的 协调一致，是机器人之间合作关系确定以后具体的动作控制问题。 本课题在大范围环境下，研究多个智能体机器人构成的群体如何实现协调与 合作，如何避障并解决冲突问题，并建立群体机器人协作实验系统等。本文具体 的研究内容如下： ( 1 ) 群体机器人的体系结构。群体机器人的体系结构也就是群体机器人系统 的社会组织形式，它的选取决定了机器人之间的通信和控制模式，影响到整个系 统的性能。这是群体机器人的协调控制系统的关键性核心技术问题。 ( 2 ) 群体机器人避碰与聚集路径规划。避碰和路径规划问题是机器人在执行 任务时所必须具备的核心能力之一。单机器人作为有自主行为能力的智能体，在 执行任务过程中，除了要与团队成员进行协作外，还要完成自主规划的任务。在 本课题所研究的案例中，单机器人的自主行为之一是基于红外对管传感器的避碰， 包括针对静态障碍物和针对动态障碍物的碰壁行为。在单个机器人避碰的基础上， 还包括机器人之间的避碰，机器人彼此还共享所探测的信息，例如前方障碍物的 位置和机器人本身的位置信息。这样，每个机器人就能更加安全的进行避障和避 碰。在无碰撞前提下，机器人需要排除障碍物的干扰，规划出一条优化的作业路 径。 ( 3 ) 群体机器人宏观机制调控。群体机器人在执行任务的过程中，各个机器 人检测到的信息集合中有相同或相近的信息元素产生交集，就有可能会产生两个 智能机器人向同一目标点运动的情况，即出现冲突。解决此类问题能够减小群体 机器人之间的冲突，提高完成任务效率。 1 6 本文主要研究方法 在群体机器人体系结构的建立上，将系统体系结构划分为任务规划层、行为 控制层、传感模块和执行模块，建立了一种复合体分层体系结构。 在通信机制研究中，采用基于k m e a n s 的能量平衡消耗分簇算法，减小群体 机器人传感网络的亚工作状态，减少信息重构次数，提高机器人之间的通信效率。 在群体机器人聚集任务协调避碰研究中，采用意愿强度策略解决机器人之间 的协调、避碰。该策略使群体机器人之间进行意愿强度的对抗，从而使意愿强度 较强的一方沿原轨迹运动，而较弱一方做出相应的让步。 在群体机器人聚集运动路径规划研究中，在离散时间设定下，提出一种新的 k m e a n s 聚类算法框架即聚类组合式框架算法，该框架下的聚类算法在运动规划 和计算上更加简单方便，可以用来研究更多种类的智能体运动，同时可以设计智 愤f ：1 市论文 能体控制规律来达成聚集运动。 在群体机器人宏观机制调控研究中，采用磋商策略，机器人在其行为决策子 集合的基础上与其他机器人进行磋商，以实现相互间的协调并解决冲突问题。 1 7 本文组织结构 论文共分六章，按照如下结构进行组织： 第一章绪论部分，介绍了群体机器人的国内外研究现状，研究方法、本文的 研究内容以及论文的组织结构。 第二章智能理论部分，介绍本文中所应用的群体机器人智能理论，对智能理 论进行详细的分析，并将该理论应用于群体机器人通信、聚集队形排列、避碰等 当中。 第三章介绍群体体系结构部分，介绍体机器人的体系结构、选择适用于本实 验的群体机器人体系结构，并设计个体机器人的行为控制层、传感模块和执行模 块。 第四章群体机器人路径规划部分，解决群体机器人聚集队形的路径规划问题， 冲突问题、信息冲突问题。通过仿真实验验证聚集队形控制策略的可行性。 第五章实体实验部分，运用群体机器人智能理论实现机器人的聚集队形控制， 分析在实验中所遇到的问题，提出解决方法。并将实体实验与仿真实验做出对比。 第六章总结与展望部分，对全文进行总结，展望群体机器人未来发展方向， 以及在未来的研究中需做出的努力。 1 8 本章小结 本章介绍了群体机器人的研究背景、国内外发展现状、典型群体机器人系统、 机器人系统的主要研究内容等，并对本文的研究内容及组织结构框架做出简要概 述。 9 琏丁聚类算i 上的群体机器人聚集运动协调忡研究 2 1 引言 第二章群体机器人智能理论 群体机器人在执行任务过程当中，要应用一系列的智能理论作为基础，智能 理论是群体机器人协作系统的基础与灵魂。本文主要运用k m e a n s 聚类算法、组 合式框架聚类算法、意愿强度与磋商策略等。k m e a n s 无线传感网络动态调度分 簇算法实现群体机器人之间的通信，组合式框架聚类算法规划个体机器人运动路 径，意愿强度策略解决群体机器人之间的冲突问题，磋商策略实现群体机器人之 间的运动协调性。 2 2 聚类算法的定义 聚类作为一种典型的数据挖掘方法，一直以来都是人工智能领域的一个研究 热点，被广泛地应用于人脸像识别，股票分析预测、搜索引擎、生物信息学等重 要的领域。数据挖掘( d a t am i n g i n g ，d m ) 是指从大型数据库中提取人们感兴趣的 知识，通常这些知识是隐含的，且包含有潜在应用的价值。更准确的说，数据挖 掘就是从数据中抽取模式、关联、变化、异常及有意义的结构【l3 1 ，数据挖掘的价 值在于利用该技术改善初始模型， 聚类是将样本分配到不同类别的过程。一般的，在聚类过程中，同一类别中 的样本往往具有较大相似性，而不同类别的样本则具有较大的相异性。聚类的目 标就是在一种特定的相似度基础上对数据进行划分。聚类与分类的不同在于：分 类作为一种监督学习方法，要求必须事先明确知道到各个类别的信息，并且断言 所有待分类项都有一个类别与之对应。但是很多时候上述条件得不到满足，尤其 是在处理海量数据的时候，如果通过预处理使得数据满足分类算法的要求，则代 价非常大，这个时候可以考虑使用聚类算法。 聚类算法是一种非监督环境下的机器人学习算法，其实质就是对人们事先不 了解的数据进行分组，使得同一组内的数据尽可能相似而不同组内的数据尽可能 不同，其目的是揭示数据分布的真实情况。目前的聚类算法大致上要被分为五类 【1 4 】：层次方法，自组织映射，基于密度的方法，基于网格的方法和基于模型的方 法。其中具有代表性的划分方法为k m e a n s 聚类算法。 2 2 1 层次聚类算法 层次方法对给出的数据集合进行层级分级，叫做树聚类算法。它使用数据的 连接规则，通过一种层次架构方式，反复将数据进行分裂或聚合，以形成一个层 坝十i 节论义 次序列的聚类的问题解。根据分解而形成的过程，层次聚类则可以分为凝聚和分 裂的。凝聚的方法也叫做自底向上方法，首先将每一个对象作为单独的一个组， 接着相继地合并相近的对象和组，直到所有的组合都合并为一个，或者达到了一 个中止条件。分裂的方法也叫做自顶向下的方法，首先将所有的对象都置于一个 簇中。在迭代的每一个步骤中，一个簇被分裂为更小的簇，一直到最终每一一个对 象在单独的一个簇中，或达到了一个中止条件。一种纯粹的层次聚类方法的缺点 主要在于一旦合并或者是分裂执行，则将不能修正。也就是说，如果某个合并或 者是分裂效果在后来证明是不好的选择，该方法无法退回或是更正。 2 2 2 自组织映射 自组织映射( s e l f o r g a n i z i n gm p s ，s o m s ) 是在k m e a n s 聚类算法基础上发展 起来的一种非监督神经网络学习算法，由位于规则网格( 通常是1 维或2 维) 上 的神经元组成。神经元通过表示网络结构的近邻关系与邻近神经元连接。s o m s 聚类克服了k m e a n s 聚类的一些缺点。它应用类间的全局关系，能提供大数据集 内相似关系的综合分析，便于研究数据变量值的分布及发现类结构。而且，它具 有更稳健更准确的特点，对噪声稳定，一般不依赖于数据分布的形状阵。s o m s 算法的目标是：找到描述输入数据集的原型向量( 又称权重向量、模型向量等) ， 同时将高维输入空间连续映射到低维网格上。对应于s o m s 每一个神经元有一个 相关的原型向量，如同k m e a n s 聚类，s o m s 依据某利，距离测量确定各输入矢量 的匹配节点，并由输入矢量调整匹配节点及其临域节点的权重，这与k m e a n s 聚 类不同。经过反复学习，节点原型矢量以有序的方式描述输入数据的概率分布。 2 2 3 基于密度聚类算法 基于密度的聚类方法是将数据对象之间的距离与某一给定范围内数据对象 的个数这两个参数相互结合，得出“密度”的概念，然后按照密度的稠密程度来 判定数据对象的聚集情况。即将簇看作是数据空间中被低密度区域分割开的稠密 数据区域。它能从含有噪声的空间数据库中发现任意形状的聚类，但需要直接面 对整个样本集进行操作，测试每个对象是否是核心对象，并对每个核心对象搜索 其直接密度可达到的对象。而由于密度连通关系的传递性，往往使得绝大多数的 样本点聚集到非常少的几个类簇中( 通常是一类) 。 2 2 4 基于网格的聚类算法 基于网格的聚类算法使用了一种多分辨率的网格的数据结构，把对象的空间 量化为有限数目的单元，进而彤成了一个网格结构。这种方法的优点是处理速度 很快。但是在构建父单元的时候则往往没有考虑到子单元及其相邻的单元之间的 关系，从而降低了聚类结果的质量及其精确性。 琏了：聚类算法的群作机器人聚囊运动协阔。陀研_ 冗 2 2 5 基于模型的聚类算法 基于模型的聚类算法为每个簇假定一个模型，寻找数据对象与给定模型之间 的最佳拟合。基于模型的算法可能通过构建反映数据的对象空间分布的密度函数 来定位聚类，或者基于标准的统计数字来自动决定聚类的数目，从而产生健壮的 聚类方法。典型的代表有e m 算法，概念聚类以及神经网络。e m 算法比较易于 实现且算法简单，但是不能达到全局最优，概念聚类在机器学习中有着广泛的应 用，但是对于大型数据集聚类没有良好的伸缩性。 2 3k m e a n s 聚类算法 k m e a n s ( k 均值方法) 是一种基于质心的聚类方法，这里的质心是指一个簇 的均值，k m e a n s 聚类算法根据聚类中心的均值进行聚类划分，输入信息为聚类 个数k 以及包含n 个数据对象的数据，输出为满足方差最小标准的k 个聚类。首 先从n 个数据对象中任意选择k 个对象作为初始聚类中心，而对于所剩下的其他 对象，则根据他们与这些聚类中心的相似度( 距离) ，分别将他们分配给与其最相 似的( 聚类中心所代表的) 聚类。然后，再计算每个所获新聚类的聚类中心( 该 聚类中所有对象的均值) ，不断重复这一过程直到标准测度函数开始收敛为止。 一般采用均方差作为标准测度函数，具体定义如下： j | 2 e = i p 一圳 ( 2 1 ) 其中e 为数据库中所有对象的均方差之和；p 为代表对象的空间中的一个点； m i 为聚类c i 的均值( p 和m i 均是多维的) 。该聚类标准旨在使所获得的k 个聚 类具有以下特点：( 1 ) 各聚类本身尽可能的紧凑( 2 ) 各聚类之间尽可能的分开。 k m e a n s 聚类算法的计算复杂度为o ( n k t ) ，因而他在处理大数据库时也是相对有效 的。 标准k m e a n s 聚类算法处理流程如下【”j ： 输入：数据库中的对象与簇的数目k ； 输出：使得平方误差准则最小的k 个簇。 ( 1 ) 从n 个数据对象中任意选择k 个对象作为初始簇的聚类中心 m ( i - 1 ，2 ，k ) ； ( 2 ) 利用公式2 2 计算数据集中的每个p 到k 个簇中心的距离d ( p ，m ) ； ( 3 ) 找到每个对象p 的最小的d ( p ，m ) ，将p 归入到与毗相同的簇中； ( 4 ) 遍历完所有对象之后，利用公式2 3 重新计算砚的值，作为新的簇中心： ( 5 ) 重新将整个数据集中的对象赋给类似的簇。将整个过程反复进行直至 帧士学1 、z 论文 平方误差准则最小。 d ( 天，) = ( 誓1 一x 1 ) 2 + ( 薯2 一工，2 ) 2 + + ( 誓。一x m ) 2 ( 2 2 ) 其中i ：( x i l ，x i 2 ，x i 。) 和j = ( i 】j i 2 ，j i l l ) 是两个n 维数据对象。 = 么 ( 2 3 ) 其中m 。代表第k 个簇的簇中心，n 代表第k 个簇中数据对象的个数。 2 3 1 改进的k m e a n s 算法 对于聚类分析中初始值的选取，目前主要有：随机法、经验选取法、距离优 化法、密度法、层次选取法、混合聚类法和多次选取取得最优法等等。无论选择 哪一种方法，都是为了能产生一个比较稳定的聚类结果，不依赖初始质心。初始 质心应该选择在密集数据区域的中心，这样才具有代表性。基于密度的方法可以 区分出数据点的不同密度，且高密度点周围的点应和这个高密度的点属于同一个 聚类，冈此我们在选取初始质心时选取高密度点和这个高密度周围的点的中心作 为初始质心。 k m e a n s 改进算法是通过在完备数据空间的不完全搜索，使得目标函数取得 极小值。由于局部极值点的存在，k m e a n s 算法对初始质心敏感，选择不同的初 始质心会产生不同的聚类结果且会有不同的聚类效果，即使随机选取初始质心相 同，聚类的结果也存在差别。改进k m e a n s 算法基于以下两点思想：( 1 ) 对数据 进行划分，最根本的目的就是使得一个聚类中的对象是相似的，而不同聚类中的 对象是不相似的。如果用距离表示对象之间的相似性程度，相似的对象之间的距 离比不相似的对象之间的距离要小。如果能找到k 个初始质心，他们分别代表了 相似程度较大的数据集合，那么就找到了与数据在空间分布上相一致的初始质心； ( 2 ) 在一个数据空间中，高密度的数据对象通常被低密度的对象区域所分割，高 密度的数据对象和其周围的点通常属于同一个聚类。 下面根据一个实验说明改进k m e a n s 算法思想【1 6 】： 如果采样过程是非常随机的方式进行的，认为这些选取出来的样本足以代表 整个样本集。所以通过分析采样样本集的数据分布情况就可以找到整个样本集的 全局较优的k 个质心，从而使得聚类结果的稳定性提高。其中参数h 为采样次数， 实验表明h - 3 1 0 通常已经足够。参数k 为各个采样的样本集质心数目，k k 。 原始k m e a n s 算法，在七的选取上可以被认为是随机爬山算法，对于具有大量局 部级高点和k 个全局最高点的数据集，k m e a n s 算法很可能陷入局部极高点。然而 类别数目七的增大类似于开辟更多的爬山路径，如果k k 个路径，则到达全局最 高点的可能性自然会增大。但同时随着k 的增大，计算的代价也会增大。在试验 鹱丁聚燮镗；_ 主的群体机器人聚集运动协调代研冗 中研究了k 均值分类算法中参数k 的设置，给出一个法则k = n 引8 。 推荐k 值的选取应该满足如下约束：k = m i n ( a n | m i n i 】，n 5 8 ) ，其中u 曲是需要 关注的最小类簇，a 1 0 。在满足上述约束条件时，k 的取值对于聚类结果不敏感。 处理流程如图2 1 所示。 h = h + l 是 图2 1 输出h 幸k ，、个簇流程图 然后再对这h 木k 个聚类中心采取以下方法：首先找到密度最大的质心，将其 放入集合s ，集合中所有对象距离之和最大的质心，也将其放入到s 中，直到选 出k 个聚类中心为止即集合s 中有k 个元素。再以这k 个质心作为k - m e a n s 原始 中