In this paper, we propose a method for reconstructing the position of a wall surface using a single-element omnidirectional active sonar. The omnidirectional active sonar consists of a single loudspeaker and a single microphone, and the direction of arrival of the reflected wave cannot be known when the robot is stationary. The proposed method can measure the time and direction of arrival of the reflected wave by using the Doppler efect that occurs when the robot is moving. The position of wall surfaces can be reconstructed using the time and direction of arrival of this reflected wave. This paper studies map reconstruction using the proposed method using simulation. We successfully captured the position of the wall surface and reconstructed it using the reflected wave of omnidirectional active sonar. In addition, by selecting moving paths facing in various directions, erroneous images caused by mirror images during reflected wave measurement could be suppressed. Furthermore, increasing the number of iterations of cyclic cross-correlation improved the angular resolution of reflected wave detection and reduced artifacts in the reconstructed images.
Light detection and ranging (LiDAR) has been used as a self-positioning method for indoor
robots, which can obtain information on surrounding objects as a point cloud by measuring the
time-of-flight of light[
Acoustic positioning methods are resilient to dust and fog. Some of the methods that have been proposed for positioning using sound waves include the installation of acoustic beacons
(a) Mapping phase Tracking system
Wall
Reconstructed wall position
e v a w iltceyoV tlfeceedR titiseynn Mapping n o i t c e ir d & n o ii t s o p s ' t o b o R (b) Positioning phase
Wall
e v a w ltiecoyV ltfeecedR tiitsenny Self-positioning
as fixed stations[
We have proposed an omnidirectional active sonar with an audible sound source that
can measure omnidirectional distance and have shown that it could perform self-position
estimation[
In this paper, we propose a mapping method for self-position estimation using the timeand direction-of-arrival of reflected waves measured by omnidirectional active sonar. An omnidirectional active sonar is an acoustic transceiver with a single loudspeaker and microphone. Therefore, when the transceiver is stationary, information on the direction of arrival of sound waves cannot be obtained. Mapping with such a device with unknown directional information is challenging. The proposed method obtains information on the direction of arrival of sound waves from the Doppler efect generated by moving the transceiver. This principle enables mapping with only a single transceiver. The overview of the proposed method is shown in Fig. 1(a). The robot has omnidirectional active sonar and wheel rotary encoders. In addition, a tracking system is installed in the measurement environment. These sensor-obtained data, such as the robot’s moving speed, acoustic reflection intensity, and self-position, will be used to create a map. Fig. 1(b) shows an example of self-position estimation. The self-position can be estimated without the tracking system by referring to the acoustic reflection map. The method proposed in this paper is evaluated on numerical simulations using the finite-diference time-domain (FDTD) method[13, 14, 15]. The numerical method used to validate the proposed method can simulate the Doppler efect of sound waves and multipath. The novelty of this study is that only a single loudspeaker and microphone are used to reconstruct the wall position. In general sonar techniques, a sensor array is configured to obtain the direction of arrival of sound waves. On the other hand, our proposed method obtains the direction of the arrival of sound waves by measuring the Doppler shift obtained from a moving sound source.
Section 2 describes a method for measuring the time- and direction-of-arrival of reflected waves from omnidirectional active sonar and a preliminary mapping method. Section 3 describes a simulation method when the transmitter and receiver points are moving. Section 4 describes the conditions of the simulation. Section 5 describes the results of the simulation and its discussion. Section 6 is the conclusion.
2.1. Method of measuring arrival time and direction of reflected waves In this section, we describe a method for measuring the time- and direction-of-arrival of reflected waves using omnidirectional active sonar. Omnidirectional active sonar consists of a pair of loudspeakers and a microphone, and can emit sound waves in all horizontal directions. Fig. 2 shows a schematic diagram of the reflected wave measurement method. The loudspeaker outputs a binary phase-modulated signal with maximal-length-sequence (m-sequence) codes. Where the carrier frequency is c, the sequence length of the M-sequence code is , the chip rate is 1/c, the number of repetitions is , and the sampling frequency is s. ()( ) shown in Fig. 2 is a block of transmitted signals of length c s. A microphone located above the loudspeaker records in sync with the loudspeaker. ()( ) shown in Fig. 2 is the th received signal block, whose length is the same as that of the transmitted signal. The arrival time and direction of the reflected wave are determined by the circular cross-correlation of the transmitted signal block and the received signal block after resampling. The ratio of resampling is defined by = a + () cos ( / ) a − () cos ( / ) (1) Resampling Resampling
Resampling L∙Tc∙M∙fs samples
BPSK signal by M-sequence Coaxially placed omnidirectional loudspeaker and microphone
Circular cross-correlation Circular cross-correlation Circular cross-correlation (Top view)
Wall 1
Wall2
W all 3
Envelope Envelope Envelope 0 0 e t a n e t a c n o C where a is the speed of sound and () is the current velocity of movement. This equation assumes that the magnitude of the Doppler shift occurring at the transmitter is equal to that of the Doppler shift occurring at the receiver. The inverse transform of the Doppler shift that occurs for all angles between the robot’s movement vector and the sound wave’s arrival ()( ) for = 0 to = . The signal direction from 0 to is calculated by computing length of one cycle of circular cross-correlation is cs, which is one sequence of M-sequence codes.
()( ) in Fig. 2 is the circular cross-correlation function of the resampled received signal ℎ and the transmitted signal block. The instantaneous amplitude ℎ¯()( ) of ℎ()( ) is calculated using the Hilbert transform to obtain the intensity value of the reflected wave. ℎ¯()( ) means the amplitude intensity of the reflected wave arriving from / direction at the th received signal block. The concatenation process shown in Fig. 2 transforms ℎ¯()( ) calculated from = 0 to = into the matrix (,) , where is the columns, and is the rows. corresponds to the direction of arrival by / , and corresponds to the distance to the wall by a /(2s). It is a two-dimensional heat map in polar coordinates. 2.2. Method of reconstructing wall positions Fig. 3 shows a schematic diagram of the mapping method. The map is created using the matrix (,) , the intensity amplitude of the reflected wave calculated in 2.1, and the accurately measured global coordinates (p), p
(), and direction (p). Heat maps in polar coordinates created in 2.1 are converted to heat maps in Cartesian coordinates. The amplitude intensity corresponding to the coordinate point (, ) in the Cartesian coordinates is represented by ^ () , = (=)^ (,), =^ (,), ^ (, ) = round ^ (, ) = round ︃(
| arctan( ) − (p)| )︃ ︃( 2s√︀(Δ)2 + (Δ)2 )︃ a
, (g) ,g =(g− ,1)g + ^()
=g − (p),=g − (p) , where (p) is round(p
()/Δm) and (p) is round(p()/Δm). The magnitude of the value of g ,g indicates the existence of a reflective wall surface.
In this paper, we verify that it is possible to estimate the position of a wall surface when omnidirectional active sonar transmits and receives sound in a room where a wall surface exists. The signals received by the microphones from sound waves emitted by a moving sound source indoors are reproduced by numerical simulations. In this section, we describe a numerical method for wave propagation when the transmitting and receiving points are moving. A sound wave propagating in two-dimensional space is represented by ︂( + )︂ + 1 = 0, (7) 0 + 1 = 0, (8) 0 where is the sound pressure, and are the particle velocity, and 0 is the density of the medium. Discretization of this governing equation by the central finite diference using a staggered grid is represented by (9) (10) (11) (12) (13) (14) (15) +1 = , − , 0a2Δ (︁ Δ
++11//22, − −+11//22, +,+1/2 − ,+− 11//22)︁ ,
+1/2 − 1/2 Δ (︀ +1, − , )︀ , ++11//22, = +1/2, − 0Δ ,++11//22 = ,−+11//22 − 0ΔΔ (︀ ,+1 − , )︀ , where and are discrete grids in the and directions, Δ = Δ is the grid width of the discretization, and Δ is the time step. It is a numerical method called the FDTD method. The moving transmitting and receiving points were simulated using the direct method[13, 14]. This method places the moving transmit and receive points directly on the grid at each simulation step. If the coordinates of the transmitting and receiving points do not exist on the grid, the sound pressure values of the coordinates of the four neighboring points are used to interpolate. When the coordinates of the transmitting point is (s, s), the sound pressure is given to the four points ⌊s/Δ⌋,⌊s/Δ⌋, ⌈s/Δ⌉,⌊s/Δ⌋, ⌈s/Δ⌉,⌈s/Δ⌉, and ⌊s/Δ⌋,⌈s/Δ⌉. The weight of the sound pressure given to each point is calculated by ⌊s/Δ⌋,⌊s/Δ⌋ = (1 − )(1 − )/4, ⌈s/Δ⌉,⌊s/Δ⌋ = (1 + )(1 − )/4, ⌈s/Δ⌉,⌈s/Δ⌉ = (1 + )(1 + )/4, ⌊s/Δ⌋,⌈s/Δ⌉ = (1 − )(1 + )/4, = 2(s − ⌊ Δs/Δ⌋) − 1, (16) = 2(s − ⌊ Δs/Δ⌋) − 1, (17) where ⌊ ⌋ is floor function and ⌈ ⌉ is ceiling function. For the receiving point, the received sound pressure is the sum of the four points in the neighborhood of the receiving point multiplied by the same weights as the transmitting point. The diference between the simulation results with and without a wall was used as the received waveform at the microphone to assume an ideal received signal that does not contain direct waves. The wall boundary condition is an impedance boundary[15]. A perfectly matched layer (PML) is set at the edge of the simulation space[16].
Table 1 shows the parameters of the proposed signal processing method. The carrier frequency c of the transmitted signal is 10 kHz, the sequence length of the M-sequence code is 1023, the chip rate 1/c is 10 kHz, and the sampling frequency s is 40 kHz. The number of iterations is 10. At this time, the length of the signal used for a single measurement is 1.023 s. The number of arrival directions is 29. The discrete grid widths Δm and Δm for mapping are 50 mm. Experiments have verified these parameters using loudspeakers and microphones to measure reflected waves. Table 2 shows the parameters of the FDTD method. The spatial grid widths Δ and Δ of the staggered grid are 5 mm, the time step Δ is 8.333 s, the number of spatial cells is 1000 × 1000 cells, the sound speed a is 340 m/s, the density of the medium 0 is 1.293 kg/m3, and the acoustic impedance of the wall surface is infinite. The appearance of the Doppler efect under these simulation conditions was verified beforehand.
Fig. 4 shows the omnidirectional active sonar’s travel path and the wall surface’s position. Two diferent travel paths were created for the omnidirectional active sonar. The omnidirectional active sonar’s instantaneous movement speed () while moving along these paths was always set to 0.1 m/s. In this case, the distance traveled in one measurement time is 0.1023 m.
Fig. 5 shows ^(), measured at points (a), (b), and (c) in Fig. 4. The intensity values are scaled with the maximum value of 1. Fig. 5(a) shows the result measured at point (a) in Fig. 4. Checking the distance from point (a) to the wall in Fig. 4, Wall 1 is 2 m in the direction, and Wall 2 is 2.5 m in the direction. The other wall surfaces are out of sight. Fig. 5 (a) shows that the reflection intensity is higher at ( = 2 m, = 4 m) and ( = 4.5 m, = 2 m). It is Wall 1
goal Path A Path B 4 consistent with the position of the wall in Fig. 4. The same can be confirmed at points (b) and (c). Therefore, the proposed system can appropriately estimate the distance and direction of the wall. In Fig. 5(a), the reflection intensity is also large at ( = 4.5 m, = 4 m). It is considered a reflected wave generated at the corners of Wall 1 and Wall 2. The intensity of the reflected wave is large at ( = 5.5 m, = 1 m) in Fig. 5(a). The reflected wave image results from multiple start
1 1.0 reflections observed through walls 1, 2, and 3. The proposed method assumes that the Doppler shift of the same magnitude occurs at the emission and reception of sound waves. Therefore, the position of the reflected wave image of multiple reflections, where the Doppler shift of diferent magnitudes occurs in emission and reception, does not coincide with the reflected wave’s arrival direction. Fig. 5(a) shows a symmetrical shape with / 4 rad, the direction of sonar travel, as the axis. This phenomenon is caused by the fact that the proposed method cannot distinguish sound waves arriving from symmetrical directions with the direction of motion as the central axis. Although the proposed method uses the Doppler efect to measure the direction-of-arrival, reflected waves from symmetrical directions with the direction of motion as the central axis have a Doppler shift of the same magnitude. Therefore, it is challenging to determine a wall’s position with only one measurement uniquely.
Fig. 6 shows the results of the mapping. Fig. 6(a) is the map created when the sonar moved along path A in Fig. 4. This result shows that the values are large at the wall surface locations. In particular, the values are large at the corners. The wall surfaces are installed at right angles in this simulation. If the corners installed at right angles are within line-of-sight, reflected waves are always observed at the same locations. Therefore, the values are larger at these locations. There are also positions other than walls and corners where the values are larger. It is because a mirror image is output in the estimation of the direction of arrival. In particular, Fig. 6(a) outputs a linearly erroneous image inside the wall surface. Since path A contains a straight path at an angle of / 4, the mirror image of a horizontally installed wall appears vertical. The mirror image of a vertically installed wall appears horizontally. Fig. 6(b) is a map created when the sonar moves along path B in Fig. 4. For path B, the size of the wrong image decreased. Because path B is traveling in a large curve, the sonar takes measurements while facing more directions than path A. As a result, the erroneous image is dispersed in space because the mirror image is 6 (a) 5 not concentrated at a specific point.
Fig. 7 shows the reconstruction results when the number of cyclic cross-correlation iterations is varied. The number of cyclic cross-correlation iterations is related to the signal length used in one measurement. As the length of the signal used in the measurement increases, the cyclic cross-correlation’s frequency resolution improves, allowing the detection of smaller Doppler shifts. Therefore, increasing the number of iterations contributes to the angular resolution of the detection results. Fig. 7(c) shows a decrease in curvilinear artifacts compared to Fig. 7(a). As shown in Figure 5, the detection result of the reflected wave outputs an image on an arc with angular spread. Increasing the number of iterations and improving the angular resolution narrows the arc angle. As a result, it is less likely that incorrect images on the arc will be output in the reconstruction process.
In this paper, we propose a method of indoor mapping using omnidirectional active sonar. Omnidirectional active sonar uses the Doppler efect to obtain the time- and direction-of-arrival of reflected waves. In addition, a position measurement system, such as a tracking system, obtains the exact position of the robot. The information obtained from these sensors was used to estimate the position of the wall surface. This paper verifies the method by numerically calculating the sound waves emitted by a moving sound source using the FDTD method. As a result, reflected waves were measured at the same location as the wall surface. In addition, the location of the wall could be mapped in global coordinates. However, measuring reflected waves using the Doppler efect also outputs a mirror image, producing erroneous images even at locations where no wall surface exists. This erroneous image reduces by using measurements with paths that point in various directions. Furthermore, increasing the number of iterations of cyclic cross-correlation improved the angular resolution of reflected wave detection and reduced artifacts in the reconstructed images.
This work was supported by JSPS KAKENHI Grant Number 22KJ0431. [12] A. Tsuchiya, N. Wakatsuki, T. Ebihara, K. Zempo, K. Mizutani, Time-of-arrival measurement method for reflected waves from multiple directions using doppler efect by a single coaxially placed omnidirectional sp and mic, in: Proceedings of the 29th International Congress on Sound and Vibration, 2023, pp. 1–8. [13] T. Tsuchiya, M. Kanamori, Moving sound source with an arbitrary trajectory in the twodimensional finite-diference time-domain method, Japanese Journal of Applied Physics 60 (2021) SDDB02. [14] T. Tsuchiya, Y. Teshima, S. Hiryu, Two-dimensional finite diference-time domain simulation of moving sound source and receiver, Acoustical Science and Technology 43 (2022) 57–65. [15] O. Yamashita, T. Tsuchiya, Y. Iwaya, M. Otani, Y. Inoguchi, Reflective boundary condition with arbitrary boundary shape for compact-explicit finite-diference time-domain method, Japanese Journal of Applied Physics 54 (2015) 07HC02. [16] Q. Qi, T. L. Geers, Evaluation of the perfectly matched layer for computational acoustics, Journal of Computational Physics 139 (1998) 166–183.