中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
题名:
基于BDD的增量启发式搜索方法及其应用
作者: 徐艳艳
答辩日期: 2009-06-04
授予单位: 中国科学院软件研究所
授予地点: 软件研究所
学位: 博士
关键词: A*算法 ; BDD ; 基于BDD的搜索 ; 启发式搜索 ; 增量搜索
其他题名: BDD-based incremental heuristic search and its applications
摘要: 增量启发式搜索是一种利用先前的搜索信息和启发信息提高本次搜索效率的方法,通常可用来解决动态环境下的重规划问题。在人工智能领域,一些实时系统常常需要根据外界环境的变化不断修正自身,这样就会产生一系列变化较小的相似问题,此时应用增量启发式搜索将会非常有效。另一方面,基于BDD的强大的搜索技术利用BDD有效操作性以及化简后唯一性的优点, 在一定程度上缓解了模型检测的状态爆炸问题,使得被检测状态的个数大大增加。 1、本文结合基于BDD的启发式搜索和基于BDD的增量搜索这两种方法给出了基于BDD的增量启发式搜索方法, 基于BDD的增量启发式搜索综合了基于BDD的搜索、增量搜索以及启发式搜索这三种方法的优点。它既用BDD作为数据结构以提高搜索的空间效率, 又结合了增量搜索的思想来提高重搜索的效率,同时,又引入了启发函数来进一步压缩搜索空间。 2、本文介绍了基于BDD的增量启发式搜索算法BDDRPA*并用大量的实验结果证明BDDRPA*的高效性。给定一个搜索问题, BDDRPA*算法先用基于BDD的启发式搜索方法搜出一条从初始节点到目标节点的最短路径;接着, 问题的状态格局发生改变,BDDRPA*再用基于BDD的增量搜索方法根据旧格局的迁移关系BDD_T构造出新格局的迁移关系BDD_{T'}, 然后再用启发式方法搜索路径,如此反复下去。 3、本文介绍了基于BDD的动态增量启发式搜索算法BDDD*并用大量的实验结果证明BDDD*的高效性。 BDDD*算法在机器人边走边扫描的过程中,不断根据机器人新获得的信息更新已知地图并重新规划路线。每次规划时,BDDD*都假设未知的领域没有任何障碍物, 也就是每个位置都是可通的,它按照这个假设去计算从当前位置到目标位置的最短路径。如果在行走的过程中扫描到了障碍物,它就把这条信息添加到它的地图中,然后重复 上面的过程,直到到达目标位置或者发现每条路径都被堵死为止。 BDDRPA*算法和BDDD*算法可以应用到机器人线路规划、智能交通及计算机网络的线路规划问题中。 另外,在机器学习和控制领域,也可以考虑使用BDDRPA*算法和BDDD*算法。
英文摘要: 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-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. In this thesis, we first introduce BDD-based heuristic search and BDD-based incremental search. Combining the two methods, we then describe BDD-based incremental heuristic search. Based on BDD-based incremental heuristic search, we give our algorithm BDDRPA*. Our experiment results show that BDDRPA* is very efficient. BDDRPA* reuses previous search results to repeatedly find shortest paths from a start vertex to a goal vertex while the edge costs of a graph change or vertices are added or deleted. Its first search is the same as that of a version of BDD-based heuristic search. As the topology of the graph changes, BDDRPA* uses the previous BDD for T to construct the new BDD for the changed transition relation T'. Many of the subsequent searches are potentially faster because it reuses the old transition relations. BDDD* apply BDD-based incremental heuristic search to robot navigation in unknown terrain. BDDD* is capable of planning paths in unknown, partially known and changing environments in an efficient, optimal, and complete manner. In BDDD*, the robot starts at the start cell and has to move to the goal cell. It always computes shortest path from its current cell to the goal cell under the assumption that cells with unknown traversability status are traversable. It then follows this path until it reaches the goal cell, in which case it stops successfully, or it observes additional untraversable cells, in which case it recomputes a shortest path from its current cell to the goal cell. BDDRPA* and BDDD*'s applications include: symbolic planning (HSP), mobile robotics and games (path planning), machine learning (reinforcement learning), control (parti-game algorithm) and so on.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/5870
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
10001_200518015029002徐艳艳_paper.pdf(2222KB)----限制开放-- 联系获取全文

Recommended Citation:
徐艳艳. 基于BDD的增量启发式搜索方法及其应用[D]. 软件研究所. 中国科学院软件研究所. 2009-06-04.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[徐艳艳]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[徐艳艳]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace