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
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;
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
DOI :
10.1109/IROS.2006.282515