中国科学院沈阳自动化研究所机构知识库
Advanced  
SIA OpenIR  > 工业信息学研究室  > 工业控制系统研究室  > 学位论文
题名: 强化学习在多智能体系统任务分配中的应用
其他题名: Research on Task Allocation in Multi-agent Systemswith Reinforcement Learning
作者: 王国权
导师: 于海斌
分类号: TP18
关键词: 多智能体系统 ; 任务分配 ; 强化学习 ; 状态集结 ; 博弈论
索取号: TP18/W32/2004
学位专业: 机械电子工程
学位类别: 硕士
答辩日期: 2004-06-29
授予单位: 中国科学院沈阳自动化研究所
学位授予地点: 中国科学院沈阳自动化研究所
作者部门: 工业控制系统研究室
中文摘要: 智能体、多智能体系统理论与技术不仅是分布式人工智能和计算机科学技术的重要研究内容之一,也是制造工程和社会学等其他学科的重要研究课题。任务分配是指针对某个目标,遵循一定的策略将规模为N的任务映射和划分到P个个体上。传统的任务分配算法大致可分为基于图论的分配策略、整数规划方法、试探法及在此基础上衍生出来的其它改进型算法;其目的一般是在众多的匹配方案中寻找一个最合理的子任务分配方案,以达到提高效率、节约成本、合理配置资源或总体收益最佳等系统目标。 多智能体系统的特点决定了其中的任务分配与传统的任务分配有很大的不同。它没有类似于集中式系统中存在的中央控制器,各个智能体只能了解到系统局部的信息,而不是全局的信息。在进行任务分配时,各智能体只能依据自身的信息以及其部分“邻居”的信息来进行任务选择和竞争。当前,多智能体系统任务分配问题已经成为分布式人工智能领域的研究热点。 强化学习是一种重要的机器学习方法,它能够利用不确定的环境奖赏值发现系统的最优策略,实现动态环境的在线学习,因而强化学习技术是构成智能体具有智能的基础之一。 本文在强调智能体之间相互竞争的基础上,对多智能体系统中的任务分配问题进行了较为深入的研究,主要工作可分为以下几点: 分析了多智能体系统任务分配问题的研究现状,较详细地归纳总结了几种典型的分布式任务分配算法,指出了各自的特点和适用范围。强调指出了基于竞争的多智能体系统任务分配算法的可行性。对强化学习基本理论、方法进行了概述,较详细地归纳总结了当前分布式强化学习研究现状,并对三种典型方法进行了分析比较,指出了它们的优劣。 介绍了多智能体系统联盟和联盟形成理论;基于社会生活中的竞争现象,提出了一种多智能体系统任务分配竞争模型:智能体通过竞争和协商的手段,实现系统任务分配;文中给出了该模型的数学描述。 介绍了博弈论基本理论;给出了任务竞争和资源竞争的详细算法描述;在求解次优收益时采用了分布式学习中的群体强化学习法,考虑到群体强化学习所需的状态存储空间随智能体个数的增加而激增的缺陷,文中采了状态集结法加以解决;给出了对状态集结法收敛性验证的仿真结果和多智能体系统任务分配的仿真试验,并对实验现象进行了分析。 最后,对本文工作进行了总结,指出其中的缺点和不足,并对未来工作进行了展望。
英文摘要: The theory and technology of agent and multi-agent system are not only the research focus of distributed artificial intelligence and computer science, but also the content of manufacturing engineering and other subjects. The task allocation problem has been studied extensively for a number of years and has been proved as an NP-hard problem. The approaches to solving the task allocation problem can be classified to the following three categories: graph theoretic approaches, integer programming approaches, heuristic approaches. Traditionally, task allocations are often considered in a centralized and static setting. A single controller would gather and examine all the relevant information about the current organization and mission, then decide and allocate tasks for every fellow agent. The characters of Multi-agent system decide that its task allocations are absolutely different from what has been described above. There is no central controller in a MAS, and agents are independent and autonomic relatively. Communications among agents are deficient and limited. And also, a solution to task allocation in MAS must consider the dynamic aspects of the environment and unexpected changes in agents. Agents in organization must be able to negotiate without any fixed leaders and find a relatively satisfying solution to all the agents. Reinforcement learning is a kind of important machine learning approach. It can find the optimal system strategy by uncertain enviroment awards through realizing the system to lean online. So it is very important to make agents intelligent. In this thesis, we propose a MAS model based on market competition to solve the task allocation problem. The main contributions are summarized as the follows: State the problem of task allocation, and summarize the presently existed algorithms to solve it. Point out the merit and demerit of each algorithm. Draw the conclusion that the task allocation algorithms based on competition is promising. Introduce the basic theory and approaches of reinforcement learning. Analyze in detail the current situations and pending problems of distributed reinforcement learning, and point out the merit and demerit of each approach. Introduce the basic theory of coalition and coalition forming. Additionally, a MAS model based on market competition has been proposed. The mathematical model is established. Introduce the basic theory of Game Theory and Nash Equilibrium. Apply game theory into task allocation problem to solve the problem of interactive agents. Based on statistics theory we analyze the experimental results. Our work is innovative, because the profits of each agent are emphasized and the payoff of the individual is principal. Based on this precondition, each agent contributes to the group profit. Experiments prove the effectiveness of our approach. Finally, draw the conclusion of this thesis, point out the innovative parts, and forecast the future research work.
语种: 中文
产权排序: 1
内容类型: 学位论文
URI标识: http://ir.sia.cn/handle/173321/9471
Appears in Collections:工业信息学研究室_工业控制系统研究室_学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
强化学习在多智能体系统任务分配中的应用.pdf(541KB)----限制开放 联系获取全文

Recommended Citation:
王国权.强化学习在多智能体系统任务分配中的应用.[硕士学位论文].中国科学院沈阳自动化研究所.2004
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