fairfolio
Saved Projects

Utilizing the Heuristic A* Search Algorithm to Determine the Shortest Path Between Locations on a Floorplan

ISEF · 2021 Systems Software

Dawadi, Avaye, Senthilkumar, Sooriya, Jovanovic, Alexander · Chamblee Charter High School

Is this your project?

Overview

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.

Working on something like this? See what's been done and what's still open.

Competition history

Resources

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

Report a problem

Source: Regeneron International Science and Engineering Fair

Save projects to your library

Sign in with Google to keep track of projects you find interesting, organized into folders. An account also raises your daily allowance for “Has this been done?”, and lets you create a key for the MCP server with a much higher limit than anonymous use. Browsing stays public.

Continue with Google