基于不确定系统的状态可达关系求规划解的算法研究

摘要

智能规划是人工智能近年来的热点研究领域，而关于不确实规划的研究是其中一个重要分支。不确定规划问题由于动作的不确定性，已存在的用来求不确定状态转移系统的强规划解、弱规划解及强循环规划解的方法都是采取从目标状态开始进行反向搜索的方法来求规划解，但由于没有任何引导信息，求规划解时常常会重复搜索大量无用的状态和动作，所以如何获得系统的引导信息，并用于求规划解以提高求解的效率一直是研究的难点。
　　本文针对以上问题，基于不确定状态转移系统的状态可达关系，对于不确定状态转移系统中规划解的求解问题，主要做了以下两方面的研究：
　　1.在不确定规划领域中，不确定状态转移系统求规划解时常常存在大量冗余操作，造成不必要的搜索和计算。本文将不确定状态转移系统转换为邻接矩阵，使用邻接矩阵的加和乘运算获得系统中的可达矩阵，即获得了系统状态间的可达关系。因此，我们基于这两个矩阵设计了基于可达关系正向搜索强规划解、弱规划解的算法，在求规划解的过程中，根据邻接矩阵为系统确定下一步该选择执行的动作，在可达矩阵中判断执行该动作到达的状态是否可达目标状态，以此确定该状态动作序偶是否能够加入到规划解中。若执行动作到达的状态不可达目标状态，则可以避免搜索这些对构成规划解没有用的状态和动作。在搜索的过程中根据两个矩阵的值判断状态和动作是否有用，若无用，则直接避免了搜索，减少了大量冗余计算，提高了求规划解的效率。
　　2.多agent规划问题首次的正式讨论出现在2010年的ICAPS上，现在关于多agent规划领域的研究多为具有确定动作的多agent规划问题，而具有不确定动作的多agent规划问题的研究还是一个很新的领域。本文针对不确定多agent规划系统协同规划解的问题，设计了基于可达关系求多agent规划解的算法。在假设agent执行每个动作的时间相等的前提下，该算法利用邻接矩阵和可达矩阵中关于状态之间的转移信息及可达信息，为多个agent确定下一步转移的动作，执行动作后，存在agent与上一个agent到达的状态相同且总执行时间相等的情况下，对该agent执行等待一个动作执行时间的操作，避免多agent造成的冲突，寻找出协同规划解。根据算法进行了实验，证明了该算法的正确性和有效性。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 引言

1.1 智能规划的相关知识

1.2 本文主要内容及组成章节

第2章 不确定规划领域的相关知识

2.1 不确定规划

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

2.3 本章小结

第3章 基于可达关系正向搜索强、弱规划解

3.1 基于可达关系求规划解中的相关定义

3.2 反向搜索方法求强规划解、弱规划解

3.3 基于状态分层正向搜索强规划解、弱规划解算法

3.4 基于可达关系正向搜索强规划解算法

3.5 基于可达关系正向搜索弱规划解算法

3.6 本章小结

第4章 基于可达关系求多agent规划解

4.1 多agent规划领域的相关知识

4.2 基于可达关系求多agent规划解

第5章 总结与展望

参考文献

致谢

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

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

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