a generalized framework for bdd-based replanning a* search

	*a generalized framework for bdd-based replanning a search**
	Xu Yanyan; Yue Weiya
	2009
会议名称	3rd International Workshop on e-Activity (IWEA2009)/10th ACIS International Conference on Software Engineering Artificial Intelligence, Networking and Parallel/Distributed Computing
会议录名称	10th ACIS Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, SNPD 2009, In conjunction with IWEA 2009 and WEACR 2009
会议日期	MAY 27-29,
会议地点	Daegu, SOUTH KOREA
出版地	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
ISBN	978-0-7695-3642-2
部门归属	Xu, Yanyan Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China.
摘要	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.
关键词	AAA Bdd-based Search Incremental Search Heuristic Search-based Planning Replanning
主办者	IEEE Comp Soc, ACIS
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/8252
专题	基础软件与系统重点实验室
推荐引用方式 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.