Title: | a generalized framework for bdd-based replanning a* search |
Author: | Xu Yanyan
; Yue Weiya
|
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 Name: | 3rd International Workshop on e-Activity (IWEA2009)/10th ACIS International Conference on Software Engineering Artificial Intelligence, Networking and Parallel/Distributed Computing
|
Conference Date: | MAY 27-29,
|
Issued Date: | 2009
|
Conference Place: | Daegu, SOUTH KOREA
|
Keyword: | A*
; BDD-based search
; incremental search
; heuristic search-based planning
; replanning
|
Publisher: | SNPD 2009: 10TH ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCES, NETWORKING AND PARALLEL DISTRIBUTED COMPUTING, PROCEEDINGS
|
Publish Place: | 10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA
|
ISBN: | 978-0-7695-3642-2
|
Department: | Xu, Yanyan Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China.
|
Sponsorship: | IEEE Comp Soc, ACIS
|
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. |
Content Type: | 会议论文
|
URI: | http://ir.iscas.ac.cn/handle/311060/8252
|
Appears in Collections: | 计算机科学国家重点实验室 _会议论文
|
There are no files associated with this item.
|
Recommended Citation: |
Xu Yanyan,Yue Weiya. a generalized framework for bdd-based replanning a* search[C]. 见:3rd International Workshop on e-Activity (IWEA2009)/10th ACIS International Conference on Software Engineering Artificial Intelligence, Networking and Parallel/Distributed Computing. Daegu, SOUTH KOREA. MAY 27-29,.
|
|
|