###
DOI:
Journal of Software:2009.20(9):2352-2365

基于BDD的增量启发式搜索
徐艳艳,岳伟亚
(中国科学院 软件研究所 计算机科学国家重点实验室,北京 100190 ;中国科学院 研究生院 信息科学工程学院,北京 100190;Department of Computer Science, College of Engineering, University of Cincinnati, Cincinnati 45219, USA)
BDD-Based Incremental Heuristic Search
XU Yan-Yan,YUE Wei-Ya
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3800   Download 3654
Received:July 19, 2008    Revised:January 15, 2009
> 中文摘要: 增量搜索是一种利用先前的搜索信息提高本次搜索效率的方法,通常可以用来解决动态环境下的重规划问题.在人工智能领域,一些实时系统常常需要根据外界环境的变化不断修正自身,这样就会产生一系列变化较小的相似问题,此时应用增量搜索将会非常有效.另外,基于BDD(binary decision diagram)的启发式搜索,结合了基于BDD的搜索和启发式搜索这两种方法的优点.它既用BDD这一紧凑的数据结构来表示系统的状态空间,又通过使用启发信息来进一步压缩搜索树的大小.在介绍基于BDD的启发式搜索和增量搜索之后,结合这两种方法给出了基于BDD的增量启发式搜索算法——BDDRPA*.大量的实验结果表明,BDDRPA*算法是非常有效的,它可以被广泛地应用到智能规划、移动机器人问题等领域中.
Abstract:Incremental search reuses information from previous searches to find solutions to a series of similar search problems. It is potentially faster than solving each search problem from scratch. This is very important because many artificial intelligence systems have to adapt their plans continuously to changes in the world. If the changes are small, incremental search will be very efficient. BDD (binary decision diagram)-Based heuristic search combines the advantages of BDD-based search and heuristic search. Heuristic search impacts the size of the resulting search trees and BDDs can be used to efficiently describe the sets of states based on their binary encodings. This article first introduces BDD-based heuristic search and incremental search. Combining the two methods, it then gives a BDD-based incremental heuristic search algorithm BDDRPA*. The experimental results show that BDDRPA* is a very efficient incremental heuristic search algorithm. It can be used to solve many problems like symbolic replanning and robot navigation problems and so on.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60833001, 60721061, 60725207 (国家自然科学基金); the National Basic Research Program of China under Grant No.2010CB328103 (国家重点基础研究发展计划(973)) Supported by the National Natural Science Foundation of China under Grant Nos.60833001, 60721061, 60725207 (国家自然科学基金); the National Basic Research Program of China under Grant No.2010CB328103 (国家重点基础研究发展计划(973))
Foundation items:
Reference text:

徐艳艳,岳伟亚.基于BDD的增量启发式搜索.软件学报,2009,20(9):2352-2365

XU Yan-Yan,YUE Wei-Ya.BDD-Based Incremental Heuristic Search.Journal of Software,2009,20(9):2352-2365