At the beginning of the week, I was working with Neha and Aidan to complete our proposal slides. This involved a lot of time looking into US and Pennsylvania Fire Code, as we knew that our group’s Use-Case Requirements were going to be dictated primarily by these standards. Once we came up with all the requirements for the project, we were able to better plan out the individual steps that needed to be completed for our project, insert them into the Gantt chart, and evenly distribute the work.
As the week progressed, I started looking into the best path-finding algorithms for our use case, their runtimes, and the general pros and cons that each provides. I am currently leaning towards Dijkstras or A*, with the heuristic function of A* being the optimal path in an ideal case: A* is generally implied to be the informed version of Dijkstras, but I wanted to run some high-level tests in python and try different heuristic functions prior to coming to a final decision. In preparation for this testing, I transcribed Wean 5’s floorplan into a graph, with possible node locations on it, so that I could work with a realistic graph during my testing.
I implemented some basic graph creation code that outputs a dictionary graph representation; this representation of a graph tends to be the most useful in graph traversal applications. I also implemented Dijkstras, and by extension, A*, but am currently working on figuring out how I want to write the heuristic function. All code is pushed to our team’s Github.
Next week, I hope to have the final decision of what path-finding algorithm we are going to use, and switch to C code after the proof of concept in python. This will be a challenge because of the restricted functionality built into C; I will likely need to implement my own hash-maps if I don’t find any suitable libraries; I have been looking into existing dictionary/hash map libraries, such as search.h, uthash.h and strmap.h which are all looking like possible candidates, but I need to research them more to know for sure. That said, despite the added difficulty, a low-level language like C is necessary to stretch the limited computing power of Arduinos.
I am currently on pace with the schedule I have set in the Gantt chart; by the end of this upcoming week, I should have path-finding working on the Arduino in C.