Category: Jeff’s Status Reports

What did I do this week?

I spent this week focused on developing the navigation system and testing its basic functionality, as well as working with my team to test the localization system over larger areas.

For the navigation system, I built on top of my progress in the previous week to work on displaying instructions and expected time of arrival for the users to view. I created a mock user interface with the header displaying the direction, as well as a footer displaying the time remaining and the total distance left to travel. I added a button in the footer to go between the different modes (navigation vs. searching for a location) and then worked on developing the CSS to improve the graphical interface.

Then, I worked on the development of the front end to improve the efficiency of the navigation system by offloading as much work as possible to the frontend, so that it would not spam the server with new navigation requests. This involved synchronizing the “path” drawn by the navigation system with either the x or y position of the user. Suppose the user were to walk in a direction parallel to the current path direction. In that case, the path will either “grow” or “shrink” to compensate to continue showing the visual indicator of where the user should go. Then, if the user chooses to deviate too far from the path, the frontend would call the navigation algorithm in the backend for updated directions to reroute the user.

Finally, all that was left was to update the backend to provide directions to the user (if they should turn left, right, or arrive at their direction). This was done by parsing the line segments generated by my A star algorithm to determine which direction they should turn in with regards to the cartesian plane. I also needed to add to the database model fields describing the scale of the image, which was calculated with regards the actual mapping I have previously done along with the size of the walkable area on the image. 

I was able to test the navigation system by using a script to provide user location to the webserver. This allowed me to verify that I was able to have  the client successfully align the user’s position with the path, as well as correctly provide directions to the user. We were also able to briefly test the system in the Hamershlag A level.

The attached video shows the navigation system functioning while using our Raspberry Pi.

Video Link

I met with my team several times to do further testing of our localization system in Roberts Hall and Hamershlag A. I provided assistance by measuring the dimensions of areas in ReH 3 that the user would be traversing throughout before updating my server with the hallway so that my team would be able to use it or testing.

 

Is my progress on schedule?

In the past two weeks, I was able to finish the rest of the navigation system (barring any bugs or user interface improvements to be found in further testing). This indicates that I am on track with everything promised on the Gantt chart schedules.

 

Next week’s deliverables:

This next week I will be testing the localization system with my team to ensure we are able to create an accurate testing environment representative of something similar to Wiegand Gym. Then, I would like to test the navigation system.

 

This weeks’s prompt:

I have taken 17-437 before (web application development) so I have a working knowledge of Django. However, prior to this project, I have never worked with WebSockets before. To accomplish low latency between the tag and the user’s browser, WebSockets were necessary (decreasing latency from >200 ms to around 67 ms). I had to learn about how to integrate Django Websockets with my project, as well as creating the Redis server to serve the requests. Most of the knowledge acquisition relied on reading the documentation for Django Websockets. Their documentation had several useful examples to help get me started on creating a channel layer for the application. Then, I needed to learn how to configure a Redis server on the EC2 instance to host the Channels layer. The Django Websockets documentation again proved to be useful as a guidance to decide what was necessary. Then, I found some forum posts on StackOverflow as necessary to provide a better idea of what the various configuration settings I was playing with could do.

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.

What did I do this week?

This week I worked on testing the A* algorithm, further developing and improving the web application, and worked with my team to test the localization system.

For testing the A* algorithm, I wrote a few scripts to help me construct a simple graph utilizing the png image of a floorplan. From here, I was able to do some performance testing to ensure the algorithm would be able to function on these larger (though simple) graphs. The algorithm was able to execute in around ~10 ms on my machine, which seemed to be a fairly positive result.

I worked on improving the web application. The first thing I worked on was to convert the server from using asynchronous HTML requests to instead using websockets. The main motivation for this was to improve the server’s performance to decrease the number of requests (offsetting more of the load onto a regis server) and decrease the latency between updating the user’s position on the browser. To implement the conversion, I worked on utilizing Django Channels and implemented the code necessary to facilitate communication between the tag and the user. The improvements over using HTML requests were fairly significant. Firstly, websockets seem to result in significantly faster update frequencies–from my testing, it seemed to be an order of 10 times faster. Additionally, the latency from sending the update to being updated on the user’s browser was improved dramatically, at around 5 times faster. With these changes, I also rewrote the script for the tag to send messages to the browser.

I worked on further development of the web application, moving a significant amount of hard-coded values onto the server’s database, as well as improving the user interface. For the floor view, I added a small form floating on top of the page for the user to input their desired destination. Then, I added a “connecting” indicator that shows up whenever the browser is no longer connected to the tag device.

Finally, I helped test the localization system with my team by mapping out the A-level corridor in HH and setting up a floor on the webapplication to view the user’s location.

Is my progress on schedule?

My main goal for this week was to assist my team in improving the accuracy and stability of the localization system. My improvements in the web application’s update frequency directly helped with the responsiveness of our tag’s localization, and I was able to implement the user interface necessary for displaying the user’s position, so I believe I was able to achieve this goal. Altogether, my progress is on track.

Next week’s deliverables:

The midpoint demo is approaching and I believe the localization system is sufficient in providing a stable calculation of the user’s position. My next deliverable is to start working on the localization system. My main goal is to have the webserver be able to take inputs from the user of where they would like to go, run that information through A* algorithm, and generate the paths to display on the browser.

 

What did I do this week?

This week I worked on the web application, assisted testing the localization system from inside of a room, and worked on developing an A* pathfinding algorithm for the navigation system.

For the webapp development, I deployed a debug version of the Django application onto an AWS EC2 instance to provide the graphical user interface platform for the rest of my team to test the navigation system on the tag device. I tested the user interfaces to make sure they would actually be able to display properly on a real mobile device. Additionally, I was skeptical of the possible performance offered by the webserver due to the high volume of AJAX requests sent by both the browser and the tag, so I decided to benchmark the average delay from creating data (with an estimated latency of 100 milliseconds) to the latency of displaying the update on the browser. My results seemed positive: it took less than 0.55 seconds on average for the entire update latency, which is much less than the 2.0 seconds we noted in our Design Report.

I spent some time working with the team to test the DWM1001’s, finding that a tag was able to connect to at least 5 anchors, as well as some preliminary testing of localization with the webapp displaying the user’s position.

Finally, I focused on implementing the A* pathfinding algorithm for the route planning with our indoor navigation system. I briefly discussed with Ifeanyi how to construct a graph necessary for representing a floorplan of a building so that he can create a graph this weekend to test the algorithm. I created a basic heuristic function to estimate distances between given coordinates, utilizing just the straight-line distance, though this has room for improvement in the future to consider obstacles or walls.  Then I implemented the rest of the algorithm, which involved iteratively exploring neighboring nodes and using a priority queue to use coordinates with the lowest cost. I was able to do a brief amount of testing to verify its behavior, though further testing is necessary.

Is my progress on schedule?

My goal this week was to finish setting up the webapp as a way to demo showing the user’s location, and I believe I was able to accomplish this goal to a satisfactory degree. Additionally, I was also able to work on implementing an A* pathfinding algorithm, which was my secondary goal. Hence, my progress is on track.

Next week’s deliverables:

The midpoint demo is approaching, so my main goal for the next week is to continue assisting my team in improving the accuracy and stability of the localization system.

I would like to test using websockets as the connection between the device and the webserver. It is possible this can result in a “smoother” connection between the client and server. Although my testing reveals the average latency of update from the tag to the user’s browser appears sufficient, there were occasional “drops” in updating, where updates were delayed by a second or two. Using websockets could improve this, as well as improve the server’s capability for handling more users.

Finally, it would be good to test the A* algorithm with Ifeanyi’s graph.

What did I do this week?

This week I primarily worked on the web application, as well as provided some support for my teammates as they worked on the DWM1001 development boards.

For the WebApp, I focused on editing the page displaying the floorplans of the building. I changed the HTML of the page, putting the image in its container, adjusting the CSS so I could use Javascript to manually center the image in the middle of the screen over the user’s hypothetical location. Additionally, I learned how to draw lines over the image to represent the path the user should take, utilizing a canvas HTML element to draw lines, and positioning it over the image.

A short video demo can be found here.

The demo consists of mock data embedded in the Javascript. Obviously, this is not going to be useful for the final product, so I worked on creating a model to hold the position of tags on the server. Then, I added the API endpoints necessary to support updating the models (sent by the tag) and obtaining the data from the models (requests from the browser running the webapp. Overall, this was successful, and I was able to create a Python script emulating the tag, sending random positions to the server, and the positions being accurately represented in the Browser.

I briefly helped Weelie test the communication of tags with multiple anchors, which was successful due to his troubleshooting.

Is my progress on schedule?

This week I was able to make significant progress on the web application, meeting the goals I set for development of the Map view page.  However, I did not end up making progress on the A* pathfinding algorithm. This is because I opted to make more progress on next week’s task, communication between webapp and Raspberry Pi, because this task has significantly more immediate importance for our Midpoint demo milestone that is upcoming. Altogether, I believe that my progress for this week is on track.

Next week’s deliverables:

I would like to continue working on the server to ensure that communication between webapp and RPi is set up correctly. I will also need to work on running the server on AWS instead of my local machine to test the full functionality of communication.

I would like to work on a version of A* algorithm implemented, though this is still second in priority to the former task, as we are not in the stages of mapping a building floor yet.

What did I do this week?

This week I focused my attention on working on the design review report, making sure to address several topics we had put less thought into developing, as well as responding to the feedback that was provided to us from the presentation.

Specifically, I wrote the introduction to the project, trying to better describe the motives around “why the problem is important to solve”, as suggested by feedback.

I worked on the Use Case requirements more, adding some of the ethical issues that are surrounding a location tracking device. Most use case requirements didn’t change, but I addressed feedback regarding the total system cost for installing the UWB anchors inside buildings (this cost is variable given how large a floor is, so I wrote it in terms of a “per hallway” cost).

I worked on the “ARCHITECTURE AND/OR PRINCIPLE OF OPERATION” section, which was mostly a rehash of the presentation.

For the Design Requirements section, I researched the time accuracy of the DWM1001 development boards when utilizing the TWR TOA protocol for distances. I made calculations regarding the required precision needed for our accuracy goal (which the devices meet).  From this, I also learned of the latency of communication for the devices (around 1.2 ms on successful communication). Regarding the feedback presented from the presentation, I also focused on why exactly 25 meters is a good range requirement for the ultrawideband transceivers. Again, the optimal minimum range is dependent on many factors, so I tried making clear that this requirement was likely sufficient for a typical hallway in a building.

For design trade studies, I researched other ultrawideband receivers we could use for our project. Most of these were more expensive than the DWM1001 Development board we are interested in using, so I made note of that in the report. I also improved the values in our “technology tradeoffs table”. As Professor Tamal mentioned in the presentation, we should have noted prices for installing systems. I made estimates of how much it would cost to map out a single hallway using Wi-Fi, BLE, or UWB.  I assumed it would take 3 devices to map out a single hallway (this estimate is different than mapping out an entire building, as we can overlap the devices for the hallways in a building. Looking back, I am not sure I was clear enough in elucidating this).

I also worked on the system implementation for the webapplication, developing a few mockups of some user interfaces.

Is my progress on schedule?

I was unable to make any meaningful progress on the Django webapp this week, though I was able to instead focus my efforts on planning what I want the design to look like going forward, as well as making contributions to significant portions of the design report. With this in mind, I will work on the “map view” page further next week and try to finish it after spring break.

Next week’s deliverables:

For the web application, I hope to work on the map view, implementing how I want the image frame to function, as well as working on drawing shapes on it to visualize the student’s location. Then I will get started on the shortest paths algorithm and work on visualizing it on the map.

What did I do this week?

This week I spent time rehearsing the Design Presentation before delivering it on Monday.

I spent time putting together several of the views of the web application, keeping in mind the need to make it as mobile-friendly as possible.

I set up a Google Maps API key so I could embed a map centered over the CMU campus, as well as working on customizing the map such that it would display fewer types of “default” pins. I followed the best case practice of utilizing a proxy on the webserver to load the map instead of including it on the client javascript to prevent unauthorized access to the API key. A header was also added, using Bootstrap to display a menu.

I worked on two models, a “Location” and a “Floor” to represent pins in the database. I added an API endpoint on the server to fetch the data for the locations, before adding client-side javascript to fetch the data using an AJAX call before creating the HTML necessary for the pins. Overall, the current map page (as viewed on a phone) looks something like this:

I also started working on another view to display the floor of the building. Current functionality allows the user to drag the image around, though I would like the image to sit in its own frame before adding javascript to move it around, and UI elements to allow the user to select a room to go to.

I worked on the Design Review Report, writing drafts of several sections such as the Use Case Requirements and Design Trade Studies.

Is my progress on schedule?

Yes, I was able to all of the Django web application tasks I wanted to accomplish this week, particularly with regards to setting up some of the main frontend pieces we need as, well as developing some models.

Next week’s deliverables:

Next week I will be working with my team to finish the Design Review Report. More research needs to be done for some of the contents, as well as a nontrivial amount of writeup.

For the web application, I hope to work on the display of the buildings. I need to work on the HTML to put the image in its own container with no overflow, along with some javascript to manipulate the position of the image.

This week I spent time researching how exactly UWB works, especially focusing on how most devices use it for calculating distances using TDOA and TOA. My findings concluded we would most likely be using TOA with Two Way Ranging to find distances.

https://link.springer.com/article/10.1007/s11277-017-4734-x

I also looked into how much it would cost to develop our own UWB tags using a DWM1000 board with an ATMega328p microcontroller.  Unfortunately or not, it appears it would be cheaper to use the preexisting DWM1001 development boards, as they are $25 apiece as opposed to at least $26.5.

I also briefly setup a Django webserver for the web application. Finally, I worked on several slides of the design presentation and created several figures for it.

My progress is overall on track for what I would have liked to accomplish this week.

Next week I will be presenting the Design presentation. Then, I will work on developing the backend of the Django webapp to include all of the models we would need for the project. I would also work on some front end templates to include a mobile-friendly version of a map.

This week I researched the various technologies that are typically used in indoor localization. I compared using Wi-Fi, Bluetooth, and UWB, finding that typically UWB has the highest accuracy, most resistance to interference, as well as having decent range, with the cons being that the devices are newer, hence the device prices are relatively higher. Next, I looked into which UWB devices would be a good fit with our project. The Qorvo DW1000 chip seems like the best UWB transceiver option, and there are a few developer boards that incorporate it, such as the ESP32 UWB.

A summary: Design Review_ What is the best indoor localization technology_

My progress is in line with our Gantt chart.

Next week I will be working on the Design presentation, as well as continuing to do research and discussing further with the team of how the project will end up unfolding. I would like to start working on the Django website by setting it up.