（系统工程专业论文）合作分布式问题求解过程及其社会性研究.pdf

华中科技大学博士学位论文 摘要 人工智能领域的合作分布式问题求解( c d p s ，c o o p e r a t i v e d i s t r i b u t e dp r o b l e m s o l v i n g ) 具有巨大的潜力，但是也面临极大的挑战。从玩偶问题、机器人搬运问 题，到今天的诸如飞行交通控制、车辆监控系统等复杂问题，c d p s 对合作的处理 越来越游刃有余，问题求解的广度和深度有了明显的拓展。但是，现实世界中更 多的复杂问题往往涉及人的因素，涉及社会和组织背景，所以c d p s 的发展之路 仍然任重道远。 本文认为，对于这些复杂问题的求解。难以用单一模型描述，用单一算法解 决。但是从人工智能传统的符号机制学派的思想出发，通过表达和推理，可以刻 画诸如其中的个体的心智状态的细微变化等现象，从而加深理解个体的社会性， 深入认识这个问题求解过程，并有助于构建更贴近于实际的、可计算的复杂问题 合作分布式求解系统。 本文的重点是讨论复杂c d p s 系统的构成和运行，特别是其中所体现的社会 性问题，目的是构建能解决复杂问题求解的c d p s 可计算模型，用于计算机实现。 本文的主要工作包括： 首先，概述了c d p s 的特点、研究现状和难点，指出合作是决定c d p s 性能 的关键，由此必须深入认识其中的社会性。归纳了当前c d p s 领域中处理合作的 主要方法，并详细综述了其中的多节点规划方法，以及m a s 领域中相关的组织构 造方法。指出当前的研究趋势是融合两个领域的研究成果，以处理更为复杂的问 题求解，这也是本文的着眼点。 其次，讨论了一般意义上的社会性的定义，明确了这个概念的范畴。从a i 、 d a i 、c d p s 研究的目标出发，分析了为什么需要研究c d p s 的社会性。阐述了社 会性研究的三种不同原则，并详细讨论了可计算框架的指导原则，给出发展c d p s 社会性需要把握的主基和方法，以及c d p s 社会性的研究内容。 在做了这些方法论方面的准备后，开始对合作问题求解的全过程进行梳理式 的分析，认为可以从个体社会性的产生和演化两个角度，来区分c d p s 中所存在 的两个相对分离，但又相互交织、相互影响的层面及其中的子过程：问题的求解 子过程、求解的组织子过程。简要讨论了两个子过程的特点，特别提出以“合弄” 概念作为c d p s 过程分析的基础，比较了合弄与a g e n t 、合弄结构与m a s ，分析了 这个概念的合理性和优越性。 接着，参照b d ia g e n t 和3 a p la g e n t 的意向观点和形式化模型，并结合c d p s 领域中已有的层级任务网络h t n 来表达任务的思想，提出了合弄的基本认知属性 华中科技大学博士学位论文 也应包括信念、目标、意图等，给出了一个合弄形式化研究的逻辑框架。特别讨 论了合弄的能力表示，与m a s 领域现常用的规划树表达相比较，指出前者的优越 性。 基于此，一方面提出了基于合弄的问题求解子过程的递归算法。另一方面围 绕问题求解的组织子过程，从构成模式和运行模式两个方面进行了详细的讨论。 构成模式包括角色概念的定义及其形式化表达，角色之间的各种关系，社会性对 求解个体心智状态的影响等方面，而针对运行模式，则说明了问题求解的组织子 过程的算法，并讨论了其中的几个主要技术细节，比如期望求解角色的设置方法， 以及潜在合作意愿的识别。 最后，针对以缩短时间为首要目标，以节约成本为优化原则，常常有组织因 素等复杂背景的快速物资调运问题，阐述了其中所存在的大量社会性特点，描述 了基于合弄的快速调运系统的概念框架，并以参与任务招投标的一个投标人为例， 讨论了该合弄可能拥有的运输问题规划方案，合弄的内部结构，合弄的裂变规则， 投标人角色的表示，角色扮演者的确定，契约的签订等技术细节。此外还阐述了 应用本文的思想来构建快速调运系统的优越性。 关键词：合作分布式问题求解，社会性，合弄，角色，组织，契约，形式化方法 华中科技大学博士学位论文 a b s t r a c t a sa ni m p o r t a n ts u b - f i e l di na r t i f i c i a li n t e l l i g e n c e ( a i ) ，c o o p e r a t i v ed i s t r i b u t e d p r o b l e m s o l v i n g ( c d p s ) r e v e a l s i t sr e m a r k a b l e p o t e n t i a lp o w e r , w h i l ea tt h es a n l et i m e b e i n gc o n f r o n t e dw i t hg r e a tc h a l l e n g e s f r o mt h ed o l tp r o b l e ma n dt h er o b o tc a r r y i n g p r o b l e m t o t h ea i rt r a f f i ce o n t r o l p r o b l e ma n dt h ed i s t r i b u t e dv e h i c l em o n i t o r i n g p r o b l e m , c d p s c a nt a c k l em o r ea n dm o r e p r o b l e m sw i t hm o r e a n dm o r es k i l la n de a s e b u ta s m a n yc o m p l e xp r o b l e m s i n v o l v eh u m a n b e i n g s a n dt h e i rs o d e t a la n d o r g a n i z a t i o n a lb a c k g r o u n d s ，t h e r e f o r e ，t h e r e i ss t i l lal o n gw a yt o g oa n dh e a v y r e s p o n s i b i l i t i e st os h o u l d e r t h i sd i s s e r t a t i o nb e l i e v e st h a t i t sp r e t t yd i f f i c u l tt os o l v es u c hc o m p l e xp r o b l e m s 晰t has i n g l em o d e lo ra s i n g l ea l g o r i t h m b l i tf r o mt h et r a d i t i o n a li d e ao f t h es y m b o l i c i n t e r a c t i o n i s ms c h o o li n a i ，t h r o u g he x p r e s s i n g a n d r e a s o n i n g , m a n y s o c i e t a l p h e n o m e n ac a l lb ed e p i c t e d ，s u c ha si n d i v i d u a lm e m b e rh o wt o ，w h e nt oa n dw h y c h a n g ei t sm e n t a ls t a t e ，a c c o r d i n g l ym a k i n gt h ec d p sp r o c e s sa n di t ss o c i a l i t ym o r e d c 培 p l yu n d e r s t o o d ，a n dh e l p i n gt o b u i l dm o r ep r a c t i c a la n dc o m p u t a t i o n a lc d p s s y s t e m s t h e r e f o r e , a i m e d a t b u i l d i n g a c o m p u t a t i o n a l c d p ss y s t e mm o d e l ，t h i s d i s s e r t a t i o nf o c u s e so ni t sc o n s t i t u t i o na n df u n c t i o n ，e s p e c i a l l yi t ss o c i a l i t y t h i sw o r ki s o u t l i n e da sf o l l o w s ： f i r s t , t h ec h a r a c t e r i s t i c so fc d p s a r cs u m m a r i z e d , t o g e t h e rw i t hi t sc u r r e n tw o r k a n dd i f f i c u l t i e s i ti s p o i n t e do u tt h a tc o o p e r a t i o ni s c r u c i a lt ot h ec d p ss y s t e m p e r f o r m a n c e ，a n dt h e ni t ss o c i a l i t yn e e dt ob ed e e p l yu n d e r s t o o d b e s i d e s ，a f t e rt h e m a j o r m e t h o d st od e a lw i t hc o o p e r a t i o nc u r r e n t l yu s e di nt h ec d p s f i e l d ，e s p e c i a l l yt h e m u l t i a g e n tp l a n n i n gm e t h o d ，a n d t h er e l a t e d o r g a n i z a t i o nc o n s t r u c t i n gm e t h o d i n m u l t i a g e n ts y s t e m ( m a s ) f i e l da r ed e s c r i b e d , i ti sc l a i m e dt h a tc o m b i n a t i o no f 也e d p sa n dm a s s t u d y i n gi st h et r e n dt os o l v ec o m p l e xp r o b l e m s ，w h i c h i sa l s ot h ef o c u s o f t h i sd i s s e r t a t i o n s e c o n d 。t h eg e n e r a lm e a n i n go ft h es o c i a l i t yi sd i s c u s s e d a r e rt h a t ，f r o mt h e o b j e c t i v eo f t h ea i ，d a ia n dc d p ss t u d y , t h eq u e s t i o na b o u tw h y s t u d y i n gt h ec d p s s o c i a l i t yi sn e c e s s a r yi se x p l a i n e d ，a n dt h r e ek i n d so fg u i d i n gp r i n c i p l e sa r ec o m p a r e d ， e s p e c i a l l yt h ec o m p u t a t i o n a lp r i n c i p l e ，w h i c hi st h ep o i n t o fv i e wo ft h i sp a p e r b a s e d o nt h i s ，t h ec o n t e n t so ft h ec d p ss o c i a l i t ys t u d i e sa r ed r a w na n ds u m m a r i z c d a f t e r m a k i n g t h e s ep r e p a r a t i o n si nt h em e t h o d o l o g i c a la s p e c t , t h ew h o l ep r o c e s so f c d p si so u t l i n e d i ti sa r g u e dt h a t f r o mt h eg e n e r a t i o na n de v o l v e m e n to f t h em e m b e r s s o c i a l i t y , t h ew h o l ep r o c e s sc a nb ed i v i d e di n t o t w oi n t e r l e a v i n ga n di n t e ra f f e c t i n g l e v e l s ：p r o b l e ms o l v i n gl e v e la n ds o l v i n go r g a n i z i n gl e v e l a c c o r d i n g l y , t h e r ea r et w o m a j o rs u b p r o c e s s e sl y i n gr e s p e c t i v e l yi nt w ol e v e l s ：p r o b l e ms o l v i n gs u b p r o c e s s i nt h e 华中科技大学博士学位论文 p r o b l e r ns o l v i n gl e v e l ，a n ds o l v i n go r g a n i z i n gs u b - p r o c e s si nt h es o l v i n go r g a n i z i n g l e v e l 1 1 l o s ec h a r a c t e r i s t i c so f t h et w o s u b - p r o c e s s e sa r eb r i e f l yd i s c u s s c d e s p e c i a l l yt h e c o n c e p to f h o l o n w h i c hg r o u n d st h ec d p sp r o c e s s ，t o g e t h e rw i t ht h ec o m p a r i s o n b e t w e e nh o l o na n d a g e n t ，b e t w e e n h o l o na n dm a s a n dt 1 1 e a n a l y s i s o fi t s r e a s o n a b l e n e s sa n d a d v a n t a g e s n e x t , d r a w no nt h ei d e a so fb d ia g e n tf o n n a l i s ma n d3 a p la g e n tf o r m a l i s m t o g e t h e rw i t h 廿l eh i e r a r c h i c a lt a s kn e t w o r k ( a t n ) t a s kp r e s e n t a t i o ni nt h ed p s f i e l d i ti s a r g u e dt h a tt h eb a s i ch o l o m ec o g n i t i v ea t t r i b u t e ss h o u l di n c l o d eb e l i e l , g o a la n d i n t e n t a n dt h e nal o g i ef o 血a l i s mf r 鲫l l e w o r ko f h o l o ni sp r e s e n t e d t h ep r e s e n t a t i o no f h o l o n s 曲i l i t i e si sd i s c u s s e de s p e c i a l l y , b a s e do nt h ed i s c u s s i o no fi t s a d v a n t a g e s c o m p a r i n g w i t ht h e p l a n n i n g t r e ep r e s e n t a t i o nc o m m o n l yu s e di nt h em a sf i e l d t h e n , a r e c u r s i v ea l g o r i t h mo f t h e p r o b l e ms o l v i n gs u b p r o c e s sb a s e d o nt h eh o l o n c o n c e p ti sp r o v i d e do no n eh a n d ，t h ep r o b l e ms o l v i n go r g a n i z i n gs u b - p r o c e s s ，w h i c h r a i s e ss o e i a l i t y , i sd i s c u s s e di nd e t a i lo nt h eo t h e rh a n d b o t l li nt h eg e n e r a t i o nm o d e a s p e c ta n dt h ef u n c t i o nm o d ea s p e c t t h ef o r m e ri n c l u d e sn o to n l yt h eo o n c e d to ft h e r o l e ，i t sd e f i n i t i o n ，i t sf o n i l a l l s m , a n dt h ev a r i o u sr e l a t i o n s h i p sa r l o n gr o l e s , b u ta l s ot h e i n f l u e n c eo f s o c i a l i t yo nt h em c n t a ls t a t e so ft h es o l v i n gi n d i v i d u a lm e m b e r t h el a t t e r c o m p r i s e st h ea l g o r i t h me x p l a n a t i o no f t h i ss u b p r o c e s s ，a n dt h ed i s c u s s i o n sa b o u th o w t os e r l et h ee x p e c t a t i o ns o l v i n gr o l e s ，a n dh o wt oi d e n t i f yt h ep o t e n t i a lf o rc o o p e r a t i o n a tl a s t ，c o n s i d e r e dt h ec o m p l e xq u i c kt r a n s p o r t a t i o np r o b l e m ，w h i c ht a k e st i m e s a v i n ga st h em o s ti m p o r t a n tf a c t o ra n do o s tr e d u c t i o n 也eo p t i m i z a t i o np r i n c i p l e a n d w h i c h u s u a l l y a s s u m e s c o m p l e x c h a r a c t e r si n r c a l i t y s u c ha s o r g a n i z a t i o n a l b a c k g r o u n d s ，m a n yo f i t sc o n t a i n i n gs o c i a l i t yc h a r a c t e r sa r ec l a r i f i e d ，a n dac o n c e p t u a l f i a n l d o v o r ko ft h i sc d p s s y s t e mi sp r o v i d e d i na d d i t i o n , f r o mt h ev i e wo f ab i d d e ri n a na u c t i o n , i t sp r o b a b l es c h e m ef o rs o l v i n gt h ec o m p l e xt r a n s p o r t a t i o np r o b l e m ，i t s i n t e r n a l s t r u c t u r e ，i t sf i s s i o nr u l e s ，t h ep r e s e n t a t i o no ft h ec o r r e s p o n d i n gr o l e ，t h e e s t a b l i s h m e n to ft h er o l e - p l a y e r , t h em a k i n go fr e l a t i v ec o n t r a c t s a n ds oo na r e d i s c u s s e d m o r e o v e r , s o m ew o r d sa b o u tt h ea d v a n t a g e so fa p p l y i n gt h ei d e a sg i v e l lb y t h i sd i s s e r t a t i o nt ob u i l dt h eq u i c kt r a n s p o r t a t i o ns y s t e ma r es u m m a r i z e d k e y w o r d s ：c o o p e r a t i v ed i s t r i b u t e dp r o b l e ms o l v i n g ( c d p s ) ，s o c i a l i t y , h o l o n ，r o l e , o r g a n i z a t i o n ，c o n t r a c t ，f o r m a lm e t h o d v 华中科技大学博士学位论文 1 绪论 摘要：本章概述了合作分布式问题求解( c d p s ) 的特点、研究现状和难点，指出 合作是决定c d p s 性能的关键，由此必须深入认识其中的社会性。归纳了当前c d p s 领域中处理合作的主要方法，并详细综述了其中的多节点规划方法，以及多a g e n t 系统( m a s ) 领域中相关的组织构造方法。指出当前的研究趋势是融合两个领域 的研究成果，以处理更为复杂的问题求解，这也是本文的着眼点。最后，简要介 绍了本文的研究内容和意义。 1 1 课题来源 本学位沦文来源于下述科研项目： 1 华中科技大学2 1 1 工程重点项目“敏捷后勤与供应” 2 】国家自然科学基金项目“面向分布式供应链管理的组织决策支持的理论与 方法” 【3 】国家自然科学基金项目“基于知识的分布式建模支持理论与实现” 【4 】水利部黄河小浪底水利枢纽工程局科研项目“小浪底企业信息集成系统 ( x l de i i s ) 总体规划” 【5 】国家教育部全国教育事业“十五”计划和2 0 1 5 年规划重点研究课题“不同经 济发展水平地区高中阶段教育发展规划”、“不同经济发展水平地区学前教 育、特殊教育发展规划” 【6 】高等学校优秀青年教师教学和科研奖励基金资助项目“中国县级教育规划 与监控决策支持系统” f 7 】广东乐百氏集团公司科研项目“乐百氏集团总公司企业信息化总体发展战 略及信息化建设” 1 2 合作分布式问题求解的特点及其研究现状 1 2 1 合作分布式问题求解及其特点 合作分布式问题求解c d p s 是分布式人工智能d a i 的一个较大的子领域。d a i 主要研究在逻辑上或物理上分散的智能系统( 节点) 如何并行地、相互协作地进 行问题求解，即研究智能协调：在一个充斥有其它带有各自目标的智能系统的世 华中科技大学博士学位论文 界中，智能系统如何做决策，以实现其目标? 当决定要采取的动作时，一个智能 系统应该使用它的所有知识，以考虑其他智能系统的潜在动作以及这些动作的影 响。所以不论智能系统之间是合作的、共存的、还是相互竞争的，对其他智能系 统的推理都是必要和重要的，协作是决定性能好坏的核心。 合作分布式问题求解c d p s 研究一组松散耦合的问题求解节点所组成的网络 如何能一起工作。以求解超越任何个体能力之外的问题。具体来说： 关于问题：范围从简单的a i 领域玩偶问题到复杂的社会技术问题； 关于求解：问题表达与分解，各种推理技术，知识库，自动推理系统： 关于合作：各种协作技术，手段和机制。 合作问题求解系统一般具有下列特点： 系统中的数据、知识。以及控制在逻辑和物理i ：都是分布的； 各求解机构由计算机网络互连，在求解过程中通信代价要比求解问题代价 低得多： 系统中各机构能够相互协作。 如同其名字所暗示的那样，c d p s 着眼于自治智能系统之间的合作形式。网络 中的各个问题求解节点能执行复杂的问题求解，能独立工作，但是节点所面临的 问题必须通过合作来完成。合作是必要的，因为没有单个节点具有足够的专长、 资源和信息来求解问题。但是这里的合作并不单纯指节点之问存在“善意”假设， 即各个节点都无条件地尽力帮助他人：而是说无论节点之间是否存在私有的不同 目标、不同观点，节点都必须一起工作，来实现共同的和各自的目标。e h d u r f e e 等认为c d p s 中合作的一般目的有l l j ： 1 ) 通过并行性增加任务完成的速率： 2 ) 通过共享资源( 信息、专长、物理设备等) 增加能实现的任务的范围； 3 ) 通过承担重复的任务增加完成任务( 可靠性) 的可能性，可能使用不同方 法来执行那些任务： 4 ) 通过避免有害的交互来减少任务之问的干扰。 为什么需要c d p s ? 即为什么不能构建一个单一的、足够有力的问题求解者? 1 ) 技术问题。硬件技术的进步使联结大量异步执行的处理器成为可能，范围 从通过共享或分：；f j i 式记忆而紧密耦合的处理器群，到通过一个局部领域通 讯网络而松散耦合的处理器群，以及通过一个通讯网络而非常松散的耦合 的、地理上分布的处理器群。 2 ) 许多a i 应用内在就是分布式的：比如空间分布、功能分布、时间分布等。 c d p s 管理分稀的数据、专长、处理能力和其他资源，比单一、集中式的 华中科技大学博士学位论文 问题求解具有更多的优势，包括：借助于并行性的更快的问题求解速度： 通过仅仅传输高层部分解到邻近节点，而不是传输原始数据到中央站点来 减少通讯量；通过将拥有不同能力的问题求解者动态组织起来求解当前问 题而获得更多的柔性；通过使问题求解者承担重复的责任来增加可靠性， 等等。 3 ) 模块化的设计和实施原则。实践证明，将复杂问题组织成相对自包含的处 理模块可以导致系统构建、调试和维护更为容易和简单。 4 ) 认识论基础。合作，或者更一般的协调，是复杂的现象，对它们的理解还 远远不够。c d p s 系统能帮助校验社会学、管理学和组织理论中的理论： 而在这些研究中所发展的技术还可以导致更有效地利用计算机，作为改善 人们之间协调的工具。 5 ) 社会学基础。a i 的一个目标是发展能成为我们日常世界一部分的系统，这 些系统能执行许多平凡的、枯燥的、要求一定智能的工作。这些系统必须 能与人类相交互，所以a i 系统必须具有灵活地、智能地合作和协调的能力， 不论是系统相互之间还是系统与人类之间。尽管这个长期目标的实现还很 遥远，但c d p s 确实代表了朝向它努力的方向。 1 2 2c d p s 的研究现状与难点 k s d e c k e r 等人认为，c d p s 研究必须解决的基本问题，包括【2 j ： ， 1 ) 发展在小群体中，以及在大型网络中组织、构建c d p s 系统的理论，指导 如何基于应用、求解节点和通讯资源的特点来在求解节点中分布领域级的 和控制级的问题求解任务； 2 ) 为在全异的求解节点中实现领域级的合作而发展能有效消解不一致、并集 成结果的范例； 3 ) 发展分布式控制的方法，以允许自治、半自治的求解节点以全局一致的方 式来工作，尽管存在关于其他求解节点动作状态的不确定性： 4 ) 发展组织或构造个体求解节点问题求解动作的指南( 知识表达、推理技术、 控制体系) ，以能容易地将它们集成进一个c d p s 环境中； 5 ) 就语言和操作系统特点来说，发展支持c d p s 计算风格的软件基础设施。 可以看出，这些问题都是围绕如何实现有效的合作，因为合作是决定性能好 坏的核心。 e h d u r f c e 等提出c d p s 中有效协调要求的三个条件是【i 】： 1 ) 要求具有一定的结构，否则节点的交互不可预测。结构体现在诸如组织和 华中科技大学博士学位论文 承诺协议等共享信息中。 2 ) 要求柔性，因为节点典型地存在于一个动态变化的环境中，各个节点可能 拥有不完整的、不正确的、或者过时的信息。 3 ) 要求知识和推理能力，以智能地利用结构和柔性。节点必须形成和推理他 们正在做什么他们的目标、规划和信念，并且形成和推理这些如何与 他们所知的他人情况相符。他们必须依赖于结构来引导这种推理，但是必 须允许他们自身拥有根据变化的场合改变其活动的柔性。一句话，节点需 要足够的局部复杂度。 过去几十年来，人们对合作问题求解这一领域进行了大量、广泛的研究。上 世纪9 0 年代以前，c d p s 的研究局限于较为简单的问题，强调对问题本身的分析， 讨论特定问题的结构，以此寻找各种求解方法；其研究的角度主要着眼于知识角 度，强调基于知识的表达、推理、集成合作仅仅是异质求解主体之间求解知识 的合作；- 研究的目的是问题求解的一致性、效率和速率。所以这个阶段虽然发展 了许多实用的专家系统，但其研究和应用常常依赖于特定领域，节点的自治性、 智能性都不高，所能求解的问题十分有限，而且对合作现象的理解无论从广度还 是深度来说都是不够的。 - 9 0 年代以后。随着d a i 领域中多a g e n t 系统( m a s ) 理论的兴起。人们逐渐 将两个子领域结合起来考虑，两者互相融合，互为补充使求解能力逐渐扩大到 处理复杂的现实世界问题。人们在广泛吸取相关学科研究成果的基础上，不断研 究新的问题，探索赣的求解方法，发现新的合作形式，在理论和实践两个方面都 取得创颞。 当前，c d p s 的研究难点包括： 复杂问题难于表达甚至难于界定，问题可能是动态形成、逐渐清晰的，涉 及定性、定量等多方面； 需要综合利用各种求解技术，需要人机协作： 需要综合利用各种协作技术，特别需要处理不确定性和动态性： 需要发展能全面评价c d p s 研究的评价体系。 1 3 相关文献综述 1 3 i c d p s 的主要方法 迄今几乎每一种方法的发展都受到一种应用领域背景的驱动和评价。 4 华中科技大学博士学位论文 e h d u d 等认为，c d p s 的方法可以分类为如下范畴【1 1 ： 1 ) 协商 2 ) 功能准确的合作f a c ( f u n c t i o n a l l y a c c u r a t e , c o o p e r a t i v e ) 3 ) 组织构造使用关于一般问题求解角色和通讯模式的公共知识，以减少 节点之间应该如何合作的不确定性； 4 ) 多节点规划 5 ) 复杂的局部控制 6 ) 理论框架 协商方法是指由一个节点将问题分解为多个予问题，并按某种投标机制在各 节点之间分配子任务。协商是一种重要的、广泛使用的合作策略，协商允许节点 通过交换任务来改善计算资源和专长的利用效果，通过并行性来增加解的生成速 率，通过分派同一任务给具有不同专长的节点来增加解生成的确定性和可能性。 但协商却是一种复杂的、多变的现象，迄今c d p s 研究者仅仅能研究它的些特 定形式，其中最著名、最常用的协商协议是合同网。在合同网协议中，节点通过 契约来协调他们的活动，以实现特定的目标。契约的细化遵从上到下的方式，细 化过程直到节点能独立完成一个契约为止。契约细化过程的结果就是一个管理者 定约者控制关系网络【3 j 。其应用非常广泛，早期的著名案例是飞彳亍交通控制领域中 的协商f 4 1 。 功能准确的协作方法( f a c ，f u n c t i o n a l l y a c c u r a t e ，c o o p e r a t i v e ) 是指各节点 依据自身对问题的有限看法，生成并交换尝试性的部分结果，通过反复地交换可 能是不完全、不准确和不致的部分求解结果，最终求出整个问题的解。如何使 用其他节点的试验性结果，以及出现矛盾时如何消除不良影响，是f a c 协作方式 中需要解决的关键问题。该模型最早由v r l e s s e r 、d d c o r k i l l 等人在实现分布 式h e a r s a y - l i 系统中提出i 5 1 ，主要适用于不确定环境下多节点问的连续协作求解。 其后提出的黑板结构常常被使用作存储多个存在相互竞争的假设的、半结构化的 仓库。姚莉等人针对军事态势估计问题求解提出一种改进的模型基于假设的 f a c 协同模型1 6 1 ，他们将协作求解过程分为三个基本部分；选择机制、推理机制 和分布式真值维护机制，然后从证据的动态积累和试探性结论中不确定性的消除 二个角度对原f m c 方法进行了改进：采用类似于基于假设的真值维护方法，作为 表示试探性求解以及识别和消除错误结论的基本框架；引入“论据结构”，即节点 间交换的试验性中间结果。据此节点可对外部结果进行分析比较以改善自己的求 解性能。 华中科技大学博士学位论文 怫商和f a c 的一个主要区别是，协商采用从上到下的问题求解观点，而f a c 则相反。f a c 允许求勰内在分布的问题的节点半自治地工作，并且通过通讯来构 建全局勰，尽管各自都不知道他人对总体解的贡献。这里一个困难就是这种无知 会导致过度的通讯和节点之间努力的重复，一般会使网络资源的使用变得低效。 相反，诸如定契约等的协商形式允许节点分解和分派他们的问题求解责任，组织 他们的活动和交互，以如同团队一样更有效地工作。这种方法的难点在于，对于 内在分布的问题而吉，节点可能最初并不知道他们试图求解什么特定问题。此外， 他们对予问题的感知也是随着问题求解而变化的，说明了需要动态调整节点之问 的合作关系。 组织构造方法试图找到一种介于定契约的从上到下观点和f a c 的从下到上的 观点之恻的平衡点。为使协作更为有效节点问应能预见何时将交换什么样的部 分解，以调整它们的解题规划和行为，减少不必要的行为和l “此产生的通信，1 ：销。 但这需要每个节点不但清楚自己的规划，而且还要了解其它节点的规划。由此可 见，预见能力是协作的关键因素。人们从人类协同工作的过程中得到了启发，提 出了组织结构的概念，利用组织结构定义各节点在系统中扮演的角色、行为、期 望和权限等关系。以此来反映它们之间的信息和控制关系、能力的分布情况以及 通信协定。为节点间提供一个基本的协作框架，每当一节点生成新的信息或需要 信息时，它可以求助于组织结构确定它要交互的对象，使节点间具有预见彼此的 可能行为的能力。尽管定约方法动态地定义了节点之间求解特定问题的关系，但 是一个组织结构提供了关于节点间关系的更一般的长期信息，即契约代表了暂时 的联盟，而组织则代表更持久的关系。 d d c o r k i l i 和v r l e s s e r 在一个c d p s 仿真测试平台：分布式车辆监控测试 平台中应用了组织结构【7 1 ，他们使用组织结构来限制节点所作的控制决策的范围， 减少了对节点信息处理能力的要求确保决策制订所需的信息都传递到适当的节 点处。这单组织结构提供了一种控制框架，通过为网络问题求解提供一般的、全 局的策略，增加了节点如同一致团队工作的可能性。姚莉针对处理大粒度节点集 成的d a i 系统，认为系统整体组织的设计应先于个别节点，各节点的性质依赖于 整体组织的定义。于是提出“系统组织模型”的概念1 8 l ，定义了d a i 系统的组织 结构、形式和组织原则，比如组织原则包括：知识分布策略、任务分布策略、协 作控制策略、通信策略等。这些定义形成关于一个组织的法律和规范，建立了系 统级全局承约，规定系统求解时各节点的意图和行为必须以之为前提。魏宝刚等 认为，随着知识数量、种类和知识源问的关系复杂程度的增加，问题仅依靠静态 分析描述很难弄清楚，对d a i 中协作问题的研究必须从静态和动态两方面入手。 于是他们一方面用一个静态结构定义每个节点在问题求解系统中所处的地位、所 华中科技大学博士学位论文 扮演的角色，从而大致确定它所采用的推理策略和交互方式；另一方面用一个动 态组织结构来定义各节点的动态特征，使组织结构具一定的修难其交互模式的能 力，以适应变化的环境【9 】。e h d u r f e e 等认为，一个静态的组织结构并不总能确保 一致的网络行为o l 。但因为网络重组织是费时费力的，并且不能预先预测特定的 问题特点，所以应该选择能在长远情况下获得可以接受的、一致的性能的组织结 构而不是在非常少的情景下得到非常好的性能的组织结构。个可接受的组织 结构将提供给节点足够的灵活度，以对变化的情景做出适当的反应。但其麻烦在 于，他们也为节点提供了可能导致不一致网络行为的决策自由度。给定所能扮演 的角色范围，节点需要解决：他们在当前情景下应该扮演什么角色的问题。实质 上，这是又一个c d p s 问题，需要节点一起求解。d u r f e 圯等扩展了组织构造方法， 发展了一个元级组织，规定了网络中的节点应该如何合作地决定如何一起求解问 题】。即用元级组织来组织节点的协调活动，而用分离的领域级组织则组织他们 的领域级问题求解活动。 关于组织构造的方法近来大多从m a s 领域吸取研究成果下- d , 节对m a s 领域的组织理论进行详细综述。 多节点规划常常用于c d p s 网络以识别和规划资源冲突。在多节点规划的合作 方法中，节点规定他们的所有未来动作和交互。该方法的独特性在于，一个或多 个节点处理的计划准确指明了各个节点在网络活动期间将要采取的动作和交互。 这不同于组织结构所施加的一般指南，也不同于诸如定约方法等协商方法，后者 中典型地节点做出关于他们将要进行的协调的成对的承诺，并且其中没有表达任 何网络协调的完整观点。定约能导致不一致的行为，而这是多节点规划所避免的。 多节点规划坚持在不一致发生之前就检测和避免，所以也不同于f a c 。由于坚持 在动作和交互之前就做出规划，多节点规划要求节点共享和处理大量信息，所以 比其他方法要求的计算和通讯资源要多。 e h d u f f e e 认为，分布式多节点规划与c d p s 紧密交织，本身既是一个问题， 同时又是解决问题的一种手段【i 2 l 。因为有时多节点要解决的问题是生成一个规划， 并且常常，即使节点正在解决其他类型的问题，他们也不得不同时解决规划问题。 所以可以说，多节点规划是c d p s 中的一个重要的子领域。本研究也将合作问题 求解视作生成一个用于仿真的规划问题，所以在1 3 3 中进行更详细的综述e c d p s 中的节点必须比单独工作的节点来的复杂，因为它必须推理自己的问题 求解，自己的活动是否符合于其他节点的活动，以及为改善网络问题求解自己可 以做什么等。协调的获得并不仅仅通过交换信息；节点必须推理信息豹表达内容， 以及信息交换将如何影响个体的和群组的行为。复杂的局部控制要求节点理解其 华中科技大学博士学位论文 他节点目标、信念和计划、问题求解行为以及通讯动作的含义，这种理解就形成 了协调决策的基础。复杂的局部控制着眼于构建能自主决定如何和什么时候进行 协调的节点，以及发展适当的通讯策略。m a s 领域中对于a g e n t 的研究可以作为 复杂节点设计的基础，m a s 的主体结构研究方面主要有基于符号逻辑的慎思结构 ( d e l i b e r a t i v ea r c h i t e c t u r e ) 和基于b r o o k s 行为主义的反应结构( r e a c t i v e a r c h i t e c t u r e ) ，更为常用的是介于二者之间的混杂结构。此外，对a g e n t 结构的更高 要求是具有适应性，比如f 1 3 l 和0 4 1 。这方面的综述很多，这里不再详述。 尽管对特定应用领域的技术取向主导了c d p s 的研究，但是大量研究者却着 眼于c d p s 的形式化模型，使用基于逻辑的或者对策理论的节点。形式化的c d p s 方法试图使用节点推理和交互的严格模型来发展对协调的认识。 c d p s 研