Locating engine

A locating engine performs the computation of locations of objects and persons based on methods of multilateration or triangulation. This applies mainly with real-time locating systems (RTLS) and navigation support systems.

Some suppliers describe the approach as a positioning engine, however no position is affected, but just a location determined.

Features of a generic locating engine

In terms of informatics, the process of locating based on distinct results from distance metering is performed in a locating engine. The prerequisite is the metering. Both processes may be implemented independently and thus tailored independently to various requirements of application.

Such locating engine combines algorithms of geometry or topography with algorithms of filtering. The key issue of qualifying such locating engines is with the problem of sets of metered distances never matching in one coordinate, but in areas encircled by circles (TOA) or hyperbolas (TDOA). The task for the locating engine is to calculate promptly (in real time) for any real location a best estimate for the coordinates of the real location.

The method of locating with an RTLS in any systems layout is always a special method out of the family of methods for dead reckoning. The location of any bearer of an RTLS node may be located with a typical accuracy. This varies with the RTLS deployed and with degradation in the actual operational situation. To make clear, that Real Time Locating with an RTLS is an operational means to achieve some information about a momentary location with only short-term validity, the term "guess" is used. RTLS is always a best guess to support an operation. At no extent it may be used to interrogate map information with topographic or geodesic accuracy.

The tendency to apply for patent rights on applied mathematics where time is a parameter leads to closing the books on algorithms. The quantity of granted patents on special breeds of locating engines will rise. Currently few offers are on the market for either open source, closed source or closed applications including locating engines. The composition of such engine from scratch is not necessary. Mathematical libraries offer a large variety of building blocks. However, the quality of any solution is ruled by experience with the error models of metering and the cohesion control with networking.

The interested party must test the offerings to find the best fit for supporting operations. There is no general approach to success.

Unambiguousness

To obtain an appropriate result with locating, not only precision is required, but primarily the unambiguousness of data for processing is required.

That is quite simple to comprehend:

• On a trajectory, it is sufficient to know two way points to determine a third location. Any leg defined with two known way points gives a unique set of coordinates for any third way point on the very same trajectory, disregarding the orientation of the trajectory on a surface or in a space. However, the trajectory must be well defined. In the case of a straight line, the two way points with coordinates and a Euclidean norm for the trajectory fulfil this condition.
• On a surface, it is sufficient to know three way points to determine a fourth location. Any triangle defined with three known way points gives a unique set of coordinates for any fourth way point on the very same surface, spanned with the triangle and disregarding the orientation of the triangle in a space and the planarity of the surface. However, the surface must be well defined. In the case of a plane, the three way points with coordinates and a Euclidean norm for the plane fulfil this condition.
• In a space, it is sufficient to know four waypoints to determine a fifth location. Any tetrahedron defined with four known waypoints gives a unique set of coordinates for any fifth waypoint in the very same space, spanned with the tetrahedron and disregarding the orientation of the tetrahedron in space and the orthogonality of the space. However, the space must be well defined. In the case of a plane, the four waypoints with coordinates and a Euclidean norm for the space fulfil this condition.

To obtain an appropriate result with locating, not only precision is required, but primarily the of sufficient complete data for processing unambiguous results is required.

In any 3D Euclidean system of coordinates, the Euclidean distance is the metrics to determine the position of objects in an interrelation. In a simplified 2D system of coordinates, the Euclidean distance simplifies to the Pythagorean distance. The inversion of the distance calculus (quadratic equation with three resp. two variables) delivers the coordinates of a current location. This requires proper distances for at least 4 known locations (in 3D) or at least 3 known locations (in 2D). Any lesser reference point count delivers ambiguous solutions.

Then, fulfilling the condition for unambiguousness, metering shall 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 ambiguousness resides. The first reason is the time consumption for measurements and the motion of the target to be located. The other insisting reasons are pertaining even motionless scenarios. The reasons are the key problem of metering:

• Accuracy,
• Reproduceability and
• Resolution
• Noise

Thus the demand for highest precision reprehends the requester: An increase in precision does generally not solve the problem. Finally noise will be kept as the residing challenge. Generally mathematics and physics provide the escape at reasonable cost, but not with increase in accuracy only. That may be observed with the geometric solutions in locating engines. The center of gravity approach in 2D and 3D concepts leads to poor results.

Data sets

Location data ages with motion. Thus a data set 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. To align these data sets, date and time comply with the needs.

To serve communication between nodes, time accompanies location data. To ease this communication, data is conveyed in containers and wrappers. Respective standardization is common for the communicating of maritime coordinates as well as satellite data. However, communication for other terrestrial usage is normally defined with proprietary methods. Hence, RTLS comply with standardization of ranging, but not with any standardization of computed data.

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, electro technically sound solutions alone do not cover this modeling requirement even by most skillful measuring methodology.

Geometric models

Basing concept of the geometric approaches is determining the area of the own location with plane circles or spherical surfaces. These 2D-circles or 3D-spherical surfaces around the transmitter position describe the range with the measured distance from any metering node. Hence several distance circles (at least 3) or spherical surfaces (at least 4) around the corresponding transmitters define a planar polygon or a multihedron and the own real location is assumed lying in the center of gravity of this polygon or multihedron.

To encircle any area or volume greater zero, tolerances are added to the measured distances for computing the location. Many of the RTLS systems in market use such a simple 2D- or 3D- geometric approach for modeling the location of metering nodes. The concept postulates that the circles describe planes or surfaces that would include area or volume greater zero or just tangle in one position. However, the easiest understanding with such didactically skilled models coincides with a very bad performance considering stochastic and systematic errors.

Success with such model is in fact hampered by multiple path errors, statistical errors and 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.

Analytical model

Basing concept of approaches with higher abstraction is a distance matrix of all pairs of nodes that performed cooperative distance metering. Some of the elements of this matrix may remain empty or distances are not metered simultaneously. The approach serves complex error models and will deliver appropriate estimates for real location. In case the inverted matrix exists, the model makes use of a priori knowledge about known distances to and coordinates of anchor nodes and the time series of error converges to sufficient low values.

The most generic approach is that of MDS, multi-dimensional scaling in Euclidean spaces.

Differential model

The other model based approach to motion detection with RTLS is the computing of differentials of the position information.

Instantiated models

The easy approach however in modeling is just recording and plotting constant field characteristics with the operational equipment for locating in the operational ambience. Such mapping of propagation characteristics requires the following for confinements as rooms or rack alleys:

• uptaking mapping instances per confinement
• precise maps valid for the existing equipping in the confinement
• no change to the local furnishing in the confinement
• few interference of moving objects other but those to locate

Then the model to support locating exists in an instance for each confinement. Such approach does not work in open air, however, there normally is not much to plot. Additionally, with such vast preparatory infrastructural work, what remains to earn the attribute "real time"? Hence this concept works in a well known environment and somewhat low grade equipped buildings. When equipment is not highly electrified, motion of any objects remains at low speed, population is sparse and whatever challenge is absent, then such approach might suffice. Whenever changes in the vicinity generates changes to the plot, there must be either an adaptation of the plot or some adaptivity in the system. Some products are rather successful based on this concept.

Plain RFID Solutions

• RFID UHF solutions details not disclosed

RSSI Solutions

• Ekahau approach
• Ekahau / Parco Merged Media approach
• Aero Scout approach
• WiFi Mesh Network
• WiFi Sniffer Solution

RFID Beacon Solutions

• beacon solution details not disclosed
• RF Code 433 MHz beacon solution

TOA / TDOA solutions

• Time Domain / Aero Scout approach
• Ubisense Approach
• Zebra WhereNet Approach

See also

• RTLS
• Real-time locating standards
• Navigation

Literature

• Multi-Dimensional scaling
• Implemented MDS software package manual
• Learning website on MDS methodology
• Communicative website on MDS methodology