基于启发式搜索和领域知识约束的智能规划方法研究

《基于启发式搜索和领域知识约束的智能规划方法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号TPl8密级公开重庆邮电大学硕士学位论文论文题目基于启发式搜索和领域知识约束的智能规划方法研究英文题目ResearchonIntelligentPlanningBasedonSearchHeuristicsandDomainControlKnowledge硕士研究生指导教师肖祖仁李伟生教授学科专业计算机软件与理论论文提交日期2012年4月论文答辩日期2012年5月26日论文评阅人答辩委员会主席2012年5月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别

2、加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庞由＆电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：FI／．／肖别二签字日期：切，1年f月Ⅸ日学位论文版权使用授权书本学位论文作者完全了解重庞邮电大堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权重迭由＆电太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采

3、用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：惴采“二导师签名：李审芝签字日期：沙f2年e月够日签字日期：劫f锌f月落日重庆邮电大学硕士论文摘要智能规划是一门前沿交叉学科，其发展对计算机科学、人工智能、认知科学等产生了重要影响。上世纪90年代，图规划理论和启发式规划方法取得了巨大进展，大部分规划器都采用了规划图和启发式搜索技术；进入21世纪，研究人员越来越注重领域知识和约束条件的运用，并将规划器分成两大类，一类是基于规划图和启发式搜索的领域无关规划器，另一类是

4、基于领域知识的领域约束规划器。目前的研究热点在于将领域无关的启发式搜索技术运用到基于领域知识的领域约束规划中去。本文研究了基于启发式搜索的领域无关规划方法和基于领域知识的领域约束规划方法，分析了各自的优缺点，深入探讨了将领域无关的启发式搜索技术运用到领域约束规划中去的方法。鉴于此，作者在领域约束规划器TLPlan的基础上，改进得出了FFheu2TL规划系统：使用FF式的启发式估价函数和有用动作剪枝技术改进标准的最佳优先(Best．First)搜索算法，得出“Best．First．Helpful．Action”搜索算法

5、，并结合TLPlan中由一阶线性时序逻辑(LTL)表示的领域知识，引导和控制规划进程，有效地降低了搜索空间，提高了规划效率。针对现有规划器主要关注求解过程，而很少对规划解的质量进行优劣分析这一不足，本文提出了基于多目标测量函数的规划解质量测评方法，重点阐述了如何使用倾向控制等软性约束条件和规划时间、规划长度、资源约束等测量依据对规划解的质量进行综合测评和优劣分析。研究发现对规划解的质量进行综合测评非常重要，这可以帮助我们获取质量最优的规划解，从而节省时间、空间或其他资源开销。实验结果表明，相比TLPIan在最佳优先(

6、Best．First)等搜索策略上的糟糕表现，FFheu2TL采用“Best．First．Helpful．Action”搜索策略取得了一定进步。另外，基于多目标测量函数的规划解质量测评方法是可行的，且具有实际意义。关键词：启发式搜索，领域知识，FFheu2TL，多目标测量函数，质量测评AbstractIntelligentplanningisanewinterdiscipline．ItsdevelopmenthasamaJorimDactonComputerScience，ArtificialIntelligence

7、andCognitiveScience·Inthe1990s。thegraphplantheoriesandheuristicplanningmethodshayemadetremendousprogress．Mostoftheintelligentplannersmakeuseottheplanning-graphandheuristicsearchtechnology．Intothe21乳century，researcherspaymoreandmoreattentiontodomainknowledgeandc

8、onstraInts，anddividetheplannersintotwocategories：domain。independentPlannersbasedonplanning．graphandheuristics，anddomain。dependentplannersbasedondomainknowledgeandconstraints