Institutional Repository
| a generalized framework for bdd-based replanning a* search | |
| Xu Yanyan; Yue Weiya | |
| 2009 | |
| Conference Name | 3rd International Workshop on e-Activity (IWEA2009)/10th ACIS International Conference on Software Engineering Artificial Intelligence, Networking and Parallel/Distributed Computing |
| Source | 10th ACIS Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, SNPD 2009, In conjunction with IWEA 2009 and WEACR 2009 |
| Conference Date | MAY 27-29, |
| Conference Place | Daegu, SOUTH KOREA |
| Publish Place | 10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA |
| Publisher | SNPD 2009: 10TH ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCES, NETWORKING AND PARALLEL DISTRIBUTED COMPUTING, PROCEEDINGS |
| ISBN | 978-0-7695-3642-2 |
| Department | Xu, Yanyan Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China. |
| English Abstract | Recently, it has been suggested that BDD-based Re-Planning A* (BDDRPA*), a BDD-based incremental version of A*, might be an efficient search method for solving path-planning problems in artificial intelligence. BDDRPA* combines ideas of BDD-based search and incremental search to repeatedly find shortest paths from a start vertex to a goal vertex while the topology of the graph changes. However BDDRPA* only works well when vertices art, added or deleted but doest consider the weighted edges. When the edge costs are changed, it doesnt work, and moreover, in BDDRPA*, the heuristic function h is set to 0, so BDDRPA* is degenerated to BDD-based incremental breadth-first search. In this article, we consider BDD-based weighted and heuristic search methods and generalize BDDRPA* to be a real BDD-based incremental heuristic search algorithm (GBDDRPA*). We then show experimentally that GBDDRPA* indeed speeds BDDRPA* up on gridworlds and thus promises to provide a good foundation for building incremental heuristic BDD-search-based replanners. |
| Keyword | A*A**A* Bdd-based Search Incremental Search Heuristic Search-based Planning Replanning |
| Sponsorship | IEEE Comp Soc, ACIS |
| Content Type | 会议论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/8252 |
| Collection | 基础软件与系统重点实验室 |
| Recommended Citation GB/T 7714 | Xu Yanyan,Yue Weiya. a generalized framework for bdd-based replanning a* search[C]. 10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA:SNPD 2009: 10TH ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCES, NETWORKING AND PARALLEL DISTRIBUTED COMPUTING, PROCEEDINGS,2009. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment