（检测技术与自动化装置专业论文）基于黑板结构的多机器人通信及协作系统研究.pdf

摘要 工程上需要多个单智能体间的相互协作和协调来共同完成一项任务。智能 体被认为是一个物理或抽象的、能在一定环境下运行的实体，它能作用于自身 和环境，并对环境作出反应。智能体具有知识、目标和能力。多智能体技术是 人工智能技术的一次质的飞跃，多智能体系统是由多个单智能体组成的集合， 该系统可以协调一组智能体的行为( 知识、目标、方法和规划) ，以协同地完成 一个任务或求解问题。 目前，多智能体系统主要的研究方向包括：多智能体系统的体系结构、多 智能体系统间智能体的通信、多智能体系统间的协作和协调、基于多智能体的 智能决策系统等。本文主要研究多智能体系统间智能体的通信、协作和协调问 题。通过对多智能体系统中无通信，方案传递，消息对话通信模式和黑板系统 这四种通信方式的分析，以及对多智能体协商模型所应包括的三元素的分析， 本文以黑板结构作为在动态多变环境下实现多智能体通信及协作的理想模型， 研究应用黑板结构系统来实现多智能体之间的通信、协作和协调的方法，并在 仿真和实物机器人两种环境下得到了实现。主要研究工作包括： 1 ) 黑板结构系统具有三个部分：黑板、控制机制及知识源。首先引入一种 基于协商模型的控制机制使得多a g e n t 之间能够快速的达成一致，且解决了局 部解和全局解间的矛盾，向着最终解决问题的方向推进。然后解决了黑板的分 区问题。最后对如何进行任务分解和任务之间的依赖关系进行研究，解决了如 何建立知识源的问题。 2 ) 对f i r a5 对5 仿真平台进行了简单的介绍。进而在这个仿真平台上建 立了黑板结构，实现了环境监测及分析模块、黑板模块、知识源模块、数据库 模块、控制机制模块的功能及结构。特别实现了仿真比赛环境下黑板结构在角 色分配和角色的协作过程。 3 ) 在中型组实物机器人平台上实现了应用模糊控制算法控制机器人的底 层运动。建立了基于黑板结构的多机器人协作系统，该系统能通过一个服务器 机器人实现对其他机器人的导航。最后该导航系统在有障碍物的实际环境下实 现了队形的行进、角色的分配以及对障碍物的清除工作，并在清除障碍物后让 机器人队伍继续前进。 本研究在北京工业大学人工智能与机器人研究所的机器人平台上实现和测 试。 关键词：多智能体；黑板结构；机器人足球；通信；协作 a l j s t r a c t a b s t r a c t p r o j e c t sr e q u i r em u t u a lm u l t i a g e n tc o l l a b o r a t i o na n dc o o r d i n a t i o nt o j o i n t l y a c c o m p l i s hat a s k a g e n ti sc o n s i d e r e dt ob eap h y s i c a lo ra b s t r a c t , i nac e r t a i n e n v i r o n m e n tt h a tc a nr u ne n t i t y i tc a na c to ni t so w na n dr e s p o n dt ot h e e n v i r o n m e n t a g e n th a sk n o w l e d g e ，o b j e c t i v e sa n dc a p a b i l i t i e s m u l t i a g e n t t e c h n o l o g yi st h ef i r s ta r t i f i c i a li n t e l l i g e n c et e c h n o l o g yq u a l i t a t i v el e a p m u l t i - a g e n t s y s t e mi sc o m p o s e do fan u m b e ro f a g e n tp o o l s ，t h es y s t e mc a nc o - o r d i n a t eag r o u p o fi n t e l l i g e n tb e h a v i o r ( k n o w l e d g e ，g o a l s ，m e t h o d s ，a n dp l a n n i n g ) ，c o m p l e t eat a s k o rs o l v ep r o b l e m sc o l l a b o r a t i v e l y a tp r e s e n t ，t h em u l t i a g e n tm a j o rr e s e a r c hi n c l u d e ：m u l t i a g e n ts y s t e m a r c h i t e c t u r e ，m u l t i a g e n ts y s t e m s ，m u l t i a g e n tc o m m u n i c a t i o n s ，m u l t i a g e n ts y s t e m s c o l l a b o r a t i o na n dc o o r d i n a t i o nb a s e do ni n t e l l i g e n td e c i s i o n - m a k i n gs y s t e m t h r o u 曲t h ea n a l y s i so f m u l t i a g e n ts y s t e mw i t h o u tc o m m u n i c a t i o n s ，p r o p o s a l t r a n s m i s s i o n ，i n f o r m a t i o n c o m m u n i c a t i o nd i a l o g u ea n db l a c k b o a r ds y s t e m ，a sw e l l a sa n a l y s i so nt h em u l t i a g e n tm o d e lw h i c hs h o u l di n c l u d et h et h r e ee l e m e n t s ，t h i s p a p e rr e c o m m e n db l a c k b o a r da r c h i t e c t u r ea st h ei d e a lm o d e li nt h ed y n a m i c c h a n g e se n v i r o n m e n tt oa c h i e v em o r ei n t e l l i g e n tc o m m u n i c a t i o n sa n dc o l l a b o r a t i o n t h e r e f o r e ，t h i sp a p e ra p p l i e sb l a c k b o a r da r c h i t e c t u r et oa c h i e v em u l t i a g e n ts y s t e m b e t w e e nc o m m u n i c a t i o n ，c o l l a b o r a t i o na n dc o o r d i n a t i o n m a j o rr e s e a r c he f f o r t s i n c l u d e ： f i r s t ，b l a c k b o a r da r c h i t e c t u r es y s t e mh a st h r e ep a r t s ：b l a c k b o a r d ，c o n t r o l m e c h a n i s m sa n dk n o w l e d g es o u r c e s t l i sp a p e ri n t r o d u c e sam o d e lb a s e do nc o n t r o l m e c h a n i s m st h a tc a nm a d ea g r e e m e n ta m o n gm u l t i - a g e n tr a p i d l y ，a n ds o l v et h e c o n t r a d i c t i o n sb e t w e e nt h ep a r t i a ls o l u t i o na n do v e r a l ls i t u a t i o n , a n dd i r e c tt h e p r o b l e mt o w a r dt h eu l t i m a t es o l u t i o n t h e ni ts o l v e st h eb l a c k b o a r dz o n i n gi s s u e s f i n a l l y ，i td i dr e s e a r c ho nt h et a s kd e c o m p o s i t i o na n dh o w t oc a r r yo u tt h e t a s k - d e p e n d e n tr e l a t i o n s h i p ，h o wt os o l v et h ei s s u eo fak n o w l e d g es o u r c e s e c o n d ，t h ep a p e ri n t r o d u c ef i r a5v s5s i m u l a t i o np l a t f o r m i nt h i ss i m u l a t i o n p l a t f o r m ，i te s t a b l i s h e dab l a c k b o a r d ，a n da c h i e v e st h ee n v i r o n m e n t a lm o n i t o r i n g a n da n a l y s i sm o d u l e ，b l a c k b o a r d sm o d u l e ，t h es o u r c eo f k n o w l e d g em o d u l e s ， d a t a b a s em o d u l e s ，t h em o d u l e sc o n t r o lm e c h a n i s m sf i m c t i o na n ds t r u c t u r e e s p e c i a l l yi ns i m u l a t i o ne n v i r o n m e n to f c o m p e t i t i o n ，i ta c h i e v e st h eb l a c k b o a r d a r c h i t e c t u r ei nt h er o l ed i s t r i b u t i o na n dc o i l a b o r a t i o n t h i r d ，i nt h em e d i u m s i z e dg r o u pr o b o tp l a t f o r m ，i ta c h i e v e st h ea p p l i c a t i o no f 1 1 1 - 北京t 业人学t 学碗卜号位论文 f u z z yc o n t r o la l g o r i t h m su n d e r l y i n gm o v e m e n tt oc o n t r o lr o b o t b a s e do n t h e e s t a b l i s h m e n to f ab l a c k b o a r ds t r u c t u r eo f m u l t i r o b o tc o o p e r a t i o ns y s t e m ，i tc a l l a c h i e v eas e r v e rr o b o ti no r d e rf o rn a v i g a t i o n f i n a l l y ，t h en a v i g a t i o ns y s t e mc a r l a c h i e v et h ef o r m a t i o no f t h er o a di nt h ea c t u a le n v i r o n m e n t ，f i n dt h er o a d b l o c k ， d i s t r i b u t et h er o l e a sw e l la sr e m o v eo b s t a c l e s t h e nt h et e a mc o n t i n u e s t om o v e f o r w a r da f t e rt h er e m o r a lo f o b s t a c l e s n l ca c h i e v e m e n t sa n dt e s t i n gw e r ed o n eu n d e rt h eb e i j i n gu n i v e r s 畸o f t e c h n o l o g ya r t i f i c i a li n t e l l i g e n c e & r o b o t i c si n s t i t u t er o b o tp l a t f o r m k e y w o r d s ：m u l t i - a g e n t ；b l a c k b o a r da r c h i t e c t u r e ；r o b o ts o c c e r ；c o m m u n i c a t i o n ； c o l l a b o r a t i o n i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：旌 日期： 口乒fu 7 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：玉趣导师签名：趣日期：迹签名：趔盈丝导师签名：乏受挫日期：鲤业 第1 审绪论 第1 章绪论 人们在研究人类智能行为中发现，大部分人类活动都涉及到多个人构成的 社会群体，大型复杂问题的求解需要多个专业人员或组织协作来完成。同样， 工程上也需要多个单智能体间的相互协作和协调束共同完成一项任务。研究和 建立多智能体系统的目的就是把多个单智能体有机地组织起来，通过一定的通 讯方式，协调它们之间的行为，使其共同协作，完成单个智能体无法完成的任 务。 智能体( a g e n t ) 是分布式人工智能( d a i ) 领域的一个基本术语，它是由美 国学者明斯基8 0 年代提出的1 3 7 】1 3 1 。一般地，智能体被认为是一个物理或抽象 的、能在一定环境下运行的实体，它能作用于自身和环境，并对环境作出反应。 智能体具有知识、目标和能力【3 】【“。知识主要包括领域知识、通讯知识、控制 知识等；目标可以根据变化情况分为静态目标和动态目标，目标可以通过算法 编入或显示给定，或通过通讯获得；能力是指智能体具有推理、决策、规划和 控制等的能力。其能力的获得可以显示地给定、学习或通过通讯获得。单智能 体都表现出如下的基本特性：自主性( a u t o n o m y ) 、社会能力( s o c i a l a b i l i t y ) 、反 应性( r e a c t i v i t y ) 、前瞻性( p r o a c t i v i t y ) 、理性( r a t i o n a l i t y ) 。 多智能体技术是人工智能技术的一次质的飞跃，多智能体系统是由多个单 智能体组成的集合，该系统可以协调一组智能体的行为( 知识、目标、方法和规 划) ，以协同地完成一个任务或求解问题。各单智能体可以有同一个目标，也可 以有多个相互作用的不同目标，它们不仅要共享有关问题求解方法的指示，而 且要就单智能体间的协调过程进行推理。 1 1 国内外研究发展动态 国际上关于多智能体系统的研究虽然时间很短，但发展相当迅速。目前， 主要的研究方向包括：多智能体系统的体系结构、多智能体系统间智能体的通 信、多智能体系统间的协作和协调、基于多智能体的智能决策系统等。 1 1 1 多智能体系统( m a s ) 的体系结构 多智能体系统( m a s ) 的体系结构主要研究如何将多个单智能体组织为一 个群体并使各个智能体有效地进行协调合作，从而产生总体解决问题的能力。 多智能体系统的构成方式有多种。从构成系统的单智能体种类出发，可分为同 构、异构以及同异构混合型三种方式。从运行的控制角度来看，m a s 可分为 集中式、分布式、集中与分布相结合的三种类型。集中式系统有一个核心a g e n t 和多个与之在结构上分散的、独立的协作a g e n t 构成。核心a g e n t 负责任务的 北京丁业大学t 学砸卜学位论文 动态分配与资源的动态调度，协调各协作a g e n t 间的竞争与合作，该类系统比 较容易实现系统的管理、控制和调度；分布式系统中各a g e n t 彼此独立、完全 平等、无逻辑上的主从关系，各a g e n t 按预先规定的协议，根据系统的目标、 状态与自身的状态、能力、资源和知识，利用通信网络相互间通过协商与谈判， 确定各自的任务，协调各自的行为活动，实现资源、知识、信息和功能的共享， 协作完成共同的任务，以达到整体目标，该系统具有良好的封装性、容错性、 开放性和可扩展性。根据系统中智能体之问的相对关系来划分，通常可以分为 如下几种结构1 3 ”： 1 ) 完全型网络结构 该结构体系要求各智能体均具有通信和控制功能模块，并且要保存系统内 所有智能体成员的信息和知识，对于解决复杂的问题，完全型网络结构体系的 效率会大大降低，并呈现出一种无组织的状态。 2 1 层次型网络结构 在该类型系统结构中，智能体被分为不同的层次，在同一层上的智能体彼 此不能够直接进行通信，而需要经过其上一层智能体来完成。上一层智能体负 责其下一层智能体的决策和控制。该结构中智能体不需要保存系统内所有的智 能体信息，只需要保存下一层智能体的相关信息和知识，该结构尽管在通信上 不如完全网络型简略，但结构层次分明，管理方便。 3 1 联盟型网络结构 系统内的智能体按照某种方式( 通常按照距离远近、智能体功能等) 来划分 为不同的智能体联盟。在各联盟内部都存在一个协助智能体，它负责不同联盟 之间的通信。不同联盟之问处于对等的关系，类似于完全网络型各智能体之间 的关系。 1 1 2 多智能体系统间智能体的通信 近年来，有更多的研究着眼于智能体间的通讯方案。例如在智能体之间关 于局域负载的通讯，使用元级通讯方案可以耗费较低的成本，得出各种组织结 构的实际成本和收益；分布式动态计划系统d i s ，d s s 中的智能体能够彼此共享 能力和可利用性，d i s d s s 是一个交换和更新资源文件的协议，资源文件包括 智能体的承诺资源、可用资源、和预计未来的要求【4 ”。d a i 系统中，智能体通 过运用自己解决问题的知识及信息的有效性来选择信息。关于如何发现信息条， 以及信息条在解决问题过程中所承担的角色的知识，通过一套探索法转变成期 望数值。另一技术采用了一个计划员，它研究当前的任务和系统的目标，执行 预先定义好的多智能体系统的协作算法，算法数量最多可达到5 个 4 4 1 。智能体 通过使用c b r 来决定：它应该发送任务公告信息给其余的那些智能体，该公 告信息是合同网络协议的一部分。所选择的案例是基于当前试图解决的任务。 笫1 章绪论 智能体开始和其它的智能体发生交互，在交互完成后，它们通过使用预先定义 好的判据，来评估协作的收益和耗费。与产生正面影响的智能体的交互得到加 强，与产生负面影响的智能体的交互加以减弱。 多智能体系统中通信模式的划分有着多种的方式，大致常见的可分为四种， 分别是无通信，方案传递，消息对话通信模式和黑板系统。 1 1 3 多智能体系统的协作和协调 尽管对于单个a g e n t 来说，它只关注自身的需求和目标，但在m a s 中， a g e n t 不是孤立存在的，这种相互依赖的关系使得a g e m 间的交互以及协作方 式对a g e n t 的设计和实现具有相当大的制约性，基于不同的交互和协作机制， m a s 的中a g e n t 的实现方式也各不相同。因此，研究a g e n t 间的协作是研究和 发展基于a g e n t 的智能系统的必然要求。 1 ) 基于符号推理智能体研究 2 1 协商模型 3 ) 协作规划模型 4 ) 基于承诺与约定的协作模型 5 1 自协调模型 1 1 4 多智能体决策系统 自从m s s c o t tm o r t o n 首先提出决策支持系统( d s s ) 这一术语，随着决策 理论、管理科学、信息技术、人工智能( a i ) 、尤其是专家系统s ) 和知识工程 ( i c e ) 、计算机技术、通讯手段的进展，d s s 有了很大的发展，并成为信息和决 策科学领域里发展最快的研究分支之一【4 “。最近几年，d s s 则更加强调各种技 术的综合运用，而且又先后提出了群决策支持系统( g d s s ) ，智能决策支持系统 ( i d s s ) ，分布式决策支持系统( d d s s ) ，集成式决策支持系统( i - d s s ) 等更高层 次的决策支持系统。由于a g e n t 具有自制能力、智能和目标驱动属性，能够通 过各种社交、学习、推理等方法感知和适应复杂的动态环境，具有自动追求目 标的能力，这些特性使得a g e n t 适合于i d s s 的开发。a v o u r i s 采用智能体技 术将多个专家系统的决策方法有机地协调起来 4 4 1 ，建立了基于多智能体协调的 环境决策支持系统。智能体采用基于规则的描述方法，实现了环境管理的分布 式智能决策。具有分布式结构的a g e n t 系统是分布式i d s s 的重要研究领域。 基于多a g e m 的智能d s s 有三种不同的分布结构： 1 ) i n t e m e t 环境下耦合的多a g e n t 智能d s s ； 2 ) i n t r a n e t 环境下耦合的多a g e n t 智能d s s ； 3 ) 单机环境下多a g e n t 智能d s s 北京工业人学丁学硕十学位论义 1 2 本课题的研究目的及主要内容 1 2 1 研究目的 由于系统中智能体的资源、能力、知识是有限的，需要多智能体间的协作 和协调，而要实现协调与协作，通常情况下智能体之间需要交换一定的信息， 即通过通信来实现。本课题通过在仿真和实物平台下的实验，不断修正基于黑 板结构的协作及通信模型程序，最终为机器人在实时性很强的足球比赛环境下 建立高效且效果好的多机器人协作系统。 1 2 2 研究内容 完全分布的通信方式中，很难保证智能体的协作遵循约束协调进行。在很 多系统中，智能体之间需要共享一些与协作有关的信息，例如环境信息，资源 利用信息，任务求解进展状况信息等，还有其它一些需要共享的知识，这些需 要提供存储和访问的机制，单靠消息传递机制不能有效解决。希望通过研究发 现基于黑板结构的通信解决以上问题。 在多智能体系统中，黑板提供公共工作区，智能体间可以交换信息、数据 和知识。开始一个智能体在黑板写入信息项，然后可为系统中其它智能体使用。 智能体可以在任何时候访问黑板，看看有没有信息到来。它不需要阅读所有信 息，可以用过滤器抽取当前工作所需的信息。智能体必须在授权中心站点登陆。 在黑板系统中智能体之间不发生直接通信。每个智能体独立的完成它们答应求 解的子问题。 黑板可以用在任务共享和结果共享系统中基于事件的问题求解策略也是 可能的。如果系统中智能体很多，那么黑板中的数据会成指数增加。与此类似 各个智能体在访问黑板时要从大量信息中搜索，决定感兴趣的信息。为了优化 处理，更先进的黑板结构在黑板上为各个智能体提供不同的区域。 1 2 3 本课题解决的关键问题 本课题解决机器人足球团队在配合过程中的基于黑板结构的协作问题。突 破这三个关键问题，可以较好的解决机器人在配合过程中的协作和决策问题。 关键问题一：黑板分区及数据格式 一般情况下，可以把黑板区分为任务信息区、通信信息区、共享信息区三 个区，如图1 - 1 所示。根据应用的不同情况，并不需要所有的这三个分区。解 决黑板的分区决定黑板结构效果的基础。 第1 章绪论 图1 - 1 黑板结构的分区 f i gl 一1t h ed i v i s i o no f b l a c k b o a r d a r c h i t e c t u r e 关键问题二：任务分解机制 任务的分解是指将任务一步步的分解为较小的需要较少知识和资源即可解 决或特定a g e n t 胜任的子任务，任务的分解需要考虑任务是如何表示的、分解 的方式、完成任务的组织、资源以及予任务之间的联系。 关键问题三：多智能体的协作方法 多智能体在协作过程中必然会遇到冲突、矛盾，如何协调多智能体的协作， 使之各个局部解向全局解推进也是本课题需要研究的重要问题。 1 3 本文的章节安排 第1 章阐述本课题的研究背景、研究目的及主要内容，并提出本课题解决 的关键问题。 第2 章介绍了智能体及多智能体的概念，多机器人通信及协作使用的主要 方法，最后通过比较选择黑板结构作为多机器人通信协作的模型。 第3 章对黑板结构进行详细的描述，并对黑板结构中的黑板、知识源、控 制机制、协商算法进行详细的阐述。 第4 章先对f i r a5 对5 仿真比赛平台进行简单的介绍，然后讲述黑板结构 在仿真平台上的实现，并对各个模块及流程设计详细描述。 第5 章先对r o b o c u p 实物机器人平台的硬件环境进行了讲述，然后介绍 底层的模糊控制算法实现，最后介绍黑板结构在多机器人导航系统上的实现。 北京 业大学t 学硕1 “学位论文 第2 章多智能体系统研究 在a g e n t 的众多定义中，比较通用的是w o o l d r i d g e 和j e n n i n g s 在1 9 9 5 年 提出的定义【4 】：a g e n t 是处在某种环境中的计算机系统，该系统有能力在这个环 境中自主行动以实现其设计目标。这个定义强调的是a g e n t 的自主性。 关于a g e n t 的另一个定义是这样的i s ：软件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 所有可能具有的特点【3 7 】： 1 ) 自治性：a g e n t 不直接由人或其它东西控制，它对自己的行为和内部 状态有一定的控制权。 2 ) 交互性：a g e n t 能够通过某种主体通信语言与其它a g e n t 交换信息，并 协同工作。 3 ) 反应性：即对周围环境的感知和影响。a g e n t 能感知周围环境并对其间 的变化产生实时响应，这些动作的执行基于知识库的规则或预定的执行计划。 a g e n t 也能够主动地进行基于自身目标和信念的活动，以改变周围环境。 4 1 推理性：软件a g e n t 可根据已有的知识和经验，以理性、可再生的方式 进行推理。软件a g e n t 的智能由三个主要部件来完成，即内部知识库、自适应 能力以及基于知识库的推理能力。 5 ) 学习和适应能力：主体可以根据过去的经验积累知识，也可以修改其行 为以适应新的环境。 6 ) 规划能力：根据目标、环境等的要求，a g e n t 应该至少对自己的短期行 为做出规划。虽然程序设计人员可以提供一些常见情况的处理策略，但这些策 略不可能覆盖a g e n t 将遇到的所有情况。所以，a g e n t 需要具有生成规划的能 力。 7 ) 时间连续性：传统程序在用户需要时激活，不需要时或者运算结束后停 止，a g e n t 与之不同，它应该至少在“相当长”的时间内连续运行。 2 1 多智能体系统 然而，在进行大型的和复杂的分布式问题求解时，单个智能体的能力是有 限的。因此，可通过适当的组织结构将多个智能体组织起来形成多智能体系统 ( m u l t i a g e n ts y s t e m ，缩写m a s ) ，从而弥补个体能力的不足，使整个系统的能 力超过任何个体的能力。在多智能体系统中，各个智能体之间相互协调各自的 瓤2 千多智能体系统硎究 知识、目标和技能，通过协作来完成某些任务或达到某些目标，并共享有关问 题和求解方法的知识。利用多智能体技术，系统问题可被概念化为分布式和自 治的智能体之间相互协作以实现全局目标的解决方案。可见，多智能体技术是 解决现实世界中动态和开放系统问题的有效计算方法。本课题研究多智能体的 通信及协作机制，范畴涉及m a s 的交互与通信、一致性与协调性多智能体规 划以及冲突处理。 2 2 多智能体的通信及协作 2 2 1 多智能体的通信方式 m a s 中的a g e n t 需要通过相互通信来进行协作。多智能体系统中通信模式 的划分有着多种的方式，大致常见的可分为四种，分别是无通信，方案传递， 消息对话通信模式和黑板系统。 2 2 1 1 通信方式p ” 1 ) 无通信 无通信是指单个的纯智能体通过“理性”思考和推理的手段，而不是通信 的方式，得到其它a g e n t 的任务方案或计划。a g e n t 之间需要的是彼此透明可 见，或者它们需要通过不断的计算和推论来得到其他a g e n t 的行动计划。这往 往会实现困难，造成系统性能降低、系统功能和规模不易扩展等限制和缺点。 因此，这种系统基本上不具备智能体系统的优越性。 2 ) 方案传递 方案传递的做法是在相互协作的a g e n t 之间，一方通过给对方传递其整个 任务方案，相互取得对问题的一致理解和相应的解决方案。这种模式常用于分 布式计算和d a i 应用中。尽管它可以使a g e n t 的合作求解比较容易实现，但 它却存在许多缺点，比如：传递方案带来的时空开销较大：传输过程易出错； 不灵活；在状态多变、不确定的现实环境下无法应用等。 3 ) 消息对话通信模式 通信方式消息对话系统，具有更大的灵活性，也更加趋近于人类的自然交 流，是实现复杂的协调策略的基础。使用规定的协议，智能体彼此直接交换的 消息可以用来建立通信和协作机制。自由消息内容格式提供非常灵活的通信能 力，不受简单命令和响应结构的限制。 4 1 黑板系统 黑板系统是由c a r n e g i e m e l l o 大学于1 9 7 6 年，在h e a r s a y - i i 口语理解 系统上实现的【4 0 1 。黑板结构主要由三部分组成：黑板、知识源、控制。黑板是 全局共享数据库，存放输入数据、中间结果和最终解，有时也存放控制信息； 各单智能体的工作范围、功能、性质等被划分成相互独立的知识源，知识源之 北京丁业大号t 学碗i 学位论文 倒不能相互调用，它们通过黑板来通讯，知识源主要由条件和动作组成；控制 机制负责在每一周期中选择出下一次将要执行的动作。控制机制根据所采取的 控制策略的不同来选择最有效的知识。黑板系统适用于任务共享和结果共享的 系统中，但对于复杂的系统来说，黑板中知识的数量较多，会造成各智能体搜 索信息的速度下降，影响系统解决任务的效率。黑板系统的发展为多智能体系 统通信问题的解决提供一种思路。 黑板系统是传统人工智能系统和专家系统的议事日程的扩充。在专家系统 中，黑板主要通过数据库实现，是用于存放用户提供的初始事实、问题描述以 及系统运行过程中得到的中间结果、最终结果、运行信息等的工作存储器。在 m a s 中黑板提供公共工作区，以保证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 独立地完成它们答应求解的子问题。为了优化 处理，更先进的黑板概念是在黑板中为各个a g e n t 提供不同的区域。 2 2 1 2 通信方式比较 在环境多变的情况下，无通信和方案传递都无法应用。而采用消息通信可 以实现灵活复杂的协调策略，但与黑板系统不同的是，消息在两个a g e n t 间直 接交换，由发送者a g e n t 传送到接收者a g e n t 。一般情况，发送者要指定唯一 的地址给消息，只有那个地址的a g e n t 才能读这条消息。所谓广播是一种特例， 消息是发给每个n e 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 之间地协调使多个a g e n t 共同协作来求解给定的问题， 同时强调将决策者的智慧和系统相结合。 2 2 2 多智能体的协作 协作是一种在两个或多个智能体之间交换信息与知识及分配任务和资源以 实现共同目标的技术。在多智能体系统中，协作不仅能提高单个智能体以及由 多个智能体所形成系统的整体行为性能，增强智能体和多智能体系统解决问题 的能力，还能使系统具有更好的灵活性，并能解决更多的实际问题，拓宽其应 用。尽管对单个智能体来说，它只关注自身的需求和目标，因而其设计和实现 可以独立于其他智能体。但在多智能体系统中，智能体并不是孤立存在的，智 第2 章彩钾能体系统研究 能体的行为必须满足某些预定的规则，而不能为所欲为。 2 2 2 1 多智能体协作模型 1 ) 基于符号推理智能体研究 对多智能体理性的研究主要有两种，一是基于逻辑学方法的b d i 模型，另 一种是基于经济学方法的对策论。 基于经济学方法的对策论，与传统的b d i 的逻辑方法不同，理性的含义是 在给定的约束条件下最大化自己的效用函数。r o s e n s c h e i n 在文献中指出了理 性智能体协作的条件，并指出在不进行通讯的情况下，智能体可以运用效用模 型进行推理选择自身行为p ”。g m y t r a s i e w i e z 与d u r f e e 使用元对策方法研究了 敌方模型不确定情况下的推理，通过利用元递归建立敌方效用概率模型，从而 在一定程度上解决了完备知识假设的局限。 1 9 8 7 年b r a t m a n 等首次提出了b d l 模型的概念，其主要思想是依据定义 的一组心智状态( 信念( b e l i e v e ) 、愿望( d e s i r e ) 、意 ( i n t e n t i o n ) ) 来描述智能体的 内部处理状态和建立相应的控制结构p ”。基于b d i 模型的智能体通过建立尽 可能完备的外部世界的符号模型，来进行知识推理，以保证智能体具有自主思 考、决策以及与外部环境进行协作的能力。但对于大型的复杂动态系统来说， 构造外部环境准确的符号模型具有很大的难度，而且智能体自身模型的计算和 推理的实时性较差，导致智能体的适应能力较差。 前一类方法所运用的各理论只适用于特定的协作环境，而一旦环境发生变 化，如智能体的个数、类型、及多智能体之间的交互关系发生改变时，基于该 理论的协作机制就失去了其存在的优势。而后一类方法则较偏重于问题的规划 与求解，并且他们所假定的协作差异是显著的。 2 1 协商模型 合同网协议( c o n t r a c t n e t p r o t o c 0 1 ) 是协商模型的典型代表，其主要原理是 采用市场机制进行任务分解、通告、投标、评标，最后签定合同来实现任务的 分配。合同网中包括管理者( m a n a g e r ) 和合同者( c o n t r a c t o r ) ，其中管理者负责任 务的分解、公布、选标等任务的执行情况，合同者是负责其接收的任务的完成。 各结点不存在预先设定的优先等级，并且一个结点可以同时担任不同任务的管 理者和合同者。合同者完成任务后将结果返给管理者，管理者发表终止广播， 结束合同。 3 ) 协作规划模型 在多智能体系统中，单智能体具有自己的求解目标，在考虑其它智能体的 行动和约束条件下，进行独立的规划，称之为部分规划：网络结点以上的部分 规划通过通信方式在所有结点之间进行协调，从而达到整个系统的全局规划。 d u r f e e 提出的部分全局规划p g p ( p a r t i a lg l o b a lp l a r m i r i 曲方法允许各智能体动 北京t 业人学t 学砸1 导位 = f = 丈 态合作，智能体的相互作用以通信规划和目标的形式抽象表述，相互告知敌方 自己的行为期望，智能体利用规划信息调节自身的局部规划，达到共同目标。 4 1 基于承诺与约定的协作模型 基于承诺和约定的协作方法采用分布目标搜索的形式化方法模型化多 a g e n t 系统，在这里承诺指a g e n t 对承担一个特定的行为序列所作的保证；约 定( c o n v e n t i o n s ) 是指在变化的环境中监控承诺进展状态的手段。前者提供了一 定程度的可预见性，使a g e n t 能够在处理a g e n t 问依赖关系、全局约束和资源 冲突时，能估计其他a g e n t 的活动：后者为多a g e n t 系统在动态环境下的协作 提供了灵活性。 5 ) 自协调模型1 4 1 在复杂的实时控制系统中，要求系统能够根据环境和被控对象的实时动态 变化，来自适应地调整控制结构、控制策略、相关参数等，该系统具备自动调 整控制结构和策略等的能力。自适应协调模型的动态协调特性主要体现在：一 是系统组织结构的动态组织，智能体间的协作网络结构能够根据解决任务的需 要自动进行调整和优化；二是系统可以根据最新的任务需要或平衡状态自主地 协调行动。该模型主要基于分布式环境下智能体的学习能力。h u 和w e l l m a n 根据智能体行动产生效果的预测来建立和修正信念过程，提出一种智能体对其 它智能体响应进行建模的多智能体系统。s t o n e 等提出的协调模型则是通过智 能体的相互作用进行智能体学习，学习的结果通过整个系统和单个智能体的效 益显示出来。该模型广泛地应用于过程控制、空中交通控制和城市交通控制中。 2 _ 2 22 基于黑板结构的协作模型选择 从多智能体协作机制建模的发展过程来看，以逻辑推理为基础的形式化建 模方法和以决策理论及动态规划为基础的建模方法正在逐渐融合，二者都强调 智能体的理性作用，而对策论是产生这种融合的媒介。纵观近十年的研究状况， 适应不同的应用环境而从不同角度产生过多种不同类型的多智能体协作模型和 应用系统，这些模型主要是多智能体协商模型 在m a s 中，需要协调的是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 行为随时间的同步等。精确的说一个协调模型应包括三个元素：协 调体，协调媒介和协调规则。而黑板结构的三元素：黑板、知识源、控制机制 恰恰对应了多智能体协调所需要的三元素协调媒介、协调体和协调规则。因而， 应用基于黑板结构的多智能体系统能够比较好的实现多智能体的协调工作。 第2 币彩智能佛系统_ | i ) | 宄 2 3 本章小结 本章通过对多智能体系统中无通信，方案传递，消息对话和黑板系统这四 种通信方式的分析，以及对多智能体协商模型所应包括的三元素的分析得出结 论：认为黑板结构是在动态多变环境下实现多智能体通信及协作的理想模型。 北京工业大学1 = 学硕十学位论殳 第3 章基于黑板结构的多智能体通信及协作 黑板系统是传统的人工智能系统和专家系统的议事同程的扩充，通过使用 合适的结构支持分布式问题求解。 黑板系统首先在口语理解系统h e a r s a y - i i 中实现，以后逐渐抽象为一种 通用的问题求解模型。它将求解问题的知识表示成独立的、松散的知识源，利 用这些知识源来协同求解问题。在黑板模型中，知识源相对独立，这样可以利 用多专家知识求解问题；知识源的精度可大可小，对问题的分割就比较容易： 黑板的层次划分又使得抽象技术得以实现。这些特点使黑板结构得以广泛的应 用，是一种比较先进的问题求解模型。 黑板系统的优越性： n 将多种知识源组合在一起，实现问题求解； 2 1 黑板系统适合于在多重抽象级上描述与处理问题； 3 1 允许知识源共享黑板中各个层次上的部分解，这对事先无法确定求解 次序的复杂问题尤为有效； 4 1 解答是由各知识源独立的对黑板的修改而逐步形成