基于因子间依赖关系的启发式规划研究

《基于因子间依赖关系的启发式规划研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号TPl8密级公开重庆邮电大学硕士学位论文论文题目基于因子间依赖关系的启发式规划研究英文题目ResearchofHeuristicStateSearchBasedonDependencyRelationsofGoals硕士研究生指导教师学科专业涂鹏李伟生教授计算机软件与理论论文提交日期2012年4月论文答辩日期2012年5月26日论文评阅人答辩委员会主席曹龙汉教授中国人民解放军重庆通信学院2012年5月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为

2、获得重庞查＆电太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：；棠l；I^匀签字日期：2,,11,-年广月≥r目学位论文版权使用授权书本学位论文作者完全了解重庆蜜＆电太堂有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权重庞由E电太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位论文作者签名：≥皋R龟§导师签名：专I弗七签字日期：u

3、12．年岁月哆日签字日期：咖抄年歹月西日重庆邮电大学硕士论文摘要随着智能规划越来越多在实际问题中的应用，更多的学者开始关注和研究智能规划，人们从多个角度去完善，并提出了多种规划策略，其中，启发式规划方法作为智能规划领域的重要问题之一，在近十几年受到了众多学者的关注和研究。目前具有代表性的启发式规划器有：FF、LPG和Fast-Downward等。由于Fast．Downward将规划问题转化为一个多值规划任务，提出并采用了基于因果图的启发函数，得到了较高的搜索效率。但Fast．Downward的主要缺点在于其采用的基于因果图的启发函数将目标因子相互独立作为一个假设前提，然而在众多的规划问题中

4、，各个目标因子之间往往存在相互依赖关系，造成计算出的启发代价比真实代价值大。针对Fast．Downward存在的不足，本文在充分考虑了因子间依赖关系的基础上，提出一种基于子目标排序和有利值提取的启发函数(HBSH)。首先，根据目标因子间存在的依赖关系，依次从目标集中提取出子目标，得到一个有序的子目标序列，即目标因子合理的实现顺序。接下来以子目标序列中子目标的启发代价依次作为启发值来引导搜索，以达到提高启发函数准确性、加快启发函数计算速度的目的；其次，通过对目标因子间存在的有利依赖关系的分析，结合Fast．Downward中的域转移图技术，提出一种计算目标集在某一状态下存在的有利值的算法，在

5、启发函数每次计算启发代价时都加入有利值提取技术，这样可得到更加准确的启发代价；最后采用最佳优先贪心算法来进行规划求解。在Linux平台下，我们采用C++语言对给出的启发函数进行了实现，并将其嵌入到Fast．Downward规划器进行搜索求解，通过对国际规划大赛2008标准领域问题的实验，结果表明新启发函数在规划解质量和规划效率上都有一定的提高。关键词：智能规划，子目标排序，依赖关系，有利值，启发式重庆邮电大学硕士论文AbstractWiththeintelligentplanningmoreandmorebeusedinpracticalproblem，morescholarsbegint

6、opayattentiontoandresearchintelligentplanning，peoplefrommanyangletoperfectit，andproposemanyplanningstrategy．HeuristicsearchingisoneofthemostimportantproblemsinAIplanning，andberesearchedbymorescholars．FF，LPGandFast—Downwardarethreewellknowheuristicplanners．TheFast-DownwardplannertranslatesaSTRIPSta

7、sktoamulti-valuedplanningtask，andexploitedtheheuristicbasedoncausalgraph，thus，Fast—Downwardyieldsabetterperformance．ThemaindefectofFast-Downwardistheheuristicbasedoncausalgraphneedsthestatevariablestobeindependen