基于Multragent的矿井通风仿真系统研究.pdf

Series No. 322 April 2003 金 属 矿 山 METAL MINE 总第 322期 2003年第 4 期 *山东省自然科学基金资助 No.Y2002G08 华 臻, 烟台大学光电信息科学与技术学院, 讲师, 硕士研究生, 264005 山东省烟台市。 基于 Multiagent 的矿井通风仿真系统研究* 华 臻 范 辉 烟台大学 李晋江 刘敬云 靳钟铭 太原理工大学 摘 要 针对实时性有一定要求的通风仿真系统中必须满足的时间和空间复杂度要求, 提出了一种基于多 A gent 系统的分析和解决方案。介绍了基于多 Agent 系统仿真的特点和功能, 给出了通风仿真系统中 Agent 的结构。 最后, 采用了一种 投票 式的协同策略, 从一个新角度来解决通风中的风网解算存在问题, 并构筑了一个通风仿真 系统。 关键词 多 Agent 系统 仿真系统 风网解算 Study of Multiagent Based Mine Ventilation Simulation System Hua Zhen Fan Hui Yantai University Li Jinjiang Liu Jingyun Jin Zhongming Taiyuan University of Technology Abstract In view of the fact that ventilation simulation system that has certain requirements on real time property should satisfy the spatio temporal complexity, it is proposed to use a multi agent based system. The characteristics and function of simulation of this system and the agent structure of ventilation simulation system are described in the paper. A coordinate strategy of voting type is used to solve the problems in the ventilation network calculation from a new angle and to construct a ventilation simulation system Keywords Multi agent system, Simulation system, Calculation of ventilation network Agent 是人工智能中的一个重要概念, 随着人 工智能及计算机网络的发展, 对 Agent 的研究及应 用正引起人们的广泛兴趣。目前, Agent 的应用已 涉及个人数字助理、 网络管理、 远程电子会议、 CAD、 医学会诊等多个应用领域。作为人工智能的一个重 要分支, 近年来分布式人工智能 DAI 已成为一个 研究的热点。其研究主要可分为 分布式问题求解 DPS, distributed artificial intelligence 和多 Agent 系统 MAS 。DPS 侧重于信息管理, 包括任务分解 和解答综合; MAS 侧重于行为管理, 包括如何协调 各Agent 的知识、 目标、 策略和规划, 以采取联合行 动或解决问题, 由于 MAS 比 DPS 更能体现人类社 会智能, 更加适合开放、 动态的环境, 因而越来越受 到人们的重视[ 1、 2]。随着分布对象技术、 网络技术, 特别是 WWW 的发展, 软件系统趋向于网络计算、 面向活动部件的特征。面向 Agent 的软件工程是基 于面向对象技术和分布计算技术, 赋予计算实体更 加灵活、 自主以及社会化的特征, 来构筑软件系统 的。 MAS 比单一的 Agent 更具模拟人类的智能, 其 核心就在于通过 MAS 中的Agent 的彼此通讯, 可以 开发新的规则或问题的求解方法, 来处理单一 A gent 所缺乏的、 不完全的和不确定的知识。而且通 过多 Agent 间的交互和合作, 能进一步了解多 A gent 社会行为, 以达到 Agent 社会的共同目标。因 此, 对多 Agent 协同和多 Agent 协调是研究 MAS 的 核心问题。MAS 在实际应用中要考虑到如何适应 实际应用环境, 根据软件需求分析, 满足在空间和时 间上的复杂性要求。特别是在一些模拟实时的仿真 系统中, 对于时间复杂性有比较严格的限制。对于 下面所提到的通风系统, 采用 MAS 设计是一种很 好的解决办法。 多年以来, 煤炭科技的发展, 使得煤矿安全技术 水平有了很大的提高, 但是由于本身所处的自然条 件, 煤炭行业仍然被认为是比较危险的行业。大多 数灾害事故都与通风有关。通风系统是矿井生产的 重要环节, 为保证通风系统正常工作, 就应合理地设 46 计和组织管理。矿井通风系统的影响因素多, 并具 有制约性和随机性。近年来计算机在矿井通风系统 方面的应用正在变得越来越普遍。国内外的科技人 员在这方面进行研究并取得了不少成果, 如通风网 络解算、 通风系统立体图绘制和矿井通风管理。目 前计算机解算通风网络问题已被广泛应用于教学、 科研和实际生产中。已有的解算方法是利用 Scott - Hinsley 法[ 3], 经过迭代计算, 使风量逼近真值。 矿井中通风设备及影响通风的相关参数非常多, 若 用迭代法计算是很费时间的, 一般少则几个小时, 多 则 10 多个小时。通常风网解算都是隔一时期进行 1次, 由于通风系统是 1 个动态的系统, 解算结果不 能真正地反映实际的动态变化情况。为了提高矿井 通风管理的质量和风网解算的速度, 本文提出了 1 种基于多 Agent 系统的通风仿真系统, 该系统能够 及时进行解算。该系统完全可以模拟 1 个真正的矿 井灾害和在火灾时期矿井的风流和烟流流动情况, 并实时采取一些救灾措施, 把救灾效果逼真地反映 给参与者。 1 基于多 Agent 的仿真系统 基于多Agent 的仿真系统研究系统中 Agent 的 大规模行为及它们之间的交互。这种仿真的方法很 直接也很有效, 已广泛应用于生物学、 经济学及社会 学中。文献[ 4]中的 Swarm 就是 1 个优秀的基于多 Agent 的仿真系统平台, 在此之上人们可开发出不 同领域的仿真系统, 而不需把精力放在算法和仿真 细节上。文献[ 5]中的 StarLogo 仿真平台, 其最新版 本的内核是由 Java 编写的, 所以能够支持任何系 统。StarLogo 的最大特点是提供了类似 Logo 的程 序设计方式, 用户通过它能够方便地编写仿真程序。 Swarm 和 StarLogo 的功能都不是很强, 并且不能够 对仿真数据进行分析, 所以很多复杂的仿真系统不 能通过这 2 个平台来建立。 1. 1 特 点 在多 Agent 所组成的 Agent 社会中, 每个智能 体具有单一Agent 所不具有的特性。系统中的每个 Agent 都具有社会性, 虽然它们都具有自己的信念、 愿望和意图等基本的思维属性, 但是必须服从 A gent 社会中所制定的规则。通信是 Agent 社会性的 体现, 也是 Agent 间思维状态的传递。为了满足在 仿真系统中的时空复杂性, 多 Agent 之间必须能够 体现社会的实时性特点。因此, 基于多 Agent 的仿 真系统除具备多 Agent 系统的特点外, 还有自己的 特点。 1. 1. 1 分布性 随着从基于网络操作系统的分布计算模式向基 于 Internet 和 Intranet 的分布计算模式的转移, 大 多数人认为未来的计算环境将由运行于多种异构平 台上的分布软件系统组成。MAS 中的各个 Agent 分布于 Agent 社会中, 能作用于自身和环境, 并对环 境的变化做出反应。由于现实世界环境纷繁复杂、 千变万化, 所以 MAS 必须具有应付动态环境的适 应能力。MAS 通过不同的拓扑结构, 来动态适应环 境。拓扑结构包括 Agent 的数目和 Agent 之间的社 会关系等。MAS 的拓扑结构可以不变, 也可以动态 改变。在对空间复杂性有较高要求的仿真系统中, 采用动态拓扑结构的 MAS 显示了很大的优势。在 Agent 社会中, 某些 Agent 的生存期比 Agent 社会 的生存期要短得多, 对于这些 Agent 可动态地生成 和释放, 以减少对内存的占用。 1. 1. 2 协同性 一般情况下, 协同是指多个主体围绕一个共同 目标而相互作用的协同过程。在 MAS 开发中, 协 同的高效实现是一个核心问题。Durfee 提出了多主 体协同的 4 个基本目标[6] 通过并行性提高任务完 成效率; 通过共享资源 信息、 专家知识、 物理设备 等 扩展完成任务的范围; 通过任务的重复分配增加 任务完成的可能性; 通过避免有害相互作用降低任 务之间的干扰。在多 Agent 社会中, 所有在物理上 独立的 Agent 通过协调各自的行为, 合作完成各自 或共同的目标。为了实现 Agent 之间的协同工作, 可以根据实际情况采用不同的控制结构。集中控制 的 MAS 是由一个中心Agent 负责整个系统的控制、 协调工作。层次控制结构的 MAS 是指 Agent 之间 具有层次机构, 各个 Agent 控制处于其下层的 A gent 的行为, 同时又受控于其上层的其它 Agent。 1. 1. 3 并发性 MAS 中的 Agent 具有并发的特性。Agent 社会 中的每个Agent 随时随地在根据 Agent 环境协调自 己的状态和行为, 及时处理实时信息。根据系统中 每个Agent 的结构和功能是否相同, 可以将MAS 分 成 ∀ 同构型系统 每个 Agent 具有相同的结构和功 能。 异构型系统 Agent 的结构、 功能、 目标都可 以不同, 由通信协议保证Agent 协调与合作的实现。 在仿真系统中往往采用以上 2 种相互结合的混合系 统, 这样的系统既具有异构型系统对现实世界模拟 47 华 臻等 基于 Multiagent 的矿井通风仿真系统研究 2003年第 4 期 的准确性和灵活性, 又具有同构型系统的高可靠性。 1. 1. 4 实时性 大多数仿真系统都对时间有一定要求, 要求系 统能够快速地响应。与思考型 Agent 相比, 反应型 Agent 不包含用符号表示的模型, 并且不使用复杂 的符号推理, 因此它能较快地做出响应。支持反应 型Agent 的人们认为, Agent 的智能取决于感知和 行动。Agent 的行为只能在现实世界与周围环境的 交互作用中表现出来[7]。无论是纯粹的思考型 A gent 还是纯粹的反应型 Agent 都不是构造 Agent 的 最佳方式。人们结合了二者的优点形成了混合型 Agent, 它具有较好的灵活性和较快的反应速度。 1. 2 功 能 基于多 Agent 的仿真系统应提供用户一个方 便、 快速的开发环境, 它的功能可分为 4 部分[8] ∀ 过程控制, 包括 开始、 暂停、 单步运行、 恢复、 保存和 退出。开始为整个仿真系统开始运行或从暂停恢 复; 暂停是使系统挂起, 系统可从断点恢复; 单步运 行为用户能单步地运行系统; 恢复实现了系统重新 运行; 保存使用户能保存运行状态和结果, 使系统在 下一时刻能继续运行; 退出为停止系统运行。 参 数控制, 为初始系统参数和 Agent 参数。用户应该 能够在系统运行前设置系统参数, 并能在运行过程 中暂停系统改变参数, 然后恢复系统运行。同样, 仿 真系统应能够显示系统运行中 Agent 的内部状态, 使用户能够动态地改变。∃ 数据分析, 仿真系统应 能够用一些图表或曲线来描述系统的运行结果, 使 用户能够直观地理解。 图形接口, 使用户能够容 易地了解或改变系统的运行状态。 2 通风仿真系统中 Agent 结构 本文以多 Agent 系统构筑了一个矿井通风仿真 系统, 该系统能够对预期的通风方案进行仿真, 并将 结果与现有的方案比较, 检查新方案是否满足要求, 或比原方案更好。实际通风系统中主要组成有 通 风网络, 包括矿井巷道的拓扑结构及巷道的风阻系 数等; 通风设备, 包括风机、 风窗、 风门等。在仿真系 统中,Agent 根据功能可被分为 4 类 设备 Agent、 网 络Agent、 接口 Agent 和学习Agent。我们采用了具 有平台无关性的 JAVA 语言来开发该仿真系统。选 择JAVA 语言是因为它的一些优点, 即与平台无关 性, 可利用多Agent 的分布式特性和 JAVA 的 WEB 支持在网络环境中进行仿真。JAVA 的另一个重要 特点是, 它提供了多线程及其同步机制, 利用该机制 可以模拟具有并发特性的 Agent。 2. 1 设备Agent 结构 设备 Agent 是通风仿真系统的核心, 它的结构 包括消息队列、 方法、 属性 数据/ 知识 和接口等, 定 义为 Agent {Msti}i∋ N 方 法; {D/ Ki}i∋ N 属性; MsgIntp 消息解释器。在仿真 系统中设备 Agent 定义如下 Class Agent Extends Threads { Msg *Message; / /Message List int MetNo;/ /Points to the being matched int cond;/ /Whether interrepter should be stoped Public Agentint condinit;/ /Constructor void IntpMsg;/ /Message interrepter void RevMsg;/ /Receiving message int FetMsg;/ /Fetching message int MatMsg;/ /Matching message void SendMsgmsg, agentNo; / /Sending message to Agent } Agent 自己决定对哪些事件响应以及如何进行 处理, Agent 不断学习和适应环境, 同时不断发展和 提高自己的能力。根据历史数据, 设备 Agent 通过 神经网络的训练和学习, 得到在不同时期相应方向 风量, 决定对新方案的选择。 2. 2 网络Agent 当设备 Agent 计划了某种通风方案时, 必须询 问相邻的设备 Agent, 根据协同策略决定该方案是 否可行。由于设备 Agent 采用轮询方式来处理消息 队列, 因此在处理消息的过程中就有了一个时间差。 为了提高设备Agent 的消息处理速度以达到仿真系 统的要求, 可采用 2 种方式来提高实时性 一是采用 基于优先级的轮转法来处理消息队列, 二是用网络 Agent 来处理查询请求消息。 2. 3 接口Agent 接口Agent 负责仿真程序的接口和多 Agent 社 会中共享信息的维护。仿真系统中其它Agent 通过 接口 Agent 获得某一时刻系统中巷道的风量大小、 风向等。 2. 4 学习Agent 该 Agent 采用递归神经网络技术, 学习以往在 通风网络中每条巷道的实际风量, 预测将来在巷道 48 总第 322 期 金 属 矿 山 2003 年第 4 期 的风量。通过学习 Agent 提供的预测风量, 设备 A gent 可以通过协同策略, 选择最佳的通风方案, 使整 个通风系统满足生产要求、 提高通风效率。学习 A gent 由 3 类功能各异的 Agent 组成 神经网络 A gent NNagent 、 协调 Agent Sagent 、 遗传算法 A gent GAagent 。其中 NNagent 和 GAagent 分别对 应神经网络方法库 NN 方法库 和遗传算法方法库 GA 方法库 , Sagent 有 1 个基于知识推理的支持 库。神经网络 Agent 完成神经网络的数据选择、 方 法选择、 消息通信和状态感知, 它包括状态集、 输入 输出转换、 消息的发送和处理等。遗传算法 Agent 要完成的功能大体与神经网络 Agent 类似, 其内容 包括状态集、 编码解码、 消息的发送和处理。协调 Sagent 主要是协调神经网络 Agent 和遗传算法 A gent 两者在时间、 资源分配和具体实施 Agent 队列 方面的管理, 它包括系统状态集、 消息的接收和发 送、 agent 队列管理等。 3 Agent 协同策略 多Agent 协同求解的方式有 2 种 协商式协同 求解, 分工式协同求解。协商式协同求解指多个 A gent 就某一主题, 根据各自的知识能力和工作经验 求解问题, 并进行协商讨论, 最后由协同 Agent 总结 协商结果, 确定任务的解决方案。分工式协同求解 就是将 1 个大的任务分解成若干粒度较小的子任 务, 并根据各Agent 的能力调度子任务给 Agent, A gent 完成子任务之后, 由协同 Agent 进行子任务合 成, 得出最终求解结果。在 MAS 中, 大多数情况 下, 一些 Agent 的行为会对其它 Agent 行为的选择 造成不同程度的影响。如果 Agent 是有理性的, 那 么当它获悉其它 Agent 的行为时, 就选择能使自身 获得最大益处或效用的一个。这种理性 Agent 如何 决策的问题主要在游戏理论中得到深入的研究, 如 Shubik[ 9]等探讨了游戏者决定采取什么行为。 在通风系统中, 某一地方风量发生改变就会影 响到其它地方的风量, 甚至会发生方向逆转。但在 大多数实际情况中, 某地风量的改变仅对它附近巷 道风量有较大的影响, 只要新的通风方案能满足附 近大多数巷道的通风要求, 则该方案就是可行的。 因此, 我们提出了一种 投票 式的协同策略[ 10], 即 Agents 对新方案进行投票, 以满足大多数 Agent。 定义 1 设 p 为一 Agent 对新方案同意的概率。 定义 2 设 p* n 为一 Agent 对满足大多数 Agent 个数为 n 方案同意的概率。 定义 3 若 Agent 的数目 n 为奇数时, p * n n/ 2 j nC j npjq n- j , 其中 q 1- p 。 定义 4 若 Agent 的数目 n 为偶数时, p * n n/ 2 1 j nC jnpjq n- j 1 2 Cn/2np n /2qn/ 2 。 根据以上定义可得出以下定理和推论 定理 1 若 Agent 的数目 n 为奇数时, p * n 2 p * n Cn/2 np n/21- pn/ 22p - 1 , p* n 1 p * n 。 定理 2 若 Agent 的数目 n 为偶数时, p * n 2 p * n Cn/2 np n/21- pn/ 2 p -1 2 , p* n 1 p * n C n- 1 /2 n- 1p n- 1/ 22p - 1 。 推论 1 若 Agent 的数目 n 为偶数时, p * n 1 p * n, 当且仅当 p 1/ 2 。 推论 2 若 Agent 的数目 n 为奇数时, p * n p , n 3, 当且仅当 p 1/ 2 。 推论 3 若 Agent 的数目 n 为偶数时, p * n p , n 4, 当且仅当 p 1/ 2 。 图 1 不同的 Agent 的个数 n 下的概率计算结果 图 1 给出了 Agent 个数 n 为 1, 3, 5, 9 时的结 果。判断一个协同策略是否有效, 就是看它是否能 使 p * n 增大。在通风仿真系统中, 设备 Agent 之间对新方案进行投票, 使得能满足大多数设备 A gent。不能满足的设备 Agent 再规划新的方案, 再 进行投票, ∗∗如此下去, 直到产生最终方案。在实 际应用中一般投票不超过 4 次便可产生最终方案。 而传统的风网解算, 经过迭代计算的结果来判断是 否满足要求, 若不满足则需改进方案, 然后再迭代计 算, 直到计算结果满足要求为止。而采用多 Agent 投票来判断新方案, 不需要很长的时间即可选出一 个满足要求的通风方案。表 1 为采用实际数据, 该 通风仿真系统解算的结果, 仅进行了 3 次投票, 解算 时间仅为几分钟, 与迭代法解算结果误差不超过 49 华 臻等 基于 Multiagent 的矿井通风仿真系统研究 2003年第 4 期 6。 表 1 仿真系统计算结果 巷 道 名分支编号起点编号终点编号自然风压 风阻 / 缪 风量 / m3s- 1 阻力 / Pa 断面积 / m2 风速 / ms- 1 石家河总回风巷97947480. 000. 004 30625. 312. 758 515. 481. 63 梁庄总回风巷9802662670. 000. 004 77125. 3083. 055 815. 891. 59 百草塔总回风巷9815595600. 000. 004 63423. 662. 594 615. 891. 48 后风坪岭斜井1120. 000. 003 61328. 402. 914 814. 391. 97 后风坪岭斜井2230. 000. 000 11528. 400. 092 713. 802. 05 北翼胶带巷3340. 000. 002 0892. 510. 013 26. 000. 41 北翼胶带巷4450. 000. 020 8962. 510. 132 26. 000. 41 北翼胶带巷5560. 000. 002 4982. 510. 015 86. 000. 41 北翼胶带巷6670. 000. 038 5392. 510. 243 96. 000. 41 北翼胶带巷7780. 000. 005 5692. 680. 040 06. 000. 44 北翼胶带巷8890. 000. 000 1881. 660. 000 56. 000. 27 北翼胶带巷99100. 000. 000 0652. 680. 000 46. 000. 44 北翼胶带巷1010110. 000. 0190 241. 410. 038 06. 000. 23 北翼胶带巷1111120. 000. 006 6561. 410. 013 26. 000. 23 北翼胶带巷128130. 000. 000 1741. 010. 000 16. 000. 16 北翼胶带巷1313140. 000. 000 1311. 010. 000 16. 000. 16 北翼胶带巷141490. 000. 000 2071. 010. 000 26. 000. 16 北翼回风巷153150. 000. 000 44725. 880. 299 513. 231. 95 北翼回风巷1615160. 000. 000 58115. 400. 137 816. 440. 93 北翼回风巷1716170. 000. 000 02412. 330. 003 616. 440. 75 北翼回风巷1817180. 000. 000 01713. 650. 003 116. 440. 83 北翼回风巷1918190. 000. 000 04016. 180. 010 416. 440. 98 北翼回风巷2019200. 000. 000 02016. 180. 005 216. 440. 98 北翼回风巷2120210. 000. 000 06016. 180. 015 711. 471. 41 北翼回风巷2216220. 000. 000 0743. 060. 000 616. 440. 18 4 结 语 基于多Agent 系统的通风仿真采用了多 Agent 系统和多 Agent 协同的思想。解决了矿井通风中风 网解算的计算量大及计算时间长等问题。在山西某 大型煤矿的运用中, 取得了良好的效果。使得风网 解算与通风数据管理一体化, 模拟结果得到了该矿 实测数据的验证, 误差在煤炭部规定的 10 之内。 该通风仿真系统将矿井通风系统看成一个多 Agent 的社会, 其每一通风设备是这个多 Agent 社会中具 有自主性、 交互性、 并发性、 分布性和协同性的 A gent。这些 Agent 均具有对 Agent 社会的感知、 学 习、 判断和行为能力, 并按照存放在知识库和策略库 中的社会行为准则, 协同完成共同目标。另外, 该系 统不仅仅适合于矿井通风, 可适用于大多数的通风 系统, 具有一定推广价值。 参 考 文 献 1 Nilsson N J. Artificial intelligence a new synthesis. Morgan Kauf mann Publishers, 1998 2 石纯一, 等 分布式人工智能进展 模式识别与人工智能, 1995 8 72 79 3 黄元平 矿井通风 徐州 中国矿业大学出版社, 1990 4 Lanton C G. http / / www. swarm. com 5 Resnick M. Turtles, T ermites, and T ranffic Jams Explorations in Massively Parallel Microworlds. Cambridge, MA MIT Press, 1994 6 Durfee E H, Lesser V R. Distributed problem solving and planning. In Weiss G ed. Multi- Agent System A modern approach to Dis tribution Artificial Intelligence, John WilleySons, 1996, 231 246 7 Brooks R. Intelligence without reason. IJCAI- 91, Sydney, Aus tralia, 1991, 569 595 8 Stytz M R.Distributed virtual environment.IEEE Computer Graphics and Applications. 1996, 16 3 1931 9 Shubik M . Games theory in the social sciences. The MIT Press, Cambridge, Massachusetts. 1985 9 Talukdar S N. Autonomous cyber agents rules for collaboration. In Proceedings of the T hirthy - First Hawaii International Conference on Systems ScienceHICSS- 31 , Hawaii, January 1998 10 范 辉 虚拟现实在矿井中的应用 计算机应用 增 , 2002 117 119 收稿日期 20021224 50 总第 322 期 金 属 矿 山 2003 年第 4 期