Author: jledon

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.