第十四章分布式人工智能81.ppt

史忠植 高级人工智能 协调 　多主体系统中的协调是指多个主体为了以一致、和谐的方式工作而进行交互的过程。进行协调是希望避免主体之间的死锁或活锁。 死锁指多个主体无法进行各自的下一步动作； 活锁指多个主体不断工作却无任何进展。 史忠植 高级人工智能 协作 　目前针对主体协作的研究大体上可分为两类： 将其它领域研究多实体行为的方法和技术用于主体协作的研究。如对策论和力学研究。 从主体的目标、意图、规划等心智态度出发来研究多主体间的协作。 史忠植 高级人工智能 协作规划 协作的动机： 某个主体相信通过协作能带来好处（如提高效率，完成以往单独无法完成的任务） 多个主体在交流的过程中，发现它们能够通过协作来实现更大的目标。 史忠植 高级人工智能 协作过程 产生需求、确定目标 协作规划、求解协作结构 寻求协作伙伴 选择协作方案 实现目标 评估结果 史忠植 高级人工智能 协作模式 从社会心理学的角度看，多主体之间的协作情形大致可分为： ·协作型：同时将自己的利益放在第二位。 ·自私型：同时将协作放在第二位。 ·完全自私型：不考虑任何协作。 ·完全协作型：不考虑自身利益。 ·协作与自私相混合型。 史忠植 高级人工智能 协作策略 ·计算生态学 ·对策论 ·规划 史忠植 高级人工智能 计算生态学 80年代末，在计算机中出现了一个崭新的学科---计算生态学(the ecolog of computation)。计算生态学是研究关于开放系统中诀定计算结点的行为与资源使用的交互过程的学科。它摒弃了封闭、静止地处理问题的传统算法，将世界看作是开放的、进化的、并发的, 通过多种协作处理问题的＂生态系统＂ (ecosystem)加以研究。它的进展与开放信息系统的研究息息相关。 史忠植 高级人工智能 计算生态学 计算生态学将计算系统看作是一个生态系统，它引进了许多生物的机制，如变异(mutation)即物种的变化。这些变化导致生命基因的改变，从而形成物种的多样性，增强了适应环境的能力。这类变异策略成为人工智能系统提高其自身能力的一种方法。Lenat与Brown成功地将变异机制引入他们的AM与Eurisko系统中, 通过小型Lisp程序的语法变异发现数学概念。他们认为未来成功的系统应该是一系列进化的、自组织的符号知识结构的``社会系统。 史忠植 高级人工智能 生物生态模型 这是最著名的生态系统，具有典型的进化特征和层次性。这种特性反映在“食物链”中。对于复杂的生物生态系统而言，各物种组成了紧密相连的网络－---食物网。这个系统的主要角色是捕食者与被食者。生命依赖于生命，共同进化，由小的生态环境组成大的生态系统。 史忠植 高级人工智能 物种进化模型 物种进化的“复制者”是基因。从门德尔的植物遗传研究到现代遗传学的成果，都说明了在物种进化过程中，基因的组合与变异起着关键作用。在一个物种的某一群体中基因的集合称为基因池。生物组织是基因的载体。如果环境变化，选择的机制就会改变。这种变化必然引起基因池的变化。特定种群的基因变化称为基因流。一个物种总是不断地经历隔绝、基因流动、变化的循环。开始时，一组地理上隔绝的群体自己孤立地发展，基因在内部快速地流动。随着开放，通过交流和竞争，优胜劣汰。 史忠植 高级人工智能 经济模型 经济系统在某种意义上类似于生物生态系统。在商品市场和理想市场中，进化决定于经济实体的决策。选择机制是市场奖励机制。进化是快速的，企业与消费者之间、企业之间主要是一种互相依赖的合作关系。决策者为了追求长远利益，可以采取各种有效的方法，甚至可以暂时做赔本买卖。 史忠植 高级人工智能 协商模型 Zlotkin的面向领域的协商理论 Zlotkin的协商理论假设： ? 各主体追求本身效用最大。 ? 知识完备。 ? 无历史信息。 ? 目标集固定。 ? 协商在两主体之间同时进行。 ? 主体操作集相同。 ? 世界仅当主体操作之后发生变化。 史忠植 高级人工智能 面向领域的协商理论 在协商过程中，若存在一个双方满意的分配，可以得到一个联合规划, 使协商终止的条件是： (1) 达成协议：如果 Utility(P(i,t)) ? Utility(P(i,t-1)), 这一协商过程将在有限步内结束。 (2) 冲突： 如果 Utility(P(i,t)) = Utility(P(i,t-1)), 则无法达成协议。 史忠植 高级人工智能 最佳平衡 传统的协商是基于Nash平衡的,它的缺点是Nash 平衡产生多个平衡点, 对结果约束较少。Kraus使用Rubinstein的“最佳”平衡(Perfect Equilibrium, 简称P.E.)理论, 建立了一种基于