信息传递法求解与维护不确定状态系统的可达关系

发布时间：2017-10-25 14:32

  本文关键词：信息传递法求解与维护不确定状态系统的可达关系

  更多相关文章： 不确定规划 可达关系 信息传递 可达关系维护

【摘要】：智能规划是隶属于人工智能领域的一个重要研究方向,近年来受到许多学者的关注。而不确定规划则是其中的一个重要分支。近几年来,有较多针对不确定规划的研究,但由于在求规划问题的解时,缺少引导信息,会导致许多无用状态和动作被搜索,造成冗余计算。因此在求规划解之前,先对不确定状态转移系统中的状态之间的关系进行预处理,找出它们之间的可达关系,这样能加快对于规划问题的求解。有学者运用邻接矩阵来表示不确定状态转移系统,运用矩阵自乘来模拟系统的中控制器的位置转移,能求出状态之间的可达关系,但该类算法对于规模较大的系统效率比较低。因此,本文仔细分析了现有算法的优势之处,找出了其存在的不足之处,设计了一种全新的求可达关系算法,能高效的求解大规模不确定状态转移系统的可达关系。并对不确定系统中可能存在动作变化(确定动作因某种因素无法执行),设计了一种局部更新其可达关系算法,避免了重新求解状态之间的可达关系,提高了效率。具体研究内容如下:1.参考了计算机网络中的RIP路由协议,提出了用信息传递法来求解可达关系,仍旧用邻接矩阵表示不确定状态转移系统,并且将每一行中的可达关系视为其他状态到达该状态的可达信息;通过状态之间的信息的收集、状态之间信息传递、状态自身信息的更新,分三个阶段求得不确定系统的状态可达关系,避免了大量的矩阵运算,并通过分析算法的时间复杂度,从理论上证明了该算法的高效性。与此同时,对每个状态的可达信息进行标记,避免了对不确定规划系统是否有回路进行分类及设计不同的算法,降低了算法实现的难度。最后通过实例以及实验,运用信息传递法求解非循环和循环的不确定状态转移系统的可达关系,进行了详细的说明。2.提出了针对非循环的不确定状态转移系统在确定动作无法执行的情况下,维护该系统可达关系的算法。在信息传递法的基础之上,提出了对于非循环不确定状态转移系统的最小信息传递集(简称MIDS),分析了MIDS的性质。通过MIDS,可以快速判断无法执行的确定动作是否会对系统的可达关系产生影响。同时,对于每个状态的可达信息建立索引,通过索引,可以实现对系统的可达关系进行局部更新,从而避免了对该系统状态之间可达关系的重新计算,提高了求可达关系的效率。
【关键词】：不确定规划 可达关系 信息传递 可达关系维护
【学位授予单位】：湘潭大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 引言9-12
• 1.1 智能规划的研究现状以及意义9-11
• 1.1.1 经典智能规划10-11
• 1.1.2 非经典智能规划11
• 1.2 本文主要内容以及章节安排11-12
• 1.2.1 主要内容11
• 1.2.2 章节安排11-12
• 第二章 不确定规划的背景知识12-16
• 2.1 不确定规划12-13
• 2.2 基于模型检测的不确定规划13-15
• 2.2.1 模型检测的发展与运用13-14
• 2.2.2 模型检测的基本概念14-15
• 2.3 本章小结15-16
• 第三章 信息传递法算法16-37
• 3.1 相关概念18-20
• 3.2 信息传递法求可达关系20-24
• 3.2.1 信息传递法步骤说明20-23
• 3.2.2 信息传递方法的正确性23-24
• 3.3 信息传递算法及复杂度分析24-27
• 3.3.1 信息传递算法24-26
• 3.3.2 信息传递算法复杂度分析26-27
• 3.3.3 性能比较27
• 3.4 算法实例27-33
• 3.4.1 非循环的不确定状态转移系统27-30
• 3.4.2 循环的不确定状态转移系统30-33
• 3.5 算法实验33-36
• 3.6 本章小节36-37
• 第四章 可达关系维护的算法37-52
• 4.1 研究维护可达关系算法的意义37-38
• 4.2 相关概念38-41
• 4.2.1 相关定义38-40
• 4.2.2 最小信息传递集合的性质40-41
• 4.3 维护非循环不确定状态转移系统可达关系的方法41-44
• 4.3.1 维护可达关系的基本思路41-42
• 4.3.2 判断可达关系是否发生变化42-43
• 4.3.3 局部更新可达关系的方法43-44
• 4.4 维护非循环不确定系统可达关系的算法及复杂度分析44-46
• 4.4.1 求最小信息传递集合算法44-45
• 4.4.2 局部更新算法45
• 4.4.3 算法复杂度分析45-46
• 4.5 实例分析及算法性能分析46-51
• 4.5.1 求最小信息传递集合举例46-48
• 4.5.2 维护可达关系举例48-50
• 4.5.3 实验性能比较50-51
• 4.6 本章小节51-52
• 第五章 总结与期望52-53
• 参考文献53-57
• 致谢57-58
• 附录A （攻读硕士学位期间发表的论文）58-59
• 附录B （攻读硕士学位期间参与的科研项目）59
• 附录C （攻读硕士学位期间获奖情况）59

【参考文献】

中国期刊全文数据库 前2条

1 黄丽芳;文中华;胡雨隆;吴正成;;不确定规划中状态循环可达关系的求解方法[J];计算机应用研究;2013年09期

2 文中华;黄巍;刘任任;姜云飞;;模型检测规划中的状态之间的可达关系研究[J];计算机学报;2012年08期

，

本文编号：1094155