Evaluation of Shortest Path Algorithms for Solving Mazes.

Brian Crutchley, Jason Rafe Miller

Abstract


Finding the optimal path through a maze is related to the shortest path problem in computer science. The first shortest path algorithm was introduced by Edsger W. Dijkstra in 1956 but multiple other solutions and optimizations have been suggested since then. We tested several algorithms for their applicability to the problem of solving mazes. We programmatically generated random 2D square mazes with independent variables for size and bias, where bias measures the deviation from random probability that a left or right turn contributes to a shorter path. We programmatically transformed each maze into a directed graph with arbitrary start and end positions and then solved for the shortest path through each graph. We speculated that maze bias, which tends to alter the graph density, would affect algorithm efficiency. We detected bias-dependent differences in resource usage between standard implementations of three shortest-path algorithms: Dijkstra’s, Bellman-Ford, and A*. Our results could help guide algorithm selection for robotic exploration of specific terrains given prior knowledge of their path properties. This project was supported by the NASA WV Space Grant Consortium.


Keywords


graph algorithms; shortest path;

Full Text:

PDF


Copyright (c) 2018 Proceedings of the West Virginia Academy of Science

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.