Booth Id:
SOFT002T
Category:
Systems Software
Year:
2021
Finalist Names:
Dawadi, Avaye (School: Chamblee Charter High School)
Jovanovic, Alexander (School: Chamblee Charter High School)
Senthilkumar, Sooriya (School: Chamblee Charter High School)
Abstract:
Our research consists of utilizing the A* search algorithm and applying it to real world scenarios of finding shortest paths that mitigate virus transmission risk and help find efficient escape routes on floor plans. We designed a program that effectively takes an image input and determines the shortest path between two points on the image using the efficient A* Algorithm. Even within the algorithm, optimizations such as using a priority queue (minimum heap), Manhattan distances (as opposed to euclidean Manhattan distance), the Von Neumann Neighborhood, and sets over arrays were decided upon through analyzing data of run times and accuracy of the algorithm. For priority queues at 2008 nodes, we see a difference of 95.2418 seconds which is a large amount in our algorithm. This difference at 2008 nodes makes it almost 430% faster than the regular array. We believe that because we were only dealing with a max of 4 values per membership test, it did not matter that sets were more efficient than arrays because with 4 values the advantage that sets hold over arrays in membership tests becomes infinitesimal. Image modification is used to turn the image into simply a matrix of black pixels that the algorithm can parse with morphological transformations serving to reduce the image noise. Flask was used for the website itself. We also used machine learning in the form of a Convolutional Neural Network (CNN) in TensorFlow to analyze submitted images in order to notify the user whether the algorithm would be suitable for their situation. Our model achieved a validation and training accuracy both of 98%. Through image manipulation, analysis of runtime and accuracy data, a CNN, and a website, we created an efficient product for outputting shortest paths on floor plans.