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-1-θn-1) along the path and until production
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.
|| 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.
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 subjects 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).
|| Trilateration technique on x-y plane
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.
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
P(d) = P(d0)-10γ
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
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,
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.
|| 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
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
||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
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.
(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 MTs actual
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).
(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 MTs consecutive motion productions (Fig.
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
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
Therefore, the FCM was made to be updated to learn the MTs 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
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
the FCMs concepts weights (node values) are set at location L(t-1).
The weights of the FCMs events (edge values) are to be optimized.
(a) Path database is used for estimation of an available
segment (P4), (b) Best estimation trials (decisions) and the segments
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
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 ,
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.
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
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
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
graphs 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
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 FCMs
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 Cns effect
on Cm is a product of Cns 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.
(a) DR analysis of motion from Li-1
and expert event definitions are used for updating the map at time
(b) Motion decision Pi
is obtained from FCM convergence.
Accordingly the MT is expected to move from location Li
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
Upon running the FCM, the finalized new weights of the concept are obtained
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.
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 travelers speed is constant. Therefore, the next travelers
displacement vector is anticipated to be as follows: .
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 travelers tendency is to make
either of the four moves, then, his tendency is lower for the others.
Figure 8a shows the travelers space when he is
about to make a new motion production. If for example the travelers
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 experts
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.
||Causal event from right turn concept to forward step
||The area of graph R
||The area of the intersection of graphs R and F
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.
|| The effects of the back-forth and left-right concepts
on the other concepts
(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