Category: Jason

The beginning of this week was heavily focused on the final presentation. Aidan, Neha and I met up to verify a lot of the metrics, finalize the content that we wanted to include within the presentation, and update the diagrams to more accurately represent the current state of the project. In additional to the overall content of the presentation, I had to focus on the actual presentation, and making sure that I knew what I wanted to say on each slide; this was relatively simple seeing as I am very familiar with nearly all parts of the project, but I could have used to work on overall pacing more.

Following the final presentation, I continued to work on the scale model that we will be using for the demonstration. I had a mockup during the last status report, but I decided to add to it and include more detail, such as how we will actually be framing it. I also put more thought into the floorplan; I tried to focus on thinking about which nodes will be good ones to show as detecting fire, and how that will impact the general path routing. I also wanted to ensure that we took advantage of the 2-story nature of the design by adding rooms on the first floor as well. This was a challenge, because the first-floor was hard to see, so after some deliberation, I decided that the best course of action would be to use wood framing for the majority of the model, but then use acrylic on two of the four exterior walls so that it would be easy to see into the model. Here is the final version of the model we will be building.

At the time of writing this, most of the parts have been cut and laid out, and assembly will happen in the next day or two.

One of the other things I have been focusing on is completing the distributed pathfinding. I have been running into some trouble with making sure that each node has the full list of paths necessary to reach the exit. Currently, I am storing the NodeIDs as a linked-list as it is being generated. This then has to be reallocated into an array once a fixed size is known, and broadcasted to all neighbors, so that they can also have access to the exit path. The issue is there is a fixed packet size that is allowed to be sent using ESP-NOW, and when testing with large graphs, this is exceeded. I tried to write a fix that would send multiple packets if the packet size was exceeded, but that had bugs.

I plan on finalizing the the pathfinding tomorrow and doing my best to ensure it has the same results as the existing pathfinding which I have tested thoroughly. To do this, I will include both header files and run both versions of pathfinding and check if they ever differ. I will also be using this to test the differency in latency between the two implementations, as that was one of the key worries we had when switching over to distributed path finding.

I am slightly behind schedule at this point, as I was supposed to have distributed pathfinding done at this point, and only be working on the final documentation, poster, etc. Seeing as this is the last week, though, I will likely just extend the duration of the task, rather than updating the Gantt chart, as there isn’t any more time to shift the remaining tasks backward.

This upcoming week, I want to finalize the model and complete and verify the new pathfinding code – including metrics. I will also be working on the final hardware integration with PCB’s with Aidan and Neha, and then focusing on the remaining logistics files that I mentioned earlier.

This week I started on distributed pathfinding, only paying attention to packets received by immediate neighbors of each node. This ended up essentially being an entire rewrite of the pathfinding code that I currently have, and therefore it has taken longer than expected to get it finalized. Rather than actually calling code to run Dijkstra’s algorithm or A*, each node is instead waiting for a response from any of its neighbors, to see if one has a path to an exit, and if so, what the distance is to it. When it receives such a response, it will note down the weight to this exit and broadcast that information to any of its neighbors. If the node receives a new shortest path, or information that the current shortest path is not invalid, it will update the path it is taking, and forward that information onward.

I also modeled a very basic idea of what I think our demo room should look like:

(this is a section view of the model)

I thought this was a decent model because it was two stories, has multiple rooms on one floor, multiple exits – there is one on the back of the model as well – and has room for 5+ nodes; it seems like this model would allow us to demonstrate a lot of the functionality of our project during the demo. This should be simple enough to make, as I have access to a significant amount of leftover material – including fasteners and tools – now that booth has been completed and torn down.

I also worked on finally getting the display integrated with the current pathfinding implementation that I have. Aidan and I have been talking about this integration for quite a while at this point, but I finally sat down and got it working. This was a relatively small integration, as all the code was already written, I just needed to import his helper function files into my code and call them; while it was a relatively small amount of effort to integrate these portions, it does represent a big step, as it officially confirms that we are able to link the pathfinding code and the display code. 

The final thing that I worked on this week was the final presentation. I am going to be the one presenting this time, so I have been spending time going through the presentation requirements making sure that we address all that we need to. I have also been touching up the diagrams that we have, and reviewing the feedback that we have received from the other presentations. Finally, I have begun rehearsal so that I am calm and confident when presenting. I am also trying to ensure that I don’t rely too heavily on talking about where we would like to be in a week, but focusing on where the project is currently and the progress that we have made. 

I am slightly behind pace according to the Gantt chart tasks I have for myself, as I was scheduled to have distributed pathfinding completed by this point. While the current pathfinding implementation is perfectly suitable for a demo and final presentation, we wanted to implement the distributed pathfinding approach, as it is much more scalable for a real-world system; it significantly reduces the computation done on each node, and greatly reduces the range as each node only needs information from its neighbors, and not every other node in the network. The primary reason we wanted to test it is because of the concerns with added latency. While I don’t believe I will have this implemented by the Final presentation on Monday, I do believe that I will have the time to get this completed by the final demo occurring during finals week.

Next week, I want to finalize the distributed pathfinding and test it against the normal pathfinding. I also am going to work with Aidan and Neha integrating the hardware components, and soldering all the parts to the PCBs that are currently being manufactured. I will also be working on getting the video submission, and poster finalized, and building the test building that we will be using for our final demo.

This week, I focused on prepping for the demo. I mentioned in last week’s status report that I had worked on refactoring the code for pathfinding so that it could be interfaced with in the .ino file that holds the entry point to the software stack. When integrating the newly refactored pathfinding code, I realized that the Arduino code needed a refactor just as badly. I ended up completely restructuring the file into individual helper functions that either perform some setup functionality for the pathfinding or hardware or perform a task, such as reading the sensors or performing the pathfinding operation using the retrieved data.

The refactor helped significantly with keeping the code organized and manageable while I was integrating the pathfinding tasks. One of my oversights when writing the pathfinding code is that it would need to be run in intervals, continuously. It also shouldn’t run the costly setup code where the graph is initialized and all necessary memory is allocated. When I had originally been testing the pathfinding code, it was only setup and run once, so when trying to include this in the Arduino file, there were errors due to freeing memory which should have persisted for the life of the program. Additionally, some of the code was making destructive modifications to the graph data structure, and because of this, after a certain number of runs of the pathfinding code, the output path would no longer be correct because the original weights of the edges had deviated too far from their default values. As a result of this, much of the logic had to be changed to use additional data structures, and passing copies of data, rather than references to the original data structure which needs to maintain its initial state.

After the debugging had been finalized, all I needed to do was change the packet contents slightly and include a few additional checks before I was able to output the shortest path from each source node to an exit, updating in real-time based on responses received from other nodes, and their reported temperatures.

This upcoming week, I want to finalize integration with Aidan’s display code. Seeing as we both had functioning demos of our respective parts during the interim demo, with me outputting a path as a list, and him receiving a list as input and using that to display a path, this should be a relatively simple integration between our pieces of code but does require us to schedule a time to meet and test it. I also want to work on adding low power mode, as this will likely be required to reach our target of 24 hours in passive mode, and 5 minutes in active mode without hardwired power. Finally, I would like to begin switching to distributed pathfinding, where each node receives only computes pathfinding based on information received from its neighbors. 

As for verification, I would like to do a significant amount of edge case testing where we ensure that the path always avoids errors and unsafe nodes. I would like to generate some test graphs using Python if possible and run the pathfinding automatically, logging if a bad path is ever found. Additionally, I would like to test the range of the ESP-NOW networking and check to see what happens if there is enough signal degradation that the node ID or sensor data is reported incorrectly. This will mostly involve running the same code as the demo but increasing the distance between each node to see if we correctly handle it. 

As for progress, I am on track with my Gantt chart and believe I am in quite a good position for the capstone: we received positive feedback after the interim demo. I have added a few tasks that had been left off, such as low power mode, and distributed path-finding code. I had forgotten to add these tasks, as I was focusing on reaching a minimum working demo, and these are complex additional features that didn’t show a base functionality but still need to get done.

This week I focused on two main tasks: a quality-of-life script for interfacing with the ESPs and working towards integration with Aidan’s display software. 

One of the annoyances that I faced when getting my networking demo using temp sensors finalized is that I would have to open an ArduinoIDE for all connected boards if I wanted to download to all of them at the same time and view their serial output. Even when I did that, often times if I changed the code and tried to recompile, it would crash with some obscure error message and I would have to close all instances of the ArduinoIDE, reopen them, compile, and upload again. I also didn’t like that I had to recompile the code each and every time I wanted to upload; there should be no need if I am uploading the same code to all boards.

To solve this issue, I decided to switch to using arduino-cli and take advantage of the scripting capabilities it has. I wrote a python script that allows you to pass flags that can compile the project, upload the project to all available boards or only ones that you specified, show the board’s serial monitors in a tmux window, and more. Here is a video of the general functionality:

This has made development with our small fleet of nodes much easier, and I think it was worth the time it took to get it set up and working correctly.

I also worked on refactoring all of my pathfinding code so that it could be called as helper functions from the main .ino file. When I was initially writing this code, I was writing it as if it were in isolation, being called from its own main() function. That was not representative of how it will actually be used in the project, and therefore there was a significant amount of refactoring required to get the code in a usable state. This was also done in preparation for integration with Aidan’s display code. Aidan and I have been working together to finalize the interface between our two pieces of code so that they can be joined together in the main project file that will be the entry point for our code. We defined a contract of what the pathfinding code will provide to the display code so that all necessary information is provided and an appropriate path can be drawn between nodes on the graph.

Based on the Gantt chart, I am on schedule. I am up to date on all the tasks I wanted to complete by the interim demo and am now at a point where I am refactoring my code and working on integration and interfacing with the rest of the team’s work. I am actually slightly ahead of schedule, as I was able to schedule in time for a significant quality-of-life improvement that will allow for much faster and pain-free development, which will be important when we move out of the proof of concept phase for all the independent pieces, and begin deployment onto every board for testing the entire system together.

This upcoming week, I want to finalize the initial stages of interaction between the pathfinding code and the LCD display code. This would be a big step, as the project hinges on being able to provide direction to user. I also want to focus on finalizing all the refactoring and define any other contracts that should be upheld between two interacting pieces of code, so that we can work on the integration of other parts of the system.

This week I focused heavily on the networking of our project and made really significant progress. During the last update, I had networking completed between two nodes using WiFi, with hardcoded MAC addresses, SSID and network password. I was really unhappy with this approach: it required that I determine the MAC addresses of all ESPs and manually added them into the code, which wouldn’t be feasible at scale. Additionally, it requires the SSID and password for the WiFi network to be stored on the board, and therefore each time the credentials change, the boards would need to be re-flashed. This would be a pain for sys-admins who are constantly changing the network configuration. Finally, specifically for when we are testing on CMU campus, each device would need to be registered to gain access to the CMU-DEVICE network. All of these annoyances led to me to spend several hours trying to figure out a better approach.

The first issue I wanted to address was the hardcoded MAC addresses. I researched sending signals to all devices on a network. I didn’t see any easy way of doing that, because it is not immediately clear to a device, what other devices are also on a network. I then decided to see how IoT devices do it, as they are often configured to interact in a mesh network. I realized that they tend to “broadcast” their signal, which is sending it to all available MAC addresses. In researching this, I came across something called ESP-NOW, which supports Pseudo-Broadcasting. During some further research into ESP-NOW, I realized that it is actually the perfect solution to networking for our capstone.

ESP-NOW is a connectionless WiFi communication protocol developed by Espressif specifically for their ESP32 and ESP8266 boards. It works by using the built-in WiFi module on the board to act as both a sending and receiving node. You can specify individual MAC addresses to send to, or you could send to FF:FF:FF:FF:FF:FF, which corresponds to the Pseudo-Broadcast mode and all ESPs that are listening within range will receive the message. Using ESP-NOW, there is no reliance on one centralized WiFi network, and we are able to broadcast to all nearby ESPs without needing to manually specify the MAC addresses; my main annoyances from last weeks approach have been completely solved. Another point of note is that ESP-NOW has a range that is nearly double what ZigBee supports: 220 meters vs 100 meters. 

I didn’t find it sooner because it is not a general standard for wireless communication – it was developed by Espressif, specifically for their ESP32 and ESP8266 boards – and therefore isn’t as widely used as Bluetooth, WiFi, or ZigBee, but it happens to work perfectly for the boards that we ended up using for our capstone.

After finding this form of communication, I made a sketch to demonstrate multiple ESP32s talking to each other bi-directionally. This was relatively simple to set up with test data, as there is good documentation on the ESP-IDF website. It got difficult, however, when trying to send structs of data and keeping the data intact. There was a significant amount of casting and address re-interpretation required to actually get the data transferred, however, I was able to get it working.

I then decided to add authentication to the packets being sent – specifically HMAC’ing using the C library LibSodium – over the network to mitigate the worst-case scenario that we discussed during our ethics meetings. We were worried about people potentially acting as one of our nodes and responding that a node was safe to travel through, even though it wasn’t. Now, this would be impossible to do as all data is verified using the HMAC prior to taking it into consideration; so long as the attacker doesn’t have the symmetric key that is being used on the nodes, we can guarantee that the message originated from one of our own nodes.

As you can see from the video above, the ESP32 on the left is outputting that every message it receives is failing the HMAC verification. That is because that specific ESP32 has a different key, and therefore its version of the HMAC of the data differs from the HMAC it received. 

To join everything into one concise demo, I have 2 LEDs per node wired up to respond to the temperature sensors on 2 of the 4 ESP32s respectively. When the temperature sensor of Board 2 (as specified by the labels on the board) exceeds the threshold, you can see all of the yellow LEDs activate; there is no physical wires between them, this information is being communicated over the ESP-NOW network. Similarly, when the temperature sensor of Board 3 exceeds the threshold, the green LEDs activate.

I am on schedule with my Gantt chart at the moment. I am really pleased with the the switch to ESP-NOW wireless communication. It provides all the benefits of ZigBee – mesh system where all nodes can talk directly to each other; no central point that could go down and disable the entire network – with none of the downsides – additional cost of XBee modules; external libraries to interface with these modules; additional wiring to connect the modules to the ESP32s. 

Next week, I am going to focus on integration between my own parts, primarily pathfinding and networking, as well as integration between the parts from my teammates. I need to ensure that I am able to interface with the C++ code I wrote for pathfinding, and incorporate the network data that I am receiving from ESP-NOW. The other primary focus will be outputting the pathfinding information into data that Aidan and Neha can use on the display to accurately draw a path out of a floorplan.

At the beginning of the week, I was working on the ethics assignment, reading the two papers that were assigned. After I had finished that, I began focusing on implementing network communication between two nodes on the same network. All development testing that we had done on the ESP32s thus far has been on either Aidan’s or Neha’s computers, so I had to work on setting up the Arduino IDE to interface with these boards. One unique thing that I had to deal with though, was that my drivers were installed incorrectly. It took a while to sort out but I had to go to SiliconLabs website and install their CP210X USB to UART drivers before my computer would recognize the ESP32s. After doing that, I was able to download to the boards as expected. 

After running a HelloWorld-type programming to ensure everything was working as expected, I began working on setting up each node’s network connections. Something that I overlooked, which caused me a bit of trouble at the beginning was that I was trying to connect to my main WiFi network; this was an issue because while there are some ESP32 models that can use the 5GHz frequency of WiFi, the C3 – which is the model that we have – can only use the 2.4GHz frequency. Once I realized that I quickly set up a 2.4GHz channel on my router, specifically for IoT-type devices, where the nodes could be isolated from the rest of my network and talk to each other.

Once I got the nodes connected to the network, I could verify their MAC addresses on my router’s interface, and use that information to establish a connection between the two nodes. From that point, I wrote some test code to verify that I could correctly send information between the two nodes, so long as I have each of their MAC addresses, and they are on the same network.

I was slightly behind last week and needed to focus on integrating communication over WiFi. I now have that implemented but at a very rudimentary level. Currently, to get two nodes to talk, their MAC addresses need to be hardcoded into the file and sent directly to this address over the shared network. This implementation has issues, for example, if that MAC address is no longer on the shared network. I technically accomplished what I sent out to as per my last Weekly Status Report, and am on track with my Gantt chart plans, but I would like to improve the usability of the current implementation of the network connections.

Next week, I want to make make the data transfer a bit smarter: rather than relying on hardcoding the individual MAC addresses, I would like to try and figure out how to recognize all of our ESPs that are on the network, add them to a list, and broadcast to all of them automatically. This would avoid the manual setup and would be important if this were to actually be a viable product. I also want to look into using ESP-IDF rather than Arduino IDE. It seems that there are some additional features available there, as it is actively developed directly by Espressif, whereas, when we are using Arduino IDE, we are limited by their update schedule to support some of these features.

This past week I focused on working on the A* version of pathfinding, touching up the code to include additional information that will eventually be necessary during implementation, and running some general benchmarks for A* vs normal Dijkstras.

Seeing as I had never used A* before, it took a bit of research to understand what went into making a heuristic function; in case anyone reading this is unfamiliar, A* is an informed version of Dijkstras, which allows the algorithm to guess what the best path is going to be by using a heuristic function written by the person implementing the function. This function will tweak the weights of the priority queue used in Dijkstra’s such the next path chosen should be favored if it is already expected to be along the current best path. Another way of phrasing it is that Dijkstras algorithm is a special case of A*, where the heuristic function is uniform across all data points. 

After having learned a bit about it and figuring out how I might write an algorithm for our specific use-case, I decided a good heuristic function would be to favor what would be the best path, assuming there were no obstructions. In the case that there are no obstructions in the graph, or there are obstructions, but they are not in the way of the best path from the current node, this should significantly speed up algorithm time.

The testing of A* vs Dijkstra’s doesn’t rely on any real-world parameters, so I was able to simulate it by running various tests where there are reported obstructions at some nodes. These are the results: 

Keep in mind that these results will vary depending on the graph that is being used for testing, what nodes are being reported as obstructed, and the weighting that is being used in the Heuristic function; that being said, I think this provides a useful insight that using A* might provide some benefit to our project, but the improvement is not guaranteed, especially if there are multiple reported obstructions. It is also important to note that A* should scale better as the graph grows because the cost of calculating the Heuristic function should become more insignificant as the time it takes to find an exit node grows. 

I am slightly behind schedule because I have not yet started wireless communication integration. We recently made the decision to use WiFi as the primary source of wireless communication for our nodes due to cost constraints; because WiFi is integrated directly into the ESP32’s that we purchased, I should be able to progress on that throughout this week. However, we still wanted to use ZigBee boards to display a proof of concept. I am unable to start on ZigBee network communication because the XBee boards that we ordered have not yet arrived. To answer the question of how I plan to get back on track, once we get back from spring break, I will have just completed my midterm exams for my other classes, and I expect to have extra time to dedicate to capstone. This additional free time should be the perfect time to catch up on some of the project tasks that I have fallen behind on. 

This upcoming week, I want to focus on getting the nodes to communicate with each other over a network. I want to focus on using WiFi first, but if the additional boards have come in over break, I want to attempt to get communication over ZigBee as well. This is going to be the main task that I want to address because it is absolutely necessary to have a working demo for the interim demo that is fast approaching on April 3rd. If there is additional time after focusing on network communication, I will begin working on sending data between the node and incorporating that into the pathfinding: the goal here is to have pathfinding update to reflect the updates sent from other nodes about what is a valid path. 

Due to the presentation that was due at the beginning of this week, a big portion of my time was spent meeting with my group and finalizing the slides and diagrams that we would be submitting. During these meetings, we came to the final consensus that we would be using ZigBee strictly for a proof of concept and relying on WiFi for the actual logic of our capstone. That decision primarily boiled down to the inability to get the ESP32 boards that we wanted – the C6s – and the fact that buying an XBee board for every node would put us over budget. We decided to use the ESP32-C3 boards instead, which, like all ESP32 boards, have built-in WiFi, and therefore allow us to conserve our budget with this new design decision to use WiFi.

I spent the rest of my time this week finalizing pathfinding in C++, ensuring that there were no memory leaks or segmentation faults. I also ensured that the output matched the python version that I had already written and tested thoroughly.

As you can see in the image above, both of the implementations match on the test graph I am using that represents Wean 5. 

Additionally, on a single execution, continuous execution, or after an error, there is no memory leakage. This is key because our nodes should be able to run in a continuous state for months, and if there was a memory leak, we would eventually crash due to being unable to allocate any additional memory; this is especially true on an ESP32, and there is relatively little onboard memory for us to be able to use. 

I spent a lot of time debugging the C++ implementation because I am not familiar with the language. I decided to use C++ over C because of some of the built-in data structures, such as Maps, Sets, and Priority Queues. That being said, there was a lot of syntax required to get them working that I was entirely unfamiliar with, which made it quite difficult to get compiling. I was also unfamiliar with a lot of the error messages, making debugging more difficult. In the end, much of my time was spent essentially learning a new language. 

During my time debugging the C++ implementation, I decided to look into other alternatives that we could write the code in, and I begin looking into the feasibility of using Rust on ESP32. I found that there has been a lot of progress in this space, with a fork of ESP-IDF called ESP-IDF-HAL, which allows you to run Rust on an ESP, with support for the Rust standard library. Given that I have already finished the implementation in C++, it is unlikely that I will rewrite the code again in Rust, especially since I am entirely unfamiliar with the language, but if we get further into the process and I see that there might be some sort of significant benefit to using it, I might make the switch.

I also have the code downloading and running on an Arduino, and logging the correct result out over serial. 

Next week I plan to try writing the code to the ESP, rather than using an Arduino for testing. Seeing as we received our ESP32-C3 order, I think the next steps should be migrating away from testing with Aruduinos and switching to using the boards we will use on our final design. I also want to try implementing A*, which should be a very minor change to the Dijkstra code; the only difference is adding a heuristic function, which aids in determining what node we visit next. 

As of this week, I believe that I am on schedule with the Gantt chart tasks that I have provided for myself. I do, however, plan to insert a new task in the Gantt chart for migrating from Arduino testing to ESP32 testing, as I’m sure that will require some time to get building and running.

This week I spent more time than I had intended researching ESP32’s, their different types, distributors, wireless capabilities, and considering alternatives to what might happen if we can’t get the boards we are interested in. When Aidan, Neha, and I were looking into what boards to order, I realized I didn’t know the difference between an ESP32 or ESP8266, or how an ESP32-S2 differed from an ESP32-C6 differed from an ESP32-H2. These links – a b – ended up being the most helpful in figuring out the differences between them. Ideally, the team would be able to get an ESP32-H2, because that was supposed to be the first board from ESPRESSIF (the maker of ESP32) that natively supported the ZigBee standard. The issue with the H2 is that it isn’t released to the public for general purchase yet. That being said, in my research, I realized that the ESP32-C6 surprised everyone by including ZigBee as well, and therefore was the board I let the team know I thought we should get. The issue with this board, however, has been finding a supplier with a stable inventory.

As of writing this, I just checked and saw that the ESP32-C6 Dev boards that we submitted a purchase order for has just sold out, and I will be working tomorrow on finding a replacement.

One of the other quirks that come with using some of the ESP32 boards is that they don’t all support the Arduino IDE; instead, some use the ESP-IDF development environment. There are a couple of ways to interface with it, and luckily its documentation seems to be quite thorough with a Github that provides tools for getting started developing projects. 

As for the pathfinding, I am slightly behind schedule for the C implementation of Dijkstras. I spent a lot of time researching the differences between the different hash maps that are available in C. I was primarily looking at search.h, uthash, and GLib’s GHashTable. I spent a lot of time trying to figure out how to get GLib installed because it had the most functionality, helper functions, best documentation, and generally seemed to be the most performant. That being said, after a couple of hours trying to configure meson, ninja, and my general environment, and still being unable to get it uninstalled, I decided to switch to using UTHash. UTHash exists in a single header file that is available on GitHub, is still relatively performant, and is very easy to use. I think the ease of development is worth the possible performance loss. Because of my struggles with getting a hash map set up – needed for creating the dictionary representation of the graph, which maps a node to its neighbors – I was put slightly behind schedule. 

I built in a couple of days into my schedule (2/20 – 2/24) for possible debugging time, so I intend to push back my Arduino pathfinding to light up LEDs back by a few days to give myself some additional time to finalize Dijkstra’s implementation in C.

I was also talking with Aidan about 2 slightly different approaches of pathfinding. Approach 1 was to give all nodes information about the entire graph, and have them complete pathfinding out entirely on their own, using temp data from other nodes. The other approach is to only give each node only information about its neighbor node, and find the optimal path based strictly on the information returned to the node by its neighbors. We think this approach might scale well but could face some latency issues. We decided the only reasonable way to test it would be to write both solutions and time which one runs faster in a real-world application, as we don’t have a good way to simulate the added latency of sending increasing amounts of data.

I also refactored my Dijkstra’s version of the code in python so I have a better reference to use when finalizing the C version. I added a bit of bash scripting for ease of testing the code as well: 

(these weights are slightly different than the actual ones I used in the code)

This upcoming week, I want to finalize my C implementation of Dijkstras, time it relative to my python implementation to check the performance difference and run valgrind on it, to make sure we don’t have memory leaks, seeing as these need to run for a long period of time without maintenance. When that is finished, I plan to set up the infrastructure to light up LED’s based on a hardcoded starting node, to indicate where to go next. Based on the way I have my code set up now, it would require very minimal changes to the structs that I am using. 

I think the classes that covered what I worked on this week fit into two categories: the first category is pathfinding, which is mostly just 15-210, which is a CS class, but it covered Dijkstras in depth. The second category is writing C code, which is 18-213, 18-344, and 18-335 where I learned how to organize C projects to make them manageable, use header files properly, Makefiles, etc. I think the final class that helped would be WebApps, because that class had such an open-ended project, I had to do a lot of research, which I had to do a lot this week when trying to decide what ESP32’s to buy. 

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.