Rsewiki - User contributions [en]

3D localization

2017-07-20T12:17:07Z

S123950: /* Results to date */

[[File:System close.jpg|thumb|right|600px|Full system with 6 anchors and 3 tags.]]

This page gives an overview of a three dimensional localization system developed. The system can be used in every scenario where it is wanted to obtain some sort of position or velocity information about something, whether it is for ground-truth information, control feedback, surveillance or the like. A few examples of such places could be:

* Robotic control position and velocity feedback, for autonomous usage
* Ground-truth to test other approaches
* Inventory tagging
* Personnel location information
* Intelligent transportation in regards to eg. smarter vehicles

The position and velocity estimates are available wherever they are needed, whether that is onboard the host as data extraction from the tag itself or at a specific anchor for data logging purposes. 
Furthermore the system features extremely rapid deployment, as the anchors will be able to find their own position in a matter of seconds from first power. This means that the system can be set-up and ready to be used in a matter of minutes, without loss of accuracy.

The developed system, is intended to be used as closed-environment system, meaning that it is intended to not require anything of the host carrying the tag. This means that the system is extremely versatile and can be used almost anywhere, as the host is not required to run any timing specific software.

==Hardware==
The localization system at hand consists of at least four anchors and one tag. 
The hardware design considerations, descriptions and overviews can be found at the [[Localization Hardware]] page. 
Each device communicates and ranges with each other through an UWB ([https://en.wikipedia.org/wiki/Ultra-wideband Ultra-wideband]) radio.
 
The system can be used by placing the anchors at fixed known positions in the room, preferably in different heights, after which the system will measure the distance from each anchor to the tag. These distances can then be combined with the known position of the associated anchor, in order to estimate the absolute position of the tag in three dimensions. The position will be calculated locally on the tag, and can as such be used to eg. control a robot carrying the tag.

==Software download==

The source code for the system is available here.
NB! the software source can not be compiled without the proper tool-chain (see [[Arm compiler environment]] for instructions on how to set this up)

A Github repository for the project is available at

https://repos.gbar.dtu.dk/git/jcan/3d_wb_loc.git

On a Linux computer this can be cloned as:
git clone https://repos.gbar.dtu.dk/git/jcan/3d_wb_loc.git

The softwares known bugs and issues can be found at [[3d Localization - Software issues]].

==Install software tools==

In order to modify the software, some tools are required.

* [[Arm compiler environment]] and tool-chain - Linux
* [[Localization Hardware]]

==Network topology==

[[File:Network flow.png|350px|thumb|right|Network notification flowchart for anchor and tag]]

The system is able to automatically register when new devices are joining the network, and as such automatically hand out network addresses to all new devices. This is done by having the tag issue a broadcast message once a second, in order to allow any new non-registered devices to answer back, letting the tag know there is an additional device available. The broadcast message is what's called a Blink message, which is actually just a very short message containing no info.

==Ranging==

[[File:DS-TWR.png|400px|thumb|right|Double-sided two way ranging scheme. Image taken from DW1000 User manual.]]

In order to estimate the distance between an anchor and a tag, the system uses [https://en.wikipedia.org/wiki/Time_of_flight Time of Flight (TOF)]. There exists a number of ways to estimate a distance from exchanging packages with timestamps, all with different pros and cons, which has been discussed elaborately in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]'''. In this project, it has been chosen to implement and use the double-sided two way ranging scheme as shown in the figure to the right. This method has the advantage that it is the best method for handling any clock skew between the two devices, this means that it will have a smaller impact on the range estimate, if the clock in one device is running slightly faster than the clock of the other device. 
The average time of flight between the two devices can be calculated as

:[[File:DS-TWR-calc.png]]

From this the distance can be calculated by multiplying the propagation time with the [https://en.wikipedia.org/wiki/Speed_of_light speed of light]. 

The DS-TWR ranging scheme mentioned above can then be extended through the use of broadcast messages, in order to minimize the required number of data exchanges between devices. One such way could be through the infrastructure based asset tracking scheme as implemented in this project. In this ranging scheme the tag sends a Poll message as a broadcast, which is received by a number of anchors (three in the following case) in the infrastructure. Each anchor then replies in successive responses with packets RespA, RespB & RespC after which the tag, sends the Final message as a broadcast again, received by all three anchors. This allows the tag to be located after sending only 2 messages and receiving 3 (including another 3 if the distances are needed on the tag).

This scheme is illustrated in the figure below.
This represents a substantial saving in message traffic, thereby saving battery power and air-time, while increasing potential update rate.

[[File:Infrastructure-based-asset-tracking.png|800px|Infrastructure based asset tracking scheme based on asymmetric double-sided two way ranging (DS-TWR). Image taken from DW1000 User manual.]]

==Positioning==
[[File:trilat.png|300px|thumb|right|Trilateration example.]]
The 3d position of the tag can be estimated, through [https://en.wikipedia.org/wiki/Multilateration multilateration] by using ranges to at least four different anchors.
 
Because there is noise in the distance estimations performed by the system, the multilateration has the issue of becoming an optimization problem. This is because there is no exact solution to the multilateration problem at hand, but there will exist a solution that minimizes the sum of the errors in the euclidean distances. Mathematically speaking that is a position solution (x,y,z) that will minimize the term (where r is the distance between the tag and the i'th anchor)

[[File:Position-minimize.png]]

Furthermore the complexity of the optimization tends to increase with more anchors being added into the system.

There are a few ways to solve the optimization problem described above, some of which will be discussed here.

====Nonlinear least squares optimization====
The direct way of solving the multilateration problem, would be through a least squares approximation. This is an iterative way of solving the problem in a purely non-statistical way, which means that it does not take into account what the previous solution was, and as such allows the tag to move an infinite distance between two consecutive samples. Another downside of the least squares method for solving the optimization problem, is that it is slightly harder to extend the system to provide more details, like velocity estimates. 
A nonlinear least squares implementation done in Matlab for the system, can be found in the ''Matlab'' folder in the github repository. Furthermore a paper on a non-iterative nonlinear least squares matrix solution to the multilateration problem can be found in ''Related papers/An Efficient Least-Squares Trilateration Algorithm for Mobile Robot Localization.pdf''

====Particle filter====
Another way of solving the optimization problem, is by utilizing a statistical particle filter, also known as a sequential Monte Carlo filter. The base idea of a particle filter, is that a number of "particles", containing a direction and a speed, is spawned in a distributed manner and is then perturbed, with the goal of having the particles converge towards the same point, with a unified direction and speed. 
The particle filter is a statistical filter, meaning that it takes into account the previous solutions found. 
The particle filter has '''not''' been implemented or tested for this project, but a sample implementation, in Python, of such filter for this specific use case can be found at [https://github.com/bitcraze/lps-ros https://github.com/bitcraze/lps-ros].

====Extended Kalman filter====
The last method of solving the optimization problem discussed here, will be the Extended Kalman filter. This way is, like the particle filter, a statistical filter capable of estimating a number of details about the system such as position, velocity and even accelerometer bias.

As the Kalman filter is still not fully implemented, and thus not tested, this section still needs some information about the Kalman filter.

===Sensor fusion===

Sensor fusion has still to be implemented in the project. The IMU on the tag is currently not used.

==Limitations==
The system does come with a few limitations, which will be discussed below.

===Line of sight (LOS)===
The most important limitation is that it is very sensitive to line of sight (LOS). This means that the tag trying to localize itself, should always have pure line of sight to at least 4 anchors, which is why it is recommended to run the system with 6 or more anchors, as this would give the system redundancy. It is possible to get a clue about whether the most recent range measurement was taken in a line of sight situation or not, by looking at the quality of the measurement. This quality is a combination of the received power level and the first path power level, and is discussed further in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]''' on page 45.

===Calibration===
Because the system is based on time of flight measurements of radio waves, even a small change in the time stamps of the system will result in huge variations in distance (1 ns results in a change of 299 mm). This means that proper calibration of the system is crucial in order to obtain any usable performance. The main calibration property of the system is the antenna delay constants, a constant describing the delay from antenna through PCB. A detailed explanation of the antenna delay and how to calibrate it properly can be found in '''[http://www.decawave.com/support/download/file/nojs/552 APS014: Antennna Delay Calibration]'''

===Range===
The range of the system varies tremendously, as a function of channel, header length, data rate, transmission power etc. A longer communication range usually means a lower data rate and a less accurate distance estimate of the system. With the configuration currently chosen for the system, the range is about 25 m, as the system is configured for the best distance approximation as possible. The relatively short range is however not a problem in this case, as the system is intended to be used indoors, where a room is seldom larger than 25 meters end-to-end.

===Received signal strength bias===

The system seems to contain a ranging bias as a function of the received signal strength. The phenomena is discussed in '''[http://www.decawave.com/support/download/file/nojs/453 APS011: Sources of error in TWR schemes]''', where a proposed bias correction curve is given as well. Numerous measurements has been taken during this localization project, in order to see whether the antenna shielding of the anchors, changes the required correction curve. It has yet to be proved with absolute certainty, that the provided curve is in fact the best curve or the job, but for now it seems like the provided curve is accurate. The measurements for this conclusion can be found in ''Matlab/bias'' in the Github repository.

==Results to date==

Previous results can be found in the ''Related papers/Previous DTU projects'' folder in the Github repository.

==Further work==

* Multiple tags
*; The current implementation can only handle one tag in the system at a time. This limitation is due to the implemented ''infrastructure based asset tracking scheme'' seen in [[3D localization#Ranging]].
* Relative positioning
*; It would be interesting to implement a way for tags to calculate relative positions, in order to allow robotic formations in an easy manner.
* Peer-to-peer mesh ranging scheme
*; Allow all of the devices to range to all other devices.
* Message push-through option
*; A structured way of utilizing the large data bandwidth of the system, in order to allow devices to exchange communication that is not ranging or position related.
* Output API
*; A proper API on how the host devices can acquire data from the tags, through I2C, USB, UART og SPI. Also allowing a data driven scheme with a physical interrupt pin.

==Further reading==

More resources on the subject can be found at:
* [http://www.decawave.com/support http://www.decawave.com/support] (Requires free signup to download)
* [https://groups.google.com/forum/#!forum/decawave_group https://groups.google.com/forum/#!forum/decawave_group] (Requires membership, everyone can obtain free membership)
* The ''Related papers'' folder in github

2016-06-01T17:17:13Z

S123950: /* Hardware */

[[File:System close.jpg|thumb|right|600px|Full system with 6 anchors and 3 tags.]]

TODO: Short intro to the system, the need for such system, possible applications and a short overview.

==Hardware==
The localization system at hand consists of at least 4 '''anchors''' and a '''tag'''. 
The hardware design considerations, descriptions and overviews can be found at the [[Localization Hardware]] page. 
Each device communicates and ranges with each other through an UWB ([https://en.wikipedia.org/wiki/Ultra-wideband Ultra-wideband]) radio.
 
The system can be used by placing the anchors at fixed known positions in the room, preferably in different heights, after which the system will measure the distance from each anchor to the tag. These distances can then be combined with the known position of the associated anchor, in order to estimate the absolute position of the tag in three dimensions. The position will be calculated locally on the tag, and can as such be used to eg. control a robot carrying the tag.

[[File:trilat.png|300px]]

==Software download==

The source code for the system is available here.
NB! the software source can not be compiled without the proper tool-chain (see [[Arm compiler environment]] for instructions on how to set this up)

A Github repository for the project is available at

https://repos.gbar.dtu.dk/git/jcan/3d_wb_loc.git

On a Linux computer this can be cloned as:
git clone https://repos.gbar.dtu.dk/git/jcan/3d_wb_loc.git

==Install software tools==

In order to modify the software, some tools are required.

* [[Arm compiler environment]] and tool-chain - Linux
* [[Localization Hardware]]

==Network topology==

[[File:Network flow.png|350px|thumb|right|Network notification flowchart for anchor and tag]]

The system is able to automatically register when new devices are joining the network, and as such automatically hand out network addresses to all new devices. This is done by having the tag issue a broadcast message once a second, in order to allow any new non-registered devices to answer back, letting the tag know there is an additional device available. The broadcast message is what's called a Blink message, which is actually just a very short message containing no info.

==Ranging==

[[File:DS-TWR.png|400px|thumb|right|Double-sided two way ranging scheme. Image taken from DW1000 User manual.]]

In order to estimate the distance between an anchor and a tag, the system uses [https://en.wikipedia.org/wiki/Time_of_flight Time of Flight (TOF)]. There exists a number of ways to estimate a distance from exchanging packages with timestamps, all with different pros and cons, which has been discussed elaborately in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]'''. In this project, it has been chosen to implement and use the double-sided two way ranging scheme as shown in the figure to the right. This method has the advantage that it is the best method for handling any clock skew between the two devices, this means that it will have a smaller impact on the range estimate, if the clock in one device is running slightly faster than the clock of the other device. 
The average time of flight between the two devices can be calculated as

:[[File:DS-TWR-calc.png]]

From this the distance can be calculated by multiplying the propagation time with the [https://en.wikipedia.org/wiki/Speed_of_light speed of light]. 

The DS-TWR ranging scheme mentioned above can then be extended through the use of broadcast messages, in order to minimize the required number of data exchanges between devices. One such way could be through the infrastructure based asset tracking scheme as implemented in this project. In this ranging scheme the tag sends a Poll message as a broadcast, which is received by a number of anchors (three in the following case) in the infrastructure. Each anchor then replies in successive responses with packets RespA, RespB & RespC after which the tag, sends the Final message as a broadcast again, received by all three anchors. This allows the tag to be located after sending only 2 messages and receiving 3 (including another 3 if the distances are needed on the tag).

This scheme is illustrated in the figure below.
This represents a substantial saving in message traffic, thereby saving battery power and air-time, while increasing potential update rate.

[[File:Infrastructure-based-asset-tracking.png|800px|Infrastructure based asset tracking scheme based on asymmetric double-sided two way ranging (DS-TWR). Image taken from DW1000 User manual.]]

* TODO: Write a bit about peer-to-peer ranging schemes for lower update rate, but where every device knows the distance to every other device.

==Positioning==
The 3d position of the tag can be estimated, through [https://en.wikipedia.org/wiki/Multilateration multilateration] by using ranges to at least four different anchors.
 
Because there is noise in the distance estimations performed by the system, the multilateration has the issue of becoming an optimization problem. This is because there is no exact solution to the multilateration problem at hand, but there will exist a solution that minimizes the sum of the errors in the euclidean distances. Mathematically speaking that is a position solution (x,y,z) that will minimize the term (where r is the distance between the tag and the i'th anchor)

[[File:Position-minimize.png]]

Furthermore the complexity of the optimization tends to increase with more anchors being added into the system.

There are a few ways to solve the optimization problem described above, some of which will be discussed here.

====Nonlinear least squares optimization====
The direct way of solving the multilateration problem, would be through a least squares approximation. This is an iterative way of solving the problem in a purely non-statistical way, which means that it does not take into account what the previous solution was, and as such allows the tag to move an infinite distance between two consecutive samples. Another downside of the least squares method for solving the optimization problem, is that it is slightly harder to extend the system to provide more details, like velocity estimates. 
A nonlinear least squares implementation done in Matlab for the system, can be found in the ''Matlab'' folder in the github repository.

====Particle filter====
Another way of solving the optimization problem, is by utilizing a statistical particle filter, also known as a sequential Monte Carlo filter. The base idea of a particle filter, is that a number of "particles", containing a direction and a speed, is spawned in a distributed manner and is then perturbed, with the goal of having the particles converge towards the same point, with a unified direction and speed. 
The particle filter is a statistical filter, meaning that it takes into account the previous solutions found. 
The particle filter has '''not''' been implemented or tested for this project, but a sample implementation, in Python, of such filter for this specific use case can be found at [https://github.com/bitcraze/lps-ros https://github.com/bitcraze/lps-ros].

====Extended Kalman filter====
The last method of solving the optimization problem discussed here, will be the Extended Kalman filter. This way is, like the particle filter, a statistical filter capable of estimating a number of details about the system such as position, velocity and even accelerometer bias.

TODO: Elaborate on the use of Kalman

===Sensor fusion===

TODO.

==Limitations==
The system does come with a few limitations, which will be discussed below.

===Line of sight (LOS)===
The most important limitation is that it is very sensitive to line of sight (LOS). This means that the tag trying to localize itself, should always have pure line of sight to at least 4 anchors, which is why it is recommended to run the system with 6 or more anchors, as this would give the system redundancy. It is possible to get a clue about whether the most recent range measurement was taken in a line of sight situation or not, by looking at the quality of the measurement. This quality is a combination of the received power level and the first path power level, and is discussed further in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]''' on page 45.

===Calibration===
Because the system is based on time of flight measurements of radio waves, even a small change in the time stamps of the system will result in huge variations in distance (1 ns results in a change of 299 mm). This means that proper calibration of the system is crucial in order to obtain any usable performance. The main calibration property of the system is the antenna delay constants, a constant describing the delay from antenna through PCB. A detailed explanation of the antenna delay and how to calibrate it properly can be found in '''[http://www.decawave.com/support/download/file/nojs/552 APS014: Antennna Delay Calibration]'''

===Range===
The range of the system varies tremendously, as a function of channel, header length, data rate, transmission power etc. A longer communication range usually means a lower data rate and a less accurate distance estimate of the system. With the configuration currently chosen for the system, the range is about 25 m, as the system is configured for the best distance approximation as possible. The relatively short range is however not a problem in this case, as the system is intended to be used indoors, where a room is seldom larger than 25 meters end-to-end.

===Received signal strength bias===

TODO: Write about the bias!

==Results to date==

BIG TODO

==Further work==

* Multiple tags
* Relative positioning
* Peer-to-peer mesh ranging scheme
* Sensor fusion in EKF or preferably UKF
* Message push-through option
* Logging

==Further reading==

More resources on the subject can be found at:
* [http://www.decawave.com/support http://www.decawave.com/support] (Requires free signup to download)
* [https://groups.google.com/forum/#!forum/decawave_group https://groups.google.com/forum/#!forum/decawave_group] (Requires membership, everyone can obtain free membership)
* The ''Related papers'' folder in github

3D localization

2016-06-01T17:17:04Z

S123950: /* Hardware */

[[File:System close.jpg|thumb|right|600px|Full system with 6 anchors and 3 tags.]]

TODO: Short intro to the system, the need for such system, possible applications and a short overview.

==Hardware==
The localization system at hand consists of at least 4 '''anchors''' and a '''tag'''. 
The hardware design considerations, descriptions and overviews can be found at the [[Localization Hardware]] page. 
Each device communicates and ranges with each other through an UWB ([https://en.wikipedia.org/wiki/Ultra-wideband Ultra-wideband]) radio.
 
The system can be used by placing the anchors at fixed known positions in the room, preferably in different heights, after which the system will measure the distance from each anchor to the tag. These distances can then be combined with the known position of the associated anchor, in order to estimate the absolute position of the tag in three dimensions. The position will be calculated locally on the tag, and can as such be used to eg. control a robot carrying the tag.
[[File:trilat.png|300px]]

==Software download==

The source code for the system is available here.
NB! the software source can not be compiled without the proper tool-chain (see [[Arm compiler environment]] for instructions on how to set this up)

A Github repository for the project is available at

https://repos.gbar.dtu.dk/git/jcan/3d_wb_loc.git

On a Linux computer this can be cloned as:
git clone https://repos.gbar.dtu.dk/git/jcan/3d_wb_loc.git

==Install software tools==

In order to modify the software, some tools are required.

* [[Arm compiler environment]] and tool-chain - Linux
* [[Localization Hardware]]

==Network topology==

[[File:Network flow.png|350px|thumb|right|Network notification flowchart for anchor and tag]]

The system is able to automatically register when new devices are joining the network, and as such automatically hand out network addresses to all new devices. This is done by having the tag issue a broadcast message once a second, in order to allow any new non-registered devices to answer back, letting the tag know there is an additional device available. The broadcast message is what's called a Blink message, which is actually just a very short message containing no info.

==Ranging==

[[File:DS-TWR.png|400px|thumb|right|Double-sided two way ranging scheme. Image taken from DW1000 User manual.]]

In order to estimate the distance between an anchor and a tag, the system uses [https://en.wikipedia.org/wiki/Time_of_flight Time of Flight (TOF)]. There exists a number of ways to estimate a distance from exchanging packages with timestamps, all with different pros and cons, which has been discussed elaborately in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]'''. In this project, it has been chosen to implement and use the double-sided two way ranging scheme as shown in the figure to the right. This method has the advantage that it is the best method for handling any clock skew between the two devices, this means that it will have a smaller impact on the range estimate, if the clock in one device is running slightly faster than the clock of the other device. 
The average time of flight between the two devices can be calculated as

:[[File:DS-TWR-calc.png]]

From this the distance can be calculated by multiplying the propagation time with the [https://en.wikipedia.org/wiki/Speed_of_light speed of light]. 

The DS-TWR ranging scheme mentioned above can then be extended through the use of broadcast messages, in order to minimize the required number of data exchanges between devices. One such way could be through the infrastructure based asset tracking scheme as implemented in this project. In this ranging scheme the tag sends a Poll message as a broadcast, which is received by a number of anchors (three in the following case) in the infrastructure. Each anchor then replies in successive responses with packets RespA, RespB & RespC after which the tag, sends the Final message as a broadcast again, received by all three anchors. This allows the tag to be located after sending only 2 messages and receiving 3 (including another 3 if the distances are needed on the tag).

This scheme is illustrated in the figure below.
This represents a substantial saving in message traffic, thereby saving battery power and air-time, while increasing potential update rate.

[[File:Infrastructure-based-asset-tracking.png|800px|Infrastructure based asset tracking scheme based on asymmetric double-sided two way ranging (DS-TWR). Image taken from DW1000 User manual.]]

* TODO: Write a bit about peer-to-peer ranging schemes for lower update rate, but where every device knows the distance to every other device.

==Positioning==
The 3d position of the tag can be estimated, through [https://en.wikipedia.org/wiki/Multilateration multilateration] by using ranges to at least four different anchors.
 
Because there is noise in the distance estimations performed by the system, the multilateration has the issue of becoming an optimization problem. This is because there is no exact solution to the multilateration problem at hand, but there will exist a solution that minimizes the sum of the errors in the euclidean distances. Mathematically speaking that is a position solution (x,y,z) that will minimize the term (where r is the distance between the tag and the i'th anchor)

[[File:Position-minimize.png]]

Furthermore the complexity of the optimization tends to increase with more anchors being added into the system.

There are a few ways to solve the optimization problem described above, some of which will be discussed here.

====Nonlinear least squares optimization====
The direct way of solving the multilateration problem, would be through a least squares approximation. This is an iterative way of solving the problem in a purely non-statistical way, which means that it does not take into account what the previous solution was, and as such allows the tag to move an infinite distance between two consecutive samples. Another downside of the least squares method for solving the optimization problem, is that it is slightly harder to extend the system to provide more details, like velocity estimates. 
A nonlinear least squares implementation done in Matlab for the system, can be found in the ''Matlab'' folder in the github repository.

====Particle filter====
Another way of solving the optimization problem, is by utilizing a statistical particle filter, also known as a sequential Monte Carlo filter. The base idea of a particle filter, is that a number of "particles", containing a direction and a speed, is spawned in a distributed manner and is then perturbed, with the goal of having the particles converge towards the same point, with a unified direction and speed. 
The particle filter is a statistical filter, meaning that it takes into account the previous solutions found. 
The particle filter has '''not''' been implemented or tested for this project, but a sample implementation, in Python, of such filter for this specific use case can be found at [https://github.com/bitcraze/lps-ros https://github.com/bitcraze/lps-ros].

====Extended Kalman filter====
The last method of solving the optimization problem discussed here, will be the Extended Kalman filter. This way is, like the particle filter, a statistical filter capable of estimating a number of details about the system such as position, velocity and even accelerometer bias.

TODO: Elaborate on the use of Kalman

===Sensor fusion===

TODO.

==Limitations==
The system does come with a few limitations, which will be discussed below.

===Line of sight (LOS)===
The most important limitation is that it is very sensitive to line of sight (LOS). This means that the tag trying to localize itself, should always have pure line of sight to at least 4 anchors, which is why it is recommended to run the system with 6 or more anchors, as this would give the system redundancy. It is possible to get a clue about whether the most recent range measurement was taken in a line of sight situation or not, by looking at the quality of the measurement. This quality is a combination of the received power level and the first path power level, and is discussed further in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]''' on page 45.

===Calibration===
Because the system is based on time of flight measurements of radio waves, even a small change in the time stamps of the system will result in huge variations in distance (1 ns results in a change of 299 mm). This means that proper calibration of the system is crucial in order to obtain any usable performance. The main calibration property of the system is the antenna delay constants, a constant describing the delay from antenna through PCB. A detailed explanation of the antenna delay and how to calibrate it properly can be found in '''[http://www.decawave.com/support/download/file/nojs/552 APS014: Antennna Delay Calibration]'''

===Range===
The range of the system varies tremendously, as a function of channel, header length, data rate, transmission power etc. A longer communication range usually means a lower data rate and a less accurate distance estimate of the system. With the configuration currently chosen for the system, the range is about 25 m, as the system is configured for the best distance approximation as possible. The relatively short range is however not a problem in this case, as the system is intended to be used indoors, where a room is seldom larger than 25 meters end-to-end.

===Received signal strength bias===

TODO: Write about the bias!

==Results to date==

BIG TODO

==Further work==

* Multiple tags
* Relative positioning
* Peer-to-peer mesh ranging scheme
* Sensor fusion in EKF or preferably UKF
* Message push-through option
* Logging

==Further reading==

More resources on the subject can be found at:
* [http://www.decawave.com/support http://www.decawave.com/support] (Requires free signup to download)
* [https://groups.google.com/forum/#!forum/decawave_group https://groups.google.com/forum/#!forum/decawave_group] (Requires membership, everyone can obtain free membership)
* The ''Related papers'' folder in github

2016-06-01T12:17:21Z

S123950:

[[File:File:System close.jpg|thumb|right|600px|Full system with 6 anchors and 3 tags.]]

TODO: Short intro to the system, the need for such system, possible applications and a short overview.

==Hardware==
The localization system at hand consists of at least 4 '''anchors''' and a '''tag'''. 
The hardware design considerations, descriptions and overviews can be found at the [[Localization Hardware]] page. 
Each device communicates and ranges with each other through an UWB ([https://en.wikipedia.org/wiki/Ultra-wideband Ultra-wideband]) radio.

==Software download==

The source code for the system is available here.
NB! the software source can not be compiled without the proper tool-chain (see [[Arm compiler environment]] for instructions on how to set this up)

A Github repository for the project is available at

TODO: Add github here!

On a Linux computer this can be cloned as:
git clone Something!

==Install software tools==

In order to modify the software, some tools are required.

* [[Arm compiler environment]] and tool-chain - Linux
* [[Localization Hardware]]

==Network topology==

[[File:Network flow.png|350px|thumb|right|Network notification flowchart for anchor and tag]]

The system is able to automatically register when new devices are joining the network, and as such automatically hand out network addresses to all new devices. This is done by having the tag issue a broadcast message once a second, in order to allow any new non-registered devices to answer back, letting the tag know there is an additional device available. The broadcast message is what's called a Blink message, which is actually just a very short message containing no info.

==Ranging==

[[File:DS-TWR.png|400px|thumb|right|Double-sided two way ranging scheme. Image taken from DW1000 User manual.]]

In order to estimate the distance between an anchor and a tag, the system uses [https://en.wikipedia.org/wiki/Time_of_flight Time of Flight (TOF)]. There exists a number of ways to estimate a distance from exchanging packages with timestamps, all with different pros and cons, which has been discussed elaborately in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]'''. In this project, it has been chosen to implement and use the double-sided two way ranging scheme as shown in the figure to the right. This method has the advantage that it is the best method for handling any clock skew between the two devices, this means that it will have a smaller impact on the range estimate, if the clock in one device is running slightly faster than the clock of the other device. 
The average time of flight between the two devices can be calculated as

:[[File:DS-TWR-calc.png]]

From this the distance can be calculated by multiplying the propagation time with the [https://en.wikipedia.org/wiki/Speed_of_light speed of light]. 

The DS-TWR ranging scheme mentioned above can then be extended through the use of broadcast messages, in order to minimize the required number of data exchanges between devices. One such way could be through the infrastructure based asset tracking scheme as implemented in this project. In this ranging scheme the tag sends a Poll message as a broadcast, which is received by a number of anchors (three in the following case) in the infrastructure. Each anchor then replies in successive responses with packets RespA, RespB & RespC after which the tag, sends the Final message as a broadcast again, received by all three anchors. This allows the tag to be located after sending only 2 messages and receiving 3 (including another 3 if the distances are needed on the tag).

This scheme is illustrated in the figure below.
This represents a substantial saving in message traffic, thereby saving battery power and air-time, while increasing potential update rate.

[[File:Infrastructure-based-asset-tracking.png|800px|Infrastructure based asset tracking scheme based on asymmetric double-sided two way ranging (DS-TWR). Image taken from DW1000 User manual.]]

* TODO: Write a bit about peer-to-peer ranging schemes for lower update rate, but where every device knows the distance to every other device.

==Positioning==
The 3d position of the tag can be estimated, through [https://en.wikipedia.org/wiki/Multilateration multilateration] by using ranges to at least four different anchors.
 
Because there is noise in the distance estimations performed by the system, the multilateration has the issue of becoming an optimization problem. This is because there is no exact solution to the multilateration problem at hand, but there will exist a solution that minimizes the sum of the errors in the euclidean distances. Mathematically speaking that is a position solution (x,y,z) that will minimize the term (where r is the distance between the tag and the i'th anchor)

[[File:Position-minimize.png]]

Furthermore the complexity of the optimization tends to increase with more anchors being added into the system.

There are a few ways to solve the optimization problem described above, some of which will be discussed here.

====Nonlinear least squares optimization====
The direct way of solving the multilateration problem, would be through a least squares approximation. This is an iterative way of solving the problem in a purely non-statistical way, which means that it does not take into account what the previous solution was, and as such allows the tag to move an infinite distance between two consecutive samples. Another downside of the least squares method for solving the optimization problem, is that it is slightly harder to extend the system to provide more details, like velocity estimates. 
A nonlinear least squares implementation done in Matlab for the system, can be found in the ''Matlab'' folder in the github repository.

====Particle filter====
Another way of solving the optimization problem, is by utilizing a statistical particle filter, also known as a sequential Monte Carlo filter. The base idea of a particle filter, is that a number of "particles", containing a direction and a speed, is spawned in a distributed manner and is then perturbed, with the goal of having the particles converge towards the same point, with a unified direction and speed. 
The particle filter is a statistical filter, meaning that it takes into account the previous solutions found. 
The particle filter has '''not''' been implemented or tested for this project, but a sample implementation, in Python, of such filter for this specific use case can be found at [https://github.com/bitcraze/lps-ros https://github.com/bitcraze/lps-ros].

====Extended Kalman filter====
The last method of solving the optimization problem discussed here, will be the Extended Kalman filter. This way is, like the particle filter, a statistical filter capable of estimating a number of details about the system such as position, velocity and even accelerometer bias.

TODO: Elaborate on the use of Kalman

===Sensor fusion===

TODO.

==Limitations==
The system does come with a few limitations, which will be discussed below.

===Line of sight (LOS)===
The most important limitation is that it is very sensitive to line of sight (LOS). This means that the tag trying to localize itself, should always have pure line of sight to at least 4 anchors, which is why it is recommended to run the system with 6 or more anchors, as this would give the system redundancy. It is possible to get a clue about whether the most recent range measurement was taken in a line of sight situation or not, by looking at the quality of the measurement. This quality is a combination of the received power level and the first path power level, and is discussed further in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]''' on page 45.

===Calibration===
Because the system is based on time of flight measurements of radio waves, even a small change in the time stamps of the system will result in huge variations in distance (1 ns results in a change of 299 mm). This means that proper calibration of the system is crucial in order to obtain any usable performance. The main calibration property of the system is the antenna delay constants, a constant describing the delay from antenna through PCB. A detailed explanation of the antenna delay and how to calibrate it properly can be found in '''[http://www.decawave.com/support/download/file/nojs/552 APS014: Antennna Delay Calibration]'''

===Range===
The range of the system varies tremendously, as a function of channel, header length, data rate, transmission power etc. A longer communication range usually means a lower data rate and a less accurate distance estimate of the system. With the configuration currently chosen for the system, the range is about 25 m, as the system is configured for the best distance approximation as possible. The relatively short range is however not a problem in this case, as the system is intended to be used indoors, where a room is seldom larger than 25 meters end-to-end.

===Received signal strength bias===

TODO: Write about the bias!

==Results to date==

BIG TODO

==Further work==

* Multiple tags
* Relative positioning
* Peer-to-peer mesh ranging scheme
* Sensor fusion in EKF or preferably UKF
* Message push-through option
* Logging

==Further reading==

More resources on the subject can be found at:
* [http://www.decawave.com/support http://www.decawave.com/support] (Requires free signup to download)
* [https://groups.google.com/forum/#!forum/decawave_group https://groups.google.com/forum/#!forum/decawave_group] (Requires membership, everyone can obtain free membership)
* The ''Related papers'' folder in github

File:System distributed.jpg

2016-06-01T12:16:29Z

S123950:

File:System close.jpg

2016-06-01T12:15:33Z

S123950:

File:Tag anchor.jpg

2016-06-01T12:14:43Z

S123950:

3D localization

2016-06-01T09:45:00Z

S123950: /* Positioning */

TODO: Short intro to the system, the need for such system, possible applications and a short overview.

==Hardware==
The localization system at hand consists of at least 4 '''anchors''' and a '''tag'''. 
The hardware design considerations, descriptions and overviews can be found at the [[Localization Hardware]] page. 
Each device communicates and ranges with each other through an UWB ([https://en.wikipedia.org/wiki/Ultra-wideband Ultra-wideband]) radio.

==Software download==

The source code for the system is available here.
NB! the software source can not be compiled without the proper tool-chain (see [[Arm compiler environment]] for instructions on how to set this up)

A Github repository for the project is available at

TODO: Add github here!

On a Linux computer this can be cloned as:
git clone Something!

==Install software tools==

In order to modify the software, some tools are required.

* [[Arm compiler environment]] and tool-chain - Linux
* [[Localization Hardware]]

==Network topology==

[[File:Network flow.png|350px|thumb|right|Network notification flowchart for anchor and tag]]

The system is able to automatically register when new devices are joining the network, and as such automatically hand out network addresses to all new devices. This is done by having the tag issue a broadcast message once a second, in order to allow any new non-registered devices to answer back, letting the tag know there is an additional device available. The broadcast message is what's called a Blink message, which is actually just a very short message containing no info.

==Ranging==

[[File:DS-TWR.png|400px|thumb|right|Double-sided two way ranging scheme. Image taken from DW1000 User manual.]]

In order to estimate the distance between an anchor and a tag, the system uses [https://en.wikipedia.org/wiki/Time_of_flight Time of Flight (TOF)]. There exists a number of ways to estimate a distance from exchanging packages with timestamps, all with different pros and cons, which has been discussed elaborately in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]'''. In this project, it has been chosen to implement and use the double-sided two way ranging scheme as shown in the figure to the right. This method has the advantage that it is the best method for handling any clock skew between the two devices, this means that it will have a smaller impact on the range estimate, if the clock in one device is running slightly faster than the clock of the other device. 
The average time of flight between the two devices can be calculated as

:[[File:DS-TWR-calc.png]]

From this the distance can be calculated by multiplying the propagation time with the [https://en.wikipedia.org/wiki/Speed_of_light speed of light]. 

The DS-TWR ranging scheme mentioned above can then be extended through the use of broadcast messages, in order to minimize the required number of data exchanges between devices. One such way could be through the infrastructure based asset tracking scheme as implemented in this project. In this ranging scheme the tag sends a Poll message as a broadcast, which is received by a number of anchors (three in the following case) in the infrastructure. Each anchor then replies in successive responses with packets RespA, RespB & RespC after which the tag, sends the Final message as a broadcast again, received by all three anchors. This allows the tag to be located after sending only 2 messages and receiving 3 (including another 3 if the distances are needed on the tag).

This scheme is illustrated in the figure below.
This represents a substantial saving in message traffic, thereby saving battery power and air-time, while increasing potential update rate.

[[File:Infrastructure-based-asset-tracking.png|800px|Infrastructure based asset tracking scheme based on asymmetric double-sided two way ranging (DS-TWR). Image taken from DW1000 User manual.]]

* TODO: Write a bit about peer-to-peer ranging schemes for lower update rate, but where every device knows the distance to every other device.

==Positioning==
The 3d position of the tag can be estimated, through [https://en.wikipedia.org/wiki/Multilateration multilateration] by using ranges to at least four different anchors.
 
Because there is noise in the distance estimations performed by the system, the multilateration has the issue of becoming an optimization problem. This is because there is no exact solution to the multilateration problem at hand, but there will exist a solution that minimizes the sum of the errors in the euclidean distances. Mathematically speaking that is a position solution (x,y,z) that will minimize the term (where r is the distance between the tag and the i'th anchor)

[[File:Position-minimize.png]]

Furthermore the complexity of the optimization tends to increase with more anchors being added into the system.

There are a few ways to solve the optimization problem described above, some of which will be discussed here.

====Nonlinear least squares optimization====
The direct way of solving the multilateration problem, would be through a least squares approximation. This is an iterative way of solving the problem in a purely non-statistical way, which means that it does not take into account what the previous solution was, and as such allows the tag to move an infinite distance between two consecutive samples. Another downside of the least squares method for solving the optimization problem, is that it is slightly harder to extend the system to provide more details, like velocity estimates. 
A nonlinear least squares implementation done in Matlab for the system, can be found in the ''Matlab'' folder in the github repository.

====Particle filter====
Another way of solving the optimization problem, is by utilizing a statistical particle filter, also known as a sequential Monte Carlo filter. The base idea of a particle filter, is that a number of "particles", containing a direction and a speed, is spawned in a distributed manner and is then perturbed, with the goal of having the particles converge towards the same point, with a unified direction and speed. 
The particle filter is a statistical filter, meaning that it takes into account the previous solutions found. 
The particle filter has '''not''' been implemented or tested for this project, but a sample implementation, in Python, of such filter for this specific use case can be found at [https://github.com/bitcraze/lps-ros https://github.com/bitcraze/lps-ros].

====Extended Kalman filter====
The last method of solving the optimization problem discussed here, will be the Extended Kalman filter. This way is, like the particle filter, a statistical filter capable of estimating a number of details about the system such as position, velocity and even accelerometer bias.

TODO: Elaborate on the use of Kalman

===Sensor fusion===

TODO.

==Limitations==
The system does come with a few limitations, which will be discussed below.

===Line of sight (LOS)===
The most important limitation is that it is very sensitive to line of sight (LOS). This means that the tag trying to localize itself, should always have pure line of sight to at least 4 anchors, which is why it is recommended to run the system with 6 or more anchors, as this would give the system redundancy. It is possible to get a clue about whether the most recent range measurement was taken in a line of sight situation or not, by looking at the quality of the measurement. This quality is a combination of the received power level and the first path power level, and is discussed further in the '''[http://www.decawave.com/support/download/file/nojs/744 DW1000 User manual]''' on page 45.

===Calibration===
Because the system is based on time of flight measurements of radio waves, even a small change in the time stamps of the system will result in huge variations in distance (1 ns results in a change of 299 mm). This means that proper calibration of the system is crucial in order to obtain any usable performance. The main calibration property of the system is the antenna delay constants, a constant describing the delay from antenna through PCB. A detailed explanation of the antenna delay and how to calibrate it properly can be found in '''[http://www.decawave.com/support/download/file/nojs/552 APS014: Antennna Delay Calibration]'''

===Range===
The range of the system varies tremendously, as a function of channel, header length, data rate, transmission power etc. A longer communication range usually means a lower data rate and a less accurate distance estimate of the system. With the configuration currently chosen for the system, the range is about 25 m, as the system is configured for the best distance approximation as possible. The relatively short range is however not a problem in this case, as the system is intended to be used indoors, where a room is seldom larger than 25 meters end-to-end.

===Received signal strength bias===

TODO: Write about the bias!

==Results to date==

BIG TODO

==Further work==

* Multiple tags
* Relative positioning
* Peer-to-peer mesh ranging scheme
* Sensor fusion in EKF or preferably UKF
* Message push-through option
* Logging

==Further reading==

More resources on the subject can be found at:
* [http://www.decawave.com/support http://www.decawave.com/support] (Requires free signup to download)
* [https://groups.google.com/forum/#!forum/decawave_group https://groups.google.com/forum/#!forum/decawave_group] (Requires membership, everyone can obtain free membership)
* The ''Related papers'' folder in github

2016-05-31T13:37:23Z

S123950:

This page describes the hardware design of the [[3D localization]] system.

The anchors and tags are made up of some main components as described in the table below. The main difference is that the anchors have 180° of the antenna shielded in order to allow mounting on walls and ceilings without changing the antenna properties from reflections, other than that the tags contains a high precision IMU for sensor fusion in order to improve the velocity estimates.

{| class="wikitable" width="50%"
|+ Main hardware elements of anchors and tags
|-
! Anchors
! Tag
|-
| a cortex-m0 processor from ST (STM32f072)
| a cortex-m3 processor from ST (STM32f103)
|-
| an UWB device (DWM1000)
| an UWB device (DWM1000)
|-
| a pressure sensor (LPS25H)
| a pressure sensor (LPS25H)
|-
| a 3.3v low noise LDO regulator (MIC5209)
| a high precision IMU (MPU-9250)
|-
| a single-cell LIPO charger (MCP73831)
| a 3.3v low noise LDO regulator (MIC5209)
|-
|
| a single-cell LIPO charger (MCP73831)
|}

===Connectivity===

The system contains a number of potential ways to extract information. It is possible to connect to the '''anchors''' through a UART serial port, a virtual serial port on the USB port, or SWD via eg. openOCD (GDB). In the same way the '''tags''' can be reached through the UART port, a virtual serial port through the USB port, SWD or I2C. The next generation of the tags are supposed to SPI extracted from the uC as well for improved connectivity to eg. a robot.

===The Anchors===
[[File:Anchor layout.png|450px|thumb|right|Anchor layout]]
The anchor schematic can be seen at [[Media:Anchor_sch.jpg|Anchor schematic]] 

The anchors can be programmed through either the USB (DFU), or the SWD link that has been broken out to ''J3''. The SWD protocol is an alternative to the full [https://en.wikipedia.org/wiki/JTAG JTAG], that only used 2 data wires for programming and debugging.

====Known errors====
The anchor hardware is ''still'' error free, meaning that there is yet to be found errors in the newest electronic design.
The only thing on the list of changes to come in the next revision is a better power control, courtesy of a switch-mode regulator and the ability to utilize the ultra-low power sleep mode of the DW1000 devices. This means that the DWM1000 modules would have to be powered directly from the battery, through its own 3.3v ''always-on'' regulator, with ''EXTON'' connected to the shutdown of the switch-mode. This would allow the anchors to be powered on and off wirelessly, while still maintaining an ultra low power consumption in ''standby mode''.

===The Tags===
[[File:Tag_layout.png|450px|thumb|right|Tag layout]]

The tag schematic can be seen at [[Media:Tag_sch.jpg|Tag schematic]] 

The tags can only be programmed through the SWD link that has been broken out to the ''U6'' connector. The SWD protocol is an alternative to the full [https://en.wikipedia.org/wiki/JTAG JTAG], that only used 2 data wires for programming and debugging. 

The tags furthermore contain a high precision IMU (MPU9250), to allow for sensor fusion with the result of a better velocity estimate. For more info in the sensor fusion see [[3D Localization#Sensor fusion]]

====Known errors====
The tags contains at least two known hardware errors, one is the missing load sharing in the charger design (see the anchors for the proper design), and the other known issue, is the '''regout''' pin being connected to 3.3v instead of bypassed to ground through 100 nF capacitor. As with the anchors, the next hardware revision of the tags should implement a proper power scheme, through a switch-mode regulator. The next revision will probably loose the battery charger entirely, as the system should be powered through the device you want to track (robot), and as such does not need a battery.

==Software==
All the PCB design is done in a software suite called DipTrace, which can be downloaded for free at [http://diptrace.com/ www.diptrace.com]. The software is currently only available in a Windows and Mac OS X version, but runs perfectly through [https://en.wikipedia.org/wiki/Wine_(software) Wine]. DipTrace offers a free student license, allowing a larger design along with some extra features. This student license can be requested by writing an email to the contact address listed at their [http://diptrace.com/buy/academic/ academic] site.

Localization Hardware

2016-05-31T13:36:03Z

S123950: /* The Tags */

This page describes the hardware design of the [[3D localization]] system.

The anchors and tags are made up of some main components as described in the table below. The main difference is that the anchors have 180° of the antenna shielded in order to allow mounting on walls and ceilings without changing the antenna properties from reflections, other than that the tags contains a high precision IMU for sensor fusion in order to improve the velocity estimates.

{| class="wikitable" width="50%"
|+ Main hardware elements of anchors and tags
|-
! Anchors
! Tag
|-
| a cortex-m0 processor from ST (STM32f072)
| a cortex-m3 processor from ST (STM32f103)
|-
| an UWB device (DWM1000)
| an UWB device (DWM1000)
|-
| a pressure sensor (LPS25H)
| a pressure sensor (LPS25H)
|-
| a 3.3v low noise LDO regulator (MIC5209)
| a high precision IMU (MPU-9250)
|-
| a single-cell LIPO charger (MCP73831)
| a 3.3v low noise LDO regulator (MIC5209)
|-
|
| a single-cell LIPO charger (MCP73831)
|}

===Connectivity===

The system contains a number of potential ways to extract information. It is possible to connect to the '''anchors''' through a UART serial port, a virtual serial port on the USB port, or SWD via eg. openOCD (GDB). In the same way the '''tags''' can be reached through the UART port, a virtual serial port through the USB port, SWD or I2C. The next generation of the tags are supposed to SPI extracted from the uC as well for improved connectivity to eg. a robot.

===The Anchors===
[[File:Anchor layout.png|450px|thumb|right|Anchor layout]]
The anchor schematic can be seen at [[Media:Anchor_sch.jpg|Anchor schematic]] 

The anchors can be programmed through either the USB (DFU), or the SWD link that has been broken out to ''J3''. The SWD protocol is an alternative to the full [https://en.wikipedia.org/wiki/JTAG JTAG], that only used 2 data wires for programming and debugging.

====Known errors====
The anchor hardware is ''still'' error free, meaning that there is yet to be found errors in the newest electronic design.
The only thing on the list of changes to come in the next revision is a better power control, courtesy of a switch-mode regulator and the ability to utilize the ultra-low power sleep mode of the DW1000 devices. This means that the DWM1000 modules would have to be powered directly from the battery, through its own 3.3v ''always-on'' regulator, with ''EXTON'' connected to the shutdown of the switch-mode. This would allow the anchors to be powered on and off wirelessly, while still maintaining an ultra low power consumption in ''standby mode''.

===The Tags===
[[File:Tag_layout.png|450px|thumb|right|Tag layout]]

The tag schematic can be seen at [[Media:Tag_sch.jpg|Tag schematic]] 

The tags can only be programmed through the SWD link that has been broken out to the ''U6'' connector. The SWD protocol is an alternative to the full [https://en.wikipedia.org/wiki/JTAG JTAG], that only used 2 data wires for programming and debugging.

====Known errors====
The tags contains at least two known hardware errors, one is the missing load sharing in the charger design (see the anchors for the proper design), and the other known issue, is the '''regout''' pin being connected to 3.3v instead of bypassed to ground through 100 nF capacitor. As with the anchors, the next hardware revision of the tags should implement a proper power scheme, through a switch-mode regulator. The next revision will probably loose the battery charger entirely, as the system should be powered through the device you want to track (robot), and as such does not need a battery.

TODO: Add some more content here about the tags, mention ST-Link/V2 and IMU for sensor fusion

==Software==
All the PCB design is done in a software suite called DipTrace, which can be downloaded for free at [http://diptrace.com/ www.diptrace.com]. The software is currently only available in a Windows and Mac OS X version, but runs perfectly through [https://en.wikipedia.org/wiki/Wine_(software) Wine]. DipTrace offers a free student license, allowing a larger design along with some extra features. This student license can be requested by writing an email to the contact address listed at their [http://diptrace.com/buy/academic/ academic] site.