基于模型检测不确定规划中状态可达性的研究

《基于模型检测不确定规划中状态可达性的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、TheResearchforStateReachabilityRelationofUncertainPlanningviaModelcheckingCandidateHuYulongSupervisorAssociateProf.WenZhonghuaCollegeInstituteofInformationEngineeringProgramComputerScienceandTechnologySpecializationAutomatedPlanningDegreeMasterofEngi

2、neeringUniversityXiangtanUniversitythDateApril,182012湘潭大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规

3、定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湘潭大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期：年月日导师签名：日期：年月日摘要智能规划是人工智能的一个重要领域，不确定规划是智能规划的一个重要分支，它比经典规划更具有现实性。近年来，很多研究人员对基于模型检测的不确定规划进行了大量而深入的研究并取得了很好的成绩。基于模型检测的不确定规划中，求

4、解规划问题时需要反复的搜索动作来寻找目标状态，这带来大量的冗余计算和重复操作。获得一个不确定状态转移系统的状态可达关系可以提高求解规划问题的效率，减少冗余计算，构建状态转移系统的引导信息。因此，本文做了如下研究：1.不确定状态转移系统中，采用传统的求解规划问题的方法去求解规划问题会产生大量的冗余计算，从而降低了求解效率。获得不确定状态转移系统的非循环状态可达关系可以使得求规划问题的强规划解和弱规划解的效率大大提高。本文设计了求不确定状态转移系统中非循环状态可达关系的方法，以及在获得不确定状态转移

5、系统的非循环状态可达关系后求解强规划解的算法，并通过分析算法时间复杂度和实验得出结论：在获得状态可达性关系后求解强规划解的效率有显著的提高。从理论上证明了求不确定状态转移系统的非循环状态可达关系方法的正确性。2.设计了求不确定状态转移系统中循环状态可达关系的方法，循环可达关系是在不确定状态转移系统中普遍存在的一个可达关系。循环可达关系是可达关系的一个重要部分，求循环可达关系可以完善可达关系，增加状态可达关系的应用范围。本文首先分析了循环可达关系的特点，通过这些特点将循环可达关系进行了分类。研究了

6、各类循环可达关系之间的联系；其次，定义了自身二可达关系并且证实了导致循环可达关系的关键是自身二可达关系；在这个前提下，设计了获得各种类型循环可达关系的方法和算法；最后，通过实例将这一求解过程展现出来并且实现了算法。关键字：不确定规划；模型检测；矩阵计算；非循环可达关系；循环可达关系IABSTRACTIntelligentplanningisanimportantfieldofartificialintelligence.Uncertainplanningisanimportantbranchof

7、theintelligentplanning,itismorerealisticthantheclassicplanning.Inrecentyears,manyresearchersextensiveandin-depthresearchonuncertaintyplanningviaModelcheckingandachievedgoodresults.UncertaintyplanningviaModelcheckingforsolvingprogrammingproblemsrequir

8、erepeatedsearchoperationtofindthetargetstate,itbringsalargenumberofredundantcomputationandrepeatoperation.Toobtainastateofuncertaintytransitionsystemreachabilityrelationforsolvingprogrammingproblemscanimproveefficiency,reducetheredundancycalculation,