Abstract
A variety of techniques have been introduced over the last decade for abstracting search graphs and then using these abstractions for search. While some basic work has been done to predict the value of an abstraction mechanism, the results have not been validated in practice. In this paper we analyze a variety of old and new abstraction mechanisms in a pathfinding testbed and show that the work done in abstraction-based refinement-style search can be predicted by the diameter and size of abstract nodes.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4(2), 100–107 (1968)
Holte, R.C., Mkadmi, T., Zimmer, R.M., MacDonald, A.J.: Speeding up problem solving by abstraction: A graph oriented approach. Artificial Intelligence 85, 321–361 (1996)
Botea, A., Müller, M., Schaeffer, J.: Near optimal hierarchical path–finding. Journal of Game Development 1(1), 7–28 (2004)
Sturtevant, N.R., Buro, M.: Partial pathfinding using map abstraction and refinement. In: AAAI, pp. 1392–1397 (2005)
Fernandez, A., Gonzalez, J.: Multi-Hierarchical Representation of Large-Scale Space. Kluwer Academic Publishers, Dordrecht (2001)
Yang, Q., Tenenberg, J., Woods, S.: On the implementation and evaluation of ABT weak. Computational Intelligence Journal 12, 295–318 (1996)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sturtevant, N., Jansen, R. (2007). An Analysis of Map-Based Abstraction and Refinement. In: Miguel, I., Ruml, W. (eds) Abstraction, Reformulation, and Approximation. SARA 2007. Lecture Notes in Computer Science(), vol 4612. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-73580-9_27
Download citation
DOI: https://doi.org/10.1007/978-3-540-73580-9_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-73579-3
Online ISBN: 978-3-540-73580-9
eBook Packages: Computer ScienceComputer Science (R0)