GEOPRIV C. Hoene
Internet Draft A. Krebs
Intended status: Informational C. Behle
M. Schmidt
Expires: April 2011 Universitaet Tuebingen
October 14, 2010
Bayesian Location Identifier
draft-hoene-geopriv-bli-00.txt
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other documents
at any time. It is inappropriate to use Internet-Drafts as
reference material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
This Internet-Draft will expire on April 14, 2011.
Copyright Notice
Copyright (c) 2010 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with
respect to this document.
Hoene et al. Expires April 14, 2011 [Page 1]
Internet-Draft Bayesian Location Identifier October 2010
Abstract
Location Generators cannot always provide exact measures of
particular locations. Instead, they estimate the location of
objects. More precisely, they use filters to aggregate noisy sensor
data and to calculate probability density distributions of estimated
positions. In location tracking applications, typically Kalman-type,
Gaussian-Sum, and Particle Filters are used.
We believe that it is reasonable to use the outputs of those filters
to describe a location estimate and its uncertainty, because they
are the natural result of location tracking algorithms. In addition,
the results of those filters can be feed into sensor fusion and
decision making engines easily.
Geometric representations such as polygons or ellipses might be
demanded by an application. The output of filters can be converted
to those application demanded shapes. However, these conversions
come at the loss of precision and are not well understood
scientifically. Thus, we think that transmitting filter results is a
solution that is easier to implement.
In this draft, we present a transmission format for PIDF-LO, which
is based on the output of Kalman-type, Gaussian-Sum, and Particle
Filters.
Table of Contents
1. Introduction...................................................3
2. Overview on Filters............................................3
2.1. Kalman Filters............................................4
2.2. Particle Filter...........................................4
2.3. Gaussian Sum Particle Filters.............................5
3. Coordinate System and Datum....................................5
4. Examples.......................................................5
4.1. Kalman Filter Results.....................................5
4.2. Particle Filter Results...................................6
4.3. Gaussian Sum Filter.......................................7
4.4. Well-know Reference Frame.................................7
4.5. Relative Datum............................................8
5. Security Considerations........................................9
6. IANA Considerations............................................9
7. Conclusions....................................................9
8. References.....................................................9
8.1. Informative References....................................9
Hoene Expires April 14, 2011 [Page 2]
Internet-Draft Bayesian Location Identifier October 2010
1. Introduction
The location of an object cannot be measured precisely always.
Especially, in an indoor environment numerous sources of measurement
errors lead to measurement results, which are uncertain in a high
degree. To represent this uncertainty, a previous draft [1] defines
how uncertainty and its associated datum and confidence is expressed
and interpreted. To simplify the representation, the draft limits
the description of uncertainty to a number of well defined shapes,
e.g. one point, a centroid, an arc-band centroid, or polygons.
However, state of the art multimodal location tracking algorithms do
not provide any location results of the above mentioned shapes.
Instead, they typically applied some sort of Kalman or Particle
Filters, which assume a Gaussian or an arbitrary error distribution.
Thus, in this draft we propose to transmit as location information
the results of Gaussian distributions or Particle Filters to present
uncertainty.
This has the following advantages:
1. Any kind of uncertainly can be transmitted. More precisely, any
form of probability distribution, which represents uncertainty,
can be represented.
2. A conversion from particles to shapes is not required, which
maintains precision and eases implementations.
3. Kalman and Particle filters are well understood statistical tools
based on research of control theory, signal processing, Monte-
Carlo simulations and Bayesian statistics. Numerous location
tracking algorithms have been developed that work with those
filters. Thus, the transmission format defined in this draft is
based on a profound scientific basis.
2. Overview on Filters
Location tracking is based on physical measurements, which estimate
time of flight, signal strength, angle of arrives, motions, objects
in images, and many other forms of sensor input. All these sensor
measurements are subjected to measurement noise. Because of that,
filters are used to estimate the real value of the measurement
despite the fact of measurement results that are subjected to noise.
Many filter types have been developed. However, in location tracking
typically only a few are applied. These include different types of
Kalman-Filters, filters that work with one or multiple Gaussian
Hoene Expires April 14, 2011 [Page 3]
Internet-Draft Bayesian Location Identifier October 2010
Normal distributions, and Particle Filters. These filters are
briefly described in the following.
2.1. Kalman Filters
A Kalman Filter uses a system model to estimate the probability of
changes. This data is combined with a model of measurement data and
control input, if any, to estimate the true value of the parameters
under study. It only allows linear relations between filter
variables and assumes Gaussian noise distributions. Despite that, it
is very robust in many applications.
The result of a Kalman filter is a posteriori state vector (for
example a location) and a posteriori estimated covariance. The state
is given by a vector $\hat{x}_{k|k}$ and the covariance by
$P_{k|k}$. Both estimates are given for the time index $k$ [2]. If
the vector has a dimension of $d$ (for example 3 for xyz), then the
covariance matrix has a size of d*d.
We suggest that, as PIDF-LO object, all these three variables shall
be transmitted to indicate a position estimate, its distribution,
and the time of measurement.
Also, this format should work well for non-linear filters such as
the Extended or Unscented Kalman Filter.
2.2. Particle Filter
Particle Filter, also called sequential Monte Carlo methods (SMC),
have the advantage that arbitrary distributions can be approximated
[3]. As such, they approximate Bayesian models, which consist of
probability distribution functions, which define the degree of
"believe" to which a particular value is true.
Particle filters approximate probability distribution function with
a number of particles. More particles are placed at positions that
are more likely. Each particle has Dirac shape.
The a posteriori state of a particle filter is approximated by $M$
particles called $x^{(M)}_i$, which are weighted with $w^{(m)}_i$.
The PIDF-LO transmission object should contain the particles, their
weights and again the time index k.
Hoene Expires April 14, 2011 [Page 4]
Internet-Draft Bayesian Location Identifier October 2010
2.3. Gaussian Sum Particle Filters
Here we assume that the probability distributions are described by
the sum of normal distributions [4]. As such, it can be seen as the
combination of two previously mentioned filtering approaches.
The a posteriori state of a Gaussian Sum Filter is approximated by
$M$ Gaussian distributions called $$\hat{x}^{(M)}_k$, which are
weighted with $w^{(m)}_k$ and have distributions described by
covariance matrices $P^{(M)}_{k|k}$.
Again, all those parameters shall be transmitted.
3. Coordinate System and Datum
Any location is relative to a frame of reference. The frame of
reference defines the position, orientation and other properties of
a coordinate system, in which an object is located. A number of
geodetic reference frames have been defined such as WGS84, ETRS89,
or ITRF2005. Typically, they define the reference point and the
orientation of the coordinate system.
In robotics, reference frames are used, too. They are referencing to
a zero point, have an orientation, and may be scaled, mirrored,
rotated. For example, a so called transformation matrix can be
applied to the location vector to transform coordinate systems.
Commonly in navigation, besides Carthesian also Polar coordinate
systems are used. In addition, a polar coordinate system has the
benefit that - for example - circular bands can be described easily
if the rotating angles have a high uncertainty or are not defined.
In summary, to describe the location of an object, the reference
frame has to be named or defined, and the type of coordinate system
must be given.
4. Examples
This section shows examples on how to transmit the location ID
described above.
4.1. Kalman Filter Results
Assuming, a Kalman filter estimates a position and assigns an
uncertainty to this estimate. Then
Hoene Expires April 14, 2011 [Page 5]
Internet-Draft Bayesian Location Identifier October 2010
-34.407242 150.882518 34 0.5
-34.500000 150.000000 34 0.25
-34.400000 151.000000 34 0.25
defines a point at [-34.407242, 150.882518, 34] with a weight of
0.5, a point [-34.5,150,34] with a weight of 0.25, and a point at [-
34.4,151,34] with a weight of 0.25.
Hoene Expires April 14, 2011 [Page 6]
Internet-Draft Bayesian Location Identifier October 2010
4.3. Gaussian Sum Filter
Next, we have a Gaussian Sum Filter with two Gaussian distributions.
Then
UTM zone=32U
EVRS2000
"Reference Point ID=0123456789"
1 0 0 0
0 0 -1 0
0 1 0 0
0 0 0 1
carthesian