Locating engine
Encyclopedia
A locating engine is the computational engine behind real-time locating systems (RTLS
) and navigation
support system. A locating engine combines algorithms of geometry
or topography
with algorithms of filtering to calculate a best estimate for objects or people, and to do so in real-time. The locating engine is the implementation of the algorithms for determining the equations of coordinates from inverting matrices of distances.
Many different approaches can be used in creating a location engine, but all modern systems are based on multilateration
or triangulation
and least squares
.
Location estimation must be performed from or towards various reference points to calculate the unknown location as the unknown position inside a plane circle triangle (3 reference points in a 2D space with three distance circles) or inside a spherical tetrahedron (4 reference points in a 3D space with four spherical shell surfaces).
Even with a sufficient count of reference points, some ambiguity persists. The first reason is the passage of time during computation, and the corresponding motion of the target to be located. The below reasons also occur even in motionless scenarios:
Success with such geometric model is in fact hampered by multiple path errors, statistical errors and diverse metering inaccuracies. Such approaches fail in highly dynamic environments and may show severe jitter even with nodes at zero speed. Beyond this, the involving of more than the least required number of reference nodes (>3 for 3D and >4 four 4D) increases the complication. The interested user should not assume that such simple approaches would allow for the good performance or high precision with systems as e.g. with GPS in open air. Some higher level of sophistication is required to obtain sound results.
s and spatio-temporal databases
.
s with data sets containing instances affected by motion is subject of spatio-temporal database, which include both location and time as parameters.
or other locating hardware requires equivalent methodology to make appropriate use of obtained measures. This shall be comprised in an RTLS locating machine that keeps the user and applicator free of considerations about how to obtain best estimates for mobile positions.
Such locating machine e.g. for planar motion in buildings and on plane surfaces comprises at least of the following:
This list may be extended upon sound modeling concepts. Interested parties may believe, electrotechnically sound solutions alone do not cover this modeling requirement even by most skillful measuring methodology.
is as valuable as tracking of other objects. The stability of tracking may be improved by knowledge about motion
. Then new locations may be estimated more easily from earlier computed data and from latest acquisition.
and has been re-introduced to plotting of propagation diagrams. Such mapping basis may improve the guessing of received wireless power levels (RSSI
) and converting it to distance metrics. However, such mapping assumes a static setup as well as linearity of propagation. Under the normal conditions in indoor applications, this generally is a very poor approach, especially under conditions of motion.
The other mapping approach is the mapping based on confinements, especially the viable paths of motions and the existing limits with walls, racks and outlets. Such modeling is a real escape from secondary path responses, as all locations that are physically not possible may be easily excluded without postulates for linearity of propagation.
The more reasonable approach is the notion of obstacles which will interfere motion, i.e. where objects can physically not pass through. Disclosing terrain or floor surfaces and solid structures in maps is information well qualified to improve tracking and thus contribute to locating.
s work in 1821–1825. The concepts of triangulation
and multilateration
have been well elaborated since then. More modern approaches take the matrix calculus
into account. The basic concept of Gauss applied the concept of over-determination
for systems of quadratic equations, thus leading to the generalized approach of least squares
.
(first published in 1928 and finally renewed in 1958) for over-determined numerical problems with unknown dimensionality and heavy stochasticity or also biased variations. This approach may be applied to 3-dimensional locating in R3 under deterministic but noisy conditions as well. Detailed tutorial may be found in . Extension to the locating problem is found in several instances of patent literature, as e.g. in .
) is a crossbred from psychology mathematics. However, uncertainty about the model to represent correct dimensionality of the data sample is not the problem in terrestrial locating. The methods developed for MDS application serve well for easy implementation of locating functions. Hence applying MDS is a strong approach to perform the locality computing [www.cs.cmu.edu/~ftorre/papers/mswim09r-Cabero.pdf]. Currently reported approaches do not consider moving nodes with TOA distance metrics and special motion models, but anyhow the method is rather docile to prevent from faulty results.
The processing of available data does not compensate for the error sources without the traditional concepts:
RTLS
RTLS may refer to:* Real-time locating system - general techniques for asset and staff tracking using wireless hardware and real-time software* Ravenna Training and Logistics Site - an Ohio Army National Guard base....
) and navigation
Navigation
Navigation is the process of monitoring and controlling the movement of a craft or vehicle from one place to another. It is also the term of art used for the specialized knowledge used by navigators to perform navigation tasks...
support system. A locating engine combines algorithms of geometry
Geometry
Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....
or topography
Topography
Topography is the study of Earth's surface shape and features or those ofplanets, moons, and asteroids...
with algorithms of filtering to calculate a best estimate for objects or people, and to do so in real-time. The locating engine is the implementation of the algorithms for determining the equations of coordinates from inverting matrices of distances.
Many different approaches can be used in creating a location engine, but all modern systems are based on multilateration
Multilateration
Multilateration is a navigation technique based on the measurement of the difference in distance to two or more stations at known locations that broadcast signals at known times. Unlike measurements of absolute distance or angle, measuring the difference in distance results in an infinite number of...
or triangulation
Triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...
and least squares
Least squares
The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
.
Topology and topography
Location information is never obtained in a single step. A location may be described through relative positional data, absolute positional data or any intermediate information for obtaining such data. Eventual descriptions are topographical, mostly referring to a terrain map or a building plan. Locating requires more than topological descriptions, which for instance only include neighbourhoods and hop counts, as is the case of communications networks. The topological description is however a prerequisite for operating some types of locating engines in order to obtain a topographical determination afterward.Ambiguity and Accuracy
To obtain an appropriate result with locating, not only is precision required, but a set of data for processing is required in order to generate an unambiguous solution.Location estimation must be performed from or towards various reference points to calculate the unknown location as the unknown position inside a plane circle triangle (3 reference points in a 2D space with three distance circles) or inside a spherical tetrahedron (4 reference points in a 3D space with four spherical shell surfaces).
Even with a sufficient count of reference points, some ambiguity persists. The first reason is the passage of time during computation, and the corresponding motion of the target to be located. The below reasons also occur even in motionless scenarios:
- Accuracy
- Reproducibility
- Resolution
- Noise
Success with such geometric model is in fact hampered by multiple path errors, statistical errors and diverse metering inaccuracies. Such approaches fail in highly dynamic environments and may show severe jitter even with nodes at zero speed. Beyond this, the involving of more than the least required number of reference nodes (>3 for 3D and >4 four 4D) increases the complication. The interested user should not assume that such simple approaches would allow for the good performance or high precision with systems as e.g. with GPS in open air. Some higher level of sophistication is required to obtain sound results.
Databases and hosts
Generally locating engines work on data obtained from databases or from measurements and export results to spatial databaseSpatial Database
A spatial database is a database that is optimized to store and query data that is related to objects in space, including points, lines and polygons. While typical databases can understand various numeric and character types of data, additional functionality needs to be added for databases to...
s and spatio-temporal databases
Spatiotemporal database
A spatiotemporal database is a database that manages both space and time information. Common examples include:* Tracking of moving objects, which typically can occupy only a single position at a given time....
.
Data sets
Location data ages with motion, thus data sets for locations must include coordinates and a time of capture. This applies as well in asynchronous metering concepts. To perform locating properly, most systems apply sequences of computed locations as a track.Data representation with motion
Motion causes aging of spatial data on moving objects, resulting in a loss of accuracy with time. The crossbreed of spatial databaseSpatial Database
A spatial database is a database that is optimized to store and query data that is related to objects in space, including points, lines and polygons. While typical databases can understand various numeric and character types of data, additional functionality needs to be added for databases to...
s with data sets containing instances affected by motion is subject of spatio-temporal database, which include both location and time as parameters.
Standardization of spatial data sets
Current work for standardization of spatial data sets is bound to conventional spatial data bases and does yet not include parameters of motion. Hence, modeling the data for locating engines may refer to standardization for unambiguous data, but then will not refer to notions of motion, i.e. location and time.Mathematical modeling for locating
Applying RTLSRTLS
RTLS may refer to:* Real-time locating system - general techniques for asset and staff tracking using wireless hardware and real-time software* Ravenna Training and Logistics Site - an Ohio Army National Guard base....
or other locating hardware requires equivalent methodology to make appropriate use of obtained measures. This shall be comprised in an RTLS locating machine that keeps the user and applicator free of considerations about how to obtain best estimates for mobile positions.
Such locating machine e.g. for planar motion in buildings and on plane surfaces comprises at least of the following:
- Measurement computation to cope with the stochastic errors of metered distance values, thus reducing noise.
- Modeling the mesh of nodes and distances as a stable network of controlled topology and as a virtual surface.
- Conformal modeling matching the real operational surfaces, to serve location data for physically purposeful positions e.g. outside obstacles and driving or settled on a plane.
- Providing stable tracks according to inherited motion capabilities, i.e. not jumping aside nor forth and aback and keeping steady speed and acceleration.
This list may be extended upon sound modeling concepts. Interested parties may believe, electrotechnically sound solutions alone do not cover this modeling requirement even by most skillful measuring methodology.
Tracking
All past information about location may be included to tracks. Self trackingTracking
Tracking can refer to:*Tracking , separating children into different classes according to their academic ability*Tracking, in computer graphics, a vital part of match moving...
is as valuable as tracking of other objects. The stability of tracking may be improved by knowledge about motion
Motion (physics)
In physics, motion is a change in position of an object with respect to time. Change in action is the result of an unbalanced force. Motion is typically described in terms of velocity, acceleration, displacement and time . An object's velocity cannot change unless it is acted upon by a force, as...
. Then new locations may be estimated more easily from earlier computed data and from latest acquisition.
Mapping
Mapping is well known to traditional navigationNavigation
Navigation is the process of monitoring and controlling the movement of a craft or vehicle from one place to another. It is also the term of art used for the specialized knowledge used by navigators to perform navigation tasks...
and has been re-introduced to plotting of propagation diagrams. Such mapping basis may improve the guessing of received wireless power levels (RSSI
RSSI
In telecommunications, received signal strength indicator is a measurement of the power present in a received radio signal.RSSI is a generic radio receiver technology metric, which is usually invisible to the user of the device containing the receiver, but is directly known to users of wireless...
) and converting it to distance metrics. However, such mapping assumes a static setup as well as linearity of propagation. Under the normal conditions in indoor applications, this generally is a very poor approach, especially under conditions of motion.
The other mapping approach is the mapping based on confinements, especially the viable paths of motions and the existing limits with walls, racks and outlets. Such modeling is a real escape from secondary path responses, as all locations that are physically not possible may be easily excluded without postulates for linearity of propagation.
The more reasonable approach is the notion of obstacles which will interfere motion, i.e. where objects can physically not pass through. Disclosing terrain or floor surfaces and solid structures in maps is information well qualified to improve tracking and thus contribute to locating.
Traditional approaches
Locating has a long tradition in geodesy since C.F. Gauss'Carl Friedrich Gauss
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...
s work in 1821–1825. The concepts of triangulation
Triangulation
In trigonometry and geometry, triangulation is the process of determining the location of a point by measuring angles to it from known points at either end of a fixed baseline, rather than measuring distances to the point directly...
and multilateration
Multilateration
Multilateration is a navigation technique based on the measurement of the difference in distance to two or more stations at known locations that broadcast signals at known times. Unlike measurements of absolute distance or angle, measuring the difference in distance results in an infinite number of...
have been well elaborated since then. More modern approaches take the matrix calculus
Matrix (mathematics)
In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...
into account. The basic concept of Gauss applied the concept of over-determination
Overdetermined system
In mathematics, a system of linear equations is considered overdetermined if there are more equations than unknowns. The terminology can be described in terms of the concept of counting constraints. Each unknown can be seen as an available degree of freedom...
for systems of quadratic equations, thus leading to the generalized approach of least squares
Least squares
The method of least squares is a standard approach to the approximate solution of overdetermined systems, i.e., sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every...
.
Advanced approaches
Especially Torgerson, proposed the concept of multidimensional scalingMDS
MDS may stand for:Companies and organizations* MDS Inc., a global health and life sciences company* MDS America, a global telecommunications company* Media Design School , a media industry tertiary training institution...
(first published in 1928 and finally renewed in 1958) for over-determined numerical problems with unknown dimensionality and heavy stochasticity or also biased variations. This approach may be applied to 3-dimensional locating in R3 under deterministic but noisy conditions as well. Detailed tutorial may be found in . Extension to the locating problem is found in several instances of patent literature, as e.g. in .
Probabilistic approaches
The other escape beyond the deterministic models for determining coordinates is a probabilistic model. There the achieved mostly noise and error loaded measures contribute to a minimization problem for best fit of estimated coordinates for each set of distances. The result gains in precision with the count of measures. As with other approaches, the discrimination of sets under conditions of motion determines the quality of the result.Multidimensional scaling
Multidimensional scaling (MDSMDS
MDS may stand for:Companies and organizations* MDS Inc., a global health and life sciences company* MDS America, a global telecommunications company* Media Design School , a media industry tertiary training institution...
) is a crossbred from psychology mathematics. However, uncertainty about the model to represent correct dimensionality of the data sample is not the problem in terrestrial locating. The methods developed for MDS application serve well for easy implementation of locating functions. Hence applying MDS is a strong approach to perform the locality computing [www.cs.cmu.edu/~ftorre/papers/mswim09r-Cabero.pdf]. Currently reported approaches do not consider moving nodes with TOA distance metrics and special motion models, but anyhow the method is rather docile to prevent from faulty results.
The processing of available data does not compensate for the error sources without the traditional concepts:
- removing outlying data measurements first
- sampling and computing statistics for the remaining measurements
- predicting and correcting for motion tracks
- matching with context information
- taking into account the basing statistical model conditions
See also
- Real-time locating
- Real-time locating systemReal-time locating systemReal-time locating systems are a type of local positioning system that allow to track and identify the location of objects in real time. Using simple, inexpensive badges or tags attached to the objects, readers receive wireless signals from these tags to determine their locations...
- Real-time locating standards
- NavigationNavigationNavigation is the process of monitoring and controlling the movement of a craft or vehicle from one place to another. It is also the term of art used for the specialized knowledge used by navigators to perform navigation tasks...
- Unilateration
Literature
- IEEE Std 802.15.4 (publication available through http://www.ieee.org)
- IEEE Std 802.15.4a Annex D1 (serving a good comparison of R2/2D models)
- Multi-Dimensional scaling
- Implemented MDS software package manual
- Learning website on MDS methodology
- Communicative website on MDS methodology
- Wiley Book::'RTLS For Dummies' by Ajay Malik