Posted on

Team Status Report for 04/06/2024

Significant Risks

This week we spent a significant amount of time testing the localization system for our interim demo. We were ultimately able to demonstrate the accuracy of the system, though the update frequency of the system running on the Raspberry Pi is insufficient. Going forward, one of our main goals is to continue testing the Raspberry Pi to make sure that the updates are more frequent. We have already made several attempts to refactor the code to use alternatives to our gradient descent with PyTorch, and have seen some improvements in performance. However, we have noticed this may have come with the tradeoff of accuracy, and we need to continue doing further optimizations. We would also like to try offloading some of the computation onto the webserver and see if it is powerful enough to do some of the computation required.

Changes to System Design

Originally we assumed an accelerometer/gyroscope would be sufficient for getting the user’s orientation, though Ifeanyi’s testing showed that it would be more accurate to also use a magnetometer as well. We are hoping that this chip may provide more useful readings than our previous chip, assisting with IMU orientation and any location prediction using that chip. Hence, acquired a new imu that had magnetometer features as well. The rest of the system design is unchanged.

Schedule

This week we worked on setting up the interim demo and additional improvements to the localization system, as well as starting on the navigation system. Next week Weelie will be working on improving the navigation system, doing more testing on the RPi and improving the latency of the update frequencies. Ifeanyi will be working on the RPi, programming the IMU and getting rotation data. Jeff will be continuing to work on the navigation system so that it can be used to provide the user with navigation directions.

Progress

Here is a video of the initial portion of our navigation system. The video shows a demo of the system working, such that the webserver is running on my local machine and I have a script sending in “dummy data” for the user’s position. Entering a new room using the search bar sends the asynchronous request to the server, which responds with the path the user should take, and is drawn on the user’s map.

Video Link

Validation

There are a number of validation tests we need to do to ensure the system satisfies the use case requirements of our clients and properly functions.

Firstly, we need to ensure that the localization system is accurate and provides timely updates. We would like the accuracy of the localization system to be on average within one meter inside of a building. We need to measure this by going to a position in a hallway and comparing the result of the localization system to the user’s actual position, before taking the difference of the distances. This accuracy is sufficient for preventing the user from becoming lost in the building, as well as decreasing the amount of fluctuations in the user’s position.

Additionally, we want the position updates to happen smoothly at a high frequency of greater than 2 Hz, as well as not have too much delay between physical movements and updates on the server. These tests will require more coordination between all team members, because these tests are dependent on how long it takes for both the localization system and user front end to run its algorithms. As long we are able to establish accurate timestamps for communication start/end times, we should be able to obtain these measurements. Also, we need to make sure that the lagging time is less than 1 second. We will verify this by taking 2 points, one is the start and the other is the end. Then, we should walk from the starting point towards the end point. We should make sure that after we reach the end point, our position on the map will update accordingly within 1 second. We should repeat this test with different walking speed to cover different situations.

Furthermore, we need to test our navigation algorithms. We can do this by benchmarking it on some example graphs with known shortest paths, to see if our solution recommends these same paths. It really is as simple as making sure the function always returns the optimal path as it is supposed to. Additionally, if we make the nodes of our graph consist only of space on our map that is walkable (that is, no walls or other fixtures), then we are assured that our returned paths will always follow journeys the are indeed walkable by the user.

Lastly, we need to validate our directions and our user experience. To do this, we need to test our app several times with different starting locations and destinations to ensure that the directions we are given in real time always line up with the path recommended by A*. Then, for the user experience, we will survey a few participants to see if the app works according to its use case statement. That is, given only the purpose of the product, can a new user pick up the device and navigate successfully to their location? We will also survey them about the quality of the directions and the user experience for possible improvements to the interface.

Posted on

Jeff’s Status Report for 04/06/2024

What did I do this week?

This week was focused on working with my teammates to make progress to our interim demo, as well as development focused on setting up the navigation system.

The first thing for the webapp development was to add a new model for the rooms in a building, storing the room’s name, floor, and position on a map (relative to the actual pixel locations on the floor plan map). Then, I added an API endpoint so that users would be able to “search” for a room to go to. With the backend done, I needed to provide the rooms to the front end of the server so the users would be able to select and search for them. To create the connection between the user and the server, I created a form to post the data (offering more security due to having a csrf token). Form submissions by default reload the page, which would interrupt the user experience, so I created a handler that would prevent the page from reloading, validate the form, before sending the form as an AJAX request to the server. The server would be doing further validation to make sure the data is safe before running its algorithms to process the data.

I made a graph of HH A-level, then focused on utilizing the A star algorithm I had written previously. To use it, I needed to write a breadth-first search algorithm to identify the closest portion of the graph to the user (due to the graph featuring only a narrow walkable section in the middle of the hallways). I just needed to call this code in my background endpoint to determine the navigation paths the user should take. The final task at hand was to visualize the paths on the frontend. This was mostly trivial due to previously experimenting with drawing lines on a canvas element.

The overall results seem to be fairly positive. The below video shows a demo of the system working, such that the webserver is running on my local machine and I have a script sending in “dummy data” for the user’s position. Entering a new room using the search bar sends the asynchronous request to the server, which responds with the path the user should take, and is drawn on the user’s map. My local machine takes approximately 150 ms to run the navigation algorithms, which is sufficient (to my surprise/dismay, the EC2 instance runs the algorithm faster than my local machine, despite being the cheapest option AWS offers).

Video Link

 

Is my progress on schedule?

This week I made significant progress on the navigation system; crucially, I added the necessary core functionality for providing directions to users. Hence, my schedule is on track and aligns with what my team planned to do.

Next week’s deliverables:

Next week I would like to augment the application’s user interface to include human-readable user directions to tell the user when they should turn or how far they need to walk. The navigation system, in return, needs to be able to constantly track the user’s progress. It may be worth looking into ways to optimize the graph. For example, I could try scaling the graph down and seeing if there are any significant performance improvements. It is possible my team wants to try offloading some of the localization computation to the server; in this case, I would need to provide more assistance with the server.

Verification and Validation Tests:

My role on the team is primarily working on the user interface and the web application. This subsystem affects several of the tests we must run for verification and validation; particularly, navigation optimality, latency of localization updates, and quality of directions and user experience.

Navigation optimality refers to our navigational algorithm’s capability of generating the most efficient route for our users. Assuming the average walking speed is the same for all hallways, this ends up being the shortest paths between two points. I have already written the A* pathfinding algorithm for navigation and have spent time benchmarking its performance on graphs of buildings as well as verifying the paths it provides are indeed the shortest. In particular, the algorithm runs fairly quickly. It is able to find navigation paths within 100 ms on our webserver. In terms of verifying the algorithm is actually finding a shortest path, a significant amount of testing has been put in. Firstly, it is always able to find the shortest and simplest obvious path between two points. Then, it is capable of finding an optimal path when given multiple paths between targets. Next, it is more than capable of navigating around obstacles in the graph. Then, I have tested the algorithm in larger and more complicated graphs, comparing the result with Dijkstra’s algorithm (which runs slower than A* but is guaranteed to find the shortest path) to make sure both are equivalent, as well as making sure that the resulting path it finds is always less than or equal to a simple breadth first search algorithm.

Another facet of the webserver is low latency between the tag’s communication and the user’s front end. Through testing, this has been shown to take an average of 70 milliseconds to complete updating through our websocket. We want to have a latency between positional changes in real life to be reflected on the application’s user interface within 2000 ms. Hence, this information shows that there is plenty of “delay” that is still allowable from the perspective of the localization system.

Additionally, it typically only takes around 30 milliseconds for the tag to send the data. We initially stated we wished to have a total latency of the localization system and the server updates to take less than 500 ms, so this value gives my partners, who are working on the localization system, approximately 470 ms to work with. Further testing is needed with the RPi to determine the latency of the entire algorithm. With this information, we would be able to determine the maximum update frequency of the device, which we wish to be greater than 2 Hz.

The final tests revolve around the navigation system. Firstly, it should provide “distance” updates in a timely manner–at least once every two seconds to provide accurate estimates of how far the user should move. Then, we will need to run trials with our clients to garner feedback from them and a quantitative rating out of 5. If the feedback is positive, this would be an indicator that the navigation system is actually providing useful feedback to the users.