| 题名 | 分布式约束满足问题及其在多智能体任务重分配中的应用 |
| 作者 | 沈志江 |
| 学位类别 | 硕士 |
| 答辩日期 | 2003-07-02 |
| 授予单位 | 中国科学院沈阳自动化研究所 |
| 授予地点 | 中国科学院沈阳自动化研究所 |
| 导师 | 张彦武 ; 于海斌 |
| 关键词 | 多智能体系统 分布式约束满足问题 任务重分配 |
| 其他题名 | Distributed Constraint Satisfaction Problem and its Application for Task Reallocation in Multi-agent Systems |
| 学位专业 | 机械电子工程 |
| 中文摘要 | 分布式约束满足问题及其在多智能体任务重分配中的应用摘 要许多关于过程控制、规划和调度的实际问题都可以用约束满足问题来描述和求解[1]。虽然约束满足模型适用性很强，它的求解算法也可以相当有效地解决这些NP难题的优化问题，但是这种传统的问题求解的方法与分布式的方法相比，具有计算复杂、稳定性差等缺点。因此，对分布式约束满足问题的研究成为了多智能体系统中的一个重要方向。在多智能体系统中，任务重新分配就是将一个被分解成一系列子任务的全局任务分配到不同智能体的过程。任务的组织结构可以很大程度地影响问题求解的过程，因此任务分配本身就是一个优化问题。任务的重新分配是与多智能体系统中的自组织问题密切相关的。为了更有效地解决因此，本文提出了一种适应性更强的算法，使一个组织结构中的智能体能够动态地协商，而不是由某一个智能体来完成任务分配的工作，通过这种方法找到满意的分配方案。我们首先用求解问题的过程中所需要传递的远程消息的数量作为衡量一个组织结构好坏的的标准。然后我们提出一个更全面的衡量问题求解代价的评价标准，这个标准既考虑到了远程消息的数量，同时也考虑了任务的重新分配导致本地任务复杂性的变化。仿真结果证实了这种动态任务调整的有效性。 |
| 索取号 | TP18/S44/2003 |
| 英文摘要 | 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 |
| 公开日期 | 2012-08-29 |
| 分类号 | TP18 |
| 内容类型 | 学位论文 |
| 源URL | [http://ir.sia.ac.cn/handle/173321/9456]  |
| 专题 | 沈阳自动化研究所_工业信息学研究室_工业控制系统研究室 |
| 推荐引用方式 GB/T 7714 | 沈志江. 分布式约束满足问题及其在多智能体任务重分配中的应用[D]. 中国科学院沈阳自动化研究所. 中国科学院沈阳自动化研究所. 2003. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论