| Subject: | 计算机软件
|
| Title: | 基于BDD的增量启发式方法及其应用 |
| Author: | 徐艳艳
|
| Issued Date: | 2009-06-04
|
| Supervisor: | 张文辉
|
| Degree Grantor: | 中国科学院软件研究所计算机科学国家重点实验室
|
| Place of Degree Grantor: | 软件所5号楼337房
|
| Degree Level: | 硕士
|
| Keyword: | A*算法，BDD，基于BDD的搜索，启发式搜索，增量搜索
|
| Abstract: | 增量启发式搜索是一种利用先前的搜索信息和启发信息提高本次搜索效率的方法，通常可用来解决动态环境下的重规划问题。在人工智能领域，一些实时系统常常需要根据外界环境的变化不断修正自身，这样就会产生一系列变化较小的相似问题，此时应用增量启发式搜索将会非常有效。
另一方面，基于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*算法。 |
| Language: | 中文
|
| Content Type: | 学位论文
|
| URI: | http://ir.iscas.ac.cn/handle/311060/156
|
| Appears in Collections: | 计算机科学国家重点实验室 _学位论文
|
| File Name/ File Size |
Content Type |
Version |
Access |
License |
|
|---|
| 10001_200518015029002徐艳艳_paper.pdf（2222KB） | -- | -- | 限制开放 | | 联系获取全文 |
|
| Recommended Citation: | |
徐艳艳. 基于BDD的增量启发式方法及其应用[D]. 软件所5号楼337房. 中国科学院软件研究所计算机科学国家重点实验室. 2009-06-04.
|
|
|
