Date of Award

2014

Degree Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

First Advisor

Goodwin, Scott

Keywords

Communication and the arts, Applied sciences, A*, Heuristic, Pathfinding, Region, Search, Transit

Rights

CC BY-NC-ND 4.0

Abstract

Pathfinding is an area of research and of practical importance in Computer Science. The A* algorithm is well known as a pathfinding algorithm that finds optimal paths. As demands increase on pathfinding systems, we need faster algorithms to keep up. We propose an algorithm that uses preparation to partition the search space into regions that we may be able to skip while searching. We call this algorithm Transit Search, and by potentially skipping regions of the search space we can expand less nodes than A*. It accomplishes this by using a maximum allowed heuristic value to tell the search if it is possible the goal is within a region. If this isn't the case the algorithm can skip the region entirely, saving us from expanding unneeded nodes.

Share

COinS