不确定规划中带权值的强规划算法研究

发布时间：2017-09-27 12:11

  本文关键词：不确定规划中带权值的强规划算法研究

  更多相关文章： 不确定规划 多agent规划 模型检测 强规划

【摘要】：基于模型检测的方法因其能够解决很多现实世界中的不确定规划问题,已成为研究不确定规划的主要方法之一。当使用基于模型检测的方法来对不确定规划问题进行求解时,可以得到三种不同类型的解:弱规划解、强循环规划解、强规划解;其中,执行强规划解能够确保不确定转移系统在有限的步长内从初始状态到达目标状态,在一些要求绝对满足安全的规划中,强规划解是唯一满足要求的解,而在实际应用中,执行规划动作需要耗费一定的时间、金钱等,这些代价可以用动作权值来表示,所以研究动作权值之和最小的强规划解是很有意义的。本文主要研究了完全可观察条件下单agent带权值的不确定规划问题和完全可观察条件下多agent带权值的不确定规划问题。针对完全可观察下单agent带权值的不确定规划问题,目前已有对最小权值强规划解的研究,但算法的效率欠佳,有必要继续研究新的方法,进一步提高求解的效率。本文通过引入基于模型检测的强规划分层法,对系统进行分层,然后利用得到的分层信息,能够快速排除那些无强规划解的情况;当存在强规划解时,设计了一种利用分层信息反向搜索最小权值的算法,该算法通过动态确定搜索上界和搜索下界的策略,避免了许多无用的搜索。通过对实验数据的分析可知,本文的算法能够较快的求出最小权值强规划解,且效率高于已有的直接搜索的算法。目前,对不确定规划问题的研究主要是针对单agent的,而对于多agent的研究则侧重于确定规划。针对这一现状,本文首次提出了完全可观察下多agent带权值的不确定规划问题,并设计了使所求解的强规划解所需的动作权值总和近似最小的算法SPSMNPW。在算法SPSMNPW中,先利用基于模型检测的强规划分层方法对每个agent进行强规划分层,然后利用规划问题中agent的初始状态集合等信息来合并所有agent的分层信息,并在合并的过程中得到同层状态之间的冲突表,再使用正向搜索方法,在保证冲突最小的情况下,以最小动作权值优先的贪心方法,求出强规划解。通过对实验结果的分析可知,本文所设计的算法能够较快的求解出使所选择的动作权值总和近似最小的强规划解。
【关键词】：不确定规划 多agent规划 模型检测 强规划
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O221
【目录】：

• 摘要4-5
• Abstract5-9
• 第1章 引言9-12
• 1.1 课题的背景和意义9-10
• 1.2 本文的主要内容和组织结构10-12
• 1.2.1 主要内容10-11
• 1.2.2 组织结构11-12
• 第2章 背景知识12-20
• 2.1 智能规划12-13
• 2.2 不确定规划与基于模型检测的不确定规划13-17
• 2.3 多agent规划17-19
• 2.4 本章小结19-20
• 第3章 完全可观察下单agent带权值的强规划算法20-36
• 3.1 问题描述20-21
• 3.2 相关定义21-24
• 3.3 算法24-32
• 3.3.1 强规划分层算法25-26
• 3.3.2 最小权值强规划解搜索算法26-28
• 3.3.3 正确性分析28-29
• 3.3.4 算法示例分析29-32
• 3.4 实验32-34
• 3.5 本章小结34-36
• 第4章 完全可观察下多agent带权值的强规划算法36-54
• 4.1 问题描述36-37
• 4.2 相关定义37-41
• 4.3 算法41-52
• 4.3.1 多agent强规划分层算法42-43
• 4.3.2 强规划算法43-46
• 4.3.3 冲突处理算法46-47
• 4.3.4 正确性分析47
• 4.3.5 算法示例分析47-52
• 4.4 实验52-53
• 4.5 本章小结53-54
• 第5章 总结与展望54-55
• 参考文献55-59
• 致谢59-60
• 附录A （攻读硕士学位期间发表的论文）60-61
• 附录B （攻读硕士学位期间参与的科研项目）61
• 附录C （攻读硕士学位期间获奖情况）61

，

本文编号：929616