Combining heuristic and landmark search for path planning

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Combining heuristic and landmark search for path planning

Full text

Pdf (379 KB)

Source

Future Play archive
Proceedings of the 2008 Conference on Future Play: Research, Play, Share table of contents

Toronto, Ontario, Canada

SESSION: Artificial intelligence table of contents

Pages 9-16

Year of Publication: 2008

ISBN:978-1-60558-218-4

Authors

Kevin Grant	University of Lethbridge, Lethbridge, AB, Canada
David Mould	Carleton University, Ottawa, ON, Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 66, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1496984.1496987 What is a DOI?

ABSTRACT

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Freeciv. www.freeciv.org.
	2	E. W. Dijkstra. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik, pages 269--271, 1959.
	3	Robert W. Floyd, Algorithm 97: Shortest path, Communications of the ACM, v.5 n.6, p.345, June 1962 [doi>10.1145/367766.368168]
	4	Andrew V. Goldberg , Chris Harrelson, Computing the shortest path: A search meets graph theory, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	5	K. Grant and D. Mould. LPI: Approximating Shortest Paths using Landmarks. In Eighteenth European Conference on Artificial Intelligence - Workshop on AI and Games, 2008.
	6	P. E. Hart, N. J. Nilsson, and B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths in Graphs. IEEE Trans. Syst. Sci. and Cybernetics, SSC-4(2):100--107, 1968.
	7	Donald B. Johnson, Efficient Algorithms for Shortest Paths in Sparse Networks, Journal of the ACM (JACM), v.24 n.1, p.1-13, Jan. 1977 [doi>10.1145/321992.321993]
	8	D. Mould and M. Horsch. An Hierarchical Terrain Representation for Approximately Shortest Paths. In Proceedings of Ninth Pacific Rim International Conference on Artificial Intelligence (PRICAI), pages 104--113, 2004.
	9	Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003