（计算机应用技术专业论文）基于多agent的pcb装配调度系统.pdf

华中科技大学硕士学位论文 摘要 p c b 印刷电路板 装配车间的生产具有多品种 小批量 制造周期短 质量要求 高 不确定性事件多等特点 它的调度问题是j o bs h o p 调度问题 是不存在多项式 时间复杂度纯优解法的n p 问题 在调度问题的各种研究方法中 基于分布式人工智 能技术的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 的p c b 装配调度系统 m a p s 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 的概念 m a p s 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 之间 流动 并在作 业完成后撤销 m a p s s 是动态实时调度系统 它在每个调度时刻计算作业的优先级 将作业按优 先级排序 优先级高的作业先获得资源执行 而对于相同优先级的作业采用一种启发 式搜索算法求解 这种调度策略既保证调度的实时性又保证解的次优性 m a p s s 采用 基于合同网协议的k q m l 的消息机制进行通信和协作 合同网的协商过程包括 所有 结点注册初始化 管理者发布任务 契约者投标 管理者发标以及中标者执行五个过 程 m a p s s 的作业调度就是多a g e n t 之间反复地应用这 协商过程实现的 m a p s s 利用a g e n t 基于知识的推理能力和多a g e n t 之间的协作机制 避开了 组 合爆炸问题 不必进行大量的计算 可以在较短的时间内获得调度问题的近优解 此外 系统还有动态可扩展性 鲁棒性等特点 关键词 a g e n t 多a g e n t 系统 j o bs h o p 调度 合同网 k q i v l l 华中科技大学硕士学位论文 a b s t r a c t t h ep c b p r i n t e dc i r c u i tb o a r d a s s e m b l i n gh a st h ef o l l o w i n gc h a r a c t e r s v a r i o u sp r o d u c t s as m a 1b a t c h s h o r tm a n u f a c t u r i n gp e r i o d h i g hq u a l i t y r e q u i r e m e n ta n dm a n yu n c e r t a i ne v e n t s t h es c h e d u i i n gp r o b l e mi saj o bs h o p s o h e d u l i n gp r o b l e m a n di t i san p c o m p l e r ep r o b l e mw i t h o u tp u r e o p t i m a l s o l u t i o no fp o y n o m i a lt i m ec o m p l i c a t i o n t h e r ea r em a n ym e t h o d st os o l v et h e s c h e d u li n g p r o b l e m t h ea g e n t a n dm u l t i a g e n t s y s t e m w h i c hd e r i v ef r o m d i s t r i b u t e da 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 y b e c o m ec u r r e n tr e s e a r c h s h o t s p o t a g e n th a sa u t o n o m y p r o a c t i v it y r e a c t i v i t y s o c i a l i t ya n ds oo n c h a r a c t e r s w h i l em u l t i a g e n ts y s t e mh a sd y n a m i cc h a n g e a b l ea r c h i t e c t u r e t h e s ec h a r a c t e r so fa g e n t t e c h n o l o g y a r ef i tf o rs o l v i n gt h es c h e d u l i n g p r o b l e m s t h ep c ba s s e m b l ys c h e d u l i n gh a sc o m p u t i n gc o m p l e x i t y d y n a m i cr a n d o m i c i t y a n dm u l t i g o a lc h a r a c t e r s t h ea g e n tc o n c e p tc a nb eu s e df o rt h ew o r k s h o p w o r k i n gc e l lm o d e l i n g a n dj o ba g e n t r e s o u r c ea g e n t m a c h i n ea g e n ta n d m a n a g e ra g e n ta r em o d e l e d f u r t h e r m o r e am u l t i a g e n tb a s e dp c ba s s e m b l y s c h e d u l i n gs y s t e m m a p s s m o d e l i sc o n s t r u c t e d m a p s si sa h i b e r a r c h y m u l t i a g e n tm o d e l t h em a n a g e ra g e n ti so nt h et o pl e v e l t h er e s o u r c ea g e n t i si nt h em i d d l e a n dt h em a c h i n ea g e n tiso r lt h eb o t t o m t h ej o ba g e n ti s d y n a m i c a l l yc r e a t e dw h e nt h es y s t e mg e t sn e wo r d e r s t h e ni tf l o w sa m o n ga g e n t s i nt h ee n di ti sc a n c e l e dw h e nt h ej o bi s c o m p l e t e d m a p s si sad y n a m i c a lr e a l t i m es c h e d u l i n gs y s t e m i tc o m p u t e st h ej o b p r i o r i t yi ne a c hs c h e d u l i n gm o m e n t o r d e r st h ej o b s a n dj o bw it ht h eh i g h e s t p r i o r i t yf i r s tg e t st h er e s o u r c et oe x e c u t e i na d d i t i o n f o rt h e j o b sw i t h t h es a m ep r i o r i t i e s ah e u r i s t i cs e a r c ha l g o r i t h mi s d e s i g n e d t h i sk i n do f s c h e d u l i n gs t r a t e g y c a t a s s u r et h e r e a l t i m e s c h e d u l i n g a n d o p t i m a l a p p r o x i m a t i o ns o l u t i o n n 华中科技大学硕士学位论文 m a p s su s e sa c o n t r a c t n e t p r o t o c o b a s e dk q m lm e s s a g em e c h a n i s mf o r c o r n m u n i c a t i o na n dc o l l a b o r a t i o n t h ea g e n tn e g o t i a t i o ni n c l u d e sf i v es t e p s a l lc o n t r a c t o rn o d e sr e g i s t e r i n ga n di n i t i a l i z i n g m a n a g e rn o d ec a l l i n gf o r p r o p o s a l c o n t r a c t o r n o d e s b i d i n g m a n a g e rn o d ea c c e p t i n gp r o p o s a la n d a w a r d e rn o d ee x e c u t i n gt h et a s k t h ej o bs c h e d u l i n go fm a p s si sr e a l i z e db y t h en e g o t i a t i n gw i t ho t h e ra g e n t sr e p e a t l y m a p s su s e st h e a g e n t sr e a s o n i n ga b i l i t y a n d t h e m u l t i a g e n t s c o l l a b o r a t i o nm e c h a n i s mf o rt h e j o bs h o ps c h e d u l i n g s o a st oa v o i d c o m b i n a t i o n b o m b i n gp r o b l e ma n d v a s t c o m p u t i o n i t c a na c h i e v e o p t i m a l a p p r o x i m a t i o ns o l u t i o ni nas h o r tt i m e i na d d i t i o n t h es y s t e mi sd y n a m i c a l l y s c a l a b ea n dr o m s t k e y w o r d s a g e n t m u l t i a g e n ts y s t e m j o bs h o ps c h e d u l i n g c o n t r a c tn e t k q m l i i l 华中科技大学硕士学位论文 1绪论 1 1 课题背景 本课题的研究背景是 武汉邮电科学研究院c i m s 应用二期工程 该项目是国 家8 6 3 计划资助的c i m s c o m p u t e ri n t e g r a t e dm a n u f a c t u r i n gs y s t e m 计算机集成制 造系统 重点应用工程 本课题是关于柔性制造车间调度问题的研究 武汉邮科院的p c b p r i n t e dc i r c u i tb o a r d 印刷电路板 装配调度是柔性车间 调度 装配车间的生产具有品种多 批量小 制造周期短 质量要求高等特它的不确 定性事件出现的频率明显高于传统的制造环境 此外 p c b 生产的另一个显著特点是 按用户订单组织生产 属于用户全定制 车间调度是根据生产系统现状与生产目标 在满足一定约束的条件下 实现机器 材料等资源的合理配置和有效利用 这一调度 问题被证明为不存在多项式时间纯优解法的n p 问题 以往仅仅依靠人工的途径进行 调度难免出现资源分配不合理等问题 因此有必要做调度系统方面的研究 柔性制造车间调度是计算机集成制造企业生产控制中的重要一环 现代产品市场 的发展对生产调度的快速反应能力和精确性也提出了更高的要求 对调度的研究不但 有理论价值 而且有实际应用意义 好的调度系统能大大提高企业的生产效益 降低 生产成本 更快的满足用户的需要 从而占领市场份额 创造经济效益 企业迫切需 要一类能解决生产现场实际问题的调度工具 改变目前依靠人工调度周期长 不准确 的现状 真正达到计算机指导或辅助指导生产过程的目的 1 2 关键技术及国内外概况 1 2 1j o bs h o p 调度问题 生产调度问题按加工系统的复杂度 可以分为单机 o n es t a g e o n ep r o c e s s o r 多台并行机 o n es t a g e m u l t i p l ep r o c e s s o r s f l o ws h o p m u l t i s t a g e 和j o b s h o p m u l t i s t a g e 四种 单机和多台并行机要求一个加工步骤必须在一个或单独在 多个资源上执行 而f l o ws h o p 和j o bs h o p 中每个作业有多个任务 每个任务要求 不同的资源 f l o ws h o p 的加工路线固定 而j o bs h o p 的加工路线不固定 即是柔 华中科技大学硕士学位论文 性的 显然 在这四种问题中j o bs h o p 调度最为复杂 典型的j o bs h o p 调度问题包括一个要完成的作业集 每个作业由一个任务集组 成 任务有时间上的偏序关系 各任务的完成需要占用资源 此外 作业可以有批量 和交货期等 在这样的柔性加工系统中 作业具有柔性任务加工路线 即作业的各操 作在哪一台机器上加工是不固定的 j o bs h o p 调度问题是 个复杂的问题 它发生在开放的动态的环境中 它有以下 特点 复杂性 由于j o bs h o p 调度问题是在等式或不等式约束下求性能指标的优 化 在计算量上是n p 完全问题 1 因而使得一些常规的最优化方法往往无能为力 动态随机性 车间一般是边生产边调度 生产过程中可能发生不可预料的问题 如机器故障 作业取消 资源短缺 作业延期等等 同时某一时刻机器的状态 忙或 闲 作业任务的到来 机器和任务的组合方式等等具有随机性 多目标 调度往 往是根据不同的情况设定多个不同的目标 并且这些目标间可能发生冲突 这些目标 大致可以分为三类 基于作业交货期的目标 基予作业完成时间的目标 基于生产成 本的目标等 具体的有 总迟滞时间最小 延期作业数目最小 系统和资源利用率最 大 在处理数量 i n p r o c e s si n v e n t o r y 最小 平均资源使用率 最大生产率等等 生产调度根据作业的加工特点 可分为静态调度和动态调度 静态调度是指所有 待安排加工的工作均处于待加工状态 只涉及生产计划 工艺计划和资源特征等静态 信息 可以预先依次排定各个工件的加工步骤及所需资源 因此静态调度也称预调度 动态再调度是指工件依次进入待加工状态 各种工件不断进入系统接受加工 同时完 成加工的工件又不断离开 还要考虑生产调度环境中不断出现的动态扰动 如工件的 加工超时 设备的损坏等 因而需要在新的时间和状态起点上重新做一遍调度 动态 实时调度指在事先没有进行预调度的情况下 根据当前系统的状态 对下一步的控制 活动作出调度 它不是一下子产生全天的作业调度单 而是不定时的产生调度命令序 列 为了产生这些命令 调度系统需要收集大量的现场数据 1 动态实时调度的优点 是现场反应速度快 调度命令可执行性好 它最能满足实际生产的需求 但比较复杂 而静态调度适于评价方案的优劣 为系统设计提供参考 动态再调度在一定程度上考 虑了环境及系统内部变化对调度的影响 但过渡频繁的再调度使系统经常处于停滞等 待状态 不利于生产的顺利进行 华中科技大学硕士学位论文 1 2 2 调度问题的研究概况 二 调度的研究有四十多年了 总的来说研究方法主要有 数学规划 分布式规则 专家系统 搜索技术 仿真技术 离散时间系统解析模型 模拟退火 神经网络和遗 传算法等等 确定性最优化方法是一种数学规划方法 它主要是通过对调度问题建立一个整数 规划模型 采用基于枚举思想的分枝定界或动态规划算法进行求解 这类方法虽然从 理论上能求得最优解 但由于其计算复杂性的原因 不能获得真正的实用 调度规则易于实现 计算复杂度低 常用于动态调度系统中 规则可分三类 简 单规则 复合规则和启发式规则 基于知识的调度方法使用专家系统自动产生调度或辅助人去调度 其中有一种基 于调度系统状态不同采用不同的调度规则策略的动态调度方法 它的特点是 在支持 某些活动发生的资源条件具备时 根据系统当时所处的属性状态 决定采取何种规则 确定或选择活动发生的顺序和时间 即所谓的状态指导的智能调度方法 一般的搜索技术是基于宽度优先的回溯算法 文献 8 提出了一种智能回跳启发 搜索技术 它有三个特点 1 动态恒坚持 即动态地专注于小的紧急的子问题 2 从失败中学习 即基于以往冲突修改自身 3 回跳启发 即当冲突产生时 取消那 些没有证明是不一致 但似乎过度限制的任务 这种方法有很好的智能性和学习能力 但不是基于a g e n t 协商 禁忌搜索是对于复杂的组合优化问题通过领域搜索以获取最优解 启发式图搜索 是对于整数规划问题 用d i s j u n c t i v e 图表述 首先构造一个可行解 然后用搜索方 法不断提高解的次优性 这种方法对于较大规模的问题搜索效率很低 基于纯仿真模型的调度方法 即在一个较短的时间段内用仿真来评价一个分派规 则集 选择最小代价规则 以适应系统状态的变化 1 文献 9 采用面向对象的方法 研制开发了具有实时在线仿真能力的f m s 仿真语言s l f m s 文献 1 0 基于工艺柔性和 小车实时性两类f m s 调度算法 提出综合实时调度算法 它兼顾了加工过程中的柔性 和运输系统的实时性 同时考虑资源的数量的限制等实际约束条件 虽然这种方法可 以包含解析模型无法描述的因素 并且可以提供给使用者一个调度性能测试机会 但 华中科技大学硕士学位论文 它存在以下问题 缺乏理论意义 应用仿真进行生产的费用很高 仿真的准确性很大 程度受编程人员的判断和技巧的限制 现有的比较著名的调度仿真软件如 s i s c r i p t i s i s 等 大都局限于静态调度 用于咨询 辅助规划或教学 离实际指 导生产还有一段距离 动态实时调度还处于研究阶段 无成熟的商品化软件 由于制造系统是一类典型的离散时间系统 因此可以用研究离散时间系统解析模 型和方法解决调度问题 如排队论 极大极小模型和p e t r i 网等 排队论方法是一种 随机优化方法 它将每台机器看成一个服务台 将每个加工任务作为一个客户 用 p e t r i 网为调度系统建模 通过优化变迁的发生序列来产生标识集 从而得到次优的 调度结果 文献 1 1 利用时间p e t r i 网对f m s 调度问题进行建模 满足约束条件的 p e t r i 网模型将调度问题限制在可行调度区域内 文献 1 2 用模糊着色p e t r i 网对p c b 装配制造建模 但p e t r i 网存在以下问题 节点语义的单义性使所携带的系统信息量 不够丰富 重用性差 很难对高级的调度规则建模 模拟退火法是将组合优化问题与统计力学中的热平衡问题类比 通过模拟退火过 程 可以找到全局或近似最优解 模拟退火法能以一定的概率接受差的能量值 因而 有可能跳出局部极小 但它的收敛速度较慢 很难用于实时动态调度环境 神经网络方法是由h o p f i e l d 提出 用于解决各种约束优化问题 有约束的资源 调度问题首先被分解成一系列多维背包模型并且为背包模型建立了一个等价的 h o p f i e l d 神经网络 然后通过扩展h o p f i e l d 网络 给出了 种求解有约束的资源调 度问题的方法 遗传算法是一种新的并行优化搜索方法 采用自然界的遗传变异和自然选择思想 进行全局优化 文献 1 5 为j o bs h o p 调度问题设计了一个自适应遗传算法 它的优 点是通过群体间的相互作用 保持已经搜索到的信息 这是基于单次搜索过程所无法 比拟的 但是它的计算速度较慢 1 2 3 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 和软件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 的研究范围和情况等等 4 华中科技大学硕士学位论文 a g e n t 的研究始于7 0 年代中期 9 0 年代以来逐步成为人工智能的研究目标和核心 它代表了信息技术最前沿的发展方向 是具有划时代战略意义的研究热点之一 比尔 盖茨曾称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 1 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 a g e n t 强概念 a g e n t 除了自治性 社会能力 反应能力和自发行为等特性以 外 还应该具有人类的某些特征 例如知识 信念 意图 承诺等心智状态 s h o h a m 对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 功能分为反应式和认知式两种a g e n t 它们的区别 在于是否有推理机制 反应型的a g e n t 通过传感器感知环境并通过执行器对环境进行 行动 认知型的a g e n t 还能够进行推理以解释感知信息或决定执行什么动作 软件 a g e n t 从功能上大致分为八类 合作 c o l l a b o r a t i v e 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 混合 h y b r i d a g e n t 异构 h e t e r o g e n e o u s a g e n t 系统和智能 s m a r t a g e n t m a s m u l t i a g e n ts y s t e m 多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 成员的目标和行为之间的矛盾和冲突 m a s 作为一个整体 也具有a g e n t 的属性 m a s 的数据和资源是分散的 每个a g e n t 对于所要完成的任务拥有不全面的信息或能力 其执行任务的观念是局部的 不存在 全局的控制系统 问题的求解和计算是异步进行的 华中科技大学硕士学位论文 按照m a s 中a g e n t 的不同通信和协作方式 可以将m a s 分为三种体系结构 a g e n t 网络 a g e n t 联盟和黑板结构u 9 1 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 通过一个协助者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 群中控制外壳 a g e n t 负责信息交互 网络控制者a g e n t 负责局部a g e n t 群体之间的远程信息交互 多a g e n t 的研究方法分为逻辑方法和对策论 决策论方法两大类 逻辑方法提出了 各种逻辑体系 定义了公理系统和推理规则 来证明一些特定命题是否成立 认为一 个合理的行为可基于当前的信念合乎逻辑的推导出来 2 0 1 思维状态模型都属于这一 派 如b d i 模型 采用对策理论和决策理论的方法则不同 其信念模型是描述如果 采用一个行动将会发生什么 就为每个后果都赋予概率 愿望模型是用实数表示那些 可能状态的效用 一个合理的行动是使期望效用最优化的行动 这需要依据信念和愿 望使用概率论工具得到 对于一个处于动态环境中资源有限的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 协调与协作 有代表性的工作有1 2 1 1 1 s m i t h 和d a v i s 提出合同网协议 结点间通过招标 投标 中标过程进行任务分 布和解决资源 知识冲突 2 c o r t r y 等用多级协商协议解决分布式约束满足问题中的任务分布和资源分配 冲突 多级协商是对传统合同网的扩充 在投标和中标过程中允许反复协商 3 d u r f e e 和l e s s e r 等提出的p g p p a r t i a lg l o b a lp l a n n i n g 部分全局规划 是一 种更一般的协商框架 a g e n t 间通过交换局部规划和p g p 来协调任务分解 分布和求 华中科技大学硕士学位论文 解 4 s y c a r a 以劳资协商为背景对非协作类的多a g e n t 相互作用进行了研究 结合基 于实例的推理和多属性效用理论提出 劝说性辩论 模型 5 g e n e s e r e t h 等用对策论和博弈论方法研究没有通信情况下的协作 z o l t k i n 等研 究协作或非协作类a g e n t 在只有部分信息情况下进行协商和冲突消解 r o s e n s c h e i n 研 究多a g e n t 协商机制 w e r k m a n 提出一种基于知识的协商方法来消解冲突 6 n e i m a n l e s s e r 等提出利用元集信息进行协商的方法 另外 石纯一提出所有的协调机制最终归结为承诺和附带的规范 2 2 1 并且总结出 下面的等式 协调 承诺 规范 社会性规范 局部推理 s h o h a m 认为基于规范的协调问题 即 给定的社会性多a g e n t 系统和若干个焦点 状态 如何定义社会规则 以保证a g e n t 可以生成在焦点状态之间进行状态转换的规 划 如何寻找法则的问题 是n p 完全的 处理协调问题有两个极端 1 没有法则 需要a g e n t 之间的协商和更多的通信 可能使系统求解性能降低 2 中心规划器 完全限制a g e n t 的行为 违背了a g e n t 的自主性 社会法则就是要在两者之间寻找平衡 b r i g g 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 结构和组织 a g e n t 语言 规划 通信和交互技术 a g e n t 之间的协作和协商等方面 研究的机构很多 从以o m g a g e n tw o r k i n gg r o u p c m u m i t u m b c 和伦敦大学为代表的学术界 到以a t t d a i m l e r b e n z d e c h p i b m l o t u s m i c r o s o f t 和o r a c l e 为代表的企业界 都相 继开展了对a g e n t 技术不同层次 不同侧重点的研究和开发工作 1 2 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 系统具有拓扑结构可动态改变的特点 这些特点非常适于解决调度问题 目前 国内外基于多a g e n t 的调度系统和制造系统研究很多 例如 中科院沈阳自动化研究所张宇等提出多代理调度系统模型 l 它是一个多 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 之间的协作能力体现不够 特别是没有涉及到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 工作单元a g e n t 代表由数台加工设备组成的具有一定加工能力 的制造单元 作业a g e n t 由外部事件管理模块根据具体的作业动态生成 事件a g e m 根据外部事件或车间事件动态生成 评价与仿真a g e n t 根据作业车间的要求对整个系 统的工作情况进行仿真与监控 系统的调度是各a g e n t 根据环境变化做出局部决策 并由工作单元a g e n t 根据自身的能力和状态选择合适的分派规则 但是它没有具体说 明a g e n t 如何决策 以及使用哪些分派规则 b u s s m a n n 提出了面向a g e n t 的制造系统体系结构 采用a g e n t 技术进行制造系 统中的物流控制研究f 2 s h a w 提出用a g e n t 方法进行制造调度和控制 指出制造单 元可以通过投标机制 将作业以子合同的形式转包给其它制造单元 2 6 1 y a m s 系统 将合同网协议用于制造控制 它将制造企业建模成许多执行不同任务的制造单元组成 的层次结构 并根据功能将这些单元组成若干柔性制造系统 然后由一组柔性制造系 统形成一个工厂 用多a g e n t 系统管理工厂的制造过程 工厂及其组成部分被表示成 若干个a g e n t 每个a g e n t 具有一组表示其能力的计划 通过合同网协议将各种任务委 托给工厂 再由工厂委托给t m s 最后由f m s 委托给工作单元 2 7 c h e n 采用a g e n t 技术进行制造调度与供应链协调研究 提出了一种基于现场总线的多a g e n t 车间动态 调度模型 28 1 首先由一个主a g e n t 向其它辅助a g e n t 发送调度任务 通过对回收的所 有调度结果进行统一判断和协调 最终得到一个可行的调度方案 m e t a m o r p hi i 提 出了一种基于混合型中介a g e n t 体系结构的仲裁模型 采用基于合同网协议的投标机 华中科技大学硕士学位论文 制 进行制造调度和再调度研究阻3 0 川 系统中的a g e n t 具有自学习能力 系统具有 很强的适应性 s h e n 等列举了近3 0 个国际上已经开展或正在进行的运用a g e n t 技术 进行制造规划 调度及控制的研究项目d 2 j o r g 等提出了一个 m a p s m u l t i a g e n t p l a n n i n g s y s t e m 口 系统中只有两种a g e n t j o ba g e n t 和r e s o u r c e a g e n t 并且提出了两种策略t c s t i g h t l yc o u p l e ds c h e d u l i n g 和l c s 1 0 0 s e l yc o u p l e d s c h e d u l i n g m a p s 综合t c s 和t l s 在它们之间寻求某种平衡 既保证在各种情况 下都有较好的结果 又不至于有太大的计算量 此外 基于多a g e n t 的系统还有a a r i a 3 4 a b c d e 1 9 j s h o l o n i cm a n u f a c t u r i n g s c h e d u l i n g 等 h m s 将制造系统的关键元素一如机器 单元 工厂 零件 产品等 都建模成具有自治和协作属性的 合弄体 3 5 合弄体 在某种意义上类似于本 文中的a g e n t 1 3 课题主要研究工作 本文将从a g e n t 入手 分析典型的a g e n t 模型 a g e n t 体系结构以及通信和协作方 式等等 在此基础上 结合各种多a g e n t 制造和调度系统的设计方法 针对p c b 装配 调度的具体特点 本文将运用a g e n t 的概念进行车间工作单元建模 构造一个p c b 装 配多a g e n t 调度系统模型 研究的重点是系统的调度机制和通信协作方式设计 具体的研究工作将从以下几方面进行 1 建立一个p c b 装配多a g e n t 调度系统模型 模型可以反映p c b 装配车间主要 特征和p c b 装配调度过程 2 设计系统的调度机制 确定各a g e n t 的调度策略 3 设计系统中a g e n t 的通信协议 调度系统的设计目标主要有 1 调度结果的次优性 2 系统的动态可扩展性 即a g e n t 可以动态的生成和撤销 3 系统的鲁棒性 即当系统出现机器故障等意外情况时仍能照常运行 9 华中科技大学硕士学位论文 2 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 的b d i 模型 2 1 a g e n t 的概念及特点 究竟什么是a g e n t 一般认为 a g e n t 是一种处于一定环境下包装的计算机系统 为了实现设计目的 它能在那种环境下灵活地 自主地活动 关于a g e n t 的定义 有 很多的解释 下面列举几个典型的定义 r u s s e l 认为a g e n t 是一种能够通过它的感 应器感知其外界环境并且通过其效应器对环境作出相应的反应的实体 m a e s 认为 a g e n t 是在复杂动态环境中能自治地感知环境并能自治地通过动作作用于环境 从而 实现其被赋予的任务或目标的计算系统 h a y e s r o t h 认为智能a g e n t 除了能对环境 进行感知信息和动作外 还应当能够进行推理以解释感知信息或决定执行什么动作 f l a n k l i n 认为自动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 组成一个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 具有以下的属性 1 自治性 a g e n t 运行时不直接由人或者其它程序控制 它对自己的行为和内部 l o 华中科技大学硕士学位论文 状态有一定的控制权 2 社会能力 a g e n t 能够通过某种a g e n t 通信语言与其它a g e n t 进行信息交换 3 反应能力 即对环境的感知和影响 无论a g e n t 在现实的世界中还是在虚拟 的世界中 它们都应该可以感知它们所处的环境 并通过行为改变环境 4 自发行为 传统的应用程序是被动的由用户来运行的而且机械的完成用户的 指令 而a g e n t 的行为应该是主动的 或者说是自发的 a g e n t 感知周围环境的变化 并做出基于目标的行为 从广义的角度上说 a g e n t 是具有以上特性的软件或硬件系统 此外 a g e n t 还有 下列其它属性 1 长寿性 传统的程序由用户在需要时激活 不需要时或者结束后停止 a g e n t 与之不同 它至少应该在 相当长 的时间内连续的运行 2 移动性 a g e n t 可以从一个地方移动到另一个地方而保持内部状态不变 a g e n t 可以携带数据和能够在远处执行智能指令 3 推理能力 a g e n t 可以根据其当前的知识和经验 以理性的 可再生的方式推理 或推测 4 规划能力 根据目标 环境的要求 a g e n t 应该至少对自己的短期行为做出规 划 虽然程序设计人员可以提供一些常见情况的处理策略 但这些策略不可能覆盖 a g e n t 将遇到的所有情况 所以 软件a g e n t 应该有生成规划的能力 同时它还有 1 学习和适应能力 a g e n t 可以根据过去的经验积累知识 并且修改其行为以适 应新的环境 另外 a g e n t 还应该具有自适应性 个性等特性 2 诚实 假定a g e n t 不会故意提供错误信息 3 善意 假定在a g e n t 之间不存在互相冲突的目标 且a g e n t 总是尽力去帮助其 它a g e n t 4 理性 假定a g e n t 总是尽力去实现自己的目标 因此 在设计a g e n t 时需要考虑下列几个问题 1 a g e n t s 必须唯一标示它们自己 2 a g e n t s 必须根据特定的服务器修改它们的请求步调和频率 华中科技大学硕士学位论文 3 a g e n t s 必须限制它们的搜索到合适的服务器上 4 a g e n t s 必须与其它的a g e n t 共享信息 5 a g e n t s 必须尊重服务器操作员对它们的授权 6 一个a g e n t 的服务必须是精确的和即时更新的 另外 还有 i 安全性一a g e n t 不应该破坏性地改变世界 2 迟滞性一a g e n t 应该让世界和它被发现时一样 3 节俭性一a g e n t 应该限制它的稀有的资源消费 4 警惕性一a g e n t 不应该允许不可预料的客户行为 a g e n t 的概念与熟悉的a i e s 和o o 有所不同 1 a g e n t 与a i a r i t f i c i a li n t e l l i g e n c e 人工智能 的区别 a i 包括学习功能 推理功能 而a g e n t 对智能的要求是 它能够根据环境等因素决定下一步要执行的动 作 至于是否要求具有学习或推理的功能要根据领域问题的要求而定 2 a g e n t 与e s e x p e r ts y s t e m 专家系统 的区别 e s 本质是非嵌入式的 即它们 不与环境发生直接交互 它不是