试论增量式动态概率规划的研究

《试论增量式动态概率规划的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、东北师范大学硕士学位论文增量式动态概率规划的研究姓名：苏卫华申请学位级别：硕士专业：计算机软件与理论指导教师：谷文祥20080501摘要无论是因为对人工智能理论研究的贡献，还是因为实际的应用前景，作为人工智能的一个重要分支，智能规划的研究价值不可小觑，近年来研究成果颇多，成绩斐然。为了让智能规划能处理更为实际及复杂的问题，当前很多研究人员热衷于不确定规划的研究，比如说概率规划。其中，很多概率规划系统研究最短路径问题，然而当环境发生变化时，原来的规划结果将不再适用或不是足够好，许多系统不得不重新进行规划。当然，环境的变化通常是渐变的，重新规划时处理的往往是相似的

2、规划问题，所以多次的重规划中，存在大量的重复规划和搜索过程，如果完全重新独立规划，规划系统的效率是低下的，在某些领域甚至是不可容忍的。如何记住已经进行过的可以复用的规划成果，在时间和空间寻求一个均衡点，就是增量式规划的任务。尽管目前对增量式规划已经有了若干研究，但并不广泛。本文将随机概率规划问题转为马尔可夫决策过程(MDP)模型来研究，同时结合了启发式搜索的算法，用启发值的迭代计算来解决最短路径规划问题，在这基础上，研究其中规划过程的特点和规律，当环境不断变化时，我们用增量式规划的方法来重规划，重复利用了前面规划的成果，减小了再次状态空间扩展时的规模，更加快速

3、的进行启发值的迭代计算，提高整个规划过程的效率。本文主要的工作有：提出了增量式动态概率规划的模型和定义，设计了增量式动态概率规划的状态空间生成算法、增量式动态概率规划启发值的迭代算法及增量式动态概率规划的算法。同时，本文用C++语言编写代码，在LiIluX系统环境下开发了赛车问题域的增量式动态概率规划系统，实现了该算法。用大量实例进行测试，结果验证了算法的有效性，特别是进行重规划时，大大减小了状态空间的再扩展规模和启发值迭代计算的次数，从而节省了规划时间，提高重规划的效率。关键词：智能规划；概率规划；增量式；最短路径；启发式搜索AbstractTheresea

4、rchinto硫elligentpla加mg，tllankstoitsco曲jbutiont0aItificialintelligencetlleo巧aIldbroad印pliedforegrouIld，is诵delyconsideredt0beofessentimiInponaIlce．Recently，remarkableachievementhasbeen晰协essed．MeaIlwmle，t0solvemorefactualandcomplexproblems，researcherscommitt11emselVestotllesmdyofuncert

5、aint)，plaI】11ing，inW11ichoneproperi11St姐ceshouldbementioned，theprobabilisticpl蛐g．Researchershaveinvestigatedm锄yprobabiliSticpl觚mngsyStemsthata110wonetosolVeshortest-patllp1砌ngproblems．HoweVer，whjletlleenViroIlIIlentchaIlges，theoriginalplansmightnolongerapply0rmightIlotbegoodenou曲a11

6、ymore，tllerefore，correspondingsystemsshouldbereplaned．Itis仃uethatthechallgesoftheenvir0Imlentareusually黟adualaIldt11ereforesmall，sotlleplal】J1ingproblemsaremoreorlesssimil跹111those伊adualckmges，therearemanyrepeatedplansa11dsearcllingprocesses，andacompletecomputationoftllebeStplancaIl

7、beinef!ficientsincesomeofthep代viollSsearchresultScanbereused，w11ichcomdbeuIlbearableiIlsomedomaills．Howt0remembernleresultsofmeplansa11dtoseekabalancepoimbetweennletiIIleandtllespaceisjllstWhatincrement村searchmethods仃yt0solVe．Although也erearcsomeresearchesonⅡlestudyofiIlcrement甜pl锄in

8、g，itisstillnotbroad