| 题名 | 基于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. |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 124 |
| 内容类型 | 学位论文 |
| 源URL | [http://124.16.136.157/handle/311060/5870]  |
| 专题 | 软件研究所_计算机科学国家重点实验室 _学位论文 |
| 推荐引用方式 GB/T 7714 | 徐艳艳. 基于BDD的增量启发式搜索方法及其应用[D]. 软件研究所. 中国科学院软件研究所. 2009. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论