Locating engine

A locating engine (sometimes referred as a positioning 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.

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 databases and spatio-temporal databases.

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 databases 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 RTLS 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 tracking 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.

Mapping

Mapping is well known to traditional navigation 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.

Traditional approaches

Locating has a long tradition in geodesy since C.F. Gauss'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.

Advanced approaches

Especially Torgerson, proposed the concept of multidimensional scaling (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 (MDS) 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

References to various approaches

There are a wide variety of vendors providing real time location services. A good list is included in "RTLS for Dummies" by Ajay Malik (Wiley 2009).

See also

• Real-time locating
• Real-time locating system
• Real-time locating standards
• Navigation

Literature

• IEEE Std 802.15.4 (publication available through [1])
• 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 Maliknl:RTLS