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