=Paper=
{{Paper
|id=Vol-2404/paper03
|storemode=property
|title=Experiments on Robust Indoor Localization of Mobile Devices Using Interval Arithmetic
|pdfUrl=https://ceur-ws.org/Vol-2404/paper03.pdf
|volume=Vol-2404
|authors=Stefania Monica,Federico Bergenti
|dblpUrl=https://dblp.org/rec/conf/woa/MonicaB19
}}
==Experiments on Robust Indoor Localization of Mobile Devices Using Interval Arithmetic==
https://ceur-ws.org/Vol-2404/paper03.pdf
Workshop "From Objects to Agents" (WOA 2019)
Experiments on Robust Indoor Localization
of Mobile Devices Using Interval Arithmetic
Stefania Monica, Federico Bergenti
Dipartimento di Scienze Matematiche, Fisiche e Informatiche
Università degli Studi di Parma
43124 Parma, Italy
{stefania.monica,federico.bergenti}@unipr.it
Abstract—The lack of techniques and tools to estimate the information that agents can use to bring about their goals.
position of mobile devices with high accuracy and robustness is Therefore, the use of the position to enrich the behaviors of
one of the major causes that limit the provision of advanced agents is expected to be simple and effective. This is the reason
location-based services in indoor environments. An algorithm to
enable mobile devices to estimate their positions in known indoor why the algorithm used to run the experiments documented
environments is discussed in this paper under the assumption in this paper was implemented as an extension of the lo-
that fixed network nodes are available at known locations. The calization add-on module (e.g. [15]) for JADE (e.g., [16]).
discussed algorithm is designed to allow devices to estimate The localization add-on module for JADE is responsible
their positions by actively measuring the distances from visible for providing timely information to agents regarding their
fixed nodes. In order to reduce the errors introduced by the
arrangement of the fixed nodes in the environment, the discussed positions using one of the available localization algorithms.
algorithm transforms the localization problem into an optimiza- Actually, the localization add-on module extends a JADE
tion problem, which is then solved using interval arithmetic. container (e.g., [16]) executed on a mobile device with the
Experimental results on the use of the discussed algorithm with possibility of interfacing the sensors of the device to obtain the
distance estimates obtained using ultra-wide band are presented low-level information needed to apply the chosen localization
to assess the performance of the algorithm and to compare
it with a reference alternative. Presented experimental results algorithm. The estimated position of the device is then passed
confirm that the discussed algorithm provides an increased level to interested agents hosted by the container so that they can
of robustness with respect to the considered reference alternative use it to bring about their goals. Note that, besides available
with no loss of accuracy. localization algorithms, additional algorithms like the one
Index Terms—localization as optimization, indoor localization, discussed in this paper can be easily integrated in the add-on
ultra-wide band, software agents
module provided that they implement a specific Java interface.
The discussions in this paper are focused on the general
I. I NTRODUCTION
problem of allowing a mobile device, denoted as Target Node
The possibility of robustly associating an accurate position (TN), to estimate its position inside an indoor environment
with a mobile device in an indoor environment has recently with known geometry under the assumption that fixed network
become a major feature needed to increase the level of nodes, denoted as Anchor Nodes (ANs), are installed at known
personalization of services and applications offered to users locations. One of the major assumption of this work is that
(e.g., [1]–[3]). Robust and accurate indoor localization can be mobile devices can actively measure the distances from the
used, for example, to personalize and increase the interactivity ANs installed in the environment using one of the available
of visits to art exhibitions by means of educational games ranging technologies. An average error of 1 m in the estimation
(e.g., [4]), it can be used to support the automation of work in of positions is considered acceptable for targeted application
warehouses (e.g., [5]), and it can be used to extend the services scenarios, and experimental results discussed in Section V
of location-based social networks (e.g. [6]) to large indoor show that such an accuracy is feasible using the discussed
areas like shopping malls, train stations, and airports. Solutions localization algorithm when ranging information are obtained
to problems related to indoor localization can be found in using UWB. With minor loss of generality, it is assumed that
recent literature (e.g., [7]–[9]), but the general problem of the considered indoor environment is composed of possibly
enabling a mobile device to accurately and robustly estimate overlapping rectangular cuboids, called boxes in this paper to
its position in a known environment is still an open issue follow a consolidated nomenclature. Under this assumption, it
(e.g., [10], [11]) even if specific technologies like Ultra-Wide is possible to focus the hunt for TNs in the environment on
Band (UWB) (e.g., [12], [13]) are readily available. the single boxes that compose the environment, and therefore
Software agents are expected to play a relevant role in the the localization problem can be simplified by considering
delivery of mentioned services and applications (e.g., [14]) only box-shaped environments. Observe that the minimum
because agents are normally characterized as situated entities bounding box containing the considered environment can be
capable of exhibiting context-aware behaviors. With this re- used if the environment cannot be split into boxes, but, in this
spect, the position can be considered as just another context case, estimated positions of TNs should be filtered accordingly.
14
Workshop "From Objects to Agents" (WOA 2019)
One of the problems that make indoor localization difficult but lightface and with a subscript, for its components. Also
is related to the fact that the positions of ANs in the envi- note that the common understanding of 00 = 1 is adopted
ronment strongly affect the accuracy of ordinary localization consistently throughout this paper.
algorithms (e.g., [17], [18]), like the Two-Stage Maximum- Given two multi-indices I ∈ Nn and J ∈ Nn , they can be
Likelihood (TSML) [19] algorithm discussed in Section V. In compared using the following partial order
particular, a significant loss of the accuracy provided by such
algorithms is normally observed when ANs are not positioned I ≤ J ⇐⇒ i1 ≤ j1 ∧ i2 ≤ j2 ∧ · · · ∧ in ≤ jn (3)
properly in the environment. Such a problematic characteristic and they can also be added componentwise
of ordinary localization algorithms is critical for indoor envi-
ronments because ANs are normally located near the ceilings I + J = (i1 + j1 , i2 + j2 , . . . , in + jn ). (4)
of rooms, which is an arrangement that exacerbates the men-
The following abbreviation is introduced for multi-indices
tioned problem. The choice of installing all ANs at (roughly)
H ∈ Nn , I ∈ Nn , and J ∈ Nn to express repeated sums
the same height near the ceilings of rooms degrades the
performance of ordinary localization algorithms because some X j1
X j2
X jn
X
of the matrices involved in computations become strongly ill- (·) = ··· (·). (5)
conditioned (e.g., [5], [20]). Unfortunately, the choice of the H≤I≤J i1 =h1 i2 =h2 in =hn
positions of ANs in indoor environments is often dictated by Note that H is omitted in (5), so that only I ≤ J remains, if
practical considerations intended, for example, to limit the it is the null multi-index (0)nk=1 .
interference caused by people and furniture, and to maximize The multi-index notation is particularly well-suited to study
coverage. Therefore, the positions of ANs cannot be changed polynomial functions. A polynomial function p : Rn 7→ R of
just to limit the mentioned problem of ordinary localization n ∈ N+ real variables with real coefficients can be written as
algorithms. The remainder of this paper is devoted to study X
the robustness of an alternative algorithm in situations in p(x) = aI xI , (6)
which the accuracy of ordinary algorithm degrades sensibly. I≤L
Experimental results presented in Section V show that the
where {aI }I≤L ⊂ R is the set of the coefficients of p and
accuracy of the studied algorithm is acceptable even when
multi-index L ∈ Nn is the multi-degree of p.
the accuracy of the TSML algorithm, which is used as a point
Observe that the localization algorithm discussed in this
of reference, degrades sensibly.
paper works by studying the bounds of polynomial functions
This paper is organized as follows. Section II introduces
over boxes. Hence, it is worth recalling the following notation
adopted notation. Section III describes the adopted approach
for intervals and boxes. A closed (real) interval from a ∈ R
to localization. Section IV describes the discussed algorithm
to a ∈ R is denoted as
and briefly presents its characteristics. Section V reports the
results of the experimental campaign performed to assess [a, a] = {x ∈ R : a ≤ x ≤ a}, (7)
the robustness of the studied algorithm. Finally, Section VI
concludes the paper. and it equals the empty set if and only if a > a. A
singleton (real) interval that contains only a ∈ R is denoted
II. N OTATION as [a] = [a, a]. Given n ∈ N+ , a (real) box B ⊂ Rn from
This section summarizes the notation commonly used to b = (bk )nk=1 ∈ Rn to b = (bk )nk=1 ∈ Rn is denoted as
study real functions of several real variables, as it is used to
present the localization problem and the discussed algorithm in B = [b, b] = [b1 , b1 ] × [b2 , b2 ] × · · · × [bn , bn ], (8)
the following sections. The set of natural numbers, including and it equals the empty set if and only if bi > bi for some
zero, is denoted as N and the set of positive natural numbers 1 ≤ i ≤ n. Note that the notation Bi = [bi , bi ] ⊂ R with
is denoted as N+ . Given n ∈ N+ , a multi-index I ∈ Nn is 1 ≤ i ≤ n is used to refer to the closed intervals that compose
defined as an n−tuple of natural numbers the nonempty box B. Also note that the notation Bi→W is
I = (i1 , i2 , . . . , in ) = (ik )nk=1 . (1) used to refer to the box obtained by replacing the i−th closed
interval that composes the nonempty box B with the nonempty
Note that it is a common notation to use an uppercase letter to closed interval W ⊂ R.
denote a multi-index and to use the same letter, but lowercase Interval arithmetic (e.g., [21]) uses the introduced nota-
and with a subscript, to denote its components. The following tion to express computations whose arguments and results
notation is adopted to use a multi-index I ∈ Nn as an exponent are closed intervals. Given two nonempty closed intervals
for t ∈ Rn with t = (t1 , t2 , . . . , tn ) = (tk )nk=1 A = [a, a] ⊂ R and C = [c, c] ⊂ R, they can be added
n
Y
tI = tikk . (2) A + C = [a + c, a + c], (9)
k=1
and they can be multiplied
Note that it is a common notation to use a boldface letter
to denote an n−tuple of real numbers, and the same letter, A · C = [min{a c, a c, a c, a c}, max{a c, a c, a c, a c}]. (10)
15
Workshop "From Objects to Agents" (WOA 2019)
In both cases the result is a nonempty closed interval. Note that algorithm briefly recalled in Section IV is a specific instanti-
the product among intervals can be used to define the m−th ation of an algorithmic framework proposed in an upcoming
power of a closed interval A ⊂ R, where m ∈ N+ . Also note paper. Interested readers can obtain from authors a preprint
that the convention [0]0 = [1] is adopted consistently in this of the paper where the algorithmic framework is proposed
paper. Given n ∈ N+ , a nonempty box B ⊂ Rn , and a multi- and studied. In the remainder of this section, the approach of
index I ∈ Nn , the following notation that uses only products localization as optimization is recalled for the tridimensional
among intervals is normally used case for the sake of clarity and to fix the adopted notation.
n A set of m ≥ 4 ANs is positioned at fixed and known
i
Y
BI = Bj j . (11) locations in the considered indoor environment. The position
j=1 of the i−th AN is denoted as ai ∈ R3 with 1 ≤ i ≤ m. The
true position of the TN is denoted as t ∈ R3 , and the true
Using the introduced notation, which is typical of interval
distance between the TN and the i−th AN is
arithmetic, a polynomial function p : Rn 7→ R of n ∈ N+
real variables with real coefficients can be extended to work ri = ||t − ai ||. (13)
on boxes. If the function is expressed as in (6), then for any The geometry of the problem suggests that the position of the
box B ⊂ Rn X TN can be found by intersecting m spheres, the i−th of which
p(B) = [aI ]B I , (12) is centered at ai and has radius ri
I≤L
||t − a1 ||2 = r12
where the notation for singleton intervals is used to treat the
||t − a2 ||2 = r22
coefficients of the polynomial function as closed intervals. (14)
..
Observe that it is easy to prove that the result of the evaluation
.
of p(B) is a closed interval that includes the range of p over
||t − am ||2 = rm 2
box B (e.g. [21]).
The localization problem is the problem of finding estimates
III. L OCALIZATION AS O PTIMIZATION of the position of the TN provided that the distances between
The localization as optimization approach was proposed the TN and each AN are estimated using one of the available
in previous works (e.g., [5], [20]) with the aim of reducing ranging technologies. The estimated position of the TN is
the loss of accuracy that characterizes ordinary algorithms denoted as t̃ ∈ R3 , while the estimated distance between the
for critical arrangements of the ANs, as briefly recalled in TN and the i−th AN is
Section I. The localization as optimization approach is based r̃i = ||t̃ − ai ||. (15)
on the possibility of rewriting any localization problem into a
Therefore, the estimated position t̃ of the TN is expected to
related optimization problem, which can then be solved using
satisfy the following system of nonlinear equations, which is
one of the algorithms documented in the vast literature on
obtained by exchanging the true values with their correspond-
optimization. Observe that many of the optimization algo-
ing estimated values in (14)
rithms available in the literature still have problems related
||t̃ − a1 ||2 = r̃12
to ill-conditioned matrices. Therefore, specific attention must
be paid to the choice of a proper optimization algorithm in ||t̃ − a2 ||2 = r̃22
order to guarantee that the reformulation of the localization .. (16)
problem in terms of an optimization problem would lead to
.
high accuracy in scenarios where the arrangements of ANs is
||t̃ − am ||2 = r̃m 2
critical. This is the reason why, among the large number of op-
Note that (16) can be used to try to compute the position
timization algorithms, the use of Particle Swarm Optimization
estimate t̃. Unfortunately, even if (14) always has a single
(PSO) [22] was chosen for initial experiments. Experimental
solution, (16) may not have a single solution because of the
results (e.g., [5], [20]) showed that the use of PSO to im-
errors introduced in the estimation of distances. In general,
plement localization as optimization proved to be effective in
(16) may have no solutions, and only rarely it has one solution.
solving the loss of accuracy caused by critical arrangements
Note that (16) can be rewritten in matrix notation as follows
of ANs. Unfortunately, PSO has two severe issues that limits
its applicability to solve practical localization problems. First, 1m t̃⊺ t̃ − 2At̃ = k̃, (17)
just like all other general optimization algorithms, PSO does where 1m ∈ Rm is a vector whose components are all equal to
not guarantee that global extrema of studied functions are 1, k̃ ∈ Rm is a vector whose i−th element is k̃i = r̃i2 −||ai ||2 ,
computed in finite time. Second, the performance of the PSO and A is the following m × 3 anchor matrix
algorithm depends on a set of parameters whose optimal ⊺
values can be determined only by simulating the behavior a1
a⊺2
of the algorithm in the considered environment. Therefore,
A = . . (18)
alternatives to the use of PSO to implement localization as ..
optimization are under experimentation. Among them, the a⊺m
16
Workshop "From Objects to Agents" (WOA 2019)
Many localization algorithms (e.g., [18]) perform algebraic rewriting a localization problem into a related optimization
manipulations of matrices whose entries depend on the po- problem that aims at finding a global minimum of the lo-
sitions of the TN and of the ANs. The matrices involved calization cost function f defined in (20). Given that one of
in such computations can become ill-conditioned in critical the adopted assumptions in this paper is that the considered
situations, and this represents one of the inherent problems environment can be split into possibly overlapping boxes, as
of such algorithms. For example, it is evident from (18) that discussed in Section I, the considered minimization problems
the anchor matrix is rank deficient if all ANs are placed at the can be restricted to boxes. In summary, the POSTI algorithm
same height because the entries in its last column are all equal. estimates the position of the TN by finding a global minimum
As discussed in detail in Section V, the TSML algorithm is not of a polynomial function f of n = 3 variables and multi-
applicable if all ANs are installed at the same height because degree L = (4, 4, 4) over a given box, which corresponds to
it would require to invert a singular matrix. Similarly, if the the considered indoor environment.
heights of the ANs are not exactly the same, but they are Note that the accuracy of the POSTI algorithm does not
sufficiently close, the TSML algorithm produces large errors depend on the positions of the TN or of the ANs, and therefore
because the matrix to be inverted is strongly ill-conditioned. it can be used when the accuracy of ordinary algorithms,
If (17) has exactly one solution, such a solution can be like the TSML algorithm, degrades sensibly. In addition, note
computed by using the equations of the system to state a proper that experimental results discussed in Section V show that
minimization problem. Actually, the solution t̃ of (17), which the POSTI algorithm ensures an accuracy of localization
is the estimated position of the TN, can be found by solving comparable to the accuracy of the TSML algorithm when the
the following minimization problem arrangement of ANs is not critical. The comparison with the
TSML algorithm is particularly relevant because the TSML
t̃ = argmin f (x), (19) algorithm is an accepted reference to assess the performance
x∈D
of localization algorithms. Actually, the TSML algorithm is
where D ⊆ R3 is the region of space where the TN is particularly relevant in the context of localization because it is
supposed to be located, and f : D 7→ R is the function to proved [23] that it can attain the Cramér-Rao lower bound [24]
be minimized, normally called localization cost function for the position estimator.
f (x) = ||1m x⊺ x − 2Ax − k̃||2 . (20) The literature on nonlinear programming proposes several
algorithms to minimize a polynomial function. When the
Even if (17) does not have exactly one solution, the refor- minimum is searched in a box, as in the scenarios considered
mulation of (17) in terms of a minimization problem can in this paper, most of the minimization algorithms make use
still provide an estimate of the position of the TN. Note that of the properties of the Bernstein polynomial basis (e.g., [25]
function f is a polynomial function of three variables whose for a comprehensive review of the subject and a historical ret-
multi-degree is L = (4, 4, 4). Also note that since it is assumed rospective). Actually, well-known properties of the Bernstein
that the indoor environment can be split into disjoint boxes, polynomial basis can be used to compute lower and upper
D can be considered as a box without loss of generality. bounds of a polynomial function over a given box, and such
bounds can be used to drive the subdivision of the box using
IV. T HE POSTI A LGORITHM a branch-and-bound approach in search for a global minimum
The Polynomial Optimization using Subdivision Trees (e.g., [26]). In particular, for each subdivision, the so called
(POST) algorithmic framework is introduced in an upcoming Bernstein coefficients are computed on the two resulting sub-
paper as an effective means to support the localization as op- boxes, and such coefficients are used to obtain the needed
timization approach described in previous section. The POST lower and upper bounds of the polynomial function for the two
framework is completed with a suitable method to compute sub-boxes. Unfortunately, such an approach is problematic in
lower and upper bounds of polynomial functions to obtain an terms of computational cost when the polynomial function to
algorithm to solve the minimization problems derived from minimize is obtained from a localization problem because of
localization problems. In this paper, the instantiation of the the number n = 3 of variables and because of multi-degree
POST framework that uses interval arithmetic to compute L = (4, 4, 4) of the polynomial function. Even if effective
lower and upper bounds of polynomial functions over boxes, algorithms for the computation of Bernstein coefficients are
normally called POSTI algorithm, is described. The experi- available (e.g., [27]–[31]), a total of 125 Bernstein coefficients
mental results presented in Section V were obtained using an are needed for each considered sub-box in the worst case, and
implementation of the POSTI algorithm integrated within the preliminary tests showed that needed computation cost is too
localization add-on module for JADE recalled in Section I. high for the intended applications of indoor localization briefly
The POSTI algorithm uses classic results from the literature mentioned in Section I.
on interval arithmetic (e.g., [21]) to compute lower and upper Classic results from the literature on interval arithmetic can
bounds of a given polynomial function over a given box. Then, be used to compute lower and upper bounds for a given poly-
the POSTI algorithm uses such bounds to drive an ordinary nomial function over a given box instead of using the bounds
subdivision method to solve the minimization problem at hand. provided by Bernstein coefficients. The bounds obtained from
In detail, the POSTI algorithm is based on the possibility of the application of interval arithmetic are typically less strict
17
Workshop "From Objects to Agents" (WOA 2019)
than the bounds obtained using Bernstein coefficients, but the
needed computation cost for n = 3 variables and multi-degree
L = (4, 4, 4) is reduced and it is compatible with the intended 3
applications of indoor localization. In particular, the following
2
proposition can be used to compute lower and upper bounds
z [m]
of a polynomial function over a box. The proposition is shown 1 3
without proof because it is a classic result of the literature on
interval arithmetic (e.g., [21]). 0
4
Proposition 1: Given a polynomial function p : Rn 7→ R of 10 7
9
n ∈ N+ variables with multi-degree L ∈ Nn 8
8 2
7 11
1
X
p(x) = aI xI , (21) 6
12
I≤L 5 6
y [m] 4
5
if B = [b, b] ⊂ Rn is a box from b ∈ Rn to b ∈ Rn , then 3
10 3
4
2
1 9 2
p ≤ min p(x) max p(x) ≤ p, (22) 0 0
1 x [m]
x∈B x∈B
where p(B) = [p, p] is computed using interval arithmetic. Figure 1. A schematization of the considered indoor environment, i.e., a 4 m
wide, 10 m long, and 3 m tall empty corridor, is shown together with the
twelve positions of the TN used for experiments (numbered in red).
V. E XPERIMENTAL RESULTS
In order to test the applicability of the POSTI algorithm for
indoor localization, an experimental campaign was performed numbers from 1 to 4, and their coordinates are expressed in
in an indoor environment, as discussed in this section. Re- meters in the coordinate system shown in the figure as
sults were obtained using a commercial Android smartphone
t1 = (0, 0, 3) t2 = (2, 0, 3)
equipped with the necessary hardware and software to com-
municate with UWB tags and to derive distance estimates t3 = (2, 5, 3) t4 = (0, 5, 3).
from the time of flight of UWB signals. The smartphone used The four positions of the TN whose heights are all equal
for experiments was a SpoonPhone, produced by BeSpoon to 1.5 m are associated with numbers from 5 to 8, and
(www.bespoon.com), which is, to the best of our knowledge, their coordinates are expressed in meters in the considered
the only commercial smartphone equipped with a dedicated coordinate system shown in Fig. 1 as
programming interface to easily estimate the distance between
the smartphone and a paired UWB tag. In the considered t5 = (0, 0, 1.5) t6 = (2, 0, 1.5)
experiments, four UWB tags were used as active ANs and t7 = (2, 5, 1.5) t8 = (0, 5, 1.5).
distance acquisition was performed by the SpoonPhone, which
The four positions of the TN near the floor are associated with
was used as TN. The collected distance estimates were then
numbers from 9 to 12, and their coordinates are expressed in
processed according to the POSTI algorithm to obtain esti-
meters in the coordinate system shown in the figure as
mates of the position of the TN. In order to compare the
performance of the POSTI algorithm with that of a known t9 = (0, 0, 0) t10 = (2, 0, 0)
and appreciated algorithm, the distance estimates passed to t11 = (2, 5, 0) t12 = (0, 5, 0).
the implementation of the POSTI algorithm were also passed
to the implementation of the TSML algorithm that is readily The localization accuracy of the two considered algorithms
available in the localization add-on module for JADE. is measured in terms of the following position error
The indoor environment used to perform reported experi- e = t − t̃, (23)
ments is a 4 m wide, 10 m long, and 3 m tall corridor. All
obstacles were removed from the corridor during experiments where t is the true position of the TN and t̃ is the estimated
to guarantee that all ANs were in line of sight with the position of the TN. Since four different scenarios correspond-
TN, and to reduce errors caused by multipath interference. ing to four different arrangements of the ANs were studied,
Four different scenarios were considered, which correspond and since experimental results were derived in correspondence
to different configurations of the ANs. For each scenario, of twelve positions of the TN for each scenario, a total of
twelve different positions of the TN were considered. Such 48 experimental configurations were considered. For each
positions are shown as red dots in Fig. 1, which also shows a considered experimental configuration, r = 100 estimates of
schematization of the considered environment. Three different the distance between the TN and each AN were acquired,
heights for the TN were considered, i.e., 3 m (near the ceiling), and such estimates were used to derive r position estimates
1.5 m, and 0 m (near the floor). The four positions of the TN using the POSTI algorithm. Then, r position estimates were
near the ceiling of the corridor are associated in Fig. 1 with also derived by processing the same distance estimates with
18
Workshop "From Objects to Agents" (WOA 2019)
Table I Table II
E XPERIMENTAL R ESULTS IN S CENARIO 1 E XPERIMENTAL R ESULTS IN S CENARIO 2
Position eP [m] σP [m] eT [m] σT [m] Position eP [m] σP [m] eT [m] σT [m]
t1 0.352 0.236 N/A N/A t1 0.400 0.489 0.430 0.198
t2 0.284 0.103 N/A N/A t2 0.403 0.231 0.997 2.137
t3 0.249 0.411 N/A N/A t3 0.628 0.580 2.190 2.572
t4 0.251 0.258 N/A N/A t4 0.305 0.158 0.801 1.135
t5 0.316 0.093 N/A N/A t5 0.350 0.174 1.421 2.468
t6 0.316 0.070 N/A N/A t6 0.348 0.192 0.740 0.663
t7 0.730 0.247 N/A N/A t7 0.793 0.229 0.754 0.818
t8 0.608 0.185 N/A N/A t8 0.585 0.197 0.856 0.634
t9 0.255 0.088 N/A N/A t9 0.246 0.092 2.387 2.903
t10 0.392 0.259 N/A N/A t10 0.341 0.188 1.359 1.746
t11 0.312 0.220 N/A N/A t11 0.435 0.189 1.679 1.575
t12 0.506 0.151 N/A N/A t12 0.440 0.099 1.804 2.313
the TSML algorithm. Finally, the average and the standard Results show that the accuracy of the POSTI algorithm is
deviation of the Euclidean norm of e over the r acquisitions similar to the accuracy measured in the first scenario. As a
obtained using the POSTI algorithm, denoted as eP and matter of fact, the values of eP vary between 0.246 m and
σP , were computed together with the corresponding values, 0.793 m, and the values of σP vary between 0.092 m and
denoted as eT and σT , obtained using the TSML algorithm. 0.580 m. The similarity between the results obtained in the
two scenarios is not surprising because the position of the
A. Scenario 1
ANs did not change significantly.
In the first scenario, the four ANs are placed at the same Table II also shows the results related to the accuracy
height near the ceiling of the considered environment. Using of the TSML algorithm, expressed in terms of eT and σT .
the coordinate system shown in Fig. 1, the positions of the Observe that such results are affected by significant errors in
ANs have the following coordinates expressed in meters correspondence of some positions of the TN. In detail, the
a1 = (0, 0, 3) a2 = (4, 0, 3) value of the average error eT is larger than 2 m when the TN
was positioned in t3 and t9 , and it is larger than 1 m when
a3 = (0, 10, 3) a4 = (4, 10, 3).
the TN was positioned in t5 , t10 , t11 , and t12 . Moreover, for
As discussed in Section I, the fact that all ANs share the 8 positions out of 12, the value of σT is larger than 1 m and
same height is problematic for ordinary algorithms, and the it is often larger than 2 m, which emphasizes the inaccuracy
TSML algorithm is actually inapplicable in this scenario. For of position estimates obtained with the TSML algorithm for
this reason, only the accuracy of the POSTI algorithm can be the studied arrangement of ANs. From obtained results it can
evaluated. Table I shows the results related to the accuracy be concluded that the performance of the POSTI algorithm is
of the POSTI algorithm using the values eP and σP defined good in this scenario, while the TSML algorithm leads to very
above for the r = 100 experiments and for each one of inaccurate position estimates.
the twelve positions of the TN shown. Observe that values
of eP vary from 0.249 m to 0.730 m. Therefore, it can C. Scenario 3
be concluded that the accuracy of localization is compatible As observed in the previous scenario, the reduction of the
with the intended applications discussed in Section I. The height of two ANs by 0.5 m is not sufficient to obtain accurate
values of standard deviations are also compatible with practical position estimates with the TSML algorithm. For this reason,
applications because they vary from 0.07 m to 0.411 m. in this scenario the height of two ANs is further reduced with
respect to the previous scenario and it equals 1.5 m. Hence,
B. Scenario 2 using the coordinate system shown in Fig. 1, the positions of
In the second scenario, the height of two of the four ANs the ANs have the following coordinates expressed in meters
is reduced with respect to the previous scenario. Using the
a1 = (0, 0, 1.5) a2 = (4, 0, 3)
coordinate system shown in Fig. 1, the positions of the ANs
have the following coordinates expressed in meters a3 = (0, 10, 1.5) a4 = (4, 10, 3).
a1 = (0, 0, 2.5) a2 = (4, 0, 3) Observe that the new height of the two relocated ANs may not
be sufficient to guarantee visibility in practical applications
a3 = (0, 10, 2.5) a4 = (4, 10, 3).
because of the possible presence of obstacles. However, in
Table II shows the accuracy of the algorithms in terms of the considered scenario, the corridor is empty and, therefore,
eP and σP (evaluated using the POSTI algorithm), and of eT visibility is guaranteed just like in previous scenarios.
and σT (evaluated using the TSML algorithm). All values are Table III shows the accuracy of the algorithms in terms of
computed using r = 100 repetitions of the experiments for eP and σP (evaluated using the POSTI algorithm), and of eT
each one of the twelve positions of the TN shown in Fig. 1. and σT (evaluated using the TSML algorithm). All values are
19
Workshop "From Objects to Agents" (WOA 2019)
Table III Table IV
E XPERIMENTAL R ESULTS IN S CENARIO 3 E XPERIMENTAL R ESULTS IN S CENARIO 4
Position eP [m] σP [m] eT [m] σT [m] Position eP [m] σP [m] eT [m] σ T [m]
t1 0.335 0.382 0.314 0.126 t1 0.275 0.068 0.583 0.551
t2 0.331 0.126 0.345 0.193 t2 0.309 0.065 0.298 0.111
t3 0.533 0.388 0.479 0.708 t3 0.326 0.333 0.313 0.336
t4 0.303 0.064 0.573 0.103 t4 0.454 0.144 0.783 0.374
t5 0.404 0.276 0.446 0.745 t5 0.350 0.213 0.426 0.446
t6 0.417 0.290 0.196 0.098 t6 0.271 0.111 0.315 0.103
t7 0.557 0.474 0.896 0.706 t7 0.218 0.328 0.385 0.509
t8 0.339 0.242 0.566 0.234 t8 0.241 0.121 0.600 0.114
t9 0.287 0.070 0.756 0.745 t9 0.308 0.070 0.257 0.104
t10 0.419 0.358 0.867 0.923 t1 0 0.483 0.420 0.627 0.589
t11 0.335 0.161 0.650 0.456 t1 1 0.346 0.309 0.878 0.194
t12 0.467 0.090 0.626 0.248 t1 2 0.409 0.069 0.782 0.168
computed using r = 100 repetitions of the experiments for eT and σT (evaluated using the TSML algorithm). All values
each one of the twelve positions of the TN shown in Fig. 1. are computed using r = 100 repetitions of the experiments
Results show that the accuracy of the POSTI algorithm is for each one of the twelve positions of the TN shown in
similar to the accuracy measured in the first and in the second Fig. 1. Results show that the accuracy of the POSTI algorithm
scenarios. Actually, the values of eP vary between 0.287 m is similar to the accuracy measured in the first, second, and
and 0.557 m, and the values of σP vary between 0.064 m and third scenarios. As a matter of fact, the values of eP vary
0.474 m. The results obtained in the considered scenarios are between 0.218 m and 0.483 m, and values of σP vary between
not surprising because the accuracy of the POSTI algorithm 0.065 m and 0.420 m. Such results are in agreement with
is expected to be independent from the position of ANs. those obtained in previous scenarios, which is not surprising,
Table III also shows the results related to the accuracy of since the accuracy of the POSTI algorithm is expected to be
the TSML algorithm, expressed in terms of eT and σT . In independent from the position of ANs.
this scenario, results obtained with the TSML algorithm are Table IV also shows the accuracy of the TSML algorithm
sufficiently accurate for many applications. As a matter of using the quantities defined previously for the r = 100
fact, the values of the average error eT vary between 0.196 m repetitions of experiments and for the twelve positions of
and 0.896 m, and the values of the standard deviation σT the TN shown in Fig. 1. In this case, the accuracy obtained
vary between 0.098 m and 0.923 m. A comparison between with the TSML algorithm is similar to the accuracy obtained
the values of the average errors eP obtained with the POSTI in the third scenario. Actually, the values of the average
algorithm and the values of the average errors eT obtained error eT vary between 0.257 m and 0.878 m, and the values
with the TSML algorithm shows that the characteristics of the of the standard deviation σT vary between 0.103 m and
two algorithms are comparable in this scenario. Analogous 0.589 m, which ensures an accuracy of localization compatible
considerations can be derived from the values of the standard with intended applications discussed in Section I. As for the
deviation σP obtained with the POSTI algorithm and the previous scenarios, the results reported in Table IV show that
value of the standard deviation σT obtained with the TSML the performance of the two algorithms are similar in this case.
algorithm, even though the values of σP are actually lower
than the corresponding values of σT for 9 out of the 12 VI. C ONCLUSIONS
positions of the TN.
The POSTI algorithm is discussed in this paper as a
D. Scenario 4 viable opportunity to support the localization as optimization
In this scenario, the height of the two relocated ANs is approach (e.g., [5], [20]). The POSTI algorithm is based on
further reduced and they are placed near the floor of the consolidated results from the literature on nonlinear program-
corridor while the other two ANs are still at their original ming, and it relies on a subdivision method to search for
positions. Using the coordinate system shown in Fig. 1, the the position of the TN in the considered indoor environment,
positions of the ANs are expressed in meters as which is assumed to be composed of possibly overlapping
a1 = (0, 0, 0) a2 = (4, 0, 3) rectangular cuboids. According to the current implementation
of the algorithm, the TN can actively obtain estimates of the
a3 = (0, 10, 0) a4 = (4, 10, 3).
distances from ANs using UWB. An alternative implemen-
As in the previous scenario, the new height of the two tation of the algorithm that uses WiFi signaling to obtain
relocated ANs may not be sufficient to guarantee visibility distance estimates was experimented, but the accurate and
in practical applications because of the presence of obstacles. robust distance estimates that UWB provides ensures far better
Table IV shows the accuracy of the algorithms in terms of localization performance and such an implementation is not
eP and σP (evaluated using the POSTI algorithm), and of discussed in this paper.
20
Workshop "From Objects to Agents" (WOA 2019)
One of the most relevant characteristics of the POSTI algo-
[8] S.-Y. Teng, W.-S. Ku, and K.-T. Chuang, “Toward mining stop-by
rithm is that it provides a level of accuracy that is independent behaviors in indoor space,” ACM Transactions on Spatial Algorithms
from the position of the ANs in the environment. This is not and Systems, vol. 3, no. 2, pp. 7:1–7:38, 2017.
true for other localization algorithms, like the TSML algo- [9] X. Zhou, T. Chen, D. Guo, X. Teng, and B. Yuan, “From one to crowd: A
survey on crowdsourcing-based wireless indoor localization,” Frontiers
rithm, whose performance significantly degrades when prob- of Computer Science, vol. 12, no. 3, pp. 423–450, 2018.
lematic arrangements of ANs are used. Experimental results [10] P. Pannuto, B. Kempke, L.-X. Chuo, D. Blaauw, and P. Dutta, “Har-
shown in the last part of this paper confirm that the POSTI monium: Ultra wideband pulse generation with bandstitched recovery
for fast, accurate, and robust indoor localization,” ACM Transactions on
algorithm leads to accurate position estimates in all considered Sensor Networks, vol. 14, no. 2, pp. 11:1–11:29, 2018.
scenarios, independently from the positions of ANs. Actually, [11] X. Teng, D. Guo, Y. Guo, X. Zhou, and Z. Liu, “CloudNavi: Toward
the average localization errors and the corresponding standard ubiquitous indoor navigation service with 3D point clouds,” ACM
Transactions on Sensor Networks, vol. 15, no. 1, pp. 1:1–1:28, 2019.
deviations are independent from the considered position of the [12] S. Gezici and H. V. Poor, “Position estimation via Ultra-Wide-Band
TN and from the adopted arrangement of ANs. At the opposite, signals,” Proceedings of the IEEE, vol. 97, no. 2, pp. 386–403, 2009.
significant localization errors are produced by the TSML [13] Z. Sahinoglu, S. Gezici, and I. Güvenc, Ultra-wideband positioning sys-
tems: Theoretical limits, ranging algorithms and protocols. Cambridge,
algorithm when ANs are installed in critical arrangements. In U.K.: Cambridge University Press, 2008.
detail, presented experimental results show that the POSTI al- [14] S. Monica and F. Bergenti, “Location-aware JADE agents in indoor
gorithm outperforms the TSML algorithm in terms of average scenarios,” in Proceedings of the 16th Workshop “From Objects to
Agents”, ser. CEUR Workshop Proceedings, vol. 1382. RWTH Aachen,
localization error and corresponding standard deviation when 2015, pp. 103–108.
considering scenarios where all the ANs are almost coplanar. [15] S. Monica and F. Bergenti, “Indoor localization of JADE agents without
Such a result is particularly significant because the TSML a dedicated infrastructure,” in Multiagent System Technologies, ser.
Lecture Notes in Computer Science, vol. 10413. Cham: Springer, 2017.
algorithm is often used as a reference for the assessment of [16] F. Bellifemine, F. Bergenti, G. Caire, and A. Poggi, “JADE – A
the performance of localization algorithms because it is well Java Agent DEvelopment framework,” in Multi-Agent Programming.
known [23] that it can attain the Cramér-Rao lower bound [24] Springer, 2005, pp. 125–147.
[17] G. Shen, R. Zetik, and R. S. Thomä, “Performance comparison of TOA
for the position estimator. and TDOA based location estimation algorithms in LOS environment,”
Finally, it is worth noting that the critical arrangements in Proceedings of the Workshop on Positioning, Navigation and Com-
of the ANs that make the use of the TSML impractical munication (WPNC 2008). Hannover: IEEE, 2008, pp. 71–78.
[18] F. Mekelleche and H. Haffaf, “Classification and comparison of range-
are those in which all the ANs are located at (roughly) the based localization techniques in wireless sensor networks,” Journal of
same height. Unfortunately, this is one of the most common Communications, vol. 12, no. 4, 2017.
arrangements in indoor environments, where all the ANs are [19] K. C. Ho, L. Xiaoning, and L.-o. Kovavisaruch, “Source localization
using TDOA and FDOA measurements in the presence of receiver
typically placed at the same height close to the ceilings of location errors: Analysis and solution,” IEEE Transactions on Signal
rooms to ensure a good line-of-sight coverage. According to Processing, vol. 55, no. 2, pp. 684–696, 2007.
such considerations, the use of the POSTI algorithm for robust [20] S. Monica and G. Ferrari, “Impact of the number of beacons in
PSO-based auto-localization in UWB networks,” in Applications of
and accurate localization seems a valid opportunity for envis- Evolutionary Computation, ser. Lecture Notes in Computer Science, vol.
aged applications of indoor localization, which demands that 7835. Berlin: Springer, 2013.
practical considerations regarding the line-of-sight coverage of [21] W. Tucker, Validated numerics: A short introduction to rigorous com-
putations. Princeton: Princeton University Press, 2011.
environments are seriously taken into consideration. [22] M. R. Bonyadi and Z. Michalewicz, “Particle swarm optimization for
single objective continuous space problems: A review,” Evolutionary
R EFERENCES Computation, vol. 25, no. 1, pp. 1–54, 2017.
[1] Z. Farid, R. Nordin, and M. Ismail, “Recent advances in wireless indoor [23] Y. T. Chan and K. C. Ho, “A simple and efficient estimator for hyperbolic
localization techniques and system,” Journal of Computer Networks and location,” IEEE Transactions on Signal Processing, vol. 42, no. 8, pp.
Communications, vol. 2013, 2013. 1905–1915, 1994.
[2] Y. Gu, A. Lo, and I. Niemegeers, “A survey of indoor positioning [24] J. Shao, Mathematical Statistics, ser. Springer Texts in Statistics. New
systems for wireless personal networks,” IEEE Communications Surveys York: Springer-Verlag, 2003.
& Tutorials, vol. 11, no. 1, pp. 13–32, 2009. [25] R. T. Farouki, “The Bernstein polynomial basis: A centennial retrospec-
[3] C. A. Patterson, R. R. Muntz, and C. M. Pancake, “Challenges in tive,” Computer Aided Geometric Design, vol. 29, no. 6, pp. 379–419,
location-aware computing,” IEEE Pervasive Computing, vol. 2, no. 2, 2012.
pp. 80–89, 2003. [26] J. Garloff, “The Bernstein algorithm,” Interval Computations, vol. 2, pp.
[4] S. Monica and F. Bergenti, “Location-aware social gaming with 154–168, 1993.
AMUSE,” in Advances in Practical Applications of Scalable Multi-agent [27] R. T. Farouki and V. T. Rajan, “Algorithms for polynomials in Bernstein
Systems, the PAAMS Collection, PAAMS 2016, ser. Lecture Notes in form,” Computer-Aided Geometric Design, vol. 5, no. 1, pp. 1–26, 1988.
Computer Science, vol. 9662. Sevilla: Springer, 2016, pp. 36–47. [28] J. Garloff and A. P. Smith, “Solution of systems of polynomial equations
[5] S. Monica and G. Ferrari, “A swarm-based approach to real-time 3D by using Bernstein expansion,” in Symbolic Algebraic Methods and
indoor localization: Experimental performance analysis,” Applied Soft Verification Methods. Vienna: Springer, 2001, pp. 87–97.
Computing, vol. 43, pp. 489–497, 2016. [29] S. Ray and P. S. Nataraj, “An efficient algorithm for range computation
[6] S. Purushotham and C.-C. J. Kuo, “Personalized group recommender of polynomials using the Bernstein form,” Journal of Global Optimiza-
systems for location- and event-based social networks,” ACM Transac- tion, vol. 45, pp. 403–426, 2009.
tions on Spatial Algorithms and Systems, vol. 2, no. 4, pp. 16:1–16:29, [30] A. P. Smith, “Fast construction of constant bound functions for sparse
2016. polynomials,” Journal of Global Optimization, vol. 43, no. 2, pp. 445–
[7] G. Skoumas, D. Pfoser, A. Kyrillidis, and T. Sellis, “Location estimation 458, 2009.
using crowdsourced spatial relations,” ACM Transactions on Spatial [31] S. Ray and P. S. Nataraj, “A matrix method for efficient computation of
Algorithms and Systems, vol. 2, no. 2, pp. 5:1–5:23, 2016. Bernstein coefficients,” Reliable Computing, vol. 17, pp. 40–71, 2012.
21