Subscribe Now Subscribe Today
Review Article

A Review on Positioning Techniques and Technologies: A Novel AI Approach

O. Motlagh, S.H. Tang, N. Ismail and A.R. Ramli
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail

There are variety of positioning techniques applied to tracking of mobile objects such as mobile robots, handheld devices carried by human subject, etc. With the advent of new technologies, new strategies have emerged from combination of algorithms and those technical capabilities. This study is dedicated to a review of past and current approaches to positioning, including their advantages and shortcomings. More focus is given on trilateral radiolocation especially for indoor human motion tracking. A solution is sought to resolve the problem of algorithm failure with applicability to all areas of positioning and tracking including trilateration when less than three reference points are available.

Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

  How to cite this article:

O. Motlagh, S.H. Tang, N. Ismail and A.R. Ramli, 2009. A Review on Positioning Techniques and Technologies: A Novel AI Approach. Journal of Applied Sciences, 9: 1601-1614.

DOI: 10.3923/jas.2009.1601.1614



Determining location is a science in itself and is often associated with the general topic area of navigation. While, tracking of a series of locations i.e., entire path estimation, is a challenging task in navigation and surveillance (Fuentes and Velastin, 2006), still the main challenge is determining individual locations or motion productions generated by traveling objects. Navigational techniques and technologies have changed dramatically over time from celestial navigation tools (Pappalardi et al., 2001) to global positioning system and from dead reckoning (Randell et al., 2005) and triangulation (Hartley and Sturm, 1997), to radiolocation (Antolovic and Wallace, 2007; Hall, 2004). Besides these, there are variety of global models such as fingerprinting i.e., location estimation by comparing some observations at the current location with observations in a database. As the oldest known method, celestial navigation is the art and science of navigating by the stars, sun, moon and planets. However, today with the rise of radio and electronic means of finding location the knowledge of celestial navigation has experienced a precipitous decline.

Dead reckoning (DR) is a simple and primitive location technique that makes use of the initial or previously determined position of the mobile device, as well as known speed, elapsed time, acceleration and the direction of motion. A simple concept of this algorithm is mathematically expressed by Eq. 1, where, D0 to Dn-1 represent a series of displacement vectors (d0, θ0) to (dn-1n-1) along the path and until production Pn:

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

The first shortcoming of DR is about directional and orientational errors which affect the anticipation of production Pn. Even in more recent methods of this type where these errors are limited to small amounts (Golfarelli et al., 2001; Yamauchi, 1996), still due to error accumulation, expected results tremendously deviate from the actual productions. Another shortcoming of DR method is that this method is highly dependant on self-localization and orientational knowledge to be supplied from the traveler itself. Usually obtaining direction and speed information requires compass and speedometer facilities at the mobile terminal MT as well as frequent supply of such data to the reference terminals (Gaunet and Briffault, 2005). In most of applications these information are not available at the MT and therefore this technique is not a complete tracking method per se.

An alternative to enhance DR strategy is to use it in combination with other techniques such as global positioning system (GPS). Other methods such as (Park et al., 1996) applied DR mostly by means of noise elimination methods such as Kalman filtering (Grewal and Andrews, 1993) etc. In these kinds of methods, usually a positioning approach such as triangulation or trilateration is used to determine a series of locations while DR is used to estimate the overall paths.

Triangulation is among oldest but yet in use methods in location estimation. Traditionally 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. The point can then be fixed as the third point of a triangle with one known side and two known angles. Figure 1 depicts this concept on an x-y plane, while location calculation is expressed by Eq. 2 and 3.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 1: The concept of triangulation on x-y plane

Once the distance d between the mobile terminal (MT) and the fixed baseline is measured, the MT coordinates can be defined accordingly. Triangulation is a popular method especially when reference terminals are equipped with directional means of communication i.e., unidirectional antenna or beacons of any type. Triangulation positioning and tracking systems are easy to develop using many technologies such as infrared IR audible signage (Crandall et al., 2001), sonar transceivers (Laurent and Christian, 2007) and directional electromagnetic antennas (Malhotra et al., 2005). The only difficulty with triangulation is with omnidirectional kind of communication between MT and reference terminals. This includes almost all modern wireless technologies such as WiFi and Bluetooth.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

The trilateration technique: Omnidirectional communication is advantageous in positioning since it does not require a precise alignment between a reference station and the MT to be located. A reference station with omnidirectional type of receiver can detect the MTs in range at any relative angle. Therefore, as an alternative to triangulation, trilateration (Thomas and Ros, 2005) method was evolved which had the advantage of directional independency compared to triangulation. Trilateration is a method of determining the relative positions of objects using the geometry of triangles in a similar fashion as triangulation. But, unlike triangulation which uses angle measurements together with at least one known distance to calculate the subject’s location, trilateration uses the known locations of two or more reference points and the measured distance between the subject and each reference point (Thapa and Case, 2003; Ciurana et al., 2007a).

In 2D trilateration, the position of an MT can be accurately and uniquely determined by measuring distances from at least three reference points (Thomas and Ros, 2005; Thapa and Case, 2003).

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 2: Trilateration technique on x-y plane

However, other systems with only two reference points (Ciurana et al., 2007a) are also able to determine two locations from which one is the actual location of an MT. The ambiguity of having two probable locations for one MT is resolved by using advanced tracking strategies such as Markov localization (Thrun, 2000) and Kalman filtering (Grewal and Andrews, 1993; Ciurana et al., 2007a, b) where probabilistic methods have been employed.

Figure 2 shows the concept of trilateration on an x-y plane. Considering the two points of R1 and R2 as the two available reference points, the x coordinate of the mobile terminal MT can be obtained from Eq. 4-6. However, the ambiguity in y coordinate can be resolved by referring to the third reference point from which a unique y coordinate can be obtained Eq. 7.

Trilateration technique is advantageous in that it does not require any supply of knowledge e.g., direction, speed, acceleration, neither from the MT as needed in dead reckoning, nor at the base stations such as in triangulation. The system works independently from the mobile terminal to be located as long as it is within the range of detection at any angle relative to the stations. This particularly allows for omnidirectional kind of signal propagation and therefore a wide range of applications in positioning and tracking.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Positioning technologies: While different algorithms have been evolved for positioning and tracking, with the advent of new technologies, new strategies have emerged from combination of algorithms and those technical capabilities. Modern approaches to navigation systems are usually based on radiolocation techniques. Radiolocation (Antolovic and Wallace, 2007; Hall, 2004) is the process of finding locations through the use of radio waves. Radar and other electromagnetic transceivers e.g., radios, radio frequency identification devices (RFID)s, wireless networks (Ciurana et al., 2007; Mason et al., 2007), etc., are capable of finding the location of a mobile device by measuring various parameters of the electromagnetic signal traveling between the mobile device and a set of fixed base stations.

There are various approaches to radiolocation with respect to measurable parameters at different situations. Angle of arrival technique (AOA) (Niculescu and Nath, 2003) computes the angle of arrival of the signals from the mobile device to more than one base station making use of directional antennas. Other methods such as time of arrival (TOA) (Ciurana et al., 2007a, b), received signal strength indication (RSSI) (Grossmann et al., 2007), signal to noise ration SNR and link quality (LQ), are suitable for distance measurement and therefore can be employed for trilateration algorithm.

TOA method is based on estimating the time of arrival of a signal transmitted by a mobile device and received at base stations or vice versa. While the applied wave velocity and the time of arrival are known, the distance between the mobile terminal MT and the station can be calculated. In RSSI method, however, there is a nonlinear relationship between the signal strength and the distance between the two sender-receiver terminals. The received signal power decreases logarithmically with distance. This relationship exists for both outdoor and indoor conditions. It can be represented by Eq. 8 where, P(d) is the signal strength at a distance d and P(d0) is the signal strength at the reference terminal. The factor γ represents the path loss exponent and is affected by the external factors like multi-path fading, absorption, air temperature and etc.

P(d) = P(d0)-10γ log (d/d0)

Acoustic and light transceivers have been used in other categories of positioning devices i.e., sonar systems such as bat-like (Laurent and Christian, 2007) and infrared (IR) (Crandall et al., 2001). However sound and light signals are less capable than electromagnetic waves due to their directional kind of propagation, while electromagnetic waves allow for both types of directional and omnidirectional antenna design. Although directional propagation such as IR is helpful in some positioning techniques e.g., triangulation, however, usually light and sound devices are more suitable for beaconing applications (Crandall et al., 2001) and not for positioning. In addition, there are major disadvantages such as intervention and noise in light and sound and obstacles blocking the signal sources.

From indoor and outdoor perspective, positioning technologies range widely with respect to the nature of signal propagation and coverage. Global positioning systems (GPS), although very popular and robust but still are limited to outdoor use due to the so called canyon effect in indoor and surrounded areas (Borriello et al., 2005). For indoor applications, electromagnetic systems e.g., wireless networks are the most popular. Up to this date, the range of detection in most wireless networks e.g., WLAN have reached as far as covering the whole space of a typical house and even more (usually up to 100 meters). Higher precision can be obtained using Bluetooth technology and RFIDs. However, RFIDs are costly and usually allow for very short detection range of about few decimeters. In contrast, Bluetooth is widely available, low cost and easy to implement and use. It provides omnidirectional medium of communication so that connectivity between user and fix station is available at any relative direction and with more precision from positioning perspective (Lindström, 2008).

Human tracking using trilateral radiolocation: Another issue to be considered in a positioning or navigation systems is the nature of the traveler itself. In some applications the mobile terminal is a mobile robot on a mapping or exploration mission. While in many others the traveler is an animal to be tracked, or a vehicle to be located in town. There are many applications in surveillance and security as well. However a substantial amount of research has been dedicated to situations where the traveler is a blind human that must be located and possibly guided in particular. A comprehensive review on available wireless technologies for elderly and disabled is given in (Lindström, 2008). Other works focused on assistive navigation systems for guiding the blinds in unknown environments (Gaunet and Briffault, 2005; Crandall et al., 2001; Laurent and Christian, 2007; Hub et al., 2004; Na, 2006) using different technologies and navigation algorithms.

Figure 3 shows a blind traveler to be located and guided through a wireless communication system such as Bluetooth. Here, Bluetooth contour circles are employed for mathematical formulation of trilateration positioning. At any time the user is able to request for his location as well as navigational guidance for wayfinding by sending a request signal from his handheld Bluetooth device.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 3: A positioning-navigation system for the blind

The RSSI of the signals sent by the user are received at each of the three fixed stations or APs. Accordingly, the radial distances from each of the stations to the user can be estimated Eq. 8 for trilateration positioning.

Unlike sonar and light systems such as IR, the system of Fig. 1 does not require any alignment between the user and the fixed stations. While in IR systems for example, before any communication, a user has to search for the signal sources in the first place. This is also regarded as a disadvantage of RFID devices since blind users have to search for RFID tags due to their short range of detection. And finally, there is difficulty and stigma for users to carry any extra transceiver device for communication. This problem is also resolved in new radiolocation technologies especially WLAN and Bluetooth systems by communicating with users through their own handheld devices such as PDA or mobile phone with IEEE 802.11 adaptability (Grossmann et al., 2007).

IEEE 802.11 radiolocation for human tracking: There are variety of positioning techniques which have been applied to tracking and navigation of mobile terminals e.g., mobile robots, handheld devices carried by human, etc. This particularly includes trilateration positioning based of radiolocation for radial distance estimation. With the advent of new technologies, new strategies have emerged from combination of algorithms and those technical capabilities. However, for indoor tracking of blind users, still radiolocation i.e., electromagnetic wireless technologies such as WLAN and Bluetooth, are the most useful among all available technologies. This is due to the following unique features offered in wireless facilities based on IEEE 802.11 technology (Kotanen et al., 2003; Antolovic and Wallace, 2007) with positioning accuracy of less than 1 meter (Ciurana et al., 2007a):

Availability: Today, wireless networks are commonly in use and variety of personal devices e.g., mobile phone, PDA, are already capable of wireless communication
Functionality: Wireless devices are usually designed for multi-functional usage. For example a blind user does not have to carry any extra device for navigation purposes as long as they already use a simple Bluetooth cell phone
Adaptability: New wireless technologies such as Bluetooth allow for automatic configuration and connection for easier use especially for the disabled and the blinds
Privacy: A wireless network is simply capable of security configuration. The advent of frequency hopping spread spectrum FHSS in Bluetooth is an intervention free and secure technique for connectivity within all members of a Piconet including the mobile terminal and the fixed stations.
Communication: And finally, wireless networks allow for communication between user carrying the mobile terminal and the fixed station operators e.g., an interactive programme for supplying navigational information to its user

Trilateral radiolocation is an established approach to indoor position tracking with a wide range of applications. However, there are still some problems in positioning with wireless networks in actual implementations. Given a typical deployment of communication networks inside buildings, in many cases the MT is likely to be in range of fewer than three APs when a positioning request is received (Ciurana et al., 2007b). This is due to the limited reliable range of coverage in all available technologies e.g., WiFi and Bluetooth. In addition there are situations occur that even when three APs are in range, still one or more Aps are purposely discarded due to unreliable and uncertain distance measurement. Of these situations, the negative effect of multiple paths in indoor radio channels and undetectable direct path (UDP) are more common wherein the path is considered undetectable due to severe attenuation of straight-line propagation (Mailaender, 2008).

Problem of positioning system failure: As exemplified in the previous parts, all of the positioning algorithms including trilateration are vulnerable to system failure which results in losing track of the mobile terminal (MT). Therefore, a solution must be sought that also allows the MT position to be obtained when less than three APs (in trilateration) are involved in the process of calculating a position. It must be noted that trilateral positioning with two references is still possible as long as there are two unique points available from which one accounts for the actual location of the MT.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 4:
(a) Unique location estimation using three fixed points (trilateration), (b) Location ambiguity imposed due to lack of positioning information, (c) No unique point is estimated as the MT’s actual location

Therefore, the main problem in radiolocation based on trilateration arises when two out of the three required reference points (APs) are not available and the location of a mobile terminal MT has to be estimated by using only one available reference point.

The significance of resolving this problem is that there is absolutely no mathematical solution to the problem due to the location ambiguity. Disconnection of the MT from two out of the three reference points causes a lack of positioning information which results in location ambiguity. In other words, the MT location is estimated to be around a circle (Fig. 4c) instead of one or two unique points as in trilateration with three or two references, respectively (Fig. 4a, b). Also due to the system inability for location estimation, there will be no means of tracking of the MT. However, based on capabilities of artificial intelligence AI and heuristic approaches, there is a solution to resolve the stated problem with respect to the nature and wayfinding strategies of the MTs e.g., moving objects or human subjects.

It is aimed to design a positioning algorithm that takes advantage of the past MT trajectory information to compensate for the missing information during MT disconnection from one or even two reference points in trilateral radiolocation. This is accomplished by applying a novel AI algorithm for learning and retrieving the motion behaviors as well as dynamical characteristics of the MT. However, still there are assumptions and limitations to be explained in future contributions.

Figure 5 shows the concept of the AI model to be designed and tested. During the time when the positioning system is working properly, the AI model is being trained to learn various behaviors of the mobile terminal MT (Fig. 5a).

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 5:
(a) The AI model is being trained by the positioning system, (b) During system disconnection the trained AI model is used for estimating motion productions

This includes behaviors if the MT is a human subject and is all about learning kinematics if the MT is a moving object. Once the system breakdown occurs, the trained AI model starts to estimate the MT’s consecutive motion productions (Fig. 5b).

The ai model of path estimation: The research problem elaborated that wireless positioning systems might fail in tracking of the mobile terminal (MT) due to disconnection of the MT from the access points (AP)s at times and from time to time. In trilateral radiolocation (Kotanen et al., 2003; Niculescu and Nath, 2003; Hall, 2004; Thomas and Ros, 2005; Grossmann et al., 2007; Ciurana et al., 2007a, b; Antolovic and Wallace, 2007), if the disconnection is only from one of the three required APs, there will be still two unique points available from which one accounts for the actual location of the MT as discussed (Ciurana et al., 2007a, b). But when two or three APs get disconnected, the MT location will be totally ambiguous and no mathematical solution can be applied for location estimation.

During the period of disconnection addressed as positioning system failure, trajectories made by the MT are no more detectable and the only solution is to resort to path prediction techniques. Dead Reckoning (DR) is suggested for motion prediction when the MT is merely a moving object with certain kinematical characteristics (Randell et al., 2005). But when the motion productions are made by an intelligent traveler i.e., MT being carried by human, pure DR methods fail since they are not capable of modeling the intelligent features of the motion.

An alternative is to use expert models of human motion. Experts took the challenge of human motion modeling. Some studies focused on the blinds’ wayfinding strategies and discovered a number of dominant behavioral factors involved in wayfinding without vision (Millar, 1994; Thinus-Blanc and Guanet, 1997; Kitchin et al., 1997; Ungar, 2000). Using such models, the future trajectories of individual human subjects are predictable to some extent but still are not so reliable due to tremendous amount of variability in biological systems.

Another alternative to human motion prediction is by using statistical motion patterns obtained from empirical observations with the same type of intelligent travelers and in the same environment (Jain et al., 1999; Vasquez and Fraichard, 2004). However, such experiments are not always possible and also do not guarantee perfect results since they highly depend on the amount of experimental work and variety of the motion patterns obtained empirically.

Finally the last solution is to make use of the capabilities of artificial intelligence (AI) for learning critical characteristics of human path planning and accordingly using the knowledge for prediction of their future trajectories from observation of the partial trajectories. Much of the work in this method is about development of a new AI algorithm to fulfill this objective. The research started from a novel idea about creation of a complete model of human motion estimation. It was hypothesized that there are two types of factors intervening each single motion production (a step, a jump, etc.) namely kinematical and behavioral. Kinematical factors are restricted to the actual limits of the human body which is discussed in many interesting areas of science e.g., kinesiology and anatomy, while behavioral factors are engaged with other bodies of sciences namely decision modeling and Artificial Intelligence (AI).

The proposed idea was further investigated by studying behaviors of the blind human. The two types of factors are obvious in wayfinding without vision. Blind motion has simpler features compared to sighted motion in terms of both kinematics and the behaviors. For example, the blind gross skills in locomotor space usually limits itself to only one type that is the walking skill, while sighted motion might involved running and so on. In terms of the behaviors, due to availability of the external frames of the space under any circumstances sighted motion is based on external referencing or map-like cognition. In contrast, blind motion behaviors are easier to discover since they are based on egocentric referencing or route-like cognition.

The research therefore started on the bases of this hypothesis and entailed with development of a new AI model for learning motion productions from both kinematical and behavioral factors simultaneously. A novel combination of established methods was proposed for creation of the AI algorithm. The dead reckoning (DR) technique was modified for modeling of the kinematical factors. And an expert model of blind path prediction (if-then expert assertions) was formed up on the basis of all reliable conclusions from the previous experts (Hill et al., 1993; Thinus-Blanc and Guanet, 1997).

The challenge of system coherency was resolved by applying causal inference mechanism of the fuzzy cognitive map (FCM) (Kosko, 1996; Khan and Quaddus, 2004; Stylios et al., 2008) in which the DR factors would be the nodes (factor concepts and decision concepts) while expert if-then assertions would be the edges (causal relationships) of the FCM graph. FCM provided the possibility of inclusion of the both sources of knowledge concurrently i.e., kinematical factors using DR-defined concept weights and behavioral factors using expert-defined event weights. FCM was used as a decision support system (DSS) for generating decision productions which would emulate motion productions of the subject or the MT.

Up to this stage, the FCM was already capable of anticipating future motion productions as shown in the results (FCM Simulator 2009). However, the expert-defined event weights were fixed and the system yet was not able to learn about trajectories being made by each individual subject. Among many techniques for FCM training, the genetic algorithm (GA) was chosen for optimization of the event weights instead of the fixed expert-defined ones.

Therefore, the FCM was made to be updated to learn the MT’s motion behaviors throughout the path i.e., due to step by step optimization of the event weights. The AI-trained FCM performed as an AI-DSS model of human motion estimation with capability of working in two modes namely 1) learning i.e., when actual trajectories are available from positioning samples and 2) performing that is used for path prediction during positioning system failure.

Figure 6 simply shows the performance of the AI-DSS model at learning and performing modes. In Fig. 6a and b, the process of learning the motion kinematics and the motion behaviors of the MT is shown when it makes its latest motion production (P4). From DR track of the path i.e., the displacement vectors Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach the FCM’s concepts weights (node values) are set at location L(t-1). The weights of the FCM’s events (edge values) are to be optimized.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 6:
(a) Path database is used for estimation of an available segment (P4), (b) Best estimation trials (decisions) and the segment’s displacement vector (kinematical behavior) are stored in the database, (c) From known DR behavior until L(t) and known decision behavior from the similar segment (P3), Production P5 is anticipated for moving to L(t+1)

For this, there are two possible approaches. First is to generate a random initial population of N chromosomes each of which containing a set of event weights. The second approach that is more efficient is to generate that initial population (the N chromosomes) from the M2 elite parents that have been previously recorded in the most similar path segment in terms of DR characteristics (P2). No matter how the initial population is generated, still each chromosome (set of event weights) must be assigned to the FCM events. Therefore, there are N trials of FCM runs with the same concepts weights but N different sets of event weights.

Upon N times running of the FCM, N decision productions will be generated that virtually lead the MT to N different locations (N motion productions). Having the actual location of the MT available at the present time i.e., L(t), each of the N motion trials can be evaluated for fitness. Only those trials within a certain range of accuracy will be selected as elite trials. Accordingly, the corresponding chromosomes (M4 chromosomes which caused the elite production trials) are selected to be recorded as elite motion productions for moving from L(t-1) to L(t).

Each of these chromosomes in fact accounts for the wayfinding behaviors of the MT during this specific segment of the path [L(t-1), L(t)] which is already learnt. On the other hand, from the actual L(t-1) and L(t), the displacement vector Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach, is measurable which constitutes for main kinematical behaviors (displacement and heading of walking locomotion). At this point, it is said that the AI-DSS model has learnt how production P4 has been made by the MT (Fig. 6b).

Now it is supposed that a wireless disconnection occurs between the MT and the APs right after the last location sample (L(t)) received. The future trajectory of the MT has to be estimated. In this research, path prediction is limited to 10 productions which will be reconstructed on obstacle free floor with the rate of one production per second. Figure 6c depicts the process of path estimation for the first motion production during the disconnection period (P5).

In order to anticipate P5, first its preceding segment (P4) should be compared against all segments previously memorized except P4 itself. The most similar segment with P4 is P2 due to similar change in heading angle that is the key factor in DR similarity. Then, the segment right after P2 that is P3 is selected to be used for anticipation of P5 by setting the FCM event weights. The M3 elites related to production P3 will be used to set the FCM event weights for M3 trials for anticipation of P5.

The FCM concept weights are set in the same fashion as in the learning stage of the algorithm. By aggregation of the DR characteristics of the entire route the changes in the heading angle (θ5) and the length of displacement (d5) are computed from which the weights of the FCM concepts can be set. Another alternative for faster runtime is to ignore the entire route and just include the kinematics (DR) characteristics of the last segment (P4). The FCM is run in either way for generation of M3 trials of P5. According to this algorithm, both kinematical and behavioral characteristics of the MT which had been learnt earlier are now used to anticipate its future trajectory.

As depicted in Fig. 6c, for an example of M3 = 4 there are 4 trials of motion production P5 pointing towards 4 possible locations of the MT in future (L(t+1)). The obtained bunch of possible productions must be evaluated for feasibility using several techniques. One means of evaluation is by measuring the kinetic traits of the move. For example the length of the motion production (displacement) must be within the normal range of human walking within 1 sec. As for the turn angle (changes in the heading direction) there is no limit since even a full return (180° of change) simply could have been made in 1 sec of time. Another measure can be from using the global map of the space including location of the walls, obstacle, etc. which is not applicable in this research where the scope is limited to obstacle free floors.

Statistical methods can be used as the best alternative for comparing the estimated locations against a number motion patterns obtained from empirical works with the same kind of subjects and on the same floor. Therefore, a statistical case based reasoning technique (Stylios et al., 2008) was integrated into the FCM in the performing mode of the algorithm.

Probability density function (PDF) was used for evaluation of the likelihood between anticipated productions and those stored in the data base (Vasquez and Fraichard, 2004). Finally, the last cue for evaluation of the production trials is from any remaining positioning information e.g., when one AP is still in connection with the MT. A combination of these evaluations must result in selection of one trial to be stored in the path data base in form of a displacement vector Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach. The vector components are of course the absolute displacement from L(t) to L(t+1) and the changes in the heading direction of motion relative to that of the previous production.

The problem of positioning system failure in radiolocation based on trilateration (Kotanen et al., 2003; Thomas and Ros, 2005; Ciurana et al., 2007a, b; Grossmann et al., 2007) was resolved using a novel AI-DSS technique. The path estimation method explained in this article has been applied to situations where the positioning system fails to locate the mobile terminal (MT) due to wireless disconnection.

When still one reference point or AP is in range, the circular region of probability available from WiFi contour circles can be used for evaluation of the anticipated motion productions i.e., tracking MT locations. But when the system entirely gets disconnected from the MT which means the total loss of the actual positioning data, the anticipated productions are completely on the basis of decision modeling i.e., DSS for emulation of MT behaviors. The presented model is therefore a new contribution to several bodies of science such as positioning and navigation, human motion estimation and decision support systems.

Experimental work and simulation results: The AI-DSS of this research is using causal inference mechanism of fuzzy cognitive map (FCM). The graph’s causal interactions (events) therefore account for the inference rules (if-then expert assertions). The process of weighting the events is the most important part of the DSS. In fact each event weight of the FCM graph implies two pieces of information in a single trait. One is called causality and the other intensity of the event or interaction.

The term causality refers to the direction of a graph edge from concept Ci to Cj and therefore shows which one is affecting the other. The degree of intensity of an event determines the extent of such effect that can be expressed numerically e.g., crisp weights, or by fuzzy grades. The intensity might be limited to lower and upper bounds for example [0, 1], or [0, 100], or unlimited. However, in order to indicate both negative and positive intensity into one value, event weights are usually expressed symmetrically around 0 or in range of [-b, +b]. In many implementations, the event weights are described with linguistic values that can be defuzzified and transformed to the interval [-1, 1] (Stylios et al., 2008). In this research, the range of the event weights is chosen to be [-100, 100] with respect to programming and other considerations. The fuzzy grades of the map inputs (input membership functions) are given in Fig. 8.

The FCM software named FCM Simulator 2009 is implemented in Microsoft VC++ environment. In order to investigate the software performance, a graphical user interface (GUI) is designed to define both the concepts and the event weights. Figure 7a shows the FCM’s GUI in a time instance (ti). The 8 concepts (C1i … C8i) have been chosen from the previous experts (studies on wayfinding without vision) and weighted from DR analysis of motion from location Li-1 to Li for the current time instance.

In this example, the earlier motion production has been a displacement vector of (d,θ) = (50cm, +60°). Accordingly the factor and decision concepts of the map acquire their new weights. The 64 event weights (E1i→ 1i, E1i→ 2i … E8i→ 7i, E8i→ 8i) have been defined form fuzzified linguistic expert definitions. The key factor in defining the event weights is the turn angle θ. For example the expert defined: a fairly large amount of positive turn angle means a strong tendency for making a right turn, a fair tendency for forward movement and a little tendency for taking a reverse step. Therefore, for θ = 60, E1→ 6 obtained +79 from input membership functions, E1→ 7 and E1→ 8 got +33 and +8 respectively. Once all events were defined by the expert(s), the map is ready to run and making a new motion decision. The map is therefore run for the results according to the formulation of definition (Eq. 9, 10).

In the FCM, each of the concepts is being influenced by others while influencing them. The amount of the total influence on a concept Cm is obtained using Eq. 9 where, Enmi shows the influence of the concept Cn on the concept Cm at a time instance ti. In fact Cn’s effect on Cm is a product of Cn’s weight multiplied by the weight of the forward connecting event between Cn and Cm (En→ m).

Using the logistic function of Eq. 10, the new weights of the concepts can be defined from squashing the total influence of other concepts on them.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 7:
(a) DR analysis of motion from Li-1 to Li and expert event definitions are used for updating the map at time ti. Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach (b) Motion decision Pi is obtained from FCM convergence. Accordingly the MT is expected to move from location Li to Li+1

The role of the logistic function is just to standardize the new concept weights by means of lower and upper bounds. This is also helpful in obtaining map convergence and avoiding chaotic and oscillatory results.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Upon running the FCM, the finalized new weights of the concept are obtained (C1i+1 … C8i+1) which account for the generated motion decision. Figure 7b demonstrates the FCM after convergence i.e., generation of a decision production Pi for moving from location Li to Li+1. In fact the map runs in a cyclic fashion which means the ultimate results will be obtained from continues run of the map. The FCM formula in this thesis is based on the definition model as explained. However, changing the model using incremental formula is also possible depending on the expert(s). The only difference between the two models is that; in the former all concept weights are defined anew after each cycle, while in the latter new values of the concepts are accumulated with the previous ones and then assigned as the new concept weights.

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 8:
(a) Expert-defined space when traveler is making a new motion production, (b) the causal influences of the decision concepts on one another and (c) The influence of the circular motion behaviors on the decision concepts

As shown in Fig. 7b, after 27 cycles, there is a convergence which means the map has reached a stable decision production. From finalized values of the decision concepts (states 5, 6, 7 and 8) the future motion production is predictable. In other words, the decision production Pi for moving from location Li to Li+1 is expected to be made by the traveler i.e., motion production Pi. Based on the obtained results, the traveler is expected to make a right turn, or a forward step, but not a left turn nor a reverse step. The resultant motion production is therefore a movement into right-front at 45° of deviation from the current heading direction while based on the DR algorithm the traveler’s speed is constant. Therefore, the next traveler’s displacement vector is anticipated to be as follows: Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach.

Using FCM Simulator 2009 in expert mode, consecutive emotion productions can be generated using DR analysis of kinematical motion behavior, as well as expert-defined weights of the map events. The FCM is already capable of predicting future trajectories of the blind traveler. However, GA optimization of the events was used instead of expert-defined events in order to complete the AI-DSS model of this research.

Expert input membership functions: The interactions or the causal relationship of the factors and the decision concepts of the FCM are investigated. An expert defined the following rules in such a way that the entire FCM gives plausible results at each decision point i.e., decision production.

As for the decision concepts namely left, right, forward and reverse moves, a general rule stated; if a traveler’s tendency is to make either of the four moves, then, his tendency is lower for the others. Figure 8a shows the traveler’s space when he is about to make a new motion production. If for example the traveler’s tendency is to make a right move, then there is also a little tendency for making a forward or reverse step too. But according to the expert’s view, there is no chance of making a left move.

The 4 motion decision concepts can therefore have a fuzzy relationship as shown in Fig. 8b. This is again up to the expert that how to design the fuzzy grades or the input membership function in order to consider a fair amount of overlap between the four subspaces namely; left, front, right and back.

Gaussian distribution perhaps is the best alternative in order to design the membership functions to be closer to the reality. The Gaussian (normal) distribution, is an important family of continuous probability distributions and is applicable in many fields. It is advantageous in modeling problems in a realistic way since it is obtained from statistical information of the parameters within the same system. Applying genetic-fuzzy techniques for enhancement of the function shapes whether normal, triangular, or of any other type is also another alternative which is not within the scope of this research.

The functions shown in Fig. 8b are used to generate the gray causal relationships of the four decision concepts. For instance, the causal effect of the right turn motion concept on the forward step motion concept is derived from ratio of the related graph areas which is expressed by Eq. 11-13.

E6→ 7 = SROF/SR

E6→ 7 = Causal event from right turn concept to forward step concept
SR = The area of graph R
SROF = The area of the intersection of graphs R and F
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Another issue in defining the causal interactions refers to the effect of the clockwise and counter-clockwise motion tendency on the decision concepts that is easily obtained from the given fuzzy grades in Fig. 8c. A general expert rule would be; if motion tendency is to make a clockwise move then there are possibilities for making forward, right, or reverse moves.

The influences on the back-forth and left-right motion behaviors is determined from the total influence on the left and right motion concepts and the total influence on the forward and reverse motion concepts, respectively. And finally, for defining the causal effect of the back-forth behavior and also the left-right behavior on the others, the expert(s) may apply the event weights given in Table 1. For example the back-forth motion behavior has nothing to do with circular kind of motion, neither with left, or right turns.

Table 1: The effects of the back-forth and left-right concepts on the other concepts
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach

Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Image for - A Review on Positioning Techniques and Technologies: A Novel AI Approach
Fig. 9:
(a) The first 10 productions are obtained from MT tracking and modeled through the learning stage of the AI algorithm and (b) The path of 5 following actual productions (triangle face) is almost enveloped by the two bounds of estimated paths (circle face)

But, there is a 50% possibility of making a forward or reverse move.

Actual Results in Comparison with the AI-DSS Simulation: The experimental work was from May to July 2008. The environment was an obstacle free floor of 11.5x6.2 m2. Twenty two blind-folded subjects contributed for motion patterns extraction (used in statistical CBR tuning). Upon completion of this stage, new subjects who were 13 blind-folded undergraduate students (aged 19 to 23) were chosen for path prediction experiments. For all experiments, the eye-masks were completely dark and the room luminance would not give any cue of light perception. The goal at this stage was to test the AI model prior to implementation of the physical network. Therefore, for tracking purposes a number of colored stickers were used to stick on the test floor and the time between intervals i.e., each sticker placement, was recorded with accuracy of 1 sec.

Figure 9a, b shows the final results obtained after adding the GA optimization module to the FCM model which was explained in the previous part. The code was writing in MatLab for graphical representation of the mobile terminal (MT) on the test floor and for using the statistical toolboxes available. Figure 9a the process of learning 10 consecutive productions is demonstrated. The dotted line segments show the GA trials, while the solid ones show the elite trials selected at each stage. Figure 9b shows a series of 5 motion productions which are estimated with acceptable accuracy in comparison with the actual path obtained from a single experiment.


A novel AI Decision Support System (DSS) is developed for learning behavioral as well as the kinematics of moving objects or human subjects. During disconnection of the mobile terminal (MT) from two out of three required access points (AP)s, the model is used for trajectory estimation and therefore resolving the problem of trilateration with only one reference point. Apart from this, there are future applications to other bodies of science and technology including assistive technology for the blind (Motlagh et al., 2007) and improving current robot navigation algorithms (Motlagh et al., 2008a) from human-robot safety prospective (Motlagh et al., 2008b).

1:  Antolovic, D. and S.S. Wallace, 2007. Design of a radio-frequency multiplexer used in radiolocation of 802.11 wireless sources. Proceedings of the International Conference on Portable Information Devices, May 25-29, 2007, IEEE Xplore London, pp: 1-6.

2:  Borriello, G., M. Chalmers, A. LaMarca and P. Nixon, 2005. Delivering real-world ubiquitous location systems. Commun. ACM, 48: 36-41.
Direct Link  |  

3:  Ciurana, M., F. Barcelo-Arroyo and F. Izquierdo, 2007. A ranging system with IEEE 802.11 data frames. Proceedings of the Radio and Wireless Symposium, January 9-11, 2007, Long Beach, CA., pp: 133-136.

4:  Ciurana, M., F. Barcelo-Arroyo and S. Cugno, 2007. A novel TOA-based indoor tracking system over IEEE 802.11 networks. Proceedings of the 16th IST Mobile and Wireless Communications Summit, July 1-5, 2007, Budapest, pp: 1-5.

5:  Crandall, W., B.L. Bentzen, L. Myers and J. Brabyn, 2001. New orientation and accessibility option for persons with visual impairment: Transportation applications for remote infrared audible signage. Clin. Exp. Optometry, 84: 120-131.
PubMed  |  Direct Link  |  

6:  Fuentes, L.M. and S.A. Velastin, 2006. People tracking in surveillance applications. Image Vision Comput., 24: 1165-1171.
CrossRef  |  Direct Link  |  

7:  Gaunet, F. and X. Briffault, 2005. Exploring the functional specifications of a localized wayfinding verbal aid for blind pedestrians: Simple and structured urban areas. Hum. Comput. Interact., 20: 267-314.
CrossRef  |  

8:  Golfarelli, M., D. Maio and S. Rizzi, 2001. Correction of dead-reckoning errors in map building for mobile robots. IEEE Trans. Robot. Automat., 17: 37-47.
CrossRef  |  

9:  Grewal, M.S. and A.P. Andrews, 1993. Kalman Filtering: Theory and Practice. 1st Edn., Prentice Hall, Englewood Cliffs, New Jersey, ISBN: 0-13-211335-X, pp: 368.

10:  Grossmann, U., M. Schauch and S. Hakobyan, 2007. RSSI based WLAN indoor positioning with personal digital assistants. Proceedings of the 4th Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, September 6-8, 2007, London, UK., pp: 653-656.

11:  Hall, T.D., 2004. Radiolocation using AM broadcast signals: The role of signal propagation irregularities. Proceedings of the Position Location and Navigation Symposium, April 26-29, 2004, London, UK., pp: 752-761.

12:  Hartley, R.I. and P. Sturm, 1997. Triangulation. Comput. Vision Image Understand., 68: 146-157.
Direct Link  |  

13:  Hub, A., J. Diepstraten and T. Ertl, 2004. Design and development of an indoor navigation and object identification system for the blind. Proceedings of the 6th International ACM SIGACCESS Conference on Computers and Accessibility, October 18-20, 2004, Atlanta, GA., USA., pp: 147-152.

14:  Kotanen, A., M. Hannikainen, H. Leppakoski and T.D. Hamalainen, 2003. Positioning with IEEE 802.11b wireless LAN. Personal Indoor Mobile Radio Commun., 3: 2218-2222.
CrossRef  |  

15:  Laurent, B. and T.N. Christian, 2007. A sonar system modeled after spatial hearing and echolocating bats for blind mobility aid. Int. J. Phys. Sci., 2: 104-111.
Direct Link  |  

16:  Lindström, J.I., 2008. New technologies to help people with disabilities and elderly people. pp: 9-23.

17:  Mailaender, L., 2008. On the geolocation bounds for round-trip time-of-arrival and all non-line-of-sight channels. EURASIP J. Adv. Signal Proc., 2008: 1-10.
CrossRef  |  

18:  Malhotra, N., M. Krasniewski, C. Yang, S. Bagchi and W. Chappell, 2005. Location estimation in ad hoc networks with directional antennas. Proceedings of the 25th International Conference on Distributed Computing Systems, June 6-10, 2005, IEEE Computer Society Washington, DC, USA., pp: 633-642.

19:  Mason, A., A. Shaw and A.I. Al-Shamma'a, 2007. Intelligent radio frequency identification positioning using wireless sensor networks. Proceedings of the Antennas and Propagation Conference, April 2-3, 2007, Loughborough, pp: 145-148.

20:  Motlagh, O., S.H. Tang and N. Ismail, 2007. An intelligent mobility aid system for visually handicapped according to the blinds cognitive map in local path planning. Proceedings of the 2nd National Intelligence System and Information Technology Symposium, (ISIT'07), Malaysia, pp: 152-157.

21:  2008. Development of a new minimum avoidance system for a behavior-based mobile robot. Fuzzy Sets Syst.
CrossRef  |  

22:  Motlagh, O., S.H. Tang, N. Ismail, A.R. Ramli, R. Samin, 2008. A novel approach to human motion estimation with applications in human-robot safety. Proceedings of the Symposium on Engineering and Technology (SET2008), Dec. 15-16, Kuching, Sarawak, Malaysia.

23:  Na, J., 2006. The blind interactive guide system using RFID-based indoor positioning system. Lecture Notes Comput. Sci., 4061: 1298-1305.
Direct Link  |  

24:  Niculescu, D. and B. Nath, 2003. Ad hoc positioning system (APS) using AOA. Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, March 30-April 3, 2003, Rutgers University, Piscataway, pp: 1734-1743.

25:  Pappalardi, F., S.J. Dunham, M.E. LeBlang, T.E. Jones, J. Bangert and G. Kaplan, 2001. Alternatives to GPS. Proceedings of the OCEANS 2001 MTS/IEEE Conference and Exhibition, November 5-8, 2001, Honolulu, HI., USA., pp: 1452-1459.

26:  Park, K.C., D. Chung, H. Chung and J.G. Lee, 1996. Dead reckoning navigation of a mobile robot using an indirect Kalman filter. Proceedings of the IEEE/SICE/RSJ International Conference on Multi-sensor Fusion and Integration for Intelligent Systems, December 8-11, 1996, Washington, DC. USA., pp: 132-138.

27:  Randell, C., C. Djiallis and H. Muller, 2005. Personal position measurement using dead reckoning. Proceedings of the 7th International Symposium on Wearable Computers, October 18-21, 2005, University of Bristol, pp: 166-173.

28:  Thapa, K. and S. Case, 2003. An indoor positioning service for bluetooth ad hoc networks. Proceedings of the Midwest Instruction and Computing Symposium, April 11-12, 2003, Duluth, MN., USA., pp: 1-11.

29:  Thomas, F. and L. Ros, 2005. Revisiting trilateration for robot localization. IEEE Trans. Robot., 21: 93-101.
CrossRef  |  

30:  Thrun, S., 2000. Probabilistic algorithms in robotics. AI Magazine, 21: 93-109.
Direct Link  |  

31:  Yamauchi, B., 1996. Mobile robot localization in dynamic environments using dead reckoning and evidence grids. Proceedings of the International Conference on Robotics and Automation, April 22-28, 1996, Minneapolis, MN. USA., pp: 1401-1406.

32:  Hill, E.W., J.J. Rieser, M.M. Hill, M. Hill, J. Halpin and R. Halpin, 1993. How persons with visual impairments explore novel spaces: Strategies of good and poor performers. J. Visual Impair. Blind., 87: 295-301.
Direct Link  |  

33:  Jain, A.K., M.N. Murty and P.J. Flynn, 1999. Data clustering: A review. ACM Comput. Surv., 31: 264-323.
CrossRef  |  Direct Link  |  

34:  Khan, M.S. and M. Quaddus, 2004. Group decision support using fuzzy cognitive maps for causal reasoning. Group Decision Negotiat., 13: 463-480.
CrossRef  |  Direct Link  |  

35:  Kitchin, R.M., M. Blades and R.G. Golledge, 1997. Understanding spatial concepts at the geographic scale without the use of vision. Progress Human Geogra., 21: 225-242.
CrossRef  |  Direct Link  |  

36:  Kosko, B., 1996. Fuzzy Engineering. Prentice-Hall Inc., New Jersey, USA.

37:  Millar, S., 1994. Understanding and Representing Space: Theory and Evidence from Studies with Blind and Sighted Children. Oxford University Press, Oxford.

38:  Stylios, C.D., V.C. Georgopoulos, G.A. Malandraki and S. Chouliara, 2008. Fuzzy cognitive map architectures for medical decision support systems. Applied Soft Comput., 8: 1243-1251.
CrossRef  |  Direct Link  |  

39:  Thinus-Blanc, C. and F. Gaunet, 1997. Representation of space in blind persons: Vision as a spatial sense?. Psychol. Bull., 121: 20-42.
PubMed  |  Direct Link  |  

40:  Ungar, S., 2000. Cognitive Mapping without Visual Experience. In: Cognitive Mapping: Past Present and Future, Kitchin, R. and S. Freundschuh (Eds.). Routledge, London.

41:  Vasquez, D. and T. Fraichard, 2004. Motion prediction for moving objects: A statistical approach. Proceedings of the International Conference on Robotics and Automation, Volume 4, April 26-May 1, 2004, IEEE Computer Society Washington, DC, USA., pp: 3931-3936.

©  2021 Science Alert. All Rights Reserved