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

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第一章 引 言

1.1智能规划的研究现状以及意义

1.2本文主要内容以及章节安排

第二章 不确定规划的背景知识

2.1不确定规划

2.2基于模型检测的不确定规划

2.3本章小结

第三章 信息传递法算法

3.1相关概念

3.2信息传递法求可达关系

3.3信息传递算法及复杂度分析

3.4算法实例

3.5算法实验

3.6本章小节

第四章 可达关系维护的算法

4.1研究维护可达关系算法的意义

4.2相关概念

4.3维护非循环不确定状态转移系统可达关系的方法

4.4维护非循环不确定系统可达关系的算法及复杂度分析

4.5实例分析及算法性能分析

4.6本章小节

第五章 总结与期望

参考文献

致谢

附录A（攻读硕士学位期间发表的论文）

附录B（攻读硕士学位期间参与的科研项目）

附录C（攻读硕士学位期间获奖情况）