Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Ultra-Wide-Band (UWB) localisation - algorithm development and embedded implementation



Paul Beuchat

The UWB project:

The Ultra-Wide-Band (UWB) localisation project was started here at IfA in 2014. The ultimate goal is to achieve sub-centimetre accuracy for 3D position localisation of a large number of moving agents (>100) within a large playing field (e.g., urban environments such as construction sites). The motivating application we use for the project is the Microsoft Indoor Localisation Competition that has been running for 4 years. The 2016 instalment of the competition allowed up to 5 stationary devices to be placed and the winning team achieved 23cm accuracy for localisation inside a large hall. See the website for more details. The challenge for the 2017 revision of the Microsoft localisation competition is expected to be released soon.

These thesis projects are in collaboration with Hexagon Mining Safety. The goal of Hexagon Mining Safety is to use the UWB technology to improve safety in the underground mining and warehouse environment where GPS signals are unavailable. The embedded optimisation solver that will be used is FORCES Pro, a high performance code generation software developed by the start-up embotech based at IfA.

Brief background on localisation

For localisation we consider having 2 types of devices operating on a field
  1. Anchors: these are devices that remain at a fixed location, for example located at the corners of a room.
  2. Tags: these are devices that move around on playing field, for example attached to robots that move around in the room
Using the UWB technology, all devices have the capability to send and receive messages, and are equipped with a high precision clock. The UWB technology we use is the Decawave DWM1000 chip, equipped with a omni-directional Chip-Antenna. These capabilities, ideally, allow a pair of devices to measure the distance between them by measuring the time it takes to send a message back and forth, and then dividing by the speed at which the message travels, i.e., the speed of light. Real world complications that reduce the accuracy of such measurements are: clock drift, device dependent timing offsets, and multiple messages cannot be receive simultaneously.

There are 3 main phases required for achieving high accuracy localisation:
  1. Phase 1 - Single anchor calibration: the device dependent timing offsets need to be identified and calibrated for each device separately.
  2. Phase 2 - Multi-anchor localisation: the anchors are placed at fixed locations but it is only practical to measure the exact position of a handful of them. The anchors must coordinate to measure the distance between all pairs, and based on this information compute the best estimate of their relative arrangement.
  3. Phase 3 - Multi-agent localisation: The tags move around the field and must communicate with the anchors using an algorithm that allows an arbitrary number of tags to simultaneously compute their location on the field.
The master's theses described below are aimed at implementing and improving the state-of-the-art across the 3 phases.

Description of the two Master Thesis' on offer:

Project 1: Multi agent localisation using Time Difference of Arrival (TDOA)

In this project the focus will be the localisation of a large number tags given that the position of the anchors is known. To achieve perfect scalability, the project will consider TDOA type measurements where the anchors are synchronised and send out messages at regular intervals. A tag measures the time at which it receives all the signals and based on the time difference of when the signals arrived, the tag can compute its position. This is essentially how GPS works.

As light travels 30cm in 1 nano-second, the main difficultly with implementing such a system is the precise synchronisation of the anchors. For GPS, the satellites have atomic clocks which keep time with extremely high precision. By contrast, the oscillations of the clock on the Decawave UWB module drift over time to be sometimes faster and sometimes slower than the "true" clock. As the clock on each anchor drifts differently, this destroys the synchronisation and, if not accounted for, significantly reduces the accuracy of localisation.

The goal of this thesis is to validate a model for the clock drift, and then use this to design an estimation algorithm for estimating the relative clock drift of each anchor, e.g., an Extended Kaman Filter.

  • Validation of a clock drift model.
  • Create a filtering algorithm to estimate the relative clock drift of each device.
  • A TDOA algorithm for the anchor transmission that achieves a similar accuracy across the whole playing field.
  • Hardware implementation to achieve the highest possible TDOA update rates. This will require hardware debugging and DMA (Direct Memory Access) programming.
  • Design and 3D-printing of a housing for the tags.

Project 2: Single-antenna calibration and multi-anchor localisation

As described above for phase 2, it is desirable to avoid measuring the exact position of all the anchors. For example, consider a large warehouse, it might require 30 anchors to have sufficient coverage for performing TDOA localisation, but it is only practical to measure the exact position of a handful of those anchors. Many techniques can be used to estimate the position of all anchors on the field based on measurements of distances between pairs of anchors. Recent student projects have shown promising results using non-linear optimisation techniques. The aim in this project is to develop these techniques further and provide experimental evidence of their potential to improve on the state-of-the-art.

The accuracy of anchor localisation depends mainly on the accuracy of the distance measurements between a pair of anchors. Off-the-shelf, the Decawave UWB module has manufacturing tolerances that limit the tightest "line-of-slight" accuracy to approximately 30cm. The main factor limiting this accuracy is the antenna delay, which is the time between the UWB chip requesting a signal to be sent, and when the signal actually leaves the antenna and begins propagating through the air. This is exactly the device dependent timing offsets that needs to be calibrated in Phase 1. Individual antenna delay calibration is complicated because all measurement that can be realistically performed involve the antenna delay of at least 2 antennas.

The goal of this thesis is to develop a repeatable antenna calibration technique, and then investigate how this affects accuracy for localising the whole field of anchors.

  • Implement, analyse, and compare a range of single antenna calibration algorithms
  • Implement, analyse, and compare a range of multi anchor localisation algorithms
  • Investigate how sensitive each anchor localisation algorithm is when some of the distance measurements between certain pairs are unavailable.
  • Design and 3D-printing of a housing for the anchors.

Who we are looking for:

These Master thesis projects involve a strong practical and theoretical component and will require the student to have a good command over both. Applicants should ideally have:
  • Completed subjects involving the study and implementation of Optimisation problems (for example MPC, Convex Optimisation).
  • Completed subjects involving estimation techniques (for example Recursive Estimation or System Identification).
  • Hardware experience is preferred, and C/C++ coding experience is desirable.
  • Strong initiative to propose localisation algorithms and a committed work ethic to implement and test multiple different options.
  • Good abilities with visualisation of data: as localisation is a 3D problem, visualisation of data can give important insights.
To be clear, the two master thesis projects proposed are separate and will be assessed separately. However, a good team work environment will greatly assist both students to make speedy progress. As such, we are happy to receive a joint application from 2 colleagues.

Starting date: Autumn/Winter 2016.
Type of project: 50% theory, 50% hardware implementation.

Weitere Informationen

John Lygeros

Art der Arbeit:
Anzahl StudentInnen:
Status: open
Projektstart: Sep 2016
Semester: Autumn 2016