-This paper describes and evaluates an optimizationbased localization algorithm which has been recently implemented to enrich the possibilities of the localization add-on module for JADE. The described algorithm targets indoor scenarios and it enables localization of JADE agents running on smart devices in known environments, provided that a conventional WiFi network is present. The algorithm assumes that WiFi access points in fixed and known positions are available, and it estimates the position of the smart device where the agent is running using estimates of the distance between the smart device and each access point. Distance estimates are used to build an optimization problem, whose solution is an estimate of the position of the smart device. The described algorithm uses particle swarm optimization to solve the built optimization problem, but it is open to the adoption of other optimization techniques. The validity of the proposed approach is supported by experimental results shown in the last part of the paper.
I. INTRODUCTION
Among the longstanding debate on the characteristics that
should be ascribed to agents, the fact that agents should be
considered situated entities immersed in a partially observable
environment seems consolidated. Agents acquire knowledge
from the environment, and they act on it to achieve their
goals. Whether the environment is physical or not is
irrelevant for a generic characterization, but agents executing in
physical environments are traditionally called robots, while
agents executing in nonphysical environments are traditionally
called software agents. Such a distinction is quickly fading
because onboard software of robots has now features that
were typical of software agents (see, e.g., [
Smart devices already integrate sophisticated sensors and
actuators that can be effectively used to provide agents with
a bidirectional link with the physical environment, but they
do not normally provide means to let agents know their
position in indoor environments. While localization can be
considered a solved problem in outdoor environments because
consolidated technologies like the Global Positioning System
(GPS) are commonly available in virtually all smart devices,
only few smart devices offer localization sensors for indoor
environments. Just to mention one of the most promising
possibilities in this respect, which is already available in
some smart devices, the Ultra-Wide Band (UWB) technology
guarantees accurate and robust indoor localization [
In this paper we document recent developments of
experiments intended to provide JADE agents running on common
Android devices with localization capabilities in known indoor
environments using only ordinary WiFi networks. In detail, the
targeted scenario assumes that a JADE agent is interested in
accurate and timely estimates of its dynamic position within
an indoor environment where known and static WiFi Access
Points (APs) are available. The proposed method is based on
the possibility of acquiring estimates of the distance between
the smart device where the agent is running and each AP
using the received power of signals from responding APs
during standard network discovery. Such distance estimates are
then processed to estimate the position of the smart device in
the indoor environment. Once computed, position estimates
are immediately made available to the JADE agent. The
processing of distance estimates can be performed using one
of the localization algorithms available in the literature [
This paper is organized as follows. Section II fixes notation and describes the implemented algorithm. Section III shows experimental results obtained in a representative indoor scenarios. Finally, Section IV concludes the paper and outlines possible future developments.
The described algorithm is implemented in a localization
add-on module for JADE, which has been recently
implemented to provide a framework to host localization algorithms,
and to offer agent developers the possibility of choosing
among different algorithms to address the specific needs of
applications [
The smart device where the agent is running, which is denoted as Target Node (TN) in the rest of the paper, is situated in an indoor environment that contains M WiFi APs. Let si = (xi, yi)T i ∈ {1, . . . , M }.
(1)
be the coordinates of such APs. We assume that APs are static
and we also assume that their coordinates si are known to
the agent. Note that, in order to simplify notation, we focus
on the description of the algorithm on bi-dimensional
scenarios. The generalization of the described algorithm to
threedimensional scenarios is straightforward. Moreover, under the
assumption that the smart device approximatively moves on a
plane, [
The ranging capabilities that the smart device is requested
to offer in order to support the implemented algorithm concern
the possibility of measuring estimates of the distances to
the M APs. Such estimates of distances are obtained by
processing the average received power of the WiFi signals
traveling between the TN and each responding AP during
standard network discovery. According to the Friis
transmission equation [
(xˆ − xM )2 + (yˆ − yM )2 = rˆM2 which is obtained from (5) by replacing the values of true distances {ri}iM=1, with their estimates, denoted as {rˆi}iM=1. Due to errors on distance estimates, the M circumferences corresponding to the equations in (6) often do not intersect in a single point and, for this reason, a proper localization always provided by operating systems to applications during standard WiFi network discovery because it is normally used to let the user choose among available networks. Each range estimate can also be associated with the corresponding AP and, eventually, with its coordinates, because communications between the TN and an AP during network discovery include the Basic Service Set IDentification (BSSID) of the latter, which can be used to identify the responding AP. Hence, assuming that each known BSSID can be associated with the coordinates si of the corresponding AP, each distance estimate can be related to the coordinates of the corresponding AP. Notably, needed information to support the computation of distance estimates is always available to applications and neither low-level access to hardware, nor privileged operating system services are needed. Indeed, the TN is not even requested to be connected to the WiFi network, because only network discovery is used.
We have already discussed the performance of some
localization algorithms in the context of agent-based indoor
localization, such as the circumference intersection algorithm [
u = (x, y)T be the true position of the TN, which is supposed to be unknown and which is what should be estimated. The true distance between the TN and the i−th AP can be denoted as ri , ||u − si||
i ∈ {1, . . . , M }.
The knowledge of true distances {ri}iM=1, together with the M knowledge of coordinates {si}i=1 of the APs, would easily determine the position of the TN. In this case, the coordinates of the TN could be found by simply intersecting the circumferences centered in {si}iM=1, whose radii are {ri}iM=1. This translates into the following system of M quadratic equations (x − x1)2 + (y − y1)2 = r12 . . .
(x − xM )2 + (y − yM )2 = rM2 .
Unfortunately, since true distances {ri}iM=1 between APs and the TN are unknown, localization can only be performed using the following system of quadratic equations (3) (4) (5) (6) algorithm needs to be considered in order to find the proper estimates of the position of the TN, which is denoted as
In order to derive a proper localization algorithm, let us first observe that (6) can be re-written in matrix notation as uˆ = (xˆ, yˆ)T . 1 uˆT uˆ + A uˆ = kˆ move all the particles towards the position corresponding to the optimal solution of the considered minimization problem.
The PSO-based algorithm that we adopted to solve the minimization problem (10) works as follows. First, the positions of the particles are randomly initialized in the search space, which, in our context, corresponds to the physical indoor environment where the APs and the TN are situated. The initial positions are denoted as x(i)(0)
i ∈ {1, . . . , S} where i is the index of the generic particle, and S is the number of particles. Analogously, the velocity of the i−th particle is initialized with the value where 1 is vector with M elements equal to 1, kˆ is a vector whose i−th element is rˆi2 − (xi2 + yi2), and A is the following M × 2 matrix x1 x2 A , −2 ...
xM y1 y2 ... . yM
Possible algorithms to solve (8), based on least square
techniques, on Taylor series expansion, or on
maximumlikelihood methods, can be found, for instance, in [
Various algorithms to solve localization problems expressed
as systems of equations like (8) can be found in the significant
body of literature on the subject (see, e.g., [
Observe that (8) can be written as a minimization problem whose solution is an estimate of the position of the TN uˆ = arg min F (u)
u where F (u) represents the fitness function associated with the problem, which is defined as
ˆ
F (u) = ||k − (1 uˆT uˆ + A uˆ)||.
In order to solve the minimization problem (10), among the wide range of possibilities, we propose to use the PSO algorithm for its proved effectiveness and robustness. According to such an algorithm, the set of potential solutions of a minimization problem can be considered as a swarm of particles whose positions and velocities are iteratively updated according to proper rules. Such rules are inspired by biological phenomena like the movements of birds in swarms. In the context of optimization problems, such rules are meant to where where (12) (13) (14) (15) (16) (17)
After the initialization phase, positions and velocities of all
the particles are updated at each iteration t ∈ N to simulate
interactions among individuals. More precisely, at the t−th
iteration, the velocity of the i−th particle whose position is
x(i)(t) is updated according to the following rule [
From (14) it can be easily observed that the velocity of a particle at the (t + 1)−th iteration is obtained as the sum of three addends. The first addend is related to the velocity of the particle at the previous iteration, which is weighed according to the inertial factor ω(t). The second addend is meant to move each particle towards the best position it reached so far. Note that such a best position is the one which corresponds to the lowest value of the fitness function and, therefore, y(i)(t) can be expressed as y(i)(t) = arg min F (z)
z∈X(i)(t)
X(i)(t) = {x(i)(0), . . . , x(i)(t)}.
Finally, the third addend aims at moving each particle towards
the global best position, which is the position that corresponds
to the smallest value of the fitness function among all those
reached by any particle in the swarm [
z∈Y (t) Y (t) = {y(1)(t), . . . , y(S)(t)}.
TN 2
3 x[m] (b) AP1 0
AP2 1
AP3 4
AP4 5 6
Typically, the inertial factor ω(t) is chosen as a decreasing
function of t to guarantee low dependence of the solution on
the initial population, and to reduce the exploration ability of
the swarm as the number of iterations increases, which makes
the method similar to a local search in last iterations [
The velocities computed with (14) are used to update the positions of particles at each iteration according to the following rule x(i)(t + 1) = x(i)(t) + v(i)(t) i ∈ {1, . . . , S}.
(19) From (19) it can be observed that the position of the i−th particle at the (t+1)−th iteration is simply obtained by adding v(i)(t) to its previous position.
The execution of the PSO algorithm terminates when a proper termination condition is met. Normally, the termination condition includes that a sufficient number of iterations was performed, or that the fitness function reached a satisfactory value. Once the execution of the algorithm terminates, the solution of the minimization problem is the position of the particle with the lowest value of the fitness function.
The PSO algorithm outlined above is used to solve the
localization problem (10). In order to obtain the experimental
results shown in the next section, we set the value of the
inertial factor to 0.5. The values of c1 and c2 are equal and
they are set to 2, so that the average values of c1R1(t) and
of c2R2(t) correspond to 1. The size of the population S is
set to 40, and the algorithm terminates after 50 iterations.
These values proved to be effective for localization purposes
as documented in the experimental results presented in [
This section shows experimental results obtained using the
described optimization-based algorithm, as implemented in
the localization add-on module for JADE. Presented results
are obtained in a representative scenario which consists in a
section of a corridor whose width is 2 m. Note that we consider
a bi-dimensional scenario, however, the algorithm can be
generalized to three-dimensional scenarios as shown in [
Moreover, under the assumption that the smart device moves
on a plane, [
We assume that M = 4 APs are used to estimate the position of the TN and, in the same environment, we consider two different configurations of such APs. The two configurations are shown in Fig. 1 and in Fig. 2, respectively. In this figures, the positions of the APs are marked with blue squares, the position of the TN is marked with a red star, and the black lines show the walls of the corridor. Note that, even if the algorithm is evaluated for M = 4 APs, it can be executed with an arbitrary number of APs. The minimum number of APs to localize a TN in a bi-dimensional environment is three, but the availability of more APs contributes to improve the accuracy of localization.
For each configuration of APs, the optimization-based localization algorithm outlined in Section II is applied 100 times, thus leading to 100 independent position estimates for the TN.
In the following, the position estimates of the TN at the j−th iteration are denoted as uˆ(j) = (xˆ(j), yˆ(j)) j ∈ {1, . . . , 100}.
(20) The performance of the proposed localization algorithm is analyzed in terms of a localization error computed as the distance between each position estimate uˆ(j) and the true position of the TN, denoted as u, which is known. Such a localization error is d(j) , ||uˆ(j) − u||
j ∈ {1, . . . , 100}.
The values of {d(j)}j1=001 can be used to compute the average localization error, denoted as davg, which is expressed as davg =
We start by considering experimental results obtained in the scenario shown in Fig. 1. In this case, the coordinates of the APs, expressed in meters, are davg 1.8 1.6 The position of the TN, instead, has the following coordinates expressed in meters According to the algorithm outlined in Section II, range estimates for each one of the four APs are acquired and used to estimate the position of the TN. This procedure is applied 100 times, thus obtaining 100 position estimates {uˆ(j)}j1=001 for the TN. Obtained results are then used to evaluate distances {d(j)}j1=001 between the j-th position estimate and the true position of the TN, according to (21). Such distances are used as a performance metrics to investigate the validity of the proposed localization algorithm. Fig. 3 shows the values of {d(j)}j1=001 and also the value of the average localization error davg, which corresponds to 62 cm. Fig. 3 also shows that the maximum value of {d(j)}j1=001 is approximately 1.4 m.
This means that the distance between the true position of the TN and its estimates is at most 1.4 m, and it is 0.62 m on average, which makes the localization sufficiently accurate for many indoor localization purposes.
Let us now consider the results obtained with the configuration of APs shown in Fig. 2, where all APs are located on the same side of the corridor. In this case, the coordinates of the APs expressed in meters are Fig. 3. The values of the localization error d(j) is shown for 100 position estimates for the configuration of APs in Fig. 1. The value of the average localization error is shown with a magenta line across the diagram.
This paper described and evaluated empirically an
The TN is located in the same point as in the first scenario, and optimization-based localization algorithm which is used to
its coordinates are shown in (24). Note that the configuration provide agents with accurate and timely estimates of their
of APs shown in Fig. 2 is less favorable for localization than position in indoor environments using only ordinary WiFi
that shown in Fig. 1, and many classic localization algorithm infrastructures. The discussed algorithm is implemented in
would fail in estimating the position of the TN. Actually, the the localization add-on module for JADE which provides a
large majority of classic localization algorithm rely on specific framework to host different localization algorithms and to let
geometric considerations concerning the positions of the APs agent developers choose among them to address the specific
and of the TN, and they are based on the solutions of non- needs of applications. In detail, the proposed approach uses
linear systems of equations. If all APs lay on the same line, the communication between the smart device where the agent
as in the scenario shown in Fig. 2, then the matrices which
appear in such classic algorithms become ill-conditioned, thus
leading to position estimates which are typically far distant
from the true position of the TN [
As done in the first scenario, 100 range estimates from each one of the four APs are acquired, but in this case the configuration of APs is shown in Fig. 2. The values of distances {d(j)}j1=001 corresponding to the 100 position estimates are then evaluated according to (21) and they are shown in Fig. 4. Fig. 4 also shows the value of the average localization error davg, which corresponds to 56 cm (green line). Finally, Fig. 4 shows that the distance between the true position of the TN and its estimates is always smaller than 1.7 m, since the maximum value of {d(j)}j1=001 is 1.68 m.
A comparison between the results shown in Fig. 3 and in Fig. 4 emphasizes that the values of the average localization errors davg are close in the two scenarios. The value of davg with the configuration of APs shown in Fig. 2, which is the less favorable, is 6 cm lower than that obtained with the configuration of APs shown in Fig. 1, even if the maximum value of {d(j)}j1=001 is smaller in the first scenario.
IV. CONCLUSIONS is running and the APs of the network, which are assumed to be static and in known positions, to acquire estimates of the distance between the smart device and each AP. Such estimates are used to build a specific optimization problem, which is then solved using PSO. The solution of such an optimization problem is an estimate of the position of the smart device which hosts the agent. No dedicated infrastructure is needed to enable localization, and smart devices are not even requested to be connected to one of the available WiFi networks because only standard network discovery messages are used.
Possible envisaged applications of the described algorithm
include location-aware social games [
Future work on the research discussed in this paper involves further investigation on the performance of the described algorithm in different indoor environments and with different configurations of APs. Moreover, it is of interest to study the effects of proper pre-processing of the range estimates in the first phase of the algorithm. Actually, as also suggested by experimental results shown in previous section, the performance of the algorithm could benefit from proper averaging of range estimates or of position estimates.