Interval arithmetic to support effective indoor positioning of software agents

Abstract

The provision of advanced location-based services in indoor environments is based on the possibility of estimating the positions of mobile devices with sufficient accuracy and robustness. An algorithm to allow a software agent hosted on a mobile device to estimate the position of its device in a known indoor environment is proposed under the ordinary assumption that fixed beacons are installed in the environment at known locations. Rather than making use of geometric considerations to estimate the position of the device, the proposed algorithm first transforms the localization problem into a related optimization problem, which is then solved by means of interval arithmetic to provide the agent with accurate and robust position estimates. The adopted approach solves a major problem that severely limits the accuracy of the position estimates that ordinary geometric algorithms provide when the beacons are positioned to maximize line-of-sight coverage. Experimental results confirm that the proposed algorithm provides position estimates that are independent of the positions of the beacons, and they show that the algorithm outperforms a well-known geometric algorithm.

Keywords

Localization as optimization indoor localization software agents

1 Introduction

The relevant possibilities that advanced location-based services are expected to provide are severely limited by the lack of tools to accurately and robustly associate mobile devices with their positions in known indoor environments (e.g., [1]). Solutions to problems related to indoor positioning have recently been proposed in the literature (e.g., [2 –4]), but the practical problem of associating mobile devices with sufficiently accurate estimates of their positions is still open and extensively studied (e.g., [5, 6]).

Software agents are expected to play a crucial role to support the provision of advanced location-based services (e.g., [7]) because one of their most interesting characteristics is that they exhibit context-aware behaviors, which are known to be especially relevant when agents are hosted on mobile devices (e.g., [8]). Agents hosted on mobile devices can use the position of their devices as relevant sources of context information to achieve their goals and to serve their users. This is the reason why the experiments documented in this paper were performed using the localization add-on module [9] for the Java Agent DEvelopment framework (JADE) [10]. The localization add-on module for JADE provides interested agents with timely information on their positions within a known indoor environment by means of pluggable localization algorithms. The module is in charge of interfacing the sensors provided by the hosting device to acquire ranging information, and it is also in charge of passing acquired ranging information to one of the available localization algorithms. The result of the application of the chosen localization algorithm is an estimate of the current position of the device, which is immediately delivered to the interested agents on the device.

This paper proposes a localization algorithm, discussed in Section 4, that has been recently included in the localization add-on module for JADE. The Polynomial Optimization using Subdivision Trees with Interval arithmetic (POST_I) algorithm can be used to compute estimates of the position of a mobile device, called Target Node (TN) hereafter, under the assumption that a few beacons, called Anchor Nodes (ANs) hereafter, are available at fixed and known locations. The POST_I algorithm computes estimates of the position of the TN using estimates of the distances from the TN to the ANs that are transparently acquired by the localization add-on module for JADE using one of the ranging technologies provided by the TN. With minor loss of generality, the POST_I algorithm assumes that the considered indoor environment is composed of possibly overlapping rectangular cuboids, which are called boxes hereafter.

The POST_I algorithm is based on the localization as optimization approach (e.g., [11, 12]), and, in particular, it is the specific instantiation of the Polynomial Optimization using Subdivision Trees (POST) algorithmic framework that uses interval arithmetic (e.g., [13]). The localization as optimization approach was proposed to solve a major problem of ordinary localization algorithms (e.g., [14, 15]) that occurs when the ANs are distributed in the environment in critical arrangements. Actually, a significant loss of the accuracy of ordinary localization algorithms is normally observed when the ANs are coplanar because some of the matrices manipulated by such algorithms become strongly ill-conditioned (e.g., [11, 12]). On the contrary, the algorithms based on the localization as optimization approach provide position estimates that are independent of the arrangement of the ANs if suitable optimization algorithms are actually used, as discussed in Section 3. Therefore, the algorithms based on the localization as optimization approach are expected to play a crucial role to support indoor localization because they allow installing the ANs in the environment to maximize line-of-sight coverage, to minimize multipath interference, and to limit the problems caused by people, furniture, and other obstacles.

The accuracy of the POST_I algorithm was empirically studied by means of the experimental campaign discussed in Section 5. The experimental campaign was designed to assess the performance of the POST_I algorithm by means of a comparison with two well-known algorithms. The first algorithm is the Two-Stage Maximum-Likelihood (TSML) algorithm [16], which was chosen because it can attain the Cramér-Rao lower bound for the position estimator (e.g., [17]), and therefore it is an accepted point of reference to assess the performance of localization algorithms. The second algorithm is the PSO (localization) algorithm [18, 19], which was chosen because it is based on the localization as optimization approach but it uses Particle Swarm Optimization (PSO) [20] instead of the POST algorithmic framework. The experimental results discussed in Section 5, which extend the preliminary results shown in [21], confirm that the performance of the POST_I algorithm does not depend on the positions of the ANs. Moreover, they show that the POST_I algorithm outperforms the TSML algorithm, and they confirm that the accuracy of the POST_I algorithm is similar to the accuracy of the PSO algorithm.

It is worth noting that the applications in which indoor localization is expected to become particularly relevant in the near future include interactive visits to exhibitions and museums supported by educational games (e.g., [22, 23]), indoor location-based social networks (e.g. [24, 25]), and advanced automation of warehouses (e.g., [26, 27]). An average position error of about one meter is normally considered acceptable for such applications, and the experimental results discussed in Section 5 show that such an accuracy is feasible when the POST_I algorithm is used with ranging information obtained by means of Ultra-Wide Band (UWB) signaling (e.g., [28]).

This paper is organized as follows. Section 2 introduces the adopted notation, and it recalls the needed background results. Section 3 formalizes the studied localization problem, it presents the localization as optimization approach, and it briefly summarizes the TSML algorithm and the PSO algorithm. Section 4 concisely describes the POST algorithmic framework and the POST_I algorithm. Section 5 documents the results of the experimental campaign performed to assess the accuracy of the POST_I algorithm. Finally, Section 6 concludes the paper.

2 Notation and background results

This section provides a short summary of the notation normally used to study real functions of several real variables. The notation is used in Section 4.

Throughout the paper, $ℕ$ denotes the set of natural numbers, and $ℕ_{+}$ denotes the set of positive natural numbers. Given $n \in ℕ_{+}$ , a multi-index $I \in ℕ^{n}$ is defined as an n-tuple of natural numbers $I = (i_{1}, i_{2}, \dots, i_{n}) = (i_{k})_{k = 1}^{n} .$ (1) As usual, an uppercase letter is used to denote a multi-index, and the same letter, but lowercase and with a subscript, is used to denote its components. A multi-index $I \in ℕ^{n}$ can be used as exponent for $t \in ℝ^{n}$ , with $t = (t_{1}, t_{2}, \dots, t_{n}) = (t_{k})_{k = 1}^{n}$ , as follows $t^{I} = \prod_{k = 1}^{n} t_{k}^{i_{k}} .$ (2) As usual, a boldface letter is used to denote an n-tuple of real numbers considered as a column vector, and the same letter, but lightface and with a subscript, is used to denote its components. Note that the equality 0⁰ = 1 is adopted consistently in this paper.

Two multi-indices $I \in ℕ^{n}$ and $J \in ℕ^{n}$ can be added componentwise as follows $I + J = (i_{1} + j_{1}, i_{2} + j_{2}, \dots, i_{n} + j_{n}) .$ (3) Two multi-indices $I \in ℕ^{n}$ and $J \in ℕ^{n}$ can be compared according to the following partial order $I \leq J \Leftrightarrow i_{1} \leq j_{1} \land i_{2} \leq j_{2} \land \dots \land i_{n} \leq j_{n} .$ The following abbreviation is introduced for multi-indices $H \in ℕ^{n}$ , $I \in ℕ^{n}$ , and $J \in ℕ^{n}$ to express repeated sums

$\sum_{H \leq I \leq J} (\cdot) = \sum_{i_{1} = h_{1}}^{j_{1}} \sum_{i_{2} = h_{2}}^{j_{2}} \dots \sum_{i_{n} = h_{n}}^{j_{n}} (\cdot) .$ (4) It is common to omit H in (4), so that only I ≤ J remains, if H is the null multi-index $(0)_{k = 1}^{n}$ .

The multi-index notation is particularly useful to study polynomial functions of several variables. A polynomial function $p : ℝ^{n} \mapsto ℝ$ of $n \in ℕ_{+}$ real variables is normally written as $p (x) = \sum_{I \leq L} a_{I} x^{I},$ (5) where ${a_{I}}_{I \leq L} \subset ℝ$ is the set of the real coefficients of p, and $L \in ℕ^{n}$ is the multi-index that represents the multi-degree of p if a_L ≠ 0.

The POST algorithmic framework and its instantiations, like the POST_I algorithm, are based on the study of the bounds of polynomial functions over boxes, and therefore a notation for intervals and boxes is briefly introduced. A closed (real) interval from $\underline{a} \in ℝ$ to $\bar{a} \in ℝ$ is denoted as $[\underline{a}, \bar{a}] = {x \in ℝ : \underline{a} \leq x \leq \bar{a}},$ (6) and it equals the empty set if and only if $\underline{a} > \bar{a}$ . A singleton (real) interval that only contains $a \in ℝ$ is denoted as [a] = [a, a].

Analogously, given $n \in ℕ_{+}$ , a (real) box $B \subset ℝ^{n}$ from $\underline{b} \in ℝ^{n}$ to $\bar{b} \in ℝ^{n}$ , with $\underline{b} = ({\underline{b}}_{k})_{k = 1}^{n}$ and $\bar{b} = ({\bar{b}}_{k})_{k = 1}^{n}$ , is denoted as $B = [\underline{b}, \bar{b}] = [{\underline{b}}_{1}, {\bar{b}}_{1}] \times [{\underline{b}}_{2}, {\bar{b}}_{2}] \times \dots \times [{\underline{b}}_{n}, {\bar{b}}_{n}],$ and it equals the empty set if and only if ${\underline{b}}_{i} > {\bar{b}}_{i}$ for some 1 ≤ i ≤ n. Note that $B_{i} = [{\underline{b}}_{i}, {\bar{b}}_{i}] \subset ℝ$ , where 1 ≤ i ≤ n, denotes the i-th closed interval used to form the nonempty box B.

The introduced notation is used in the context of interval arithmetic (e.g., [13]) to express computations whose arguments and results are closed intervals. The sum of two nonempty closed intervals $A = [\underline{a}, \bar{a}] \subset ℝ$ and $C = [\underline{c}, \bar{c}] \subset ℝ$ can be defined as follows $A + C = [\underline{a} + \underline{c}, \bar{a} + \bar{c}] .$ (7) Similarly, the product of the same nonempty intervals can be defined as follows $A \cdot C = [min M, max M],$ (8) where $M = {\underline{a} \underline{c}, \underline{a} \bar{c}, \bar{a} \underline{c}, \bar{a} \bar{c}}$ . The definition of the product among intervals allows defining the m-th power of a closed interval A for $m \in ℕ_{+}$ . Note that [0] ⁰ = [1] is adopted consistently in this paper.

Given $n \in ℕ_{+}$ , a nonempty box $B \subset ℝ^{n}$ , and a multi-index $I \in ℕ^{n}$ , the following notation that only uses products among intervals is normally adopted in interval arithmetic $B^{I} = \prod_{k = 1}^{n} B_{k}^{i_{k}} .$ (9) Using the introduced notation for intervals and boxes, a polynomial function $p : ℝ^{n} \mapsto ℝ$ of $n \in ℕ_{+}$ real variables can be extended to work on boxes. For any nonempty box $B \subset ℝ^{n}$ , it is possible to compute $p (B) = \sum_{I \leq L} [a_{I}] B^{I},$ (10) where the real coefficients of the polynomial function are used to form singleton intervals. Using the introduced notation, it is easy to prove that p (B) is a closed interval that includes the range of the polynomial function p computed over the box B (e.g. [13]).

3 The localization problem and its algorithms

The localization problem assumes that m ≥ 4 static ANs are positioned at known locations in the indoor environment. The positions of the ANs are denoted as $a_{i} \in ℝ^{3}$ , where 1 ≤ i ≤ m. The true position of the TN is denoted as $t \in ℝ^{3}$ , and the true distance between the TN and the i-th AN can be expressed as $r_{i} = | | t - a_{i} | | .$ (11)

From a geometric point of view, the position of the TN can be computed by intersecting m spheres, the i-th of which is centered in a_i and has radius r_i. The equations of the m spheres are grouped in the following system of nonlinear equations, whose unique solution corresponds to the true position of the TN

${\begin{matrix} | | t - a_{1} | |^{2} & = r_{1}^{2} \\ | | t - a_{2} | |^{2} & = r_{2}^{2} \\ ⋮ \\ | | t - a_{m} | |^{2} & = r_{m}^{2} . \end{matrix}$ (12)

The position of the TN is unknown in actual localization scenarios, and it must be computed using the distance estimates obtained by means of one of the available ranging technologies. In the following, the estimated position of the TN is denoted as $\tilde{t} \in ℝ^{3}$ , while the estimated distance between the TN and the i-th AN is denoted as ${\tilde{r}}_{i} = | | \tilde{t} - a_{i} | | .$ (13) The geometric considerations mentioned previously suggest that the estimated position of the TN is expected to satisfy the following system of nonlinear equations, which is obtained by replacing the true values with the estimated values in (12) ${\begin{matrix} | | \tilde{t} - a_{1} | |^{2} & = {\tilde{r}}_{1}^{2} \\ | | \tilde{t} - a_{2} | |^{2} & = {\tilde{r}}_{2}^{2} \\ ⋮ \\ | | \tilde{t} - a_{m} | |^{2} & = {\tilde{r}}_{m}^{2} . \end{matrix}$ (14) In contrast with previous considerations on the number of solutions of (12), it is worth noting that (14) does not normally have a single solution because of the errors introduced in the estimation of distances. Therefore, a localization algorithm (e.g., [15]) is needed to compute a solution to the localization problem (14) that appropriately estimates the position of the TN with the needed accuracy and robustness.

3.1 Localization as optimization

The localization as optimization approach was proposed in previous works (e.g., [11, 18]) to solve the problems related to ill-conditioned matrices that ordinary localization algorithms exhibit for critical arrangements of the ANs, as discussed in Section 1. In particular, the localization as optimization approach is based on the possibility of reformulating a localization problem as a related optimization problem. First, note that the localization problem (14) can be rewritten in matrix notation as $1 {\tilde{t}}^{⊤} \tilde{t} - 2 A \tilde{t} = \tilde{k},$ (15) where $1 \in ℝ^{m}$ is a column vector whose components are all equal to 1, $\tilde{k} \in ℝ^{m}$ is a column vector whose i-th component is ${\tilde{k}}_{i} = {\tilde{r}}_{i}^{2} - | | a_{i} | |^{2}$ , and A is the following m × 3 anchor matrix

$A = (\begin{matrix} a_{1}^{⊤} \\ a_{2}^{⊤} \\ ⋮ \\ a_{m}^{⊤} \end{matrix}) .$ (16)

A solution $\tilde{t}$ of the matrix equation (15) corresponds to an estimate of the position of the TN, and it can be found by solving the following minimization problem

$\underset{x \in D}{\tilde{t} = argmin λ (x),}$ (17)

where $D \subseteq ℝ^{3}$ is the domain in which the TN is supposed to be located, and $λ : D \mapsto ℝ$ is the function to minimize, normally called localization cost function $λ (x) = | | 1 x^{⊤} x - 2 A x - \tilde{k} | |^{2} .$ (18) The reformulation of the original localization problem (14) as the related optimization problem (17) ensures that the localization problem can be solved by resorting to one of the algorithms documented in the vast literature on nonlinear optimization.

3.2 The TSML algorithm

The Two-Stage Maximum-Likelihood (TSML) algorithm [16] is a well-known and appreciated localization algorithm that directly solves the localization problem (14). It is normally considered as a point of reference to assess the performance of other localization algorithms because it can attain the Cramér-Rao lower bound for the position estimator [17].

The TSML algorithm is structured in two cascaded phases. First, the localization problem (14) is rewritten in matrix notation as $G v = {\tilde{h}}_{1}$ (19) using the following definitions to embed in (19) the characteristics of the localization problem

(20)

Note that (19) is not a linear system of equations because the last component of v is related to its first three components. However, in the first phase of the algorithm, (19) is considered as linear, and it is solved using the maximum-likelihood approach, so that its solution v can be expressed as $v = (G^{⊤} W_{1} G)^{- 1} G^{⊤} W_{1} {\tilde{h}}_{1},$ (21) where W₁ is a positive definite matrix. Observe that the simplest choice for W₁ is the identity matrix, but another possible choice for W₁ is suggested in [16] on the basis of the least squares approach. However, the experiments discussed in Section 5 were performed using the identity matrix.

The computation of v using (21) does not allow expressing the solutions to the localization problem (14) because the last component of v is related to its first three components. In order to take such a dependence into account, the second phase of the TSML algorithm is needed, and a second system of equations is derived and solved. Given the explicit expression of v obtained using (21), the following linear system of equations is considered in the second phase of the algorithm $H w = {\tilde{h}}_{2},$ (22) where $\begin{matrix} H = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}) w = (\begin{matrix} {\tilde{t}}_{1}^{2} \\ {\tilde{t}}_{2}^{2} \\ {\tilde{t}}_{3}^{2} \end{matrix}) {\tilde{h}}_{2} = (\begin{matrix} v_{1}^{2} \\ v_{2}^{2} \\ v_{3}^{2} \\ v_{4} \end{matrix}) . \end{matrix}$ Note that (22) is linear, and it can be solved according to the maximum-likelihood approach as $w = (H^{⊤} W_{2} H)^{- 1} H^{⊤} W_{2} {\tilde{h}}_{2},$ (23) where W₂ is a positive definite matrix. The simplest choice for W₂ is the identity matrix, but different choices can be considered, as discussed in [14]. However, the experiments presented in Section 5 were performed using the identity matrix.

Given the explicit expression of w obtained using (23), the estimated position of the TN can be finally computed as $\tilde{t} = U s,$ (24) where U is a 3 × 3 diagonal matrix whose diagonal entries are u_i,i = sgnv_i, with 1 ≤ i ≤ 3, and s depends on w as follows $s = (\sqrt{| w_{1} |}, \sqrt{| w_{2} |}, \sqrt{| w_{3} |}) .$ (25) Even if the TSML algorithm is an accepted point of reference for localization algorithms, its application is problematic when manipulated matrices are ill-conditioned. For example, the TSML algorithm is not applicable if all the ANs are installed at the same height because it requires to invert G^⊤W₁G, which is singular in this case. Similarly, if the heights of the ANs are not exactly the same, but they are sufficiently close, the TSML algorithm introduces large errors because the matrix that it needs to invert is strongly ill-conditioned. Note that this problem is common to many localization algorithms, and it is neither related to the precision of the ranging technology nor to the floating-point accuracy of computation. The only way to prevent the problem is to relocate the ANs, which is often impractical in indoor scenarios because the choices regarding the positions of the ANs are often driven by pragmatic considerations intended to maximize line-of-sight coverage.

3.3 The PSO algorithm

The localization as optimization approach was proposed (e.g., [11, 12]) to solve the problems caused by ill-conditioned matrices that many ordinary localization algorithms, like the TSML algorithm, exhibit for critical arrangements of the ANs. All the localization algorithms that rely on the localization as optimization approach first transform a localization problem into a related optimization problem, and then they solve the obtained optimization problem to estimate the position of the TN. However, since many optimization algorithms available in the literature have severe problems related to ill-conditioned matrices, special attention must be paid to the choice of the adopted optimization algorithm. This is the reason why Particle Swarm Optimization (PSO) [29] was initially chosen to support the PSO (localization) algorithm [18, 19]. The PSO algorithm, which proved to be effective in preliminary experiments (e.g., [11, 18]), can be shortly outlined as follows.

During the initialization phase of the PSO algorithm, $s \in ℕ_{+}$ particles are randomly positioned in the search space, which corresponds to the indoor environment where localization is performed. The position of the i-th particle is denoted as p⁽ⁱ⁾ (0), where 1 ≤ i ≤ s. Each particle is also associated with a random velocity, and the velocity of the i-th particle is denoted as w⁽ⁱ⁾ (0), where 1 ≤ i ≤ s. After the initialization phase, the positions and the velocities of the particles are updated through subsequent iterations in the attempt to move the particles toward a position that solves the optimization problem related to the original localization problem. The position and the velocity of the i-th particle at the t-th iteration are denoted as p⁽ⁱ⁾ (t) and w⁽ⁱ⁾ (t), respectively.

In order to define a rule to update the velocities of the particles, P⁽ⁱ⁾ (t) = {p⁽ⁱ⁾ (0) , …, p⁽ⁱ⁾ (t)} is introduced to denote the set of the positions reached by the i-th particle from the first to the t-th iteration of the algorithm. Then, the best position reached at the t-th iteration by the i-th particle is denoted as $\underset{z}{y^{(i)} (t) = argmin λ (z),} \in P^{(i)} (t)$ (26) where λ is the localization cost function defined in (18). Moreover, Y (t) = {y⁽¹⁾ (t) , …, y^(s) (t)} is introduced to represent the set of the best positions reached by the particles from the first to the t-th iteration of the algorithm. The global best position [29] reached at the t-th iteration is $\underset{z}{y (t) = argmin λ (z) .} \in Y (t)$ (27) Using the introduced notation, the velocity of the i-th particle is updated at each iteration of the algorithm according to the following rule [30, 31] $\begin{matrix} w^{(i)} (t + 1) = & ω w^{(i)} (t) + \\ c_{1} R_{1} (y^{(i)} (t) - p^{(i)} (t)) + \\ c_{2} R_{2} (y (t) - p^{(i)} (t)), \end{matrix}$ (28) where ω is called inertial factor, c₁ is called cognition parameter, c₂ is called social parameter, while R₁ and R₂ are independent random variables uniformly distributed in (0, 1). Note that the first addend in (28) is proportional to the velocity of the i-th particle at the previous iteration, which is weighed with the inertial factor ω. The second addend in (28) is meant to move each particle toward its current best position. The third addend in (28) is meant to move each particle toward the current global best position, which is the position, among those reached by the particles, that corresponds to the lowest value of the localization cost function.

Once the velocities of the particles are updated according to (28), the position of the i-th particle is updated as follows $p^{(i)} (t + 1) = p^{(i)} (t) + w^{(i)} (t + 1) .$ (29) The PSO algorithm is iterated until a termination condition is met. One of the possible termination conditions is the reaching of a maximum number of iterations. At the end of the execution of the algorithm, the solution to the minimization problem is the global best position and, in the context of localization, such a solution corresponds to the estimated position of the TN. Experimental results shown in Section 5 were obtained with s = 40, ω = 0.5, c₁ = c₂ = 2, and the adopted termination condition considered 50 iterations.

The PSO algorithm has two relevant issues that limit its applicability to solve practical localization problems. First, it does not guarantee that a global minimum of the localization cost function is actually computed. Second, its performance depends on a set of parameters whose optimal values can only be determined by simulating the behavior of the algorithm in the considered environment.

4 The POST_I algorithm

The localization as optimization approach is based on the possibility of reformulating a localization problem in terms of an optimization problem. Any solution to the optimization problem is a valid estimate of the position of the TN. If the performance of the algorithm used to solve the optimization problem does not degrade for some arrangements of the ANs, the localization as optimization approach can be used to devise localization algorithms to effectively replace ordinary localization algorithms for critical arrangements of the ANs. This section describes a localization algorithm based on the localization as optimization approach whose embedded optimization algorithm uses interval arithmetic to ensure accurate localization independently of the positions of the ANs.

The localization cost function λ defined in (18), which is obtained by rewriting the localization problem (14) into the minimization problem (17), is a polynomial function of three variables whose multi-degree is L = (4, 4, 4). Since, with minor loss of generality, the work presented in this paper assumes that the indoor environment can be split into boxes, the domain D in which the solutions to the minimization problem (17) are defined can be considered as a box. Under such an assumption, the Polynomial Optimization using Subdivision Trees (POST) algorithmic framework can be introduced as an effective means to support the localization as optimization approach, as follows.

The POST algorithmic framework is based on the branch-and-bound approach (e.g., [32]), and it can be instantiated to a localization algorithm once it is completed with a suitable method to compute lower and upper bounds of a given polynomial function over a given box. An instantiation of the POST algorithmic framework recursively subdivides the initial box into disjoint sub-boxes to produce a subdivision tree intended to search for the minimum of the localization cost function λ. An instantiation of the framework refines the subdivision tree until produced sub-boxes have edges whose lengths are smaller than the accepted localization tolerance ɛ > 0, which is a parameter that is set according to the considered application. The method to compute the bounds of polynomial functions that characterizes an instantiation of the framework is used to compute suitable lower and upper bounds for the produced sub-boxes to effectively prune the subdivision tree. Only the sub-boxes that can potentially contain solutions to the minimization problem are further subdivided.

In summary, the instantiations of the POST algorithmic framework are branch-and-bound algorithms in which the pruning rules [32] are based on the bounds computed using the method to study polynomial functions that characterizes the instantiation. As such, the instantiations of the framework share the asymptotic worst-case time complexity of branch-and-bound algorithms [32], which can be measured in terms of the number of analyzed sub-boxes. If b > 0 is the maximum length of the edges of the initial box, the number of analyzed sub-boxes in the worst case is $𝒪 ((\frac{b}{ɛ})^{3})$ . Note that the adopted pruning rules can drastically reduce the actual execution time in practical cases, as expected for ordinary branch-and-bound algorithms [32]. The actual execution time of the instantiations of the POST algorithmic framework largely depends on the characteristics of the targeted localization problem and on the characteristics of the computed lower and upper bounds. The instantiation of the POST framework proposed in this paper, namely the Polynomial Optimization using Subdivision Trees with Interval arithmetic (POST_I) algorithm, uses interval arithmetic to compute needed bounds of polynomial functions over boxes.

Note that when the global minimum of a polynomial function is searched in a box, most of the algorithms available in the literature make use of the properties of Bernstein coefficients (e.g., [33] for a comprehensive review and a historical retrospective). Actually, the well-known properties of Bernstein coefficients can be used to compute lower and upper bounds of polynomial functions over boxes. Unfortunately, the use of Bernstein coefficients is problematic in terms of the expected execution time when the polynomial function to minimize is derived from a localization problem because of the characteristics of the localization cost function λ. Even if effective algorithms for the computation of Bernstein coefficients are available (e.g., [34 –39]), a total of 125 Bernstein coefficients are needed for each considered sub-box in the worst case, and preliminary tests showed that needed execution time is too high for envisaged applications of indoor localization.

Instead of using the bounds that Bernstein coefficients provide, the POST_I algorithm uses the classic result recalled in Proposition 1 to compute the bounds needed to drive the subdivision of the initial box into disjoint sub-boxes in search of the minimum of the localization cost function. The proposition is shown without proof because it is a classic result of the literature on interval arithmetic (e.g., [13]).

Proposition 1. Let $p : ℝ^{n} \mapsto ℝ$ be a polynomial function of $n \in ℕ_{+}$ variables with multi-degree $L \in ℕ^{n}$ $p (x) = \sum_{I \leq L} a_{I} x^{I},$ (30) if $B \subset ℝ^{n}$ is a box and $p (B) = [\underline{p}, \bar{p}]$ , then $\underline{p} \leq min_{x \in B} p (x) max_{x \in B} p (x) \leq \bar{p} .$ (31)

The bounds that Proposition 1 provides are typically less strict than the bounds obtained using Bernstein coefficients, but the expected execution time for n = 3 variables and multi-degree L = (4, 4, 4) is highly reduced, and it becomes compatible with the applications of indoor localization.

Note that the accuracy of the POST_I algorithm is independent of the positions of the ANs because the bounds that Proposition 1 provides are not influenced by the condition numbers of the matrices that characterize the localization problem (15). Therefore, the POST_I algorithm can be used when the accuracy of ordinary localization algorithms, like the TSML algorithm, degrades significantly because of the arrangement of the ANs in the environment. Section 5 shows experimental results that compare the accuracy of the POST_I algorithm with the accuracies of the TSML algorithm and of the PSO algorithm.

5 Experimental results

In order to analyze the performance of the proposed algorithm, an experimental campaign was performed in a selected indoor environment. The indoor environment used to perform the experiments is a 4 m wide, 10 m long, and 3 m tall corridor, which is schematized in Fig. 1. Obstacles were removed from the corridor during experiments to guarantee that the TN was in the lines of sight of ANs and to reduce the errors caused by multipath interference.

Fig.1

The twelve positions of the TN (numbered in red) considered in the four experimental scenarios are shown in a schematization of the indoor environment used for experiments (a 4 m wide, 10 m long, and 3 m tall empty corridor).

A SpoonPhone (www.bespoon.com) was used as TN in all reported experiments. To the best of our knowledge, SpoonPhones are the only commercial smartphones equipped with the necessary hardware and software modules to communicate with coupled UWB beacons and to accurately compute distance estimates using the time of flight of UWB signals. In the discussed experimental campaign, four UWB beacons were placed at known locations inside the corridor to serve as ANs. Distance acquisition was performed using the SpoonPhone, and collected distance estimates were processed using the three considered localization algorithms, namely, the TSML algorithm, the PSO algorithm, and the proposed POST_I algorithm.

The accuracies of the three localization algorithms were measured in four different scenarios, which correspond to four arrangements of the ANs. For each scenario, twelve different positions of the TN were considered, as shown in Fig. 1. The twelve positions were divided in three groups, each of which is characterized by the height of the TN: 3 m (near the ceiling), 1.5 m, and 0 m (near the floor).

The positions of the TN near the ceiling of the corridor are shown in Fig. 1 with numbers from 1 to 4, and the coordinates of such positions are expressed in meters as $\begin{matrix} t_{1} & = (0, 0, 3) \\ t_{3} & = (2, 5, 3) \end{matrix} \begin{matrix} t_{2} & = (2, 0, 3) \\ t_{4} & = (0, 5, 3) . \end{matrix}$ The positions of the TN whose heights are all equal to 1.5 m are shown in Fig. 1 with numbers from 5 to 8, and the coordinates of such positions are expressed in meters in the considered coordinate system as $\begin{matrix} t_{5} & = (0, 0, 1.5) \\ t_{7} & = (2, 5, 1.5) \end{matrix} \begin{matrix} t_{6} & = (2, 0, 1.5) \\ t_{8} & = (0, 5, 1.5) . \end{matrix}$ Finally, the four positions of the TN near the floor are shown in Fig. 1 with numbers from 9 to 12, and the coordinates of such positions are expressed in meters in the coordinate system shown in the figure as $\begin{matrix} t_{9} & = (0, 0, 0) \\ t_{11} & = (2, 5, 0) \end{matrix} \begin{matrix} t_{10} & = (2, 0, 0) \\ t_{12} & = (0, 5, 0) . \end{matrix}$

Four scenarios corresponding to four different arrangements of the ANs were studied, and twelve positions of the TN were considered in each scenario, which results in a total of forty-eight experimental configurations. For each one of the forty-eight experimental configuration, r = 100 estimates of the distances from the TN to the ANs were acquired using UWB signaling. Each considered algorithm was then used to compute r position estimates that were used to compare the accuracies of the algorithms.

Using the nomenclature introduced in Section 3, t denotes the true position of the TN, and $\tilde{t}$ denotes the estimated position of the TN. Therefore, the localization accuracies of the three considered algorithms can be measured in terms of the localization error $e = t - \tilde{t} .$ (32)

In order to make a fair comparison among the three algorithms, the position estimates obtained with the three algorithms were computed using the same distance estimates. In particular, the average and the standard deviation of the Euclidean norm of e were computed using the r acquisitions of each scenario for the TSML algorithm (denoted as e_T and σ_T), for the PSO algorithm (denoted as e_P and σ_P), and for the POST_I algorithm (denoted as e_I and σ_I).

5.1 Scenario 1

In Scenario 1, the four ANs are placed close to the ceiling of the considered environment, all at the same height. Using the coordinate system shown in Fig. 1, the positions of the ANs have the following coordinates expressed in meters $\begin{matrix} a_{1} & = (0, 0, 3) \\ a_{3} & = (4, 10, 3) \end{matrix} \begin{matrix} a_{2} & = (4, 0, 3) \\ a_{4} & = (0, 10, 3) . \end{matrix}$ As discussed in Section 1, the fact that the ANs share the same height is problematic for ordinary localization algorithms. In particular, the TSML algorithm is actually inapplicable in this scenario because (G^⊤W₁G) ^-1 in (21) cannot be computed when G is not full rank. This is the reason why only the accuracies of the PSO algorithm and of the POST_I algorithm can be assessed in this scenario.

Table 1 shows the results related to the accuracies of the PSO algorithm and of the POST_I algorithm in terms of the average and of the standard deviation of the Euclidean norm of the localization error e computed using the r acquisitions performed in this scenario. Note that the accuracy of the TSML algorithm is not shown in the table because the TSML algorithm is not applicable in this scenario.

Table 1
Experimental Results in Scenario 1

Position e_T [m] σ_T [m] e_P [m] σ_P [m] e_I [m] σ_I [m]

1 N/A N/A 0.387 0.164 0.353 0.237

2 N/A N/A 0.327 0.117 0.285 0.103

3 N/A N/A 0.235 0.376 0.249 0.412

4 N/A N/A 0.256 0.241 0.252 0.258

5 N/A N/A 0.391 0.287 0.316 0.093

6 N/A N/A 0.307 0.073 0.317 0.070

7 N/A N/A 0.793 0.419 0.731 0.247

8 N/A N/A 0.704 0.437 0.608 0.186

9 N/A N/A 0.411 0.333 0.255 0.089

10 N/A N/A 0.395 0.257 0.393 0.260

11 N/A N/A 0.305 0.192 0.313 0.220

12 N/A N/A 0.599 0.333 0.506 0.151

Position	e_T [m]	σ_T [m]	e_P [m]	σ_P [m]	e_I [m]	σ_I [m]
1	N/A	N/A	0.387	0.164	0.353	0.237
2	N/A	N/A	0.327	0.117	0.285	0.103
3	N/A	N/A	0.235	0.376	0.249	0.412
4	N/A	N/A	0.256	0.241	0.252	0.258
5	N/A	N/A	0.391	0.287	0.316	0.093
6	N/A	N/A	0.307	0.073	0.317	0.070
7	N/A	N/A	0.793	0.419	0.731	0.247
8	N/A	N/A	0.704	0.437	0.608	0.186
9	N/A	N/A	0.411	0.333	0.255	0.089
10	N/A	N/A	0.395	0.257	0.393	0.260
11	N/A	N/A	0.305	0.192	0.313	0.220
12	N/A	N/A	0.599	0.333	0.506	0.151

Table 1 shows the values of e_P and of σ_P relative to the PSO algorithm for each one of the twelve positions of the TN. Observe that the values of e_P vary from 0.235 m to 0.793 m, and the values of σ_P vary from 0.073 m to 0.437 m. Therefore, it can be concluded that the accuracy of the PSO algorithm in this scenario is compatible with the envisaged applications of indoor localization mentioned in Section 1.

Table 1 also shows the values of e_I and of σ_I relative to the POST_I algorithm for each one of the twelve positions of the TN. Observe that values of e_I vary from 0.249 m to 0.731 m, and the values of σ_I vary from 0.070 m to 0.412 m. From such results, it can be concluded that the accuracy of the POST_I algorithm is similar to the accuracy of the PSO algorithm in this scenario, and therefore it is compatible with the envisaged applications briefly discussed in Section 1.

For the sake of clarity, Fig. 2 shows for Scenario 1 the values of e_P (red squares) and of e_I (green triangles) for each one of the twelve positions of the TN (upper plot). The figure also shows the values of σ_P (red squares) and of σ_I (green triangles) for each one of the twelve positions of the TN (lower plot).

Fig.2

The average errors in Scenario 1 for the PSO algorithm (e_P) and for the POST_I algorithm (e_I) are shown in meters (upper plot). The standard deviations in Scenario 1 for the two algorithms, (σ_P) and (σ_I), respectively, are shown in meters (lower plot).

5.2 Scenario 2

In Scenario 2, the heights of the two ANs that were located in a₁ and a₃ in Scenario 1 were reduced by 0.5 m. Using the coordinate system shown in Fig. 1, the positions of the ANs in Scenario 2 have the following coordinates expressed in meters $\begin{matrix} a_{1} & = (0, 0, 2.5) \\ a_{3} & = (4, 10, 2.5) \end{matrix} \begin{matrix} a_{2} & = (4, 0, 3) \\ a_{4} & = (0, 10, 3) . \end{matrix}$

Table 2 shows the results related to the accuracies of the three localization algorithms discussed in this paper in terms of the average and of the standard deviation of the Euclidean norm of the localization error e computed using the r acquisitions performed in this scenario. Note that the TSML algorithm is technically applicable in this scenario and it is listed in the table.

Table 2
Experimental Results in Scenario 2

Position e_T [m] σ_T [m] e_P [m] σ_P [m] e_I [m] σ_I [m]

1 0.431 0.198 0.354 0.138 0.400 0.489

2 0.997 2.138 0.411 0.212 0.404 0.232

3 2.190 2.573 0.638 0.530 0.629 0.580

4 0.801 1.136 0.315 0.199 0.306 0.158

5 1.422 2.468 0.408 0.345 0.350 0.175

6 0.740 0.664 0.362 0.255 0.349 0.193

7 0.755 0.818 0.814 0.315 0.793 0.230

8 0.857 0.635 0.566 0.221 0.586 0.197

9 2.388 2.903 0.653 0.937 0.247 0.093

10 1.359 1.747 0.340 0.188 0.342 0.189

11 1.680 1.576 0.431 0.164 0.435 0.189

12 1.804 2.313 0.492 0.261 0.441 0.099

Position	e_T [m]	σ_T [m]	e_P [m]	σ_P [m]	e_I [m]	σ_I [m]
1	0.431	0.198	0.354	0.138	0.400	0.489
2	0.997	2.138	0.411	0.212	0.404	0.232
3	2.190	2.573	0.638	0.530	0.629	0.580
4	0.801	1.136	0.315	0.199	0.306	0.158
5	1.422	2.468	0.408	0.345	0.350	0.175
6	0.740	0.664	0.362	0.255	0.349	0.193
7	0.755	0.818	0.814	0.315	0.793	0.230
8	0.857	0.635	0.566	0.221	0.586	0.197
9	2.388	2.903	0.653	0.937	0.247	0.093
10	1.359	1.747	0.340	0.188	0.342	0.189
11	1.680	1.576	0.431	0.164	0.435	0.189
12	1.804	2.313	0.492	0.261	0.441	0.099

Table 2 shows the values of e_T and of σ_T relative to the TSML algorithm for each one of the twelve positions of the TN. Observe that values of e_T vary from 0.431 m to 2.388 m, and the values of σ_T vary from 0.198 m to 2.903 m. Therefore, it can be concluded that the estimates of the position of the TN obtained with the TSML algorithm in this scenario are not sufficiently accurate to support the applications of indoor localization discussed in Section 1.

Table 2 also shows the values of e_P and of σ_P relative to the PSO algorithm for each one of the twelve positions of the TN. Observe that values of e_P vary from 0.315 m to 0.653 m, and the values σ_P vary from 0.138 m to 0.938 m. Unsurprisingly, the accuracy of localization of the PSO algorithm in this scenario is compatible with the envisaged applications briefly mentioned in Section 1.

Finally, Table 2 shows the values of e_I and of σ_I for each one of the twelve positions of the TN. Observe that values of e_I vary from 0.249 m to 0.731 m, and the values of σ_I vary from 0.247 m to 0.793 m. From the obtained results it can be concluded that the PSO algorithm and the POST_I algorithm have similar accuracies in this scenario, and that the obtained accuracies are sufficiently good for applications.

For the sake of clarity, Fig. 3 shows for Scenario 2 the values of e_T (blue circles), of e_P (red squares), and of e_I (green triangles) for each one of the twelve positions of the TN (upper plot). In addition, it shows the values of σ_T (blue circles), of σ_P (red squares), and of σ_I (green triangles) for each one of the twelve positions of the TN (lower plot).

Fig.3

The average errors in Scenario 2 for the TSML algorithm (e_T), the PSO algorithm (e_P), and the POST_I algorithm (e_I) are shown in meters (upper plot). The standard deviations in Scenario 2 for the TSML algorithm (σ_T), the PSO algorithm (σ_P), and the POST_I algorithm (σ_I) are shown in meters (lower plot).

5.3 Scenario 3

The experimental results of Scenario 2 show that it is not sufficient to reduce the heights of two ANs by 0.5 m to obtain accurate position estimates with the TSML algorithm. This is the reason why, in this scenario, the heights of the two ANs that were located in a₁ and a₃ in Scenario 1 were further reduced, and now their heights equal 1.5 m. Using the coordinate system shown in Fig. 1, the positions of the ANs have the following coordinates expressed in meters $\begin{matrix} a_{1} & = (0, 0, 1.5) \\ a_{3} & = (4, 10, 1.5) \end{matrix} \begin{matrix} a_{2} & = (4, 0, 3) \\ a_{4} & = (0, 10, 3) . \end{matrix}$ Observe that the new heights of the two relocated ANs may not be sufficient to guarantee line-of-sight visibility in practical applications because obstacles are normally present in the environment. However, the corridor is empty in the considered experimental campaign and, therefore, line-of-sight visibility is guaranteed.

Table 3 shows the results related to the accuracies of the three localization algorithms in terms of the average and of the standard deviation of the Euclidean norm of the localization error e computed using the r acquisitions performed in this scenario.

Table 3
Experimental results in Scenario 3

Position e_T [m] σ_T [m] e_P [m] σ_P [m] e_I [m] σ_I [m]

1 0.314 0.127 0.316 0.105 0.335 0.382

2 0.345 0.194 0.324 0.124 0.332 0.127

3 0.480 0.708 0.533 0.377 0.533 0.389

4 0.573 0.104 0.324 0.119 0.303 0.064

5 0.447 0.746 0.417 0.326 0.405 0.277

6 0.197 0.098 0.332 0.105 0.417 0.290

7 0.897 0.707 0.569 0.505 0.558 0.474

8 0.567 0.234 0.344 0.254 0.340 0.242

9 0.757 0.745 0.442 0.580 0.287 0.070

10 0.867 0.923 0.387 0.261 0.420 0.358

11 0.650 0.456 0.341 0.163 0.335 0.161

12 0.627 0.249 0.491 0.163 0.467 0.090

Position	e_T [m]	σ_T [m]	e_P [m]	σ_P [m]	e_I [m]	σ_I [m]
1	0.314	0.127	0.316	0.105	0.335	0.382
2	0.345	0.194	0.324	0.124	0.332	0.127
3	0.480	0.708	0.533	0.377	0.533	0.389
4	0.573	0.104	0.324	0.119	0.303	0.064
5	0.447	0.746	0.417	0.326	0.405	0.277
6	0.197	0.098	0.332	0.105	0.417	0.290
7	0.897	0.707	0.569	0.505	0.558	0.474
8	0.567	0.234	0.344	0.254	0.340	0.242
9	0.757	0.745	0.442	0.580	0.287	0.070
10	0.867	0.923	0.387	0.261	0.420	0.358
11	0.650	0.456	0.341	0.163	0.335	0.161
12	0.627	0.249	0.491	0.163	0.467	0.090

Table 3 shows the values of e_T and of σ_T relative to the TSML algorithm for each one of the twelve positions of the TN. Observe that values of e_T vary from 0.197 m to 0.897 m, and the values σ_T vary from 0.098 m to 0.923 m. Therefore, it can be concluded that the reduction of the heights of the two relocated ANs leads to accurate position estimates.

Table 3 also shows the values of e_P and of σ_P relative to the PSO algorithm for each one of the twelve positions of the TN. Observe that values of e_P vary from 0.316 m to 0.579 m, and the values of σ_P vary from 0.105 m to 0.580 m. It can be concluded that the accuracy of localization when the PSO algorithm is used is compatible with envisaged applications.

Finally, Table 3 shows the values of e_I and of σ_I relative to the POST_I algorithm for each one of the twelve positions of the TN. Observe that values of e_I vary from 0.287 m to 0.558 m, and the values of σ_I vary from 0.064 m to 0.474 m. Therefore, it can be concluded that the accuracy of the POST_I algorithm is compatible with intended uses of indoor localization.

From the obtained results, it can be concluded that the accuracies of the three algorithms in this scenario are compatible with the envisaged applications mentioned in Section 1. However, it is worth noting that the localization errors obtained with the TSML algorithm are typically larger than those obtained with the PSO algorithm and with the POST_I algorithm.

For the sake of clarity, Fig. 4 shows for Scenario 3 the values of e_T (blue circles), of e_P (red squares), and of e_I (green triangles) for each one of the twelve positions of the TN (upper plot). In addition, it shows the values of σ_T (blue circles), of σ_P (red squares), and of σ_I (green triangles) for each one of the twelve positions of the TN (lower plot).

Fig.4

The average errors in Scenario 3 for the TSML algorithm (e_T), the PSO algorithm (e_P), and the POST_I algorithm (e_I) are shown in meters (upper plot). The standard deviations in Scenario 3 for the TSML algorithm (σ_T), the PSO algorithm (σ_P), and the POST_I algorithm (σ_I) are shown in meters (lower plot).

5.4 Scenario 4

In this scenario, the heights of the ANs that were located in a₁ and a₃ in Scenario 1 were further reduced, and they are now placed near the floor of the corridor. Note that the two ANs that were located in a₂ and a₄ in Scenario 1 are still in their original positions. Using the coordinate system shown in Fig. 1, the positions of the ANs in this scenario are expressed in meters as $\begin{matrix} a_{1} & = (0, 0, 0) \\ a_{3} & = (4, 10, 0) \end{matrix} \begin{matrix} a_{2} & = (4, 0, 3) \\ a_{4} & = (0, 10, 3) . \end{matrix}$ As in the previous scenario, the new heights of the two relocated ANs are not sufficient to guarantee line-of-sight visibility in practical applications because of the presence of obstacles in the environment.

Table 4 shows the results related to the accuracies of the three localization algorithms in terms of the average and of the standard deviation of the Euclidean norm of the localization error e computed using the r acquisitions performed in this scenario.

Table 4
Experimental results in Scenario 4

Position e_T [m] σ_T [m] e_P [m] σ_P [m] e_I [m] σ_I [m]

1 0.584 0.552 0.312 0.122 0.276 0.068

2 0.298 0.111 0.304 0.064 0.309 0.065

3 0.313 0.336 0.321 0.336 0.327 0.334

4 0.783 0.374 0.563 0.406 0.455 0.144

5 0.427 0.446 0.347 0.216 0.350 0.214

6 0.316 0.103 0.279 0.103 0.271 0.111

7 0.385 0.509 0.214 0.331 0.219 0.328

8 0.600 0.115 0.246 0.116 0.241 0.121

9 0.258 0.104 0.329 0.125 0.308 0.071

10 0.627 0.589 0.451 0.334 0.483 0.421

11 0.879 0.195 0.347 0.315 0.346 0.309

12 0.783 0.168 0.430 0.157 0.409 0.070

Position	e_T [m]	σ_T [m]	e_P [m]	σ_P [m]	e_I [m]	σ_I [m]
1	0.584	0.552	0.312	0.122	0.276	0.068
2	0.298	0.111	0.304	0.064	0.309	0.065
3	0.313	0.336	0.321	0.336	0.327	0.334
4	0.783	0.374	0.563	0.406	0.455	0.144
5	0.427	0.446	0.347	0.216	0.350	0.214
6	0.316	0.103	0.279	0.103	0.271	0.111
7	0.385	0.509	0.214	0.331	0.219	0.328
8	0.600	0.115	0.246	0.116	0.241	0.121
9	0.258	0.104	0.329	0.125	0.308	0.071
10	0.627	0.589	0.451	0.334	0.483	0.421
11	0.879	0.195	0.347	0.315	0.346	0.309
12	0.783	0.168	0.430	0.157	0.409	0.070

Table 4 shows the values of e_T and of σ_T relative to the TSML algorithm for each one of the twelve positions of the TN. Observe that values of e_T vary from 0.258 m to 0.879 m, and the values σ_T vary from 0.103 m to 0.589 m. Therefore, it can be concluded that the reduction of the heights of two ANs leads to more accurate estimates of the position of the TN when the TSML algorithm is used.

Table 4 also shows the values of e_P and of σ_P relative to the PSO algorithm for each one of the twelve positions of the TN. Observe that values of e_P vary from 0.214 m to 0.563 m, and the values of σ_P vary from 0.064 m to 0.406 m. Unsurprisingly, the accuracy of the PSO algorithm is compatible with the envisaged applications discussed in Section 1.

Finally, Table 4 shows the values of e_I and of σ_I relative to the POST_I algorithm for each one of the twelve positions of the TN. Observe that values of e_I vary from 0.219 m to 0.483 m, and the values of σ_I vary from 0.065 m to 0.421 m. As expected, the POST_I algorithm provides an accuracy compatible with considered applications.

From the discussed results it can be concluded that, in this scenario, the accuracies of the three algorithms are compatible with the envisaged applications mentioned in Section 1. However, it is worth noting that the localization errors obtained with the TSML algorithm are typically larger than those obtained with the PSO algorithm and with the POST_I algorithm.

For the sake of clarity, Fig. 5 shows for Scenario 4 the values of e_T (blue circles), of e_P (red squares), and of e_I (green triangles) for each one of the twelve positions of the TN (upper plot). In addition, it shows the values of σ_T (blue circles), of σ_P (red squares), and of σ_I (green triangles) for each one of the twelve positions of the TN (lower plot).

Fig.5

The average errors in Scenario 4 for the TSML algorithm (e_T), the PSO algorithm (e_P), and the POST_I algorithm (e_I) are shown in meters (upper plot). The standard deviations in Scenario 4 for the TSML algorithm (σ_T), the PSO algorithm (σ_P), and the POST_I algorithm (σ_I) are shown in meters (lower plot).

6 Conclusions

The major contribution of this paper is to propose the POST_I algorithm as a relevant opportunity to adopt the localization as optimization approach for accurate and robust indoor localization. The POST_I algorithm is based on solid results from the literature on interval arithmetic, and it relies on a subdivision method to search for the position of the TN in the considered environment, which, with minor loss of generality, is assumed to be composed of boxes.

One of the most important characteristics of the POST_I algorithm is that it provides a level of accuracy that is independent of the positions of the ANs in the environment. On the contrary, the performance of ordinary localization algorithms, such as the TSML algorithm, are strongly dependent on the arrangement of the ANs. Experimental results shown in the last part of this paper confirm that the POST_I algorithm provides accurate position estimates in all considered scenarios, while the TSML algorithm exhibits significant localization errors when the ANs are installed in critical arrangements. The accuracy of the POST_I algorithm is similar to the accuracy of the PSO algorithm in the considered scenarios, which makes the POST_I algorithm a valid alternative to the PSO algorithm. Actually, one of the problems of the PSO algorithm is that it requires to properly set the values of several parameters that are not easily related to the characteristics of the considered application. On the contrary, the POST_I algorithm only depends on the accepted localization tolerance, which can be easily set on the basis of the characteristics of the considered application.

The current implementation of the POST_I algorithm is natively integrated into the localization add-on module for JADE, and it uses UWB signaling to acquire distance estimates. Note that the architecture of the module allows the algorithm to transparently work with distance estimates acquired using other ranging technologies. In particular, it is possible to use the algorithm with distance estimates obtained using WiFi signaling, even if the accuracy of position estimates is expected to degrade sensibly because the distance estimates obtained using WiFi signaling are less accurate than those obtained using UWB signaling [40]. However, a WiFi infrastructure is already available in the large majority of the indoor environments in which indoor localization can be relevant for envisaged applications, and therefore the use of WiFi signaling can benefit from existing infrastructures, rather than requiring dedicated, and often expensive, infrastructures.

Finally, it is worth noting that the critical arrangements of the ANs that make the use of the TSML algorithm impractical are those in which the ANs are (roughly) coplanar. Unfortunately, this is one of the most common arrangements in indoor environments because the ANs are typically placed at the same height close to the ceiling of the environment to ensure a good line-of-sight coverage. When WiFi signaling is used instead of UWB signaling, the problems caused by the arrangement of the ANs in the environment are particularly relevant. The WiFi access points are not installed to serve as ANs for localization, and therefore they are typically located on regular grids near the ceiling of the environment, which makes their use as ANs for the TSML algorithm practically inapplicable. On the contrary, they can be effectively used as ANs for the POST_I algorithm and other algorithms based on the localization as optimization approach. This is one of the major reasons why the localization as optimization approach is expected to play a crucial role for the adoption of WiFi signaling to support ubiquitous, accurate, and robust indoor localization.

References

Zafari

, Gkelias

and Leung

K.K.

, A survey of indoor localization systems and technologies, IEEE Communications Surveys & Tutorials21(3) (2019), 2568–2599.

Skoumas

, Pfoser

, Kyrillidis

and Sellis

, Location estimation using crowdsourced spatial relations, ACM Transactions on Spatial Algorithms and Systems2(2) (2016), 5:1–5:23.

Teng

S.-Y.

, Ku

W.-S.

and Chuang

K.-T.

, Toward mining stopby behaviors in indoor space, ACM Transactions on Spatial Algorithms and Systems3(2) (2017), 7:1–7:38.

Zhou

, Chen

, Guo

, Teng

and Yuan

, From one to crowd: A survey on crowdsourcing-based wireless indoor localization, Frontiers of Computer Science12(3) (2018), 423–450.

Pannuto

, Kempke

, Chuo

L.-X.

, Blaauw

and Dutta

, Harmonium: Ultra wideband pulse generation with bandstitched recovery for fast, accurate, and robust indoor localization, ACM Transactions on Sensor Networks14(2) (2018), 11:1–11:29.

Mendoza-Silva

G.M.

, Torres-Sospedra

and Huerta

, A meta-review of indoor positioning systems, Sensors19 (2019), 4507.

Monica

, Bergenti

, Location-aware JADE agents in indoor scenarios, in: Proceedings of the 16th Workshop “From Objects to Agents” (WOA 2015), CEUR Workshop Proceedings Vol. 1382, RWTH Aachen, (2015), pp. 103–108.

Bergenti

, Caire

, Gotta

, Agents on the move: JADE for Android devices, in: Proceedings of the 15th Workshop “From Objects to Agents” (WOA 2014), CEURWorkshop Proceedings Vol. 1260, RWTH Aachen, 2014.

Monica

, Bergenti

, Indoor localization of JADE agents without a dedicated infrastructure, in: Multiagent System Technologies (MATES 2017), Lecture Notes in Computer Science Vol. 10413, Springer, (2017), pp. 256–271.

10.

Bellifemine

, Bergenti

, Caire

, Poggi

, JADE–A Java agent development framework, in: Multi-Agent Programming, Multiagent Systems, Artificial Societies, and Simulated Organizations Vol. 15, Springer, (2005), pp. 125–147.

11.

Monica

, Ferrari

, Impact of the number of beacons in PSO-based auto-localization in UWB networks, in: Applications of Evolutionary Computation (EvoApplications 2013), Lecture Notes in Computer Science, Vol. 7835, Springer, (2013), pp. 42–51.

12.

Monica

and Ferrari

, Swarm intelligent approaches to auto-localization of nodes in static UWB networks, Applied Soft Computing25 (2014), 426–434.

13.

Tucker

, Validated numerics: A short introduction to rigorous computations, Princeton University Press, 2011.

14.

Shen

, Zetik

, Thomä

R.S.

, Performance comparison of TOA and TDOA based location estimation algorithms in LOS environment, in: Proceedings of the IEEE Workshop on Positioning, Navigation and Communication (WPNC 2008), IEEE (2008), pp. 71–78.

15.

Mekelleche

and Haffaf

, Classification and comparison of range-based localization techniques in wireless sensor networks, Journal of Communications12(4) (2017), 221–227.

16.

K.C.

, Xiaoning

and Kovavisaruch

, Source localization using TDOA and FDOA measurements in the presence of receiver location errors: Analysis and solution, IEEE Transactions on Signal Processing55(2) (2007), 684–696.

17.

Álvarez

, Díez-González

, Alonso

, Fernández-Robles

, Castejón-Limas

and Perez

, Accuracy analysis in sensor networks for asynchronous positioning methods, Sensors19 (2019), 3024.

18.

Monica

and Ferrari

, A swarm-based approach to realtime 3D indoor localization: Experimental performance analysis, Applied Soft Computing43 (2016), 489–497.

19.

Monica

, Bergenti

, Optimization-based robust localization of JADE agents in indoor environments, in: Proceedings of the 3rd Italian Workshop on Artificial Intelligence for Ambient Assisted Living (AI*AAL.it 2017), CEUR Workshop Proceedings, Vol. 2061, RWTH Aachen (2018), pp. 58–73 .

20.

Bonyadi

M.R.

and Michalewicz

, Particle swarm optimization for single objective continuous space problems: A review, Evolutionary Computation25(1) (2017), 1–54.

21.

Bergenti

, Monica

, Experiments on robust indoor localization of mobile devices using interval arithmetic, in: Proceedings of the 20th Workshop “From Objects to Agents” (WOA 2019), CEUR Workshop Proceedings Vol. 2402, RWTH Aachen, (2019), pp. 14–21.

22.

Bergenti

, Caire

and Gotta

, An overview of the AMUSE social gaming platform, in: Proceedings of the 14th Workshop “From Objects to Agents” (WOA 2013), CEUR Workshop Proceedings, Vol. 1099, RWTH Aachen, (2013), pp. 85–90.

23.

Monica

, Bergenti

, Location-aware social gaming with AMUSE, in: Advances in Practical Applications of Scalable Multi-agent Systems (PAAMS 2016), Lecture Notes in Computer Science,Vol. 9662, Springer, (2016), pp. 36–47.

24.

Bergenti

, Franchi

and Poggi

, Agent-based social networks for enterprise collaboration, in: Proceedings of the 20th IEEE International Workshop on Enabling Technologies: Infrastructure for Collaborative Enterprises (WETICE 2011), IEEE (2011), 25–28.

25.

Purushotham

and Kuo

C.-C.J.

, Personalized group recommender systems for location- and event-based social networks, ACM Transactions on Spatial Algorithms and Systems2(4) (2016), 16:1–16:29.

26.

Monica

, Ferrari

, Optimized anchors placement: An analytical approach in UWB-based TDOA localization, in: Proceedings of the 9th International Wireless Communications and Mobile Computing Conference (IWCMC 2013), IEEE (2013), pp. 982–987.

27.

Monica

, Bergenti

, Experimental evaluation of agentbased localization of smart appliances, in: Proceedings of the 14th European Conference on Multi-Agent Systems (EUMAS 2016), Lecture Notes in Artificial Intelligence Vol. 10207, Springer, (2017), pp. 293–304.

28.

Shi

, Ming

, Survey of indoor positioning systems based on ultra-wideband (UWB) technology, in: Wireless Communications, Networking and Applications, Lecture Notes in Electrical Engineering Vol. 348, Springer, (2016), pp. 1269–1278.

29.

Poli

, Kennedy

and Blackwell

, Particle swarm optimization, Swarm Intelligence Journal1(1) (2007), 33–57.

30.

Shi

, Eberhart

, A modified particle swarm optimizer, in: Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC 1999), IEEE (1999), pp. 69–73 .

31.

Eberhart

, Kennedy

, A new optimizer using particles swarm theory, in: Proceedings of the 6th International Symposium on Micro Machine and Human Science (MHS 1995), IEEE (1995), pp. 39–43 .

32.

Morrison

D.R.

, Jacobson

S.H.

, Sauppe

J.J.

and Sewell

E.C.

, Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning, Discrete Optimization19 (2016), 79–102.

33.

Farouki

R.T.

, The Bernstein polynomial basis: A centennial retrospective, Computer Aided Geometric Design29(6) (2012), 379–419.

34.

Farouki

R.T.

and Rajan

V.T.

, Algorithms for polynomials in Bernstein form, Computer-Aided Geometric Design5(1) (1988), 1–26.

35.

Garloff

, Smith

A.P.

, Solution of systems of polynomial equations by using Bernstein expansion, in: Symbolic Algebraic Methods and Verification Methods, Springer, (2001), pp. 87–97.

36.

Ray

and Nataraj

P.S.V.

, An efficient algorithm for range computation of polynomials using the Bernstein form, Journal of Global Optimization45 (2009), 403–426.

37.

Smith

A.P.

, Fast construction of constant bound functions for sparse polynomials, Journal of Global Optimization43(2) (2009), 445–458.

38.

Ray

and Nataraj

P.S.V.

, A matrix method for efficient computation of Bernstein coefficients, Reliable Computing17 (2012), 40–71.

39.

Titi

and Garloff

, Matrix methods for the tensorial Bernstein form, Applied Mathematics and Computation346 (2019), 254–271.

40.

Monica

, Bergenti

, A comparison of accurate indoor localization of static targets via WiFi and UWB ranging, in: Trends in Practical Applications of Scalable Multi-Agent System (PAAMS 2016), Advances in Intelligent Systems and Computing Vol. 473, Springer, (2016), pp.111–123.