人工智能启发方法OBDD搜索技术重搜索算法

来源：互联网   发布日期：2011-09-29 17:00:36   浏览：35431次  

摘要:在人工智能领域，不确定的动态环境下的重搜索问题的求解空间、时间复杂度都是比较大的，如何改进算法以提高重搜索效率就成为研究者们一直关注的问题在近两年研究成果基础上，本文对如何把启发方法A*算法、基于OBDD的搜索技术和渐进搜索incrementalsearch结合在一起，从而改进重搜索算法这一问题进行了研究本文提出了一个在动态环境下的搜索算法BDDRPA*，它的优点是可以应用到动态的持续变化的领域中，例如持续规划问题、移动的机器人问题等这些问题的特点是系统的状态随时间不断发生改变，因此，初始的规划会变得不太合适甚至不能再使用一般的处理方法是对新的状态的全局进行重新搜索，从而得到新的规划来执行但是，我们发现在较多的问题中，这些改变是局部的，对于整个系统来说都往往是比较小的这样，由于搜索状态的改变只是一小部分，那么再进行一次彻底的搜索就显得不必要，因为我们可以利用上很多原先的搜索记录，这样可以减少我们的搜索空间和时间，这就是渐进搜索的基本思想而BDDRPA*算法就是综合了渐进搜索和基于OBDD的启发式搜索方法而提出的本文首先简要地介绍了经典的搜索算法比如A*，宽度优先搜索算法等，和基于OBDD的搜索算法BDDA*和SetA*接着详细介绍了我们提出的Pre-BDDRPA*算法以及在它基础上做了改进后的正式的BDDRPA*算法，我们给出了该算法的C++伪代码并对其做了一些详细的分析然后通过实验将BDDRPA*和BDDA*算法、LPA*算法、A*算法以及BFS宽度优先等重搜索算法进行比较，实验结果证明，BDDRPA*算法确实能提高了重搜索的效率最后，我们探讨了BDDRPA*在自动规划、机器学习和自动控制三个领域上的应用前景标题:人工智能启发方法OBDD搜索技术重搜索算法专业:计算机软件与理论学位:硕士单位:中山大学@关键词:人工智能　启发方法　OBDD搜索技术　重搜索算法　论文时间:2005分类:TP18 TP301.6 导师:苏开乐 语种:中文文摘URL:

赞助本站