主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第6期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
徐艳艳,岳伟亚.基于BDD的增量启发式搜索.软件学报,2009,20(9):2352-2365
基于BDD的增量启发式搜索
BDD-Based Incremental Heuristic Search
投稿时间:2008-07-19  修订日期:2009-01-15
DOI:
中文关键词:  增量搜索  启发式搜索  BDD(binary decision diagram)  重规划
英文关键词:incremental search  heuristic search  BDD (binary decision diagram)  replanning
基金项目: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))
作者单位
徐艳艳 中国科学院 软件研究所 计算机科学国家重点实验室,北京 100190
中国科学院 研究生院 信息科学工程学院,北京 100190 
岳伟亚 Department of Computer Science, College of Engineering, University of Cincinnati, Cincinnati 45219, USA 
摘要点击次数: 3707
全文下载次数: 3583
中文摘要:
      增量搜索是一种利用先前的搜索信息提高本次搜索效率的方法,通常可以用来解决动态环境下的重规划问题.在人工智能领域,一些实时系统常常需要根据外界环境的变化不断修正自身,这样就会产生一系列变化较小的相似问题,此时应用增量搜索将会非常有效.另外,基于BDD(binary decision diagram)的启发式搜索,结合了基于BDD的搜索和启发式搜索这两种方法的优点.它既用BDD这一紧凑的数据结构来表示系统的状态空间,又通过使用启发信息来进一步压缩搜索树的大小.在介绍基于BDD的启发式搜索和增量搜索之后,结合这两种方法给出了基于BDD的增量启发式搜索算法——BDDRPA*.大量的实验结果表明,BDDRPA*算法是非常有效的,它可以被广泛地应用到智能规划、移动机器人问题等领域中.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利