We propose a hybridization of heuristic search and the LPI algorithm. Our approach uses heuristic search to find paths to landmarks, and employs a small amount of landmark information to correct itself when the heuristic search deviates from the shortest path. The use of the heuristic allows lower memory usage than LPI, while the use of the landmarks permits the algorithm to operate effectively even with a poor heuristic. When the heuristic accuracy is very high, the algorithm tends towards greedy search; when the heuristic accuracy is low, the algorithm tends towards LPI. Experiments show that the memory usage of LPI can be reduced by more than half while preserving the accuracy of the solutions. Copyright 2008 ACM.

Additional Metadata
Keywords Heuristics, LPI, Path planning, Precomputation
Persistent URL dx.doi.org/10.1145/1496984.1496987
Conference 2008 Conference on Future Play: Research, Play, Share, Future Play 2008
Citation
Grant, K. (Kevin), & Mould, D. (2008). Combining heuristic and landmark search for path planning. Presented at the 2008 Conference on Future Play: Research, Play, Share, Future Play 2008. doi:10.1145/1496984.1496987