面向公路施工的机群体系结构及其通讯机制研究
|
摘要
随着单智能体技术的不断完善，以及对多智能体技术研究的不断深入，多智能体系统在
实际中的应用也越来越广泛。近年来，国外一些研究学者已经开始尝试开发多智能体技术与
工程机械相结合的机群施工产品，国内也将机群智能化的开发列为“863”计划的重要研究
项目，本课题的研究就是在国家“863”计划项目“机群智能化工程机械实施方案研究”(项
目编号：2001AA422011)支持下开展的。
本论文构建了高等级公路施工机群分布——分层式树状控制结构，设计了混合式通讯方
式，并解决了无线通讯方案及系统硬件配置的问题，以保证该机群系统能够高效率、低成本
的实现智能体之间的协调与协作，完成高等级公路施工任务。
本论文的主要研究内容如下：
1．针对当前高等级公路施工中的特点，构建了高等级公路施工机群分布——分层式树
状控制结构，并着重分析了各智能控制主体的结构和功能。
2．分析了合同网方法的基本工作原理，并且利用合同网方法来解决该系统中智能体之
间的任务管理及协作问题；同时应用IGS和E-PERT图方法，避免了大多数冲突的
发生。
3．针对分布——分层式树状控制结构，建立了直接寻址和广播方式相结合的通讯机
制，并解决了无线通讯方案及系统硬件配置的问题，以保证系统能够更高效率更低
耗费地实现信息传输。
The multiagent technique is putting into practice wider and wider as the fully development of single agent technique and the academic research concerning multiagent. In recent years, many a foreign researcher has began to try to study new products of mechanical group about multiagent. And China has listed the research about application of multiagent system into the National 863 Plan. Under the support of Project NO. 2001AA422011, the application of multiagent technique in mechanical practice.
The special distributed-layered tree control architecture of a mechanical group for high-level road constructing is set up to adapt to the characteristics of high-level road, and a special composite communication mechanism is constructed correspondingly. At the same time, a scheme of wireless communication is designed, and relevant hardwares required are prepared. All what the steps are taken to ensure that our multiagent system may finish its task with higher efficiency and lower cost.
All what are done in this dissertation includes three questions as follows:
1. The special distributed-layered tree control architecture of a mechanical group for high-level road constructing is set up to adapt to the characteristics of high-level road, and all control architecture of agents are mainly analyzed as well as their functions.
2. The basal principle of contract net protocol is analyzed and introduced in this dissertation. The method of contract net protocol is employed to manage and cooperate the task among the agents, and chart of IGS and E-PERT are used to avoid most conflicts.
3. The special communication mechanism, which makes use of two communication methods of direct routing and routing by signal propagation, is estimated to accommodate to the system architecture. Meanwhile, a scheme of wireless communication is designed, and relevant hardwares required are prepared. All what the steps are taken to ensure that our multiagent system may finish its task with higher efficiency and lower cost.
实际中的应用也越来越广泛。近年来，国外一些研究学者已经开始尝试开发多智能体技术与
工程机械相结合的机群施工产品，国内也将机群智能化的开发列为“863”计划的重要研究
项目，本课题的研究就是在国家“863”计划项目“机群智能化工程机械实施方案研究”(项
目编号：2001AA422011)支持下开展的。
本论文构建了高等级公路施工机群分布——分层式树状控制结构，设计了混合式通讯方
式，并解决了无线通讯方案及系统硬件配置的问题，以保证该机群系统能够高效率、低成本
的实现智能体之间的协调与协作，完成高等级公路施工任务。
本论文的主要研究内容如下：
1．针对当前高等级公路施工中的特点，构建了高等级公路施工机群分布——分层式树
状控制结构，并着重分析了各智能控制主体的结构和功能。
2．分析了合同网方法的基本工作原理，并且利用合同网方法来解决该系统中智能体之
间的任务管理及协作问题；同时应用IGS和E-PERT图方法，避免了大多数冲突的
发生。
3．针对分布——分层式树状控制结构，建立了直接寻址和广播方式相结合的通讯机
制，并解决了无线通讯方案及系统硬件配置的问题，以保证系统能够更高效率更低
耗费地实现信息传输。
The multiagent technique is putting into practice wider and wider as the fully development of single agent technique and the academic research concerning multiagent. In recent years, many a foreign researcher has began to try to study new products of mechanical group about multiagent. And China has listed the research about application of multiagent system into the National 863 Plan. Under the support of Project NO. 2001AA422011, the application of multiagent technique in mechanical practice.
The special distributed-layered tree control architecture of a mechanical group for high-level road constructing is set up to adapt to the characteristics of high-level road, and a special composite communication mechanism is constructed correspondingly. At the same time, a scheme of wireless communication is designed, and relevant hardwares required are prepared. All what the steps are taken to ensure that our multiagent system may finish its task with higher efficiency and lower cost.
All what are done in this dissertation includes three questions as follows:
1. The special distributed-layered tree control architecture of a mechanical group for high-level road constructing is set up to adapt to the characteristics of high-level road, and all control architecture of agents are mainly analyzed as well as their functions.
2. The basal principle of contract net protocol is analyzed and introduced in this dissertation. The method of contract net protocol is employed to manage and cooperate the task among the agents, and chart of IGS and E-PERT are used to avoid most conflicts.
3. The special communication mechanism, which makes use of two communication methods of direct routing and routing by signal propagation, is estimated to accommodate to the system architecture. Meanwhile, a scheme of wireless communication is designed, and relevant hardwares required are prepared. All what the steps are taken to ensure that our multiagent system may finish its task with higher efficiency and lower cost.
引文
[01] Wooldridge,M.,N.R.Jennings.Agents Theories, Architecures and languages: a Survey. In Wooldridge and Jennings, Intelligent Agents,Berlin:Springer-VERLAG, 1995
[02] 史忠植，智能主体及其应用，科学出版社，2000．12
[03] 董红斌，于建华，多Agent技术研究[J]，计算机应用研究，2001．1：54～56
[04] 胡山立，石纯一，一个改进的理性Agent-BDI模型，计算机研究与发展，2000．No9．Vol37．1125～1129
[05] Bratman, M.E., David J. Israel, and Martha E. Pollack. Intentions, Plans, and Practical Reason Havard University Press: Cambridge, MA, 1987
[06] Brooks R A, Intelligence Without Representation[J], Artificial Intelligence, 1991,41 (9)
[07] 曹子宁，石纯一．多Agent理论的对策论方法．计算机科学．2000．No．7 Vol27．63～65
[08] Rosenschein J S, Genesereth M. Cooperation without Communication. In: Reading in DAI 1986
[09] Wooldridge M, Temporal Belief Logics for Modeling Distributed Artificial Intelligence[A], In:Foundations of Distributed Artificial Intelligence[M], John Wiley & Sons, Inc, 1996
[10] Gmvtrasiewicz P J, Durfee E H, A Decision Theoretic Approach to Coordinating Multiagent Intercations. In: IJCAI 91.1991.63～68
[11] Gmvtrasiewicz P J, Durfee E H, Elemants of a Utilitarian Theoory of Knowledge and Action,In: IJCAI-93.1993.396～403
[12] 颜跃进，李舟军，陈跃新，等．多agent系统体系结构，计算机科学，2001．No5．Vol28．77～80
[13] 胡舜耕，张莉，钟义伯．Agent系统的理论、技术及其应用，计算机科学，1999，26(9)：20～24
[14] 王怀民，陈火旺，面向智能体的知识表述，NCTCS，1992，273～276
[15] 陈进才，多agent系统的形式化理论研究，西安交通大学[博士毕业论文]，2000．6
[16] 张松懋，关于黑板模型和分布式黑板模型，微电子学与计算机，1993．8．p1～5
[17] 周光明，徐琳．面向对象的黑板模型．微电子学与计算机，1993．6：28～30
[18] K.S.Decker and V,R.Lesser, "Analyzing the need for meta-level communication," in Proc. Of IJCAI-94, 1994
[19] Danicl E.Neiman, David W. Hildum, and V.R.Lesser, "Exploiting meta-level information in a distributed scheduling system," in Proc. Of IJCAI-94, 1994
[20] Elise H.Turner, "Exploiting problem solving to select information to include dialogues between cooperating agents," in Proc. Of Sixteenth Annual Conference of the Cognitive Science Society,1994.pp.882～886
[21] K.S. Decker and V.R.Lesser, and S.Lander, "Designing a family of coordination algorithms," in Proc.First Int. Conf. On Multiagent Systems, AAAI Press, 1995.pp 73～80 Prasad
[22] T. Ohkno, K.Hiraki, and Y. Anzai, "Reducing communication load on contract net by case-based reasoning—Exension with directed contract and forgetting," in Proc. Seconf Int. Conf on Multiagent
Systems, AAAI Press, 1996.pp. 244～251
[23] R. Foisel. V. Chevrier, and J.-P. Haton, "Improving global coherence by adaptive organization in a multi-agent system," in Proc, Second Int. Conf. on Multiagent System," in Proc. Second Int. Conf. On Multiagent Systems, AAAI Press, 1996.pp.435
[24] Michael Kinney and Costas Tsatsoulis, "Learning Communication Strategies in Multiagent Systems", Applied Intelligence. 1998.9.71-91
[25] 程显毅，石纯一等，MAS理性与模型的研究，计算机工程与科学，2001．Nol．Vol23．101～107
[26] 梁全，许晓鸣，张钟俊，分布式智能控制及系统，1995年中国控制与决策学术年会论文集，东北大学出版社，1995．499～502
[27] 刘金琨，王树青，多智能体控制系统的设计与实现，控制理论与应用，1999．No4．Vol 16．580～582
[28] 董红斌，石纯一，一个多Agent系统模型小型微型计算机系统，2000．No7．Vol21．740～743
[29] 徐光，张晨东，一个人-机协作智能体环境模型 系统工程与电子技术，1999．21(12)：69～72
[30] 马俊涛，傅韶勇，刘积仁 A-ADL：一种多智能体系统体系结构描述语言 软件学报，2002．11(10)：1382～1389
[31] 刘洁，不确定推理及其在多智能体环境下的应用，中国科学技术大学[博士毕业论文]，2000，5
[32] 陈卫东，董胜龙等，基于开放式多智能体结构的分布式自主机器人系统，机器人，2001．No1．Vol23．45～50
[33] 唐平，杨宜民，多智能体协调系统的研究及实现方法，现代计算机 1999．11：28～35
[34] 马海波，熊光楞，李涛，协同设计中冲突的集成解决方案2001．1：61～65
[35] 陈振洲，郑金华，蔡自兴，用遗传算法解决智能体协商问题，计算机工程与应用，2001．15：113～114
[36] 肖晴，多智能体协调协作方法及其在制造企业集成中的应用研究，同济大学[博士毕业论文]，1998．7
[37] 宋宇，孙茂相，等．网络环境下基于Agent的多机器人协调与路径规划[J]，机器人，2000．No1．Vol22．48～54
[38] R G Smith. The Contract Net Protocol: High-Level Communication and Control in a Distributed Solver, IEEE Transaction on Computer, 1980.29(12)1104～1113
[39] Cheng Gu & Toru Ishida, Annalyzing the Social Behavior of Contract Net Protocol, Agent Breaking Away, 7th European workshop on Modelling Antonous Agents in a Multi-Agent World, MAAMAW'96, pp.116～127,1996
[40] 吴伟蔚，杨叔子，基于智能Agent的故障诊断系统研究[J]，模式识别与人工智能，2000．No1．Vol13．78～81
[41] 李春，郑志强，多移动机器人无碰合作的行为规划[J]，机器人，2000．No7．Vol21．720～724
[42] 姚莉，张维明，徐振宁，等．群体协作求解系统的设计和实现．计算机工程与应用，1999．8：79～80
[43] 魏宝刚．基于协商的冲突消解研究．小型微型计算机系统，1998．19(11)：44～49
[44] G. Ziotkin J. S. Rosenschein, Comromise in negotiation: exploiting worth functions over states.
Artificial Intelligence vol84, 1996.pp. 151～176
[45] 刘海龙，吴铁军，刘海龙，面向多智能体的知识查询管理语言模型分析，软件学报，2002．11(4)：933～936
[46] 王广运，薛鸿印，GPS精密动态定位．海洋测绘．No．1
[47] 刘大杰，施一民，等，全球定位系统(GPS)的原理与数据处理．同济大学出版社．1996
[48] 夏林元，杜道生．全球定位系统(GPS)研究．科技术语研究．1999．4
[49] 徐绍铨，张华海等，GPS测量原理及应用，武汉大学出版社，2001年7月
[50] 徐振宁，姚莉，张维明，等，智能通信主体的设计与实现．小型微型计算机系统，1999，20(8)：619～622
[51] 张维明，刘忠，肖卫东，等，信息系统建模，电子：正业出版社，2002年3月，176～198
[52] 何炎祥，吴思，宋文欣，等，基于多Agent的分布开放计算环境模型，高技术通讯，1996．19(6)：118～121
[53] 汪涛，多主体处理环境MAPE中的主体结构、主体通信语言和主体构造方法[硕士学位论文]，中国科学院计算技术研究所，1996
[54] 刘利民，尚朝轩，等，基于DSSS系统的无线局域网MAC层协议的设计与实现．计算机工程，1999．25(3)：46～47
[55] 丁隆厚．基于MAS的区域无线报警网络系统设计．计算机应用，1999．(8)：74～75
[56] 李智军，周晓，吕恬生，等．基于群体协作的分布式多机器人通讯系统的设计与实现[J]，机器人，2000．No4．Vol22．300～304
[57] van Linder, B., W. van der Hoek, J. -J Ch. Meyer. Communication Rational Agents. Utrecht University, Department of Computer Science, The Netherlands, 1997
[58] Stone, P., Veloso, M. Task decomposition, dynamic role assignment, and low-bandwidth communication for real time strategic teamwork. Artificial Intelligence, 1999.110(2):241～273
[59] 孙宪鹏，张宇，王成恩等，基于KQML语言的合同网协议模型及实现，2000．No5．Vol29．454～460
[60] ARPA Knowledge Sharing Initiative, Specification of the KQML Agent-communication Language. ARPA Knowledge Sharing Initiative, External Interfaces Working Group working paper July 1993
[61] Yannis Labrou & Tim Finin, A Proposal for a new KQML Specification, ARPA Knowledge Sharing Initiative, External Interfaces Working Group working paper, February 1997
[02] 史忠植，智能主体及其应用，科学出版社，2000．12
[03] 董红斌，于建华，多Agent技术研究[J]，计算机应用研究，2001．1：54～56
[04] 胡山立，石纯一，一个改进的理性Agent-BDI模型，计算机研究与发展，2000．No9．Vol37．1125～1129
[05] Bratman, M.E., David J. Israel, and Martha E. Pollack. Intentions, Plans, and Practical Reason Havard University Press: Cambridge, MA, 1987
[06] Brooks R A, Intelligence Without Representation[J], Artificial Intelligence, 1991,41 (9)
[07] 曹子宁，石纯一．多Agent理论的对策论方法．计算机科学．2000．No．7 Vol27．63～65
[08] Rosenschein J S, Genesereth M. Cooperation without Communication. In: Reading in DAI 1986
[09] Wooldridge M, Temporal Belief Logics for Modeling Distributed Artificial Intelligence[A], In:Foundations of Distributed Artificial Intelligence[M], John Wiley & Sons, Inc, 1996
[10] Gmvtrasiewicz P J, Durfee E H, A Decision Theoretic Approach to Coordinating Multiagent Intercations. In: IJCAI 91.1991.63～68
[11] Gmvtrasiewicz P J, Durfee E H, Elemants of a Utilitarian Theoory of Knowledge and Action,In: IJCAI-93.1993.396～403
[12] 颜跃进，李舟军，陈跃新，等．多agent系统体系结构，计算机科学，2001．No5．Vol28．77～80
[13] 胡舜耕，张莉，钟义伯．Agent系统的理论、技术及其应用，计算机科学，1999，26(9)：20～24
[14] 王怀民，陈火旺，面向智能体的知识表述，NCTCS，1992，273～276
[15] 陈进才，多agent系统的形式化理论研究，西安交通大学[博士毕业论文]，2000．6
[16] 张松懋，关于黑板模型和分布式黑板模型，微电子学与计算机，1993．8．p1～5
[17] 周光明，徐琳．面向对象的黑板模型．微电子学与计算机，1993．6：28～30
[18] K.S.Decker and V,R.Lesser, "Analyzing the need for meta-level communication," in Proc. Of IJCAI-94, 1994
[19] Danicl E.Neiman, David W. Hildum, and V.R.Lesser, "Exploiting meta-level information in a distributed scheduling system," in Proc. Of IJCAI-94, 1994
[20] Elise H.Turner, "Exploiting problem solving to select information to include dialogues between cooperating agents," in Proc. Of Sixteenth Annual Conference of the Cognitive Science Society,1994.pp.882～886
[21] K.S. Decker and V.R.Lesser, and S.Lander, "Designing a family of coordination algorithms," in Proc.First Int. Conf. On Multiagent Systems, AAAI Press, 1995.pp 73～80 Prasad
[22] T. Ohkno, K.Hiraki, and Y. Anzai, "Reducing communication load on contract net by case-based reasoning—Exension with directed contract and forgetting," in Proc. Seconf Int. Conf on Multiagent
Systems, AAAI Press, 1996.pp. 244～251
[23] R. Foisel. V. Chevrier, and J.-P. Haton, "Improving global coherence by adaptive organization in a multi-agent system," in Proc, Second Int. Conf. on Multiagent System," in Proc. Second Int. Conf. On Multiagent Systems, AAAI Press, 1996.pp.435
[24] Michael Kinney and Costas Tsatsoulis, "Learning Communication Strategies in Multiagent Systems", Applied Intelligence. 1998.9.71-91
[25] 程显毅，石纯一等，MAS理性与模型的研究，计算机工程与科学，2001．Nol．Vol23．101～107
[26] 梁全，许晓鸣，张钟俊，分布式智能控制及系统，1995年中国控制与决策学术年会论文集，东北大学出版社，1995．499～502
[27] 刘金琨，王树青，多智能体控制系统的设计与实现，控制理论与应用，1999．No4．Vol 16．580～582
[28] 董红斌，石纯一，一个多Agent系统模型小型微型计算机系统，2000．No7．Vol21．740～743
[29] 徐光，张晨东，一个人-机协作智能体环境模型 系统工程与电子技术，1999．21(12)：69～72
[30] 马俊涛，傅韶勇，刘积仁 A-ADL：一种多智能体系统体系结构描述语言 软件学报，2002．11(10)：1382～1389
[31] 刘洁，不确定推理及其在多智能体环境下的应用，中国科学技术大学[博士毕业论文]，2000，5
[32] 陈卫东，董胜龙等，基于开放式多智能体结构的分布式自主机器人系统，机器人，2001．No1．Vol23．45～50
[33] 唐平，杨宜民，多智能体协调系统的研究及实现方法，现代计算机 1999．11：28～35
[34] 马海波，熊光楞，李涛，协同设计中冲突的集成解决方案2001．1：61～65
[35] 陈振洲，郑金华，蔡自兴，用遗传算法解决智能体协商问题，计算机工程与应用，2001．15：113～114
[36] 肖晴，多智能体协调协作方法及其在制造企业集成中的应用研究，同济大学[博士毕业论文]，1998．7
[37] 宋宇，孙茂相，等．网络环境下基于Agent的多机器人协调与路径规划[J]，机器人，2000．No1．Vol22．48～54
[38] R G Smith. The Contract Net Protocol: High-Level Communication and Control in a Distributed Solver, IEEE Transaction on Computer, 1980.29(12)1104～1113
[39] Cheng Gu & Toru Ishida, Annalyzing the Social Behavior of Contract Net Protocol, Agent Breaking Away, 7th European workshop on Modelling Antonous Agents in a Multi-Agent World, MAAMAW'96, pp.116～127,1996
[40] 吴伟蔚，杨叔子，基于智能Agent的故障诊断系统研究[J]，模式识别与人工智能，2000．No1．Vol13．78～81
[41] 李春，郑志强，多移动机器人无碰合作的行为规划[J]，机器人，2000．No7．Vol21．720～724
[42] 姚莉，张维明，徐振宁，等．群体协作求解系统的设计和实现．计算机工程与应用，1999．8：79～80
[43] 魏宝刚．基于协商的冲突消解研究．小型微型计算机系统，1998．19(11)：44～49
[44] G. Ziotkin J. S. Rosenschein, Comromise in negotiation: exploiting worth functions over states.
Artificial Intelligence vol84, 1996.pp. 151～176
[45] 刘海龙，吴铁军，刘海龙，面向多智能体的知识查询管理语言模型分析，软件学报，2002．11(4)：933～936
[46] 王广运，薛鸿印，GPS精密动态定位．海洋测绘．No．1
[47] 刘大杰，施一民，等，全球定位系统(GPS)的原理与数据处理．同济大学出版社．1996
[48] 夏林元，杜道生．全球定位系统(GPS)研究．科技术语研究．1999．4
[49] 徐绍铨，张华海等，GPS测量原理及应用，武汉大学出版社，2001年7月
[50] 徐振宁，姚莉，张维明，等，智能通信主体的设计与实现．小型微型计算机系统，1999，20(8)：619～622
[51] 张维明，刘忠，肖卫东，等，信息系统建模，电子：正业出版社，2002年3月，176～198
[52] 何炎祥，吴思，宋文欣，等，基于多Agent的分布开放计算环境模型，高技术通讯，1996．19(6)：118～121
[53] 汪涛，多主体处理环境MAPE中的主体结构、主体通信语言和主体构造方法[硕士学位论文]，中国科学院计算技术研究所，1996
[54] 刘利民，尚朝轩，等，基于DSSS系统的无线局域网MAC层协议的设计与实现．计算机工程，1999．25(3)：46～47
[55] 丁隆厚．基于MAS的区域无线报警网络系统设计．计算机应用，1999．(8)：74～75
[56] 李智军，周晓，吕恬生，等．基于群体协作的分布式多机器人通讯系统的设计与实现[J]，机器人，2000．No4．Vol22．300～304
[57] van Linder, B., W. van der Hoek, J. -J Ch. Meyer. Communication Rational Agents. Utrecht University, Department of Computer Science, The Netherlands, 1997
[58] Stone, P., Veloso, M. Task decomposition, dynamic role assignment, and low-bandwidth communication for real time strategic teamwork. Artificial Intelligence, 1999.110(2):241～273
[59] 孙宪鹏，张宇，王成恩等，基于KQML语言的合同网协议模型及实现，2000．No5．Vol29．454～460
[60] ARPA Knowledge Sharing Initiative, Specification of the KQML Agent-communication Language. ARPA Knowledge Sharing Initiative, External Interfaces Working Group working paper July 1993
[61] Yannis Labrou & Tim Finin, A Proposal for a new KQML Specification, ARPA Knowledge Sharing Initiative, External Interfaces Working Group working paper, February 1997