中国科学院沈阳自动化研究所机构知识库
Advanced  
SIA OpenIR  > 工业信息学研究室  > 工业控制系统研究室  > 学位论文
题名: 分布式约束满足问题及其在多智能体任务重分配中的应用
其他题名: Distributed Constraint Satisfaction Problem and its Application for Task Reallocation in Multi-agent Systems
作者: 沈志江
导师: 张彦武 ; 于海斌
分类号: TP18
关键词: 多智能体系统 ; 分布式约束满足问题 ; 任务重分配
索取号: TP18/S44/2003
学位专业: 机械电子工程
学位类别: 硕士
答辩日期: 2003-07-02
授予单位: 中国科学院沈阳自动化研究所
学位授予地点: 中国科学院沈阳自动化研究所
作者部门: 工业控制系统研究室
中文摘要: 分布式约束满足问题及其在多智能体任务重分配中的应用摘 要许多关于过程控制、规划和调度的实际问题都可以用约束满足问题来描述和求解[1]。虽然约束满足模型适用性很强,它的求解算法也可以相当有效地解决这些NP难题的优化问题,但是这种传统的问题求解的方法与分布式的方法相比,具有计算复杂、稳定性差等缺点。因此,对分布式约束满足问题的研究成为了多智能体系统中的一个重要方向。在多智能体系统中,任务重新分配就是将一个被分解成一系列子任务的全局任务分配到不同智能体的过程。任务的组织结构可以很大程度地影响问题求解的过程,因此任务分配本身就是一个优化问题。任务的重新分配是与多智能体系统中的自组织问题密切相关的。为了更有效地解决因此,本文提出了一种适应性更强的算法,使一个组织结构中的智能体能够动态地协商,而不是由某一个智能体来完成任务分配的工作,通过这种方法找到满意的分配方案。我们首先用求解问题的过程中所需要传递的远程消息的数量作为衡量一个组织结构好坏的的标准。然后我们提出一个更全面的衡量问题求解代价的评价标准,这个标准既考虑到了远程消息的数量,同时也考虑了任务的重新分配导致本地任务复杂性的变化。仿真结果证实了这种动态任务调整的有效性。
英文摘要: Several interesting practical problems in process control, planning and scheduling can be expressed and solved using the model of constraint satisfaction problems. Although the CSP framework is very generic and its algorithms are often quite successful in solving NP-hard problems near to optimum very effectively, there are at least four drawbacks of this classical model compared with its distributed counterpart: complexity, scalability, privacy and robustness. Hence research on distributed constraint satisfaction problems is a very important direction in multi-agent systems. Task reallocation in a multi-agent organization is a process that distributes a decomposed global task to individual agents. A careful look at this task reveals that the organization of distribution is critical to the quality and efficiency of the problem solving process and is itself an optimization problem. This paper presents a representation of this task reallocation process using distributed constraint satisfaction model. The process of task reallocation must be distributed and dynamic because it relies on critical information that can only be obtained during mission execution. We first use the total number of remote communication messages generated during problem solving as the criterion to measure the quality of the organization. Later, a more complete criterion was proposed which can not only considers the cost of transmitting remote messages but the computational complexity variance of the local problems caused by task trading. Through these sub-task trading algorithm, a locally optimal task allocation was constructed during mission execution. At last, the simulation results were presented and analyzed.
语种: 中文
产权排序: 1
内容类型: 学位论文
URI标识: http://ir.sia.cn/handle/173321/9456
Appears in Collections:工业信息学研究室_工业控制系统研究室_学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
分布式约束满足问题及其在多智能体任务重分配中的应用.pdf(2087KB)----限制开放 联系获取全文

Recommended Citation:
沈志江.分布式约束满足问题及其在多智能体任务重分配中的应用.[硕士学位论文].中国科学院沈阳自动化研究所.2003
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[沈志江]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[沈志江]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2016  中国科学院沈阳自动化研究所 - Feedback
Powered by CSpace