WAIfinder

Inspiration

One day, one member of our team (in India) got stranded in the middle of the road in a car in a flood. The flood came insanely quickly, and while we went to a place further from the river to ride the monsoon out, a road was submerged, and we had to evacuate the car. This program essentially targets this idea, where some roads or paths may be blocked, but people need to find the direct way to their shelter.

What it does

The core of our project is the A* algorithm, which is highly optimized for finding the optimal route between two points. We take the user’s location, find nearby shelters, and obtain the local road network. We then use A* to find the optimal route. Incorporated within our A* implementation is an AI (Random Forest Classifier) which dynamically predicts flood risk of each rode (edge) along the path using data like elevation, soil quality, and rainfall. This helps avoid road closures before they even happen. In our custom formula (cost = travel time + travel time*(risk*k)^2), we include a tunable value k which indicates how much our algorithm prioritizes safety over travel time, allowing it to be adaptable to a variety of situations and emergencies. We display the resulting path on a map view, which also indicates the flood risk of nearby areas through shading.

How we built it

First, we used OpenStreetMap to obtain a graph of local road networks, while another API was used to convert the address into a coordinate point (lat, lon). Then, we found a database that has the location of all FEMA-approved emergency shelters across the US. A* Algorithm was used (as said above) to find the lowest cost path by travel time. Concurrently, we found a Random Forest Classifier on Hugging Face that was used in Indonesia to determine the flood risk of different cities. The RFC contained multiple different input features. We found APIs that gave these input features, for example, the elevation of a certain location or the soil and drainage quality. Lastly, we got the current (and past) weather data to finalize all the input features. By refactoring it and fine-tuning it for our use case, we tuned it to 91.55% accuracy, which was then deployed and gave out 4 different levels of flood risks: Safe, Low, Medium, High. This was then implemented into our A* via our formula that increases the weight between two points (basically, increasing the distance proportional to the risk).

Challenges we ran into

Our Random Forest Classifier was quite slow, which is problematic as it needs to be called 50-100 times (each per generated route) in a typical program run. This was likely due to preprocessing/postprocessing stages; we couldn’t simply remove these, so we made a cache out of a hashmap and rounded long floats to a fixed number of decimal points, reducing the number of predictions the AI needed to make and speeding up our application tenfold.

Accomplishments that we're proud of

We had never implemented the A* algorithm, and it was nice to work with NetworkX to implement it, especially as A* is especially applicable in this scenario/in our project. A* is a highly-tuned algorithm used by applications like Google Maps in routing, so we gained experience that has powerful real-world applications. We also learned a new frontend library, FLET, made by Google. FLET is styled after Flutter, which one of our group members have experience in, but FLET is written in python while Flutter is in Dart, making Flet websites highly accessible and easy to draft up.

What we learned

As said above, we will continue to further continue to learn FLET, as well as work with maps. We found it interesting to work with geological data and pathfinding algorithms, and we will explore this further in the future.

What's next for WAIfinder

We want to include considerations as to the number of people routing, which we would be able to obtain through crowdsourcing. We would also introduce other nodes, such as food, water, and gas stops as required, which will obviously make the pathfinding more complex to handle but will be interesting and give this project even more applicability. To make the application more useable, another development would be to make a mobile version of this to make it more accessable

Built With

• a*
• api
• flet
• gui
• huggingface
• networkx
• python