DocumentCode :
3182491
Title :
High Performance State Lattice Planning Using Heuristic Look-Up Tables
Author :
Knepper, Ross A. ; Kelly, Alonzo
Author_Institution :
Robotics Inst., Carnegie Mellon Univ., Pittsburgh, PA
fYear :
2006
fDate :
9-15 Oct. 2006
Firstpage :
3375
Lastpage :
3380
Abstract :
This paper presents a solution to the problem of finding an effective yet admissible heuristic function for A* by precomputing a look-up table of solutions. This is necessary because traditional heuristic functions such as Euclidean distance often produce poor performance for certain problems. Here, the technique is applied to the state lattice, which is used for full state space motion planning. However, the approach is applicable to many applications of heuristic search algorithms. The look-up table is demonstrated to be feasible to generate and store. A principled technique is presented for selecting which queries belong in the table. Finally, the results are validated through testing on a variety of path planning problems
Keywords :
heuristic programming; path planning; search problems; state-space methods; A* algorithm; heuristic look-up tables; heuristic search algorithm; path planning; state lattice planning; state space motion planning; Cost function; Euclidean distance; Heuristic algorithms; Intelligent robots; Lattices; Motion planning; Path planning; State-space methods; Table lookup; Vehicles; heuristic; mobile robot; motion planning; nonholonomic; state lattice;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on
Conference_Location :
Beijing
Print_ISBN :
1-4244-0258-1
Electronic_ISBN :
1-4244-0259-X
Type :
conf
DOI :
10.1109/IROS.2006.282515
Filename :
4058921
Link To Document :
بازگشت