the bdd-based dynamic a* algorithm for real-time replanning

	*the bdd-based dynamic a algorithm for real-time replanning**
	Xu Yanyan; Yue Weiya; Su Kaile
	2009
会议名称	3rd International Workshop on Frontiers in Algorithmics
会议录名称	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
会议日期	JUN 20-23,
会议地点	Hefei, PEOPLES R CHINA
出版地	HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
出版者	FRONTIERS IN ALGORITHMICS, PROCEEDINGS
ISSN	0302-9743
ISBN	978-3-642-02269-2
部门归属	Xu, Yanyan Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China.
摘要	Finding optimal path through a graph efficiently is central to many problems; including route planning for a mobile robot. BDD-based incremental heuristic search method uses heuristics to focus their search and reuses BDD-based information from previous searches to find solutions to series of similar search problems much faster than solving each search problem from scratch. In this paper, we apply BDD-based incremental heuristic search to robot navigation in unknown terrain, including goal-directed navigation in unknown terrain and mapping of unknown terrain. The resulting BDD-based dynamic A* (BDDD) algorithm is capable of planning paths in unknown, partially known and changing environments in an efficient, optimal, and complete manner. We present properties about BDDD and demonstrate experimentally the advantages of combining BDD-based incremental and heuristic search for the applications studied. We believe that our experimental results will make BDD-based D* like replanning algorithms more popular and enable robotics researchers to adapt them to additional applications.
关键词	Modular Robots Navigation Robot Programming
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/8340
专题	基础软件与系统重点实验室
推荐引用方式 GB/T 7714	Xu Yanyan,Yue Weiya,Su Kaile. the bdd-based dynamic a* algorithm for real-time replanning[C]. HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY:FRONTIERS IN ALGORITHMICS, PROCEEDINGS,2009.