Improved FastMap

• Author / Creator

  Mashayekhi, Reza

• 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.

• Subjects / Keywords

  • Heuristic
  • Heuristic search
  • A*
  • FastMap
  • Embedding
  • Pathfinding
  • Algorithms
  • Algorithm
  • Embeddings

• Graduation date

  Spring 2023

• Type of Item

  Thesis

• Degree

  Master of Science

• DOI

  https://doi.org/10.7939/r3-fckh-jz12

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.