arXiv:1612.05793v1 [cs.RO] 17 Dec 2016  1  Autonomous Localization and Mapping Using a Single Mobile Device  Tiexing Wang, Fangrong Peng and Biao Chen  Abstract —This paper considers the problem of simultaneous  2 - D   room   shape   reconstruction   and   self-localization   without the requirement of any pre-established infrastructure. A mobile device equipped with co-located microphone and loudspeaker as   well   as   internal   motion   sensors   is   used   to   emit   acoustic pulses and collect echoes reflected by the walls. Using only first order echoes, room shape recovery and self-localization is feasible when auxiliary information is obtained using motion sensors. In particular, it is established that using echoes collected at three measurement locations and the two distances between consecutive measurement points, unique localization and mapping can be achieved provided that the three measurement points are not collinear. Practical algorithms for room shape reconstruction and self-localization in the presence of noise and higher order echoes are proposed along with experimental results to demonstrate the effectiveness of the proposed approach.  Index   Terms — 2 - D   room   shape   recovery,   self-localization, acoustic sensor, room impulse response, self-localization.  I.   INTRODUCTION  Indoor localization has become more important in recent years as numerous applications, e.g., public safety or location based services, rely on accurate indoor localization [1]. As GPS signals are severely attenuated in typical indoor environ- ment, a number of alternative technologies have been proposed for indoor localization, e.g. those using WiFi [2]–[4], UWB signal [5]–[7], LED light [8], [9] , or some combination of the above. These technologies inevitably require indoor geometry in- formation. There are   applications where the   indoor room geometry may need to be acquired concurrently with lo- calization. This is generally referred to as simultaneous lo- calization and mapping (SLAM). We comment that the so- called WiFi-SLAM still requires indoor mapping information; SLAM refers to the training process that associates mapping information with the WiFi signature [10]. There are also applications where mapping itself is the ultimate goal instead of self-localization [11], [12]. For many applications where room shape reconstruction is required, acoustic based approach is arguably more suitable as rooms are often defined by dominant sound reflectors (walls). The distance measurements as measured through acoustic echoes contain rich information about the location of the measurement points as well as the room geometry. A key advantage of the acoustic based approach is that no pre- established infrastructure is needed; this is in sharp contrast with other approaches which inevitably require either deploy- ment of anchor nodes [13], [14] or the availability of ambient WiFi signals as well as preliminary maps [10]. This unique advantage has the potential to broaden the applications of indoor mapping and localization to systems where current technologies are either unsuitable or too expensive to imple- ment. The most prevalent acoustic based approach is to   em- ploy a single fixed loudspeaker and a microphone array, or equivalently, a fixed loudspeaker and a mobile microphone [15]–[20]. It was shown that both the room shape and the geometry of the microphone array (or the trajectory of the mobile microphone) can be estimated by first order echoes [21]. Furthermore, bearing only SLAM can be achieved using a mobile microphone array [22]. The fact that a microphone array needs to be deployed leaves much to be desired: fully autonomous SLAM should require minimum deployment effort. Ideally, a single mobile device that moves around would autonomously reconstruct the room shape while tracking its own movement within the recovered room geometry. Indeed, room shape recovery using a single acoustic device has been addressed in the literature. It was established that any convex polygon can be reconstructed by the   entire   set of both first and second order echoes collected using a fixed device with a collocated microphone and loud- speaker [18]. However, experimental results, including that of our own, demonstrated that higher order acoustic echoes are often difficult to recover, thus the requirement of having the entire set of second order echoes makes such an approach impractical. On the other hand, given only   grouped   first order echoes, SLAM can be achieved for a large class of convex polygon other than parallelograms [23]. This result was strengthened in [24] where it was established that parallelograms are the only convex polygons that are not recoverable via grouped first order echoes. Here “- grouped ” means correct labeling, i.e., the correspondence between collected echoes and walls is known. This paper makes further progress in overcoming the short- comings of the approaches in [23], [24]. The reconstruction will again be based on first order echoes only but without the knowledge of echo labeling. To overcome the ambiguity associated with parallelograms, our approach leverages the ever expanding capability of various motion sensors embedded in latest smart phones, including accelerometer, magnetome- ter, and gyroscope. Those sensors are capable of measuring distance and direction information of a moving device [25]– [27]. However, existing results indicate that while distance measures have reasonable accuracy, direction measurement is often subject to large measurement error [28]. Thus our current approach only exploits the distance measurements and the key question to be addressed is how much additional information
2  will be needed for acoustic SLAM to be able to recover all convex polygons. The major contribution of the paper is to establish that with three non-collinear measurement points, SLAM can be achieved for all convex polygons using   ungrouped   first or- der echoes provided that the distances between consecutive measurement points are known. Note that this additional in- formation is much weaker than the knowledge of the complete geometry of the measurement - this is tantamount to knowing only two sides of a triangle which is inadequate to construct the triangle. An added advantage of this additional distance information is that it removes the need for grouped echoes, making the scheme much more widely applicable as it can accommodate a great deal of freedom in the movement of the device. Preliminary results have been reported in [29]. The   present work, in   addition to   expanding on technical details, contains several new results including a more detailed analysis on exactly what is the minimum amount of distance information that is needed for SLAM. Specifically, it is further established that with ungrouped echoes, a single distance measure does not suffice for parallelograms. Note the subtle but important difference with that of [23], [24] in which grouped instead of ungrouped echoes are assumed. The rest of the paper is organized as follows. Section II introduces the indoor propagation model of acoustic signals, image   source   model   and   existing   results   on   2 -D   with   a single device. Theoretical guarantee of successful SLAM given distances between consecutive measurement points is provided in Section III along with a practical algorithm that handles the presence of measurement noise and higher order/spurious peaks. Experiment results are provided in Section IV followed by conclusion in Section V. II.   PROBLEM STATEMENT  A. Room Impulse Response Model  Acoustic signal propagation from a loudspeaker to a mi- crophone in a room can be described by the room impulse response (RIR), which includes both line-of-sight (LOS) and reflected components. If the microphone and loudspeaker are much closer to each other compared to the distance between the device and the walls, we say it is a co-located device. For a co-located device at the   j th measurement point denoted by  O j   , the RIR is, ignoring dispersion,  h ( j ) ( t ) =   ∑  i  α ( j )  i   δ ( t   −   τ   ( j )  i   ) ,   (1) where   α ( j )  i   ’s and   τ   ( j )  i   ’s are path gains and delays from the transmitter to the receiver, respectively. Since higher order reflective paths typically have much weaker power,   h ( j ) ( t )   can be approximated by the first   N j   +1   components including LOS and   N j   reflective paths:  h ( j ) ( t )   ≈  N j  ∑  i =0  α ( j )  i   δ ( t   −   τ   ( j )  i   ) ,  where we assume that the   N j   reflective paths contain all first order reflections and higher order ones that are detectable. Notice that for an arbitrary convex polygon, not every mea- surement point has first order echoes to all the walls. We refer to those measurement points can receive all first order echoes as   feasible   measurement points. Denote by   s ( t )   the emitted signal at the speaker. Then the received signal at the microphone for the   j th measurement point is  r ( j )   ( t ) =   s ( t )   ∗   h ( j ) ( t ) +   ω ( t ) ,   (2) where   ∗   denotes linear convolution and   ω ( t )   is the additive noise. Ideally, the delays can be recovered from the received signal   r ( j )   ( t )   if   s ( t )   behaves like a Dirac delta function [17]. However, this requires a wideband acoustic signal along with a wideband acoustic channel, including that of the microphone receiver. A more practical alternative is to emit   s ( t )   with a desired auto-correlation function that is   peaky   and then implement a correlator at the microphone:  m ( j ) ( t ) =   r ( j )   ( t )   ∗   s ( t ) .   (3) Thus, the first and dominant peak of   m ( j ) ( t )   corresponds to the LOS components, while the remaining peaks correspond to reflective components. The time difference of arrival (TDOA) in reference to the LOS component can be used for estimating the delays of different reflective paths. A simple peak-detection method will be introduced in Section V.A, where the chirp signal is used for   s ( t )   because of its nice auto-correlation property. Define a column vector   ̃ r j   =  {   ( τ   ( j )  i   −   τ   ( j ) 0   ) c  2  } N j  i =1  ,   (4) where   c   is the speed of sound and   τ   ( j )  i   is the arrival time of the   i th path with   τ   ( j ) 0   corresponding to the LOS component. Then    ̃ r j   contains all the distances between the device and the walls, along with some higher order terms.  B. Image Source Model  With the image source model [15], reflections within a con- strained space can be viewed as free space LOS propagations from virtual sources to the receiver. Let the coordinate of   O j  be denoted by   o j   . As show in Fig.   1 , the first order image source of   O j   with respect to the   i th wall is   ̃ o j,i   = 2 〈 p i   −   o j   ,   n i 〉 n i   +   o j   ,  where   p i   is any point on the   i th wall,   n i   is the outward norm vector of the   i th wall and   〈 x ,   y 〉   denotes the inner product between   x   and   y . Let   r j,i   be the distance between   O j   and the  i th wall, then  r j,i   = 1  2   ||  ̃ o j,i   −   o j   || 2 .   (5) Moreover, the second order image source of   O j   with respect to the   i th and the   k th wall is   ̃ o j,ik   = 2 〈 p k   −    ̃ o j,i ,   n k 〉 n k   +  ̃ o j,i .  Similarly, we denote by   r j,ik   the half distance between   o j  and    ̃ o j,ik . Following similar steps, higher order image sources can be represented by lower order image sources. Then all
3  Wall   i  Wall   k  !  ɶ  !"  ɶ !  ɶ  Fig. 1: The image source model:    ̃ o j,i   and    ̃ o j,k   are first-order image sources with respect to the   i th and   k th wall and    ̃ o j,ik  is the second-order image source with respect to the   i th and  k th wall in the stated order. the elements of    ̃ r j   can be represented by the real source and image sources. For the rest of the paper, the term   echo   is used to refer to either the delay   τ   ( j )  i   or the corresponding elements of    ̃ r j   if no ambiguity occurs.  C. Two Extreme Cases  The most benign case is when the location of the measure- ment points are known, or equivalently, the distance between pairwise measurement points are given [30]. In this case, only room shape reconstruction is of interest and the problem becomes trivial, at least in the noiseless case. It amounts to finding common tangent lines of circles centered at three non- collinear measurement points. The other extreme is when the reconstruction is free of any geometry information of the measurement points. In this case, both room shape and self-localization are of interest. This was first investigated in [23] where it was established that a large class of convex polygons can be reconstructed by  grouped   first order echoes and, subsequently, the coordinates of measurement points can be also estimated. An important exception is parallelograms and it was shown in [23] that unique reconstruction of parallelograms is impossible using first-order echoes alone. The result was later strengthened in [24] where it was proved that all convex polygons except parallelogram can be reconstructed subject to the usual rotation and reflection ambiguities. III. SLAM   WITH KNOWN PATH LENGTHS  A. SLAM with Two Path Lengths  Consider a convex planar   K -polygon. As shown in Fig. 2 , a mobile device with co-located microphone and loudspeaker emits pulses and receives echoes at   { O j   } 3  j =1 . Without loss of generality, we assume that   O 1   is the origin,   O 2   lies on the   x - axis, and   O 3   lies above the   x -axis. Let   φ   = ( π − ∠ O 1 O 2 O 3 )   ∈  (0 , π )   and the lengths of   O 1 O 2   and   O 2 O 3   be denoted by  d 12   and   d 23 , respectively. 1   Suppose the mobile device is  1 If   φ   ∈   (0 ,   2 π ) , i.e. we do not have control of where to place   O 3 , then the reconstruction is subject to reflection ambiguity (c.f. Theorem III.3).  Wall   i  !  !  !  π   φ −  !   !  θ  Fig. 2: A mobile device is employed to achieve SLAM. The mobile device emits signal and collects echoes at   O 1 ,   O 2  and   O 3   successively. The distances between the consecutive measurement points are   d 12   and   d 23 . capable of measuring its path length when moving from one place to another, i.e.   d 12   and   d 23   are known. Our goal is to simultaneously determine the room shape and the coordinate of   O 3   using first-order echoes. From Fig.   2 , it is straightforward to show that  ( r 2 ,i   −   r 1 ,i ) +   d 12   cos   θ i   = 0 ,   (6)  d 23   cos( θ i   −   φ ) + ( r 3 ,i   −   r 2 ,i ) = 0 .   (7)  B. Ideal Case  Let   r j   =   { r j,i } K i =1   be a column vector with its entries defined   in   (5).   We   assume   for   now   that,   the   one-to-one mapping   f j   :  ̃ r j   7   →   r j   is known for all   j ’s. In other words,  r j,i ’s have been correctly chosen from    ̃ r j   for   j   = 1 ,   2 ,   3   and  i   =   1 , . . . , K . For the rest of the paper, we say that the received echoes are   grouped   if echoes are correctly labeled. The remaining problem is to determine the uniqueness of   θ i ’s and   φ   given (6) and (7). Define   α ii ′   =   −   r 2 ,i − r 1 ,i ′  d 12   and   β ii ′   =   −   r 3 ,i ′   − r 2 ,i  d 23   . For simplicity we denote   α ii   and   β ii   by   α i   and   β i , respectively. Given grouped echoes and Eqs. (6) and (7), we have  θ i   =   ±   arccos   α i   and   θ i   −   φ   =   ±   arccos   β i ,   (8) There are four possible sign combinations for a given   i ,  θ i   = arccos   α i   and   θ i   −   φ   = arccos   β i   (9)  θ i   = arccos   α i   and   θ i   −   φ   =   −   arccos   β i   (10)  θ i   =   −   arccos   α i   and   θ i   −   φ   = arccos   β i   (11)  θ i   =   −   arccos   α i   and   θ i   −   φ   =   −   arccos   β i .   (12)  Lemma III.1.   Suppose   O j   ( j   = 1 ,   2 ,   3)   are feasible and not collinear. Given grouped first order echoes, with probability  1 , there exist exactly two sign combinations such that   (6)   and  (7)   hold simultaneously for all   i   if   φ   and the direction of both   − − − →  O 1 O 2   and   − − − →  O 2 O 3   are randomly chosen. The two possible sign combinations have opposite signs for   φ   and all   θ i ’s and correspond to reflection of each other in terms of recovered room shapes.
4  Proof:   Assume without loss of generality that the ground truth of the polygon is (9) for all   i   ∈ { 1 , . . . , K } . Note that (9) implies that (12) holds for   θ ′  i   =   − θ i   and   φ ′   =   − φ <   0   for all   i , i.e., they correspond to reflections of each other. Suppose multiple sign combinations hold for a wall. With- out loss of generality, let   i   = 1 . From (9) we have  φ   = arccos   α 1   −   arccos   β 1 .   (13) Assume that one of the following equations also holds,  φ   =   −   arccos   α 1   −   arccos   β 1 ,   (14)  φ   = arccos   α 1   + arccos   β 1 ,   (15)  φ   =   −   arccos   α 1   + arccos   β 1 .   (16) Then we have the following three cases 1) If (13) and (14) hold, we must have   θ 1   = 0   which implies that   O 1 O 2   is perpendicular to the first wall, and  φ   =   −   arccos   β 1 . 2) If (13) and (15) hold, we must have   arccos   β 1   = 0 , which implies that   O 2 O 3   is perpendicular to the first wall. 3) If (13) and (16) hold, we must have   φ   = 0 , which contradicts the assumption that   O 1 ,   O 2   and   O 3   are not collinear. Given that the three measurement points are randomly chosen, and, subsequently,   φ ,   − − − →  O 1 O 2   and   − − − →  O 2 O 3   are random, the first two cases do not occur with probability one. If a subset of (10)-(12) holds for   i   and   i ′   simultaneously, then we must have   ( θ i , θ i ′   )   ∈ { θ i   = 0 , θ i   =   φ, φ   = 0 }×{ θ i ′   = 0 , θ i ′   =   φ, φ   = 0 } , which again, do not occur due to randomly chosen measurement points. Similarly, it can be shown that for more than   2   walls, (9) would imply none of (10)-(12) holds for all walls.  C. Echo Labeling  Since echoes may arrive in different orders at different   O j   ’s and    ̃ r j   contains higher order echoes if   N j   > K ,   f j   is usually unknown. We say the received echoes are   ungrouped   if   f j  is unknown for some   j . Thus given    ̃ r j   , our task is to first determine the mapping   f j   , i.e., label the echoes, followed by estimation of   θ i ’s and   φ .  Lemma III.2.   With ungrouped echoes, any mapping   f   ′  j   that differs from the correct mapping   f j   will result, with probability  1 , the following two possible cases  1)   there exists no solution to   (6)   and   (7)   given no parallel edges, or  2)   the reconstructed room shape has larger dimension with respect to parallel edges. Proof:   We illustrate the proof by considering the case  K   = 4 . The result can be easily extended to   K   = 3   and  K >   4 . Suppose again that the ground truth is (9) for all   i . We first consider parallelograms and exclude odd higher order echoes resulting from a pair of parallel walls. The distances between  O j   ( j   = 1 ,   2 ,   3)   and the four walls satisfy  r 1 , 1   +   r 1 , 2   =   r 2 , 1   +   r 2 , 2   =   r 3 , 1   +   r 3 , 2   =   a,   (17)  r 1 , 3   +   r 1 , 4   =   r 2 , 3   +   r 2 , 4   =   r 3 , 3   +   r 3 , 4   =   b.   (18) One can see that for some   f   ′  j   ’s, pairs of   { α ii ′   , β ii ′   }   ( i, i ′   ∈ { 1 ,   2 ,   3 ,   4 } )   are related to each other. Consider for example the  f   ′  j   ’s resulting in   { α 12 , α 21 , α 34 , α 43 }   and   { β 12 , β 21 , β 34 , β 43 } . Since   α 12   +   α 21   = 0 ,   α 34   +   α 43   = 0 ,   β 12   +   β 21   = 0   and  β 34   +   β 43   = 0 , we have  arccos( α 21 ) =   π   ±   arccos( α 12 ) ,  arccos( α 43 ) =   π   ±   arccos( α 34 ) ,  arccos( β 21 ) =   π   ±   arccos( β 12 ) ,  arccos( β 43 ) =   π   ±   arccos( β 34 ) .  Thus (8) reduces to two equations  φ   =   ±   arccos( α 12 )   ±   arccos( β 12 ) , φ   =   ±   arccos( α 34 )   ±   arccos( β 34 ) .  With probability   1 , these two equations do not hold simultane- ously as   α 12 ,   β 12   are independent of   α 34 ,   β 34   due to randomly chosen measurement points. Other   f   ′  j   ( 6 =   f j   ) ’s always have at least two equations with independent choice of   α   and   β . Hence no solution can be found for those instances. Suppose   f   ′  j   ’s are chosen such that we have   α ii ′   and   β ii ′′  ( i   6   =   i ′ , i   6   =   i ′′ ). For rooms with no more than one pair of parallel walls, only echoes chosen according to   f j   ’s satisfy (9) for all   i . This is because for those rooms, at least one of (17) and (18) does not hold. Thus some   α ii ′   ’s and   β ii ′′   ’s are not related since   r 1 i ′   ,   r 2 i   and   r 3 i ′′   are randomly chosen from   ̃ r 1 ,    ̃ r 2   and    ̃ r 3 , respectively. Given parallel edges, however, higher order echoes may also satisfy (6) and (7). For instance, as shown in Fig.   3 , suppose that walls   1   and   3   are parallel. Then it is easy to verify that  r j, 131   −   r j ′   , 131   =   r j, 1   −   r j ′   , 1 , r j, 313   −   r j ′   , 313   =   r j, 3   −   r j ′   , 3 ,  where   j   6   =   j ′ . Hence, (6) and (7) provide the same   cos   θ 1 ,  cos   θ 3 ,   cos( θ 1   − φ )   and   cos( θ 3   − φ )   if   r j, 1   and   r j, 3   are replaced by   r j, 131   and   r j, 313 , respectively. By Lemma III.1, the third order echoes resulting from a pair of parallel edges lead to a larger room with the same norm vectors. Exactly the same argument applies to odd higher order echoes from a pair of parallel edges. Therefore, Lemma III.2 is proved.  Remark   1: The ambiguities resulting from parallel edges can be easily eliminated if we always choose SLAM result with the smallest room size. Given Lemma III.1 and Lemma III.2, we have the following result on the identifiability of any convex polygonal room by using only first order echoes.  Theorem III.3.   With probability   1 , SLAM can be achieved subject to reflection ambiguity given any convex planar   K - polygon, by using the first order echoes received at three random points in the feasible region, with known   d 12   and   d 23  and unknown   φ   ∈   (0 ,   2 π ) . Remark   2: Both the room shape and the coordinate of   O 3  are subject to reflection ambiguity for   φ   ∈   (0 ,   2 π ) . If, however, we can limit   φ   ∈   (0 , π ) , SLAM will be free of such ambiguity.
5  Wall 4  !  !  !  π   φ −  Wall 1 Wall 2 Wall 3  !"  !"  !  !"  Fig. 3: A room with a pair of parallel edges. Here wall   1   and  3   are parallel.  Remark   3: In reality, it is inevitable to collect reflections from the ceiling and the floor. However, by Theorem III.3, if distances corresponding to these echoes are included, no polygon can be recovered provided that the trajectory of the device lies in a plane that is perpendicular to the walls.  D. A Practical Algorithm  In a real acoustic system,   m ( j ) ( t ) ’s in (3) are inevitably corrupted by measurement noise leading to corrupted mea- surement of    ̃ r j   . Let the corrupted version of    ̃ r j   be denoted by   ˆ r j   . Two issues arise. First, given   f j   ’s,   φ   obtained by (8) for different   i ’s are not necessarily identical. The second issue is the possibility that the computed cosine values in (6) may have absolute value exceeding   1 . For the former, we propose a heuristic scheme of choosing the echo and sign combination that yield the smallest variance of the estimated   φ ’s across different   i ’s. Notice that in the noiseless case with perfect echo measurements, the variance of the estimated   φ ’s across different   i ’s is   0   if the correct echo and sign combination is selected while all others will have non-zero (potentially large variance). For the latter, define a feasible   cos   θ i   as  cos   θ i   =        1 ,   if   1   ≤ −   ˆ r 2 ,i − ˆ r 1 ,i  d 12   <   1 +   ǫ  −   ˆ r 2 ,i   − ˆ r 1 ,i  d 12   ,   if   −   1   <   −   ˆ r 2 ,i − ˆ r 1 ,i  d 12   <   1  − 1 ,   if   −   1   −   ǫ <   −   ˆ r 2 ,i   − ˆ r 1 ,i  d 12   ≤ − 1  ,  where   ǫ >   0   is a tuning parameter determined by the noise level. Feasible   cos( θ i   −   φ )   can be similarly defined. The echo combination is said to be infeasible if either   |   ˆ r 2 ,i   − ˆ r 1 ,i  d 12   |   >   1 +   ǫ  or   |   ˆ r 3 ,i − ˆ r 2 ,i  d 23   |   >   1 +   ǫ . Only those feasible   θ i ’s and   φ   will be used in computing the variance of the estimated   φ . As the number of walls for the room is not known in prior, the proposed algorithm needs to first reconstruct some room shapes with   K   = 3 , . . . , N   walls. Then the desired room shape is the feasible one with the largest number of walls. In order to reconstruct a room shape with   K   walls, the number of echo combinations that need to be exhausted is  ( N 1  K  )( N 2  K  )( N 3  K  )  ( K !) 2 .  For simplicity assume that   N   =   N 1   =   N 2   =   N 3 . Let   V th   be the threshold of the variance. The corresponding algorithm is summarized as Algorithm 1.  Algorithm   1   Reconstruct convex polygon given distances between consecutive measurement points  1:   Set   K   = 3   and   V th .  2:   if   K   ≤   N   then  3:   Set   V K   = inf   and the stored polygon with   K   walls be empty.  4:   for   n   = 1 :   (( N K  )) 3 ( K !) 2   do  5:   Based on the   n th echo combination, choose   K  elements from   ˆ r 1 ,   ˆ r 2 ,   ˆ r 3 , respectively.  6:   Compute   cos   θ i ’s and   cos( θ i   − φ )   for   i   = 1 , . . . , K .  7:   if   cos   θ i ’s and   cos( θ i   −   φ )   are feasible   then  8:   Compute Var [ φ ]   for different sign combina- tions and keep the one with the smallest Var [ φ ] .  9:   if   Var [ φ ]   < V K   and the room shape does not fully cover the stored one with   K   walls   then  10:   Keep the echo and sign combination and set   V K   =   Var [ φ ]   for   K .  11:   end if  12:   end if  13:   end for  14:   K   =   K   + 1 .  15:   else  16:   Keep the SLAM results the largest   K   such that   V K   < V th .  17:   end if  E. SLAM with One Path Length  Now that we have established that two distances between three consecutive measurement points are sufficient to over- come the drawback of using first order echoes alone, a natural question is what would be the least amount of information that is required to achieve SLAM for any convex polygons. Specifically we examine the case where only one distance between a pair of measurement points is known. We show that for a parallelogram, there exist multiple rooms satisfying (6) and (19) in this case, thus the answer is negative, i.e. a single distance measurement is insufficient for SLAM with ungrouped first order echoes. Without loss of generality, assume   d 12   is known but   d 23   is not. As shown in Fig.   4 , let   O 1   be the origin,   O 2   be on the x-axis and   O 3 ( x 3 , y 3 ) ( y 3   6   = 0)   is unknown. We also assume that the direction of   − − − →  O 1 O 2   with respect to the desired room is unknown. By geometry, we have (6) and  ( r 3 ,i   −   r 1 ,i ) +   x 3   cos   θ i   +   y 3   sin   θ i   = 0 .   (19) Eq. (19) can also be rewritten in a matrix form  A [ x 3 , y 3 ] T   =   b ,   (20) where  A   =      cos   θ 1   sin   θ 1  . . .   . . .  cos   θ K   sin   θ K       ,  and  b   = [ − ( r 3 , 1   −   r 1 , 1 ) , . . . ,   − ( r 3 ,K   −   r 1 ,K   )] T   .
6  Wall   i  !  !  !   !  θ  Fig. 4: A mobile device is employed to measure the geometry of a room. The mobile device collects echoes at   O 1 ,   O 2   and  O 3   successively. Only the distances between   O 1   and   O 2   ( d 12 ) is known. The ground truth of a parallelogram is assumed to be  A   =       cos   θ 1   sin   θ 1  cos   θ 2   sin   θ 2  cos   θ 3   sin   θ 3  cos   θ 4   sin   θ 4        and   b   =       − ( r 3 , 1   −   r 1 , 1 )  − ( r 3 , 2   −   r 1 , 2 )  − ( r 3 , 3   −   r 1 , 3 )  − ( r 3 , 4   −   r 1 , 4 )        ,  where  r 1 , 1   +   r 1 , 3   =   r 2 , 1   +   r 2 , 3   =   r 3 , 1   +   r 3 , 3 , r 1 , 2   +   r 1 , 4   =   r 2 , 2   +   r 2 , 4   =   r 3 , 2   +   r 3 , 4 .  Let  A ′   =       cos   θ 13   sin   θ 13  cos   θ 24   sin   θ 24  cos   θ 31   sin   θ 31  cos   θ 42   sin   θ 42        b ′   =       − ( r 3 , 1   −   r 1 , 3 )  − ( r 3 , 2   −   r 1 , 4 )  − ( r 3 , 3   −   r 1 , 1 )  − ( r 3 , 4   −   r 1 , 2 )        .  Then  cos   θ 13   + cos   θ 31   = 0   and   cos   θ 24   + cos   θ 42   = 0 .  Moreover, since   sin   θ   =   ±√ 1   −   cos 2   θ ,  sin   θ 13   + sin   θ 31   = 0   and   sin   θ 24   + sin   θ 42   = 0  can hold if we manipulate the sign of square root properly. Then rank ( A ′ ) =   rank ([ A ′ ,   b ′ ]) = 2 . Thus a room shape and the coordinate of   O 3   different from the ground truth and its reflection also satisfy both (6) and (19). IV. E XPERIMENTAL RESULTS  A. Experiment Setup  We describe in the following some preliminary experimental results. Enormous challenges exist to conduct a truly au- tonomous SLAM. Chief among them are: the search space (number of   combinations) is   extremely large   -   using   for example, some modest numbers, e.g.   K   =   4   and   N 1   =  N 2   =   N 3   = 8 , the number of echo combinations exceeds  10 7 , combining with the sign combinations the search space is in   the billions;   the measurement of motion sensors is still subject to large errors and some robustification of the reconstruction algorithm will need to be investigated if the true motion sensor measurements are used. The purpose of the experimental design is thus to demonstrate the feasibility of the proposed scheme in an idealized situation with a certain degree of human intervention to alleviate the above challenges. We use a laptop as a microphone and a HTC M8 phone as our loudspeaker. As the loudspeaker of the cell phone is not omnidirectional and is power limited, we place the speaker of the cell phone towards each wall to ensure the corresponding first order echo is strong enough. Note that the microphone will record both first order echoes and some higher order ones. A chirp signal linearly sweeping from   30 Hz to   8 kHz is emitted by the cell phone. The sample rate at the receiver is  f s   = 96 kHz. It has been shown in [31], [32] that if the input chirp signal is correlated with its windowed version, the output may resemble a delta function, which is desirable for better delay resolution. Our simulation indicates that correlating the  !"#   !"$   !"%   !"&   !""   !"'   !'   !'(   !' )*(+  ,($++  ,(+++  ,$++  +  $++  (+++  ($++  (a) Transmitted signal convolves with itself  !"#   !"$   !"%   !"&   !""   !"'   !'   !'(   !' )*(+  ,(+++  ,"++  ,%++  ,#++  , ++  +  ++  #++  %++  "++  (+++  (b) Transmitted signal convolves with its windowed version  Fig.   5:   Comparison of   convolution result.   The   maximum values of the two convolution result are set to be identical. received signals with its triangularly windowed version outper- forms the correlator using the original one. The comparison is shown in Fig.   5 . Fig.   6   is a sample path of the correlator output collected in the room where this experiment is conducted. In Fig.   6 , peaks marked with red ellipse are desired while those with green ellipse correspond to noise, the ceiling, the floor, higher order echoes or other spurious sources. In our experiment, we use  | m ( j ) ( t ) |   rather than   m ( j ) ( t )   since the true peaks may be either positive or negative. Local maxima of   | m ( j ) ( t ) |   corresponding to Fig.   6   are shown in Fig.   7 . A heuristic way to detect peaks, summarized in Algorithm 3, is to check the slope of each local maxima. Three requirements are   needed   for   the   proposed algorithm:   1)   the   minimum distance between the device and the walls is no less than  d min , 2) the minimum TDOA of two detected consecutive echoes is no less than   ∆ t , 3) the maximum candidate distance corresponding to detected peaks is no more than   d max . The reason for the requirements is as follows: 1) since the corre- lation property of the chirp signal is not ideal and the power of the LOS component is much larger than that of reflective components, the distance between the device and the walls should be large enough such that the peaks corresponding to reflective components are not overshadowed by the LOS component, 2) as the power of reflective paths decays rapidly, it is reasonable to restrict the detectable echoes within certain distances which depends on the power of loudspeaker. Given  d min   =   0 . 6 m,   d max   =   6 . 5 m   and   ∆ t   =   0 . 5 m  c   ,   where
7  !"#   !"$   !"$   !"%   !"%   !"   !"   !"&   !"& '()"  *)"""  * ""  "  ""  )"""  !"#$%&'%()(*   +,--#. +,--#/  (a) Correlator output at   O 1   towards the first wall  !"#   !"#$   !""   !""$   $   $!%%$   $!%& '(&%  )&%%%  )$%%  %  $%%  &%%%   !"#$%&'%()(*   +,--#.  (b) Correlator output at   O 2   towards the second wall  !"#   !"   !"$   !"%   !"&   !"' ()*+  ,%+++  ,$+++  , +++  ,#+++  ,*+++  +  *+++  #+++  +++  $+++  %+++  !"#$%&'%()(*  +,--#.  (c) Correlator output at   O 3   towards the third wall  Fig. 6: Sample of correlator output: Peaks with solid red ellipses correspond to walls while peaks with dash green ellipses correspond to either noise or higher order echoes  c   = 346 m/s, the detection results are marked by arrows in Fig.   7 . We can see that the desired peaks are always detected. In order to detect as less false peaks as possible, one possible modification is to apply a tapering threshold which decreases as   t   increases.  B. SLAM Results  Echoes are collected at   O j   ( j   = 1 , . . . ,   4)   and   d j,j +1   ( j   = 1 ,   2 ,   3)   are measured by tape measure. The proposed peak  Algorithm 2   Peak detection algorithm  1:   find LOS peak   ( t ( j ) 0   , m ( j ) 0   ) .  2:   find local maxima of   | m ( j ) ( t ) |   appearing from   t ( j ) 0   +   t min  to   t ( j ) 0   +   t max .  3:   find all peaks that are   peaky   and store them in   M  4:   set   P   = Ø  5:   if   then | P   |   <   | M   |  6:   if   there exist peaks in   M   whose locations are ”close” to any peak in   P   then  7:   remove those peaks from   M   .  8:   else  9:   add the peak with the largest magnitude of   M   to  P   .  10:   end if  11:   end if  detection algorithm is used to estimate the candidate distances from   received   signals.   Note   that   the   number of   detected peaks are much larger than the number of first order echoes. Heuristics are used to remove peaks (e.g. those of small magnitudes) - otherwise, checking all combinations of echoes become computationally prohibitive. The proposed algorithm for SLAM is verified by experiment at   O 1 ,   O 2 ,   O 3   and   O 2 ,  O 3 ,   O 4 . Given   O 2 ,   O 3 ,   O 4 , we assume that   O 2   is the origin and   O 3   lies on the   x -axis. Even if some elements of   r j   have measurement errors up to   10 cm, SLAM is accomplished with small error of both the room shape and the coordinates of   O 3  and   O 4   with only unlabeled first-order echoes. In the presence of higher order echoes, the proposed algorithm may perform poorly and ambiguity may occur when the variance of   φ   is the only criterion used to determine   f j   ’s. With noisy measurement, it is possible that the incorrect echo combination may yield feasible   θ i   and   φ   with variance smaller than that of the correct echo combination. Furthermore, an interesting phenomenon is that sometimes the proposed algorithm is unable to provide the correct room shape, but the estimate of   φ   is always close to the true value. This means that better echo labeling approach is needed for robust SLAM. As most rooms are regular, we add a heuristic constraint: all the angles of two adjacent walls are between   50 ◦   and   130 ◦ . The comparison between the SLAM result and the ground truth is illustrated in Fig.   8 . The candi- date distances are obtained by the peak detection algorithm. Note that the coordinate system in Fig.   8 (b) is a rotation of that in Fig.   8 (a) by   135 ◦   counterclockwise. The SLAM results shown in the two figures are rotational images of each other. Experimental result indicate that heuristic constraints such as the above can largely eliminate incorrect combinations. V. C ONCLUSION  This work makes progress in acoustic SLAM using a single mobile device with unlabeled first order echoes. Theoretical guarantee of   2 -D SLAM is established when two path lengths corresponding to three consecutive measurement points are available. Conversely, it was also shown that with only a single distance measurement,   2 -d SLAM with unlabeled first order
8  !"#   !"$   !"$   !"%   !"%   !"   !"   !"& '()"  "  #""  %""  &""  *""  )"""  )#""  )%""  )&""  )*""  #"""  !"!#"! $%!&'$()$*&++$,  !"!#"! $%!&'$,)$*&++$(  !"!#"! $%!&'$-)$./01!  (a) Peaks detected from correlator output at   O 1   towards the first wall  !"#   !"#$   !""   !""$   $   $!%%$   $!%&   $!%&$   $!%' ()&%  %  &%%  '%%  *%%  %%  $%%  +%%  ,%%  #%%  "%%  &%%%  !"!#"! $%!&'$()$*&++$,  !"!#"! $%!&'$,)$-./0!  !"!#"! $%!&'$1)$-./0!  (b) Peaks detected from correlator output at   O 2   towards the second wall  !"#   !"#$   !"   !" $   !"%   !"%$   !"$   !"$$   !"& '()*  *  $**  )***  )$**  #***  #$**  ***  !"!#"! $%!&'$()$*&++$,  !"!#"! $%!&'$-)$./01!  !"!#"! $%!&'$,)$./01!  !"!#"! $%!&'$2)$./01!  (c) Peaks detected from correlator output at   O 3   towards the third wall  Fig. 7: Illustration of the performance of the proposed peak detection algorithm. echoes is not possible for all convex polygons. The result is summarized in Table I. While   theoretical   guarantee   can   be   established   for   the noiseless case, the proposed algorithm needs to be enhanced to ensure a fully autonomous   2 -D SLAM. Two particular  3.67 3.06 1.44   4.59  1.4236  3.0509  3.6582  4.5953  1 3 5 º  1 3 9 º  y x 1.62 1.97  26.8º  116.4º   -63.3º  -152.9º  (a) SLAM via echoes collected at   O 1 ,   O 2   and   O 3  4.83 2.30 1.90   3.73  1.8904  2.3067  4.8026  3.7195  y x 1.62   71.0º   160.9º  0.198  -18.2º   -108.1º  125º  124.2º  (b) SLAM via echoes collected at   O 2 ,   O 3   and   O 4  Fig. 8: Comparison between the ground truth (black) and experiment result (red underlined) TABLE I: Feasibility of SLAM with unlabeled first order echoes and different geometry knowledge  geometry knowledge   any convex polygon  d 12 ,   d 23   ,   d 13   Yes  d 12 ,   d 23   Yes  d 12   No  none   No  issues that need to be further addressed include the robustness with respect to measurement noise and the computational complexity when a large number of peaks are detected at each measurement location. R EFERENCES [1]   H. Liu, H. Darabi, P. Banerjee, and J. Liu, “Survey of wireless indoor positioning techniques and systems,”   IEEE Trans. Syst. Man Cybern. C, Appl. Rev. , vol. 37, no. 6, pp. 1067–1080, Nov. 2007. [2]   K. Chintalapudi, A. Padmanabha Iyer, and V. N. Padmanabhan, “Indoor localization without the pain,”   in   Proc. 16th Annu. Int. Conf. Mobile Computing, Networking (MobiCom) , Chicago, IL, USA, Oct. 2010, pp. 173–184. [3]   C. H. Lim, Y. Wan, B. P. Ng, and C. M. S. See,   “A real-time indoor wifi localization system utilizing smart antennas,”   IEEE Trans. Consum. Electron. , vol. 53, no. 2, pp. 618–622, May 2007.
9  [4]   E. Martin, O. Vinyals, G. Friedland, and R. Bajcsy,   “Precise indoor localization   using   smart   phones,”   in   Proc.   18th   ACM   Int.   Conf. Multimedia , Firenze, Italy, Oct. 2010, pp. 787–790. [5]   M. A. Stelios, A. D. Nick, M. T. Effie, K. M. Dimitris, and S. C. A. Thomopoulos, “An indoor localization platform for ambient assisted liv- ing using uwb,” in   Proc. 6th Int. Conf. Advances in Mobile Computing, Multimedia (MoMM) , Linz, Austria, Nov. 2008, pp. 178–182. [6]   J. Schroeder, S. Galler, K. Kyamakya, and T. Kaiser, “Three-dimensional indoor localization in non line of sight uwb channels,”   in   Proc. IEEE Int. Conf. Ultra-Wideband , Singapore, Sept. 2007, pp. 89–93. [7]   Y. Zhou, C. L. Law, Y. L. Guan, and F. Chin,   “Indoor elliptical localization based on asynchronous uwb range measurement,”   IEEE Trans. Instrum. Meas. , vol. 60, no. 1, pp. 248–257, Jan. 2011. [8]   S. Y. Jung, S. Hann, and C. S. Park, “Tdoa-based optical wireless indoor localization using led ceiling lamps,”   IEEE Trans. Consum. Electron. , vol. 57, no. 4, pp. 1592–1597, Nov. 2011. [9]   A. M. Vegni and M. Biagi, “An indoor localization algorithm in a small- cell led-based lighting system,” in   Proc. Int. Conf. Indoor Positioning and Indoor Navigation (IPIN) , Sydney, Australia, Nov. 2012, pp. 1–7. [10]   J. Huang, D. Millman, M. Quigley, D. Stavens, S. Thrun, and A. Aggar- wal, “Efficient, generalized indoor wifi graphslam,” in   Proc. IEEE Int. Conf. Robotics and Automation (ICRA) , Shanghai, China, May 2011, pp. 1038–1043. [11]   A. Canclini, F. Antonacci, A. Sarti, and S. Tubaro,   “Acoustic source localization with distributed asynchronous microphone networks,”   IEEE Trans. Audio, Speech, Language Processing , vol. 21, no. 2, pp. 439–443, Feb. 2013. [12]   Y. Kuang, S. Burgess, A. Torstensson, and K.    ̊ Astr ̈ om,   “A complete characterization and solution to the microphone position self-calibration problem,”   in   Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP) , Vancouver, BC, Canada, May 2013, pp. 3875–3879. [13]   J. L. Blanco, J. A. Fernandez-Madrigal, and J. Gonzalez,   “Efficient probabilistic range-only slam,”   in   Proc. IEEE/RSJ Int. Conf. Intell. Robots, Syst. , Nice, France, Sep. 2008, pp. 1017–1022. [14]   J. Djugash, S. Singh, G. Kantor, and W. Zhang, “Range-only slam for robots operating cooperatively with sensor networks,” in   Proc. IEEE Int. Conf. on Robotics, Automation (ICRA) , Orlando, FL, USA, May 2006, pp. 2078–2084. [15]   I. Dokmani ́ c,   R. Parhizkar,   A. Walther,   Y.M. Lu, and M. Vetterli, “Acoustic echoes reveal room shape,”   Proc. Nat. Academy of Sci. , vol. 110, no. 30, pp. 12186–12191, 2013. [16]   S. Tervo and T. Tossavainen,   “3d room geometry estimation from measured impulse responses,” in   Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP) , Kyoto, Japan, Mar. 2012, pp. 513–516. [17]   F. Antonacci, J. Filos, M.R.P. Thomas, E.A.P. Habets, A. Sarti, P.A. Naylor, and S. Tubaro,   “Inference of room geometry from acoustic impulse responses,”   IEEE Trans. Audio, Speech, and Language Process. , vol. 20, no. 10, pp. 2683–2695, Dec. 2012. [18]   I. Dokmani ́ c, Y.M. Lu, and M. Vetterli,   “Can one hear the shape of a room: The 2-d polygonal case,”   in   Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP) , Prague, Czech Republic, May 2011, pp. 321–324. [19]   D. Ba, F. Ribeiro, C. Zhang, and D. Florencio,   “L1 regularized room modeling with compact microphone arrays,”   in   Proc. IEEE Int. Conf. Acoust. Speech, Signal Process. (ICASSP) , Dallas, TX, USA, Mar. 2010, pp. 157–160. [20]   M. Crocco, A. Trucco, V. Murino, and A. Del Bue,   “Towards fully uncalibrated room reconstruction with sound,” in   Proc. 22nd Eur. Signal Process. Conf. (EUSIPCO) , Lisbon, Potugal, Sept. 2014, pp. 910–914. [21]   I.   Dokmani ́ c,   L.   Daudet,   and   M.   Vetterli,   “From   acoustic   room reconstruction to slam,” in   Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP) , Shanghai, China, Mar. 2016, pp. 6345–6349. [22]   C. Evers, A. H. Moore, and P. A. Naylor,   “Acoustic simultaneous localization and mapping (a-slam) of a moving microphone array and its surrounding speakers,” in   Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP) , Shanghai, China, Mar. 2016, pp. 6–10. [23]   F. Peng, T. Wang, and B. Chen,   “Room shape reconstruction with a single mobile acoustic sensor,” in   Proc. IEEE Int. Conf. Signal, Inform. Process. (GlobalSIP) , Orlando, FL, USA, pp. 1116–1120. [24]   M. Krekovic, I. Dokmanic, and M. Vetterli, “Look, no beacons! optimal all-in-one echoslam,”   arXiv preprint , 2016. [25]   W. Kang, S. Nam, Y. Han, and S. Lee, “Improved heading estimation for smartphone-based indoor positioning systems,” in   Proc. IEEE 23rd Int. Symp. Personal, Indoor, Mobile Radio Commun. (PIMRC) , Sydney, Australia, Sep. 2012, pp. 2449–2453. [26]   F. Li, C. Zhao, G. Ding, J. Gong, C. Liu, and F. Zhao,   “A reliable and accurate indoor localization method using phone inertial sensors,” in   Proc. ACM Conf. Ubiquitous Computing (UbiComp) , Pittsburgh, PA, USA, Sep. 2012, pp. 421–430. [27]   N. Roy, H. Wang, and R. Roy Choudhury,   “I am a smartphone and i can tell my user’s walking direction,”   in   Proc. 12th Annu. Int. Conf. Mobile Syst., Applicat., Services (MobiSys) , Bretton Woods, NH, USA, June 2014, pp. 329–342. [28]   L. Zhang, K. Liu, Y. Jiang, X. Y. Li, Y. Liu, P. Yang, and Z. Li, “Montage:   Combine frames with movement continuity   for realtime multi-user tracking,”   IEEE Trans. Mobile Computing , vol. PP, no. 99, pp. 1–1, 2016. [29]   T. Wang, F. Peng, and B. Chen,   “First order echo based room shape recovery using a single mobile device,” in   Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP) , Shanghai, China, Mar. 2016, pp. 21– 25. [30]   M. Krekovi ́ c, I. Dokmani ́ c, and M. Vetterli, “Echoslam: Simultaneous localization and mapping with acoustic echoes,” in   Proc. IEEE Int. Conf. Acoust., Speech, Signal Process. (ICASSP) , Shanghai, China, Mar. 2016, pp. 11–15. [31]   A. Farina, “Simultaneous measurement of impulse response and distor- tion with a swept-sine technique,” in   Audio Eng. Soc. Conv. 108 , Paris, France, Feb. 2000. [32]   G. Stan, J. Embrechts, and D. Archambeau,   “Comparison of different impulse response measurement techniques,”   J. Audio Eng. Soc. , vol. 50, no. 4, pp. 249–262, 2002.