Posted on

Team Status Report 4/19

Shiva has been working on collecting experimental demo values for the hardware so that we can model them in the simulator. We actually got REALLY promising results with very low standard deviation and a very consistent pattern (after removing outliers).

This graph had a standard deviation of <1ns which again is really promising because it means if you assume a synchronized clock, the error from other hardware components is quite low! Plus, the very consistent shape of the graph (same shape in multiple trials) looked like the result of oscillator clock drift to us.

So we implemented a simple algorithm to sync slave anchors with a master clock to see if it would improve our results. Shiva managed to implement it, but we are still trying to process and interpret the results.

As soon as those results are ready, we should be able to incorporate them into the simulator that Rhea and Udit have been working on. Details of that are available on Udit’s status page.

We are hoping that we can get that integration done by the demo. We have collected so many data points and graphs that will at least make our Final Paper quite interesting.

Posted on

Udit’s Status Report 4/19

So I had a pretty productive and interesting 2 weeks (missed last week’s update so will combine with this)

  • By the end of last week, we came together and formalized our mathematical models. We are going to go with 3 approaches: System of Linear Eqs, System of Non-Lins, and an Extended Kalman Filter Smoothened model. I worked on implementing the former 2 options.
  • Then I implemented that math with a visualizer for each type where the TDoAs from the simulated tag will get passed to the algorithms and they will spit out a value that gets visualized back on the map
    • Rhea was able to add in the algorithm for Kalman filter as well
  • Here is an image of what the live visualization. The black circle is the tag (real location), purple square is linear-algorithm calculated location, green square is hyperbolic-algorithm calculated location, and blue square is the kalman filter algorithm calculated location.
  • Then for this week I worked on adding in error-reporting so that we can calculate the Root Mean Squared Error for each algorithm
  • Also have exported all values to CSVs so that we can store logs for each file and play back the data. I will be adding in a separate program that reads this CSV and visualizes the real path taken and the path modeled (for the paper).
  • Here is sample of results  for a basic movement of the tag around the lines of hte basketball court.
    • Our RMSE (in meters) for that sample run was the following:
      • Lin RMSE: 3.8608529220466794
        nonLin RMSE: 0.14847987088052897
        filter RMSE: 0.11742101999581132
      • This is really promising because it lines up with our general expectations that Linear<Non-linear<filtered
        • Right now this test is with 4 anchors which only leaves 2 equations for the linear. Hopefully Linear numbers become a lot more usable with 6 anchors
  • I am awaiting finalized hardware error numbers from Shiva to add in artificial error
  • I will also be looking for a dataset of player movements for real NBA games so we can get realistic movement of players/tags.
  • I will try to run a BUNCH of variations of tests with multiple player paths (real-NBA and simulated), multiple anchor configurations, and multiple error simulations.
Posted on

Team Status Report 4/5/20

We finalized handing all the hardware we had over the Shiva and ordering more of our final hardware from Quinn to Shiva. He was able to use UART to export data from decawave radio into RPi (no longer need SPI since hardware requirement are lessened). He can now read data into the RPi and timestamp.

Shiva has MANY tests to run and data to collect. First he will use a stationary tag and stationary anchor to measure various errors and reliability. We want to see the difference between theoretical pulse transmission time differences and the differences in reception. We want to measure both the precision of the reception differences as well as the absolute difference between it and the transmission as an offset in our server code. We want to also do these tests by first timestamping in the Decawave chip and then in the raspberry Pi to see if we see which measure is more reliable. He can move on to looking at reliability with 1 stationary tag and 2 anchors and test differences in Non-LOS settings.

These experiments will be used to validate the the simulated error we will add to the hardware simulator program. If our simulator has the same percent errors as Shiva reports, we can safely validate our simulator as a way to scale our project and test the success of our Kalman smoothing and Gauss-Newton approximator.

Rhea and I have been precisely been researching and implementing those just mentioned algorithms.

We hope that we can have a basic demo with Shiva’s error graphs + Udit ideal simulation + Gauss-Newton localization by Wednesday.

Posted on

Udit’s Status Report 4/5

This week’s focus was trying to fully understand the mathematical approach for my localization software.

I genuinely spent >10 hours reading papers. Based a lot of research and looking at results, I feel confident that our best approach right now is the following.

  1. Simulate player movements on a bball court in a variety of patterns and speeds (Straight line, zigzag, random, circular).
  2. Use the simulated distance between anchors and player to calculate TOAs at each anchor
  3. Send data to server program via sockets
  4. Calculate time differences (Taus) and other measurements
  5. Use the iterative Gauss-Newton method to solve the set of non-linear hyperbolic equations by least squares approximation to get (x,y) location with least residual
  6. Smooth these values by using a recursive extended Kalman filter

We are working to start off implementing this with perfect data from steps 1-2. Shiva is working on collecting experimental data from the hardware to give us an idea of high error and consistency will be in reading these numbers. We will add in simulated error based on that experimental error as our next step.

Once we get this stack working with decent success on simulations, we can replace steps 1 and 2 with the real hardware with Shiva sending packets from his simulated setup to our server code.

Step 5 is what I am in charge of and step 6 is what Rhea is in charge of.

I spent many hours reading multiple papers that offer strategies to solve the equations needed in step 5 but typos and slightly incorrect equations has slowed down the process. But here is the math I have thus far:

For each anchor i there is a (x_i, y_i) known location with an unknown (x,y) tag location.
R_i = v*T_i where v is speed of light in air and T_i is the TOF from tag to anchor i (unknown value)
tau_ij = T_i-T_j (tau is known because you can subtract timestamps)
R_i-R_j = v*T_i-v*T_j=v(T_i-T_j)=v(tau_ij)
Via algebraic manipulation, plugging in the distance formula (R_i = sqrt((x_i-x)^2+(y_i-y)^2)), and using 2 anchors as a reference, you get an equation

alpha_i*x+beta_i*y+C_i = 0 for i in {3,4} where alpha, beta and C are values calculated from v, tau_1i, x_1, y_1, x_i, y_i, tau_12, x_2, y_2 (which are all known constants or values from data).

alpha_i*x+beta_i*y+C_i = 0 for i in {3,4} gives us 2 linear equations with 2 unknowns that can be easily solved using an inverse matrix assuming perfect data. Because we don’t have perfect data, we have to use the hyperbolic equations and use a Gauss-newton least squares approximator.

I don’t fully understand the least squares method (especially how to implement it in code) and what are the exact hyperbolic equations that need to be approximated. Right now, I don’t see why we can’t estimate using the linear equation but that is my task for the next day or so.

Posted on

Team Status Report 3/29

This week we re-organized our rest of semester plan once again. Due to our advisers insisting we stick to executing our hardware plan.

Due to working from remote, we needed to find solderless headers which we had shipped from the UK. We are still awaiting our shipment of RPi4s.

Shiva was able to debug and fix the overflow issue he was having. He will take over figuring out the MCU–RPi interface portions from Rhea and run some tests to ensure consistency in measurements between anchor and tag.

Udit finished writing an ideal hardware timestamp simulator in Python.

Rhea and Udit spent the week reading 5+ papers on TDoA. The approaches that were considered were Iterative Hyperbolic Least Squares, Maximum Likelihood Estimator, Pseudo-Ranging, Weighted Delta-Range, Gauss-Newton Position Estimation, and Kalman Filter Smoothening.

We will be finalizing our research based on these approaches and picking a final approach to take by Monday.  We will implement these algorithms and test them using the hardware simulator (we will add in artificial hardware sampling and radio error) to get a clear idea of what accuracy we can achieve with different hardware errors. These will be used alongside the real measurements Shiva collects for Radio Delay to tell us how accurate our time-sync error must be.

Here is the updated Gantt Chart:

Gantt Chart V4 – Sheet1

Posted on

Udit’s Status Report for 3/28/20

This week I built our MVP for the hardware simulator. It visualizes one tag you can move with your arrow keys. It is paramaterized with ability to choose where anchors are placed and how often to send pulse the tags.

You can see a vague demo here:
https://1drv.ms/v/s!Aq6sdyvl6aqAn_EzuCtRUauMuckqig?e=53zhJC

As Rhea and I move into the main algorithm next week. Here is a TDoA overview of the general approach.

Rhea and I also read 3 papers for probabilistic approaches to TDoA that we are going to debate and refer as our primary approach tomorrow. Those papers methods are HLS and MLE, pseudo-ranging and weighted delta-range, and the most complex: kalman filter .

We are going to discuss and share our findings tomorrow. We will pick/combine approaches for our final implementation.

 

Posted on

Udit’s Status Report for 3/21/20

Pre-spring break I had been doing a lot of work into helping program the TDoA anchor code with shiva but that work became put on the backburner with the changes to our project due to COVID

I spent this week, thinking about the software for my simulation. I will work on converting it into a block diagram soon. But here is the jist of it.

  • Build a grid-based approximation of a basketball court. Hardcode placement of anchor objects on the edges of the court. Have tags in the grid on the court moving around semi-randomly as well as user controlled.
  • Use the distances between tags and anchors to calculate a time to travel between them. Use that plus a single centralized time-stamp (i.e. assuming perfect time sync) to generate a perfectly accurate time stamp for each anchor per tag pulse.
  • Use sockets to forward these timestamps to the localization software.
  • Log actual locations for comparison with the calculated locations by multilat software.

There a bunch of reach features that would be useful to have after the MVP described above. This includes a GUI for the bball court virtualization and adding in simulated hardware error. There would be a separate errors for radio transmission delay, anchor time-sync error, and LoS blockage delays.

Posted on

Team Status Update for 03/21

We spent most of our time this week trying to get reoriented after the major changes to our lives due to COVID19. Our project also went through some major changes.

  • We spent a lot of time trying to figure out how we could get the remaining hardware we needed. We needed our cables we ordered to ECE, and new solderless headers. Our only option for the latter seems to be importing from the UK
  • We redesigned the project to remove reliance on hardware by having Udit build a hardware timestamp simulator. Shiva will work on localization and Rhea will work on localization with error-correction.
  • Our refocused SOW is attached.

Refocus SOW

Posted on

Udit’s Status Report for 2/29/20

What was done this week:

I was focused on figuring out a way to program the chips with Python through SPI as a backup plan for if doing baremetal or the decawave API proved too difficult. Someone did something like this here:https://iosoft.blog/category/ultra-wideband-uwb/

I read through the entire thing and learned a lot about some of the math. But Shiva was able to figure out how to directly program the chips starting from some C examples so this approach was put on the backburner for later.  I also did significant work on the Design Presentation and the Design Report since I wanted to work on that while Shiva and Rhea worked on the TWR/TDoA communication + SPI backhaul.

I also kept track of these new facts about TWR/TDoA calculations that will be important.

  • You need to use asymmetric 3 message TWR to make sure that different clock speeds will be matched
    • Formula: 
      rnd1 = Rx2 - Tx1 # Round-trip 1 to 2
rep1 = Tx2 - Rx1 # Reply time 1 to 2
rnd2 = Rx3 - Tx2 # Round-trip 2 to 3
rep2 = Tx3 - Rx2 # Reply time 2 to 3 
time = (rnd1 × rnd2 - rep1 * rep2) / (rnd1 + rnd2 + rep1 + rep2)
  • Even with this formula, you have to experimentally determine the UWB clock delay (how long it takes for chips to send the signal) to get the exact distance

Our team is about 1 day behind since we have TWR working but still are yet to do radio delay calibration since the output we are getting seems inaccurate. We still have a sizable amount of the design report to do and finalize but we have most of it in pieces.

The hardest part remains time sync but we tackle that problem with the many options we have to solve as soon as we get backhaul into RPi working in any fashion.

I feel much better about the project than last week.

Posted on

Udit’s Status Report for 2/22/20

This week I confirmed that the design I will first be testing is just using the C calls for oscillators on the Decawave/RaspPi chips.

I found enough other people who were able to use this to enough accuracy for TWR/TDoA communication so it is important for us to give it a try.

I wrote a script in both C and python that calculated nanosecond clock ticks using the monotonic performance counter clock. Now we just need to focus on getting the UWB signals sent and received.

Our split up work is being severely hamstrung by that one component so it makes sense for all of us to work on that one part for now.

Also spent significant time this week reading through decawave documentation to start programming a tag software on the decawave chip. I am approaching the problem with Python while Shiva approaches it with C. We will take whichever one works first and run with it. And worked on the design presentation.

Roadblocks maintain programming the decawave chip (as, begrudgingly, Tamal was 100% right about).