Booth Id:
SOFT008
Category:
Year:
2016
Finalist Names:
Kumar, Haran
Abstract:
The least-cost graph traversal algorithm A* has diverse applications from video game pathfinding to accessibility programs for the visually impaired. While there is substantial research concerning its use in two spatial dimensions, this study investigation focuses on higher dimensionality. A* works by iterating through elements in a graph in an order based on the known distance from the start and the estimated distance to the goal, based on a heuristic function. This approach can efficiently find the path of least cost from the initial to final node, but its efficiency and accuracy depend on the distance heuristic itself. In this study, several were tested using randomized computer simulation and evaluated based on the scaling of performance over increasing dimensionality. The study provides recommendations for A* implementation in higher dimensions and analysis and research methodology for further research.