Improved FastMap

Abstract

Pathfinding has been an interesting research area throughout the years. Heuristic search algorithms are used to find a path with the minimum length between a start and a goal in a graph, which has applications in GPS navigation and video games. There are different ways to create a heuristic for these search algorithms. Using embeddings is one of the ways to create a heuristic. In this method, an algorithm builds an embedding space for a given graph. Then, distances in the embedding space can be used to compute the heuristic between any two arbitrary vertices in the graph. Embeddings have other applications, like finding the midpoint between states, but here we focus on their use of heuristics. Cohen et al. (2017) introduced FastMap embedding, which provides a consistent heuristic. This thesis shows that the FastMap heuristic is not as strong as it was originally shown to be. While the median performance is strong, the average is not. We then analyze the FastMap approach. We show that FastMap is an additive heuristic. Also, we generalize the FastMap embedding by generalizing its embedding function and pivot selection methods. We introduce several new embedding functions and pivot selection methods. We show that the new pivot selection methods enable us to use multiple FastMap embeddings together, which was not effective before. Finally, we evaluate the newly created heuristics and show that using differential heuristics and the Heuristic Error pivot selection method improves the FastMap heuristic.