Ultra-wide-band-based adaptive Monte Carlo localization for kidnap recovery of mobile robot

Abstract

In the article, a global localization algorithm based on improved ultra-wide-band-based adaptive Monte Carlo localization is proposed for quick and robust kidnap recovery of mobile robot. First, two ultra-wide-band modules, the tag installed inside the mobile robot and the anchor installed inside charging station, are used to obtain the relative distance between the mobile robot and the charging station. Second, the global grid map is converted into a map with obstacle noise given the ranging accuracy of the ultra-wide-band modules with different obstacles. Third, while the robot is kidnapped, matching grids are screened based on the range information of ultra-wide-band modules and the obstacle noise of the grids. Finally, global localization algorithm is performed based on ultra-wide-band-based adaptive Monte Carlo localization to convert randomly generated particles from the whole map into randomly generated particles in the local map. Experimental results based on gazebo simulation and a real scenario showed that our global localization algorithm based on improved ultra-wide-band-based adaptive Monte Carlo localization not only significantly helped to improve the chances of the robot global pose recovery from lost or kidnapped state but also enabled the robot kidnap recovery with a smaller number of randomly generated particles, thus reducing the time to recover its accurate global localization. The algorithm was also more effective especially for kidnap recovery in a similar and large scenario.

Keywords

Kidnap recovery UWB-based adaptive Monte Carlo localization grid map mobile robot

Introduction

Intelligent mobile robots are playing a more and more important role as logistics robots, cleaning robots, food delivery robots, and so on. The accurate global localization technology is a key problem for the mobile robot navigation.^1
–3 However, when the robot is in a complex and dynamic working environment, it is particularly prone to losing its global poses.

Depending on how mobile robot localizes itself in the global coordinate system, it can be divided into relative and absolute localization.⁴ Relative localization of mobile robot, also known as position tracking, assumes that the initial position of mobile robot is known and uses sensor information from adjacent moments to track and estimate the robot’s current position. Common relative localization methods include the odometry and inertial navigation methods.⁵ Absolute localization is also known as global positioning and the initial robot position is also unknown in advance. Global localization of mobile robot requires a predetermined environment model or external localization information provided directly by the robot from sensors to estimate the robot’s position in the global coordinate system. Common absolute localization methods mainly include landmark localization, map matching and probabilistic localization, and so on.⁶ In this article, the ultra-wide-band (UWB) modules for point-to-point ranging can be classified as absolute positioning according to this classification.

In robotics, the process of describing the environment and understanding it by mobile robot relies mainly on global maps. There are four main types of map representation: grid map, feature point map, direct representation, and topological map.⁷ The most common description is the grid map, which divides the environment into a series of grids, each of which is given a possible value that indicates the probability of the grid may be occupied.⁸ Feature point map represents the environment in terms of relevant geometric features (e.g. points, lines, faces) and are commonly used in visual SLAM.⁹ The direct representation method, which eliminates the intermediate mitigation of features or rasters, directly uses data from sensors to construct the robot’s positional space.¹⁰ Topological map is a relatively more abstract form of map. The indoor environment is represented as a topological structure map with nodes and associated connecting lines.¹¹ In this article, an obstacle noise variable based on UWB ranging accuracy is introduced for each grid based on the grid map, which reduces the area range of randomly generated particles during robot localization while avoiding the loss of correct particles due to the influence of UWB ranging accuracy.

The difficulties and challenges of global localization arise from three main aspects.¹² First, a priori position is lost, that is, the position of the robot in the previous application is unknown. Second, changes occur during repositioning and closed-loop detection.¹³ Third, the problem of large scale exists, when matching the information observed by the sensors with the different positional information in the map, and results in computational complexity.¹⁴

Adaptive Monte Carlo localization (AMCL) is an optimization of the Monte Carlo localization (MCL) algorithm that allows the robot to recover from a global localization failure. In fact, the particle can only survive in the vicinity of a single scene, and if that scene happens to be incorrect, the algorithm will not be able to recover. This means that in practice we need to use a larger number of particles to cover as much of that pose as possible. A large number of particles mean a huge amount of computation, and the trade-off between efficiency and the probability of successfully recovering the global localization is important.

Based on the grid map and AMCL, this article uses the UWB modules to obtain the precise point-to-point distance between the mobile robot and the charging station, and in view of the influence of different obstacles on the UWB ranging accuracy, the grid map is converted into a grid map representation with obstacle noise. Two UWB modules used in the article consist of an anchor and a tag. The UWB modules can offer the rough distance data from the tag to the anchor, which are easily and separately installed inside the robot and the charging station. Based on the ranging distance date given by the tag module, we propose an occupied raster map with obstacle noise based on the ranging characteristics of the UWB modules, which facilitates mobile robot to localize a more accurate particle generation area during global localization. The effective ranging distance of the UWB modules is relatively far, even more than 300 m. They are suitable for very large working scene. We only need to localize the charging station on the robot global map. Then the position of the anchor is known and motionless. The tag may move along with the mobile robot. Additionally, the UWB modules do not need to be deployed in advance in the working scene. The prices of the UWB modules are very low and the ranging data of the tag can be obtained in real time. The UWB modules are very easy to use in a word. The global localization of the AMCL algorithm is optimized, and the randomly particles generated by the global localization are converted into randomly particles generated by the localization. This work has substantially improved the chances of the robot recovering global positioning. In addition, the global map scattering approach is optimized for local map scattering, effectively reducing the number of particles required for localization and reducing the time required to recover global localization. The mobile robot can also easily recover its global pose in a similar and large scenario.

In summary, our main contributions are:

Based on the UWB ranging accuracy in different obstacles, the map rasterization is optimized in such a way that for each grid in addition to the occupied state, the noise of different obstacles is included;

UWB-based relative distance is used to improve efficiency of AMCL global localization;

Extensive experiments have been carried out in a real environment and the scheme is effective in reducing the number of particles required by the AMCL, thus reducing the time and having a higher success probability of relocalization.

Related works

There are several algorithms for solving the global localization problem. The most classical approach is the AMCL algorithm proposed by Fox et al., a standard and popular tool in the field of mobile robotics.^15
–17 This approach used 2D laser, artificial features, and optimized computational methods to complete the global localization process. This approach represented the probability density involved by maintaining a set of samples that are randomly drawn from it. Using a sampling-based representation to obtain a localization method that could represent arbitrary distributions. The resulting method was able to efficiently localize a mobile robot without knowledge of its starting location.

Bosse et al. presented an enhanced algorithm for matching laser-scanned maps using histogram correlation.¹⁸ The histogram representation effectively summarizes the salient features of the map so that map pairs could be matched efficiently without the need to guess their alignment in advance. To work well in outdoor unstructured environments, the algorithm was enhanced in the following ways: a series of entropy measures of the projected histogram can be used instead of the orientation histogram, the projected histogram was weighted by the orientation of the scanned points to make the projected histogram more salient, and an empirical method was used to determine a threshold for the quality metric which produces few false positives. This technique greatly improved the ability of Atlas scan matching to achieve real-time closure of large loops, even when the odometer was unavailable. In addition, the ability to quickly identify matches without the need for an initial guess at alignment allowed for real-time resolution of mobile robots.¹⁹

Olson proposed and experimentally validated a 2D SLAM system that combined scan-to-submap matching with loop closure detection and graphical optimization.²⁰ Individual submap trajectories were created using a local, grid-based SLAM approach. In the background, all scans were matched to nearby submaps, using pixel-accurate scan matching to create loop closure. The constraint maps for submaps and scan poses were regularly optimized in the background.²¹

Ding and Feng presented the DeepMapping, a novel alignment framework that used deep neural networks (DNNs) as an auxiliary function to align multiple point clouds from scratch to a globally consistent framework.²² They used DNNs to model highly nonconvex mapping processes that traditionally involve manual data correlation, sensor pose initialization, and global refinement. The key novelty was that “training” these DNNs with properly defined unsupervised losses was equivalent to solving potential alignment problems, but was not iterative closest points (ICP) sensitive to good initialization.

Fahima and Abdelkrim proposed a novel method for mobile robot localization and navigation based on multispectral visual odometry.²³ The proposed approach consisted in combining visible and infrared images to localize the mobile robot under different conditions (day, night, indoor, and outdoor). The proposed approaches were validated with success experimentally for trajectory tracking using the mobile robot called Pioneer P3-AT through the real experiments.

Zhao et al. proposed a coupled UWB/inertial navigation sensor (INS) localization framework which combining the UWB technique and the INS.²⁴ A minimum variance unbiased finite impulse response (MVU FIR) method was then applied to obtain accurate position and velocity estimations from noisy measurements. It could handle the kidnapped problem, and recover from some extreme failures satisfactorily. Moreover, the MVU FIR filtering algorithm was fast and easily implementable.

System overview

The flow of the improved global localization system is shown in Figure 1. The mobile robot is given a global grid map of the scene before it is localized. The internal odometer $X_{o, k} = [x_{o, k}, y_{o, k}, θ_{o, k}]^{T}$ is widely used to provide easy accessible real-time rough pose estimation for mobile robot. The pose errors accumulate constantly and orientation errors dominate as they can grow without bound into translational position errors. Due to slippery and uneven floor, wheel slippage can also result in odometry error, as well as uncontrolled motion. The gyroscope on the IMU installed inside the mobile robot acquires the Euler angles by means of angular velocity integration. However, the mobile robot works in a 2D horizontal environment, as the pitch and roll angles can be ignored and only the heading angle $θ_{i m u, k}$ is used.

Figure 1.

Flow chart of the global localization system.

The heading angle $θ_{i m u, k}$ is used to correct the orientation error given by the internal odometer using extended Kalman filter, which is a common sensor fusion algorithm. The heading angle can be updated by the following equations

Δ θ_{o, k} = θ_{o, k} - θ_{o, k - 1}

Δ θ_{i m u, k} = θ_{i m u, k} - θ_{i m u, k - 1}

Δ θ_{k} = Δ θ_{o, k} + P_{k} Δ θ_{i m u, k}

where P_k is an estimate covariance; P_k is usually set to a constant near to 1, considering that the IMU can provide very accurate angle data in a short sampling time. We can compute the new odometry pose estimate $X_{k} = [x_{k}, y_{k}, θ_{k}]^{T}$ at current time k based on the estimated orientation angle variable $Δ θ_{k}$ . If $Δ θ_{k} \neq 0$ , X_k is expressed as

X_{k} = [\begin{matrix} x_{k - 1} + r_{k} (s i n (θ_{k - 1} + Δ θ_{k}) - s i n (θ_{k - 1})) \\ y_{k - 1} - r_{k} (c o s (θ_{k - 1} + Δ θ_{k}) - c o s (θ_{k - 1})) \\ θ_{k - 1} + Δ θ_{k} \end{matrix}]

else if $Δ θ_{k} = 0$ , X_k is expressed as

X_{k} = [\begin{matrix} x_{k - 1} + Δ D_{k} s i n θ_{k - 1} \\ y_{k - 1} + Δ D_{k} c o s θ_{k - 1} \\ θ_{k - 1} \end{matrix}]

where $r_{k} = Δ D_{k} / Δ θ_{k}$ is the radius of movement; $Δ D_{k}$ is a track curvature or length of track line the mobile robot movement, which can be directly obtained from the odometry; $Δ θ_{k} = θ_{k} - θ_{k - 1}$ ; $X_{k - 1} = [x_{k - 1}, y_{k - 1}, θ_{k - 1}]^{T}$ is the pose estimate at last sampling time $k - 1$ .

AMCL is a probabilistic localization system for mobile robot moving in the 2D horizontal space, using the particle filter (PF) to track robot poses in an already known map, and works well for a wide range of local localization problems. $X_{k} = [x_{k}, y_{k}, θ_{k}]^{T}$ to help complete the motion update of the AMCL algorithm, and then the filter is updated based on the laser scanning data to complete the measurement update.

However, the global localization algorithm is triggered while the robot is kidnapped or lost. The original AMCL algorithm uses randomly generated particles over the entire map, and updates the particles through a resampling process and releases new particles, eventually converging to a cluster of particles that may or may not be correct. The improved AMCL algorithm introduces the UWB modules, which consist of an anchor and a tag and are used to measure the distance $D_{u w b}$ between the robot and the charging station. Given that UWB modules have different ranging accuracy for different obstacles, the grid map is converted to a grid map with obstacle noise, and the grids closer to the wall will have greater ranging error. Based on the relative distance information provided by the UWB modules about the distance from the robot to the charging station, we improve the area where AMCL initializes randomly generated particles. The PF of AMCL converts the random particle generation from generating particles on the whole grid map to generating particles on an incomplete and not perfectly regular circle. Within this defined area, the resampling process is repeated to form a cluster of aggregated particles.

Preparation for algorithm

The distance measurement of UWB

In this article, two UWB modules are used as nodes, one node called anchor is placed at the charging station and the other node called tag is placed on the robot. UWB modules are communication device similar to Bluetooth, and their ranging principle is based on calculating the product of the time of flight (TOF) and the speed of electromagnetic wave propagation, so the main mechanism of the modules is to record the time of sending and arrival of information by exchanging messages and the UWB modules have a high static ranging accuracy of $10 cm$ in the absence of obstacles, and a fast update rate of 50HZ.

As shown in Figure 2, we place the charging station in the designated position $X_{p} = [x_{p}, y_{p}, θ_{p}]$ . To simplify the task, we install the UWB module anchor inside the station at the same height from the ground as the UWB module tag mounted on the robot, and read the relative distance $D_{u w b}$ from the tag between the robot and the charging station via the serial port.

Figure 2.

The distance measurement of UWB modules. UWB: ultra-wide-band.

In addition, as the UWB ranging principle is calculated based on TOF, the farther the robot is from the charging station, the wider the TOF of the electromagnetic waves and the more accurate the measurement will be. For example, $D_{k + 3}$ in the Figure 2 is much more precise than D_k . We set up the UWB modules to dynamically adjust the measurement error according to the distance, thus ensuring that the specified area is as small as possible while ensuring that possible poses are not overlooked.

UWB-based occupied grid map with obstacle noise

The pre-built global map is one of the basic input data for localization and navigation of robots. In this article, an occupied grid map is used. This map is a rasterization of the working scene into a series of grids, for each of which the status is either occupied, free or unknown as shown in Figure 3. Each grid is therefore given a possible value that indicates the probability that it will be occupied.

Figure 3.

The definition of grids.

In an occupied grid map, we use $p (s = 1)$ to denote the state in which this grid is free and $p (s = 0)$ to denote the state in which it is occupied, with the sum of the two probabilities being 1. It is too cumbersome to use two values for a grid to represent occupancy, so the ratio $O d d (s) = \frac{p (s = 1 | z)}{p (s = 0 | z)}$ of the two is introduced as the state of the grid.

Bringing the Bayesian formula into this equation

O d d (s | z) = \frac{p (z = 1 | s = 1)}{p (z | s = 0)} \times O d d (s)

Take the logarithm of both sides of the equation (6), the term containing the measured value is left with only $log (\frac{p (z | s = 1)}{p (z | s = 0)})$ , this ratio is a measurement model, and there are only two models of measurement values, $l o f r e e = log (\frac{p (z = 0 | s = 1)}{p (z = 0 | s = 0)})$ and $l o o c c u = log (\frac{p (z = 1 | s = 1)}{p (z = 1 | s = 0)})$ , both of which are constant values. Therefore, updating the status of a point is a simple addition or subtraction, and the larger the value of a grid is, the more likely it is occupied. While the smaller the value is, the more likely free it is.

In the program, the map is transferred from the world coordinate system to a grid coordinate system, each grid has two numbers i, j and the size of the grid is related to the resolution of the map. For example, a map resolution of $0.15 cm$ means that $3 m$ is represented by 20 grids. In addition, as the accuracy of the UWB modules vary considerably in terms of noise affected by different obstacles, we assign each grid a ranging noise variable representing the permissible error in the distance of that grid coordinate from the charging station grid coordinate. Figure 4 shows a schematic diagram of an occupancy grid map with obstacle noise based on UWB ranging accuracy. As known from experiments, the UWB ranging error with a $45 cm$ thick concrete wall obstacle is about $0.30 m$ . Therefore, the obstacle noise variable of the grid closest to the wall is set to $30 cm$ ; the obstacle noise variable of the farther grid is set to $15 cm$ ; the farther grid is not affected by this and the obstacle noise variable is set to 0. Then the value of each free grid can be set: $V_{g r i d} = V_{g r i d} + N D$ , where $N D$ is a noise constant determined by the distance from the grid to the nearest obstacle. This grid map representation with obstacle noise is used to reduce possible matching grids in the process of kidnap recovery with consideration of the UWB ranging error.

Figure 4.

The occupied grid map with obstacle noise.

Improved global localization based on UWB-based AMCL

MCL is a localization algorithm that represents confidence $b e l (x_{t})$ in terms of particles and is applicable to both local and global localization problems. The adaptive nature of AMCL is reflected in the application of Kullback–Leibler Divergence (KLD) sampling, where the difference between two probability distributions is calculated by KLD to obtain a statistical bound for evaluating the quality of the sample, and the number of particles is determined based on this bound.

The core of our algorithm lies in the PF, which uses a large number of samples to describe the probability density of states. UWB modules are used to help robot global localization using fewer samples, reducing time while maintaining the success rate of the robot in recovering global localization. Similarly, our algorithm goes through four stages of initializing the particle swarm, recursive sample, weight calculation, and resampling.

In this article, the mobile robot is in a known two-dimensional map of the environment, where the coordinate and heading angle of motion of the mobile robot are randomly generated, a maximum $M_{χ max}$ and minimum number $M_{χ min}$ of adaptive particles are set, and each particle is initialized to a robot’s positional data. Approximating the confidence level $b e l (x_{t})$ with a series of particles $χ_{t}$ , assuming that the likelihood that the state hypothesis $χ_{t}$ is contained in the set of particles $χ_{t}$ and its proportionality to the Bayesian filtered posterior $b e l (x_{t})$

x_{t}^{[m]} \sim p (x_{t} | z_{1 : t}, u_{1 : t})

For each particle, a prediction of the next state is performed based on the robot’s motion state. The relative poses provided by the wheel odometry and IMU are used for prediction in this article, and point cloud matching using laser is used to calculate the degree of proximity and assign weights $W_{t}^{i}$ . The closer the assumed poses of the particles are to the true poses, the greater the weights are. Then the weight of the updated example is

W_{t}^{i} = p (z_{t} | x_{t}^{[i]})

Maintain a weight for each particle and initialize the weight to 1

W_{t}^{i} = p (z_{t} | x_{t}^{[i]}) W_{t - 1}^{i}

KLD sampling algorithm is taken for sampling, and KLD algorithm generates new particles until the number of particles exceeds $M_{χ}$ and the defined minimum value $M_{χ min}$ . $M_{χ}$ is the number of particles given as the number needed to reach the statistical bound determined by the particles. The threshold $M_{χ}$ is the active target for the number of particles M. The larger the number of samples M produced by the algorithm, the higher the threshold $M_{χ}$ will be. As M increases with each new sample, M will eventually reach $M_{χ}$ . Then, KLD sampling process stops.

As shown in Algorithm 1, the UWB-based AMCL localization algorithm is given. The first to fifth lines of the Algorithm 1 filter all the free grids on the map according to the distance data provided by the UWB, and only those grids that match the UWB ranging data can have particles on them. The fifth line calls the $U p d a t e A c t i o n$ interface of the odometer object to complete the motion update. The filter is then updated based on the scanning data from the laser. The measurement update of the PF is done via the $U p d a t e S e n s o r$ interface of the object of laser. The empirical measurement likelihood is calculated in row 13 and the short and long term likelihood averages are maintained in rows 16 and 17. The maintenance is done mainly by means of two parameters $α_{s l o w}$ and $α_{f a s t}$ . $α_{s l o w}$ is the estimated long-term average decay rate of the prime filter and $α_{f a s t}$ is the estimated short-term average decay rate of the prime filter. If the short-term likelihood $ω_{f a s t}$ is inferior to the long-term likelihood $ω_{s l o w}$ , then random sampling is increased in proportion to the ratio of the two values. Conversely, no random sampling is added.

Algorithm 1.

AMCL with the relative distance of UWB.

Input:

χ_{t - 1}

(collection of particles at time

t - 1

);

f r e e g r i d s

(free grids on the map);

D_{u w b}

(distance between charging station and robot); z_t (measurement at time t); m (environmental map);
Output:

χ_{t}

(collection of particles at time t)

1: for grid in free grids do

2: if $∥ D_{u w b} - D ∥ \leq D_{e r r o r}$ then

3: designed grids $\leftarrow$ grid

4: end if

5: end for

6: if particle in $χ_{t}$ $\in$ designed grids then

7: ${\bar{χ}}_{t}$ $\leftarrow$ this particle

8: end if

9: for m=1 to M do

10: $x_{t}^{[m]}$ =UpdateAction(u_t , $x_{t - 1}^{[m]}$ )

11: $ω_{t}^{[m]}$ =UpdateSensor(u_t , $x_{t - 1}^{[m]}$ ,m)

12: ${\bar{χ}}_{t}$ = ${\bar{χ}}_{t}$ + $〈 x_{t}^{[m]}, ω_{t}^{[m]} 〉$

13: $ω_{a v g}$ = $ω_{a v g}$ + $\frac{1}{M} ω_{t}^{[m]}$

14: end for

15: Declare $ω_{s l o w}$ , $ω_{f a s t}$ , $α_{s l o w}$ , $α_{f a s t}$

16: $ω_{s l o w}$ = $ω_{s l o w}$ + $α_{s l o w}$ ( $ω_{a v g}$ - $ω_{s l o w}$ )

17: $ω_{f a s t}$ = $ω_{f a s t}$ + $α_{f a s t}$ ( $ω_{a v g}$ - $ω_{f a s t}$ )

18: for $m = 1$ to M do

19: if $ω_{f a s t}$ $<$ $ω_{s l o w}$ then

20: add random pose to $χ_{t}$

21: else

22: draw $i \in {1, 2, ..., N}$ with probability $\infty$ $ω_{t}^{[i]}$

23: add $χ_{t}^{[i]}$ to $χ_{t}$

24: end if

25: end for

26: return $χ_{t}$ (collection of particles at time t)

Figure 5 shows a running process of the algorithm flow of the original AMCL and UWB-based AMCL optimization. As can be seen, AMCL algorithm before the improvement attempts to recover localization over the whole global grid map, converging to a particle swarm after continuous iteration. However, UWB-based AMCL algorithm provides a rough distance between the robot and the charging station as a range of possible areas to delineate the scattering point, effectively reducing the size of the map to be matched, i.e. substantially improving the efficiency of the matching and, at the same time, being more robust for the success of recovering the global pose.

Figure 5.

Schematic diagram of global localization based on original AMCL and improved UWB-based AMCL. (a) Global localization based on original AMCL. (b) Global localization based on improved UWB-based AMCL.AMCL: adaptive Monte Carlo localization; UWB: ultra-wide-band.

Algorithm 2 shows the strategy for calling the UWB-based AMCL algorithm for global localization, distinguishing whether the robot is powered on or off. Power on or off determines whether the IMU is calibrated, optimizing the all-random nature of the particles when the AMCL algorithm recovers the global poses. The calibrated IMU provides a better heading angle, and the particles generated at this moment can converge quickly to a correct pose. When the robot is switched off and restarted, the IMU is not calibrated, the data are invalid and the heading angles of the generated particles are random, but the UWB can still provide a defined region to speed up convergence.

Algorithm 2.

Global Localization in both power-on and power-off conditions.

Input: UWB distance and AMCL algorithm
Output:

p o s e = [x, y, θ]

1: The pose of a particle

2: Call the UWB-based AMCL algorithm

3: Determining whether the robot was powered on or off before it was lost

4: if power on then

5: IMU’s heading angle still works fine

6: The heading angle of all generated particles $y a w = θ_{i m u}$

7: else

8: IMU is not calibrated, invalid

9: Generated particles with random heading angles

10: end if

11: return $p o s e = [x, y, θ]$

Figure 6 shows a gazebo simulation map scene of the algorithm demonstration map, with the actual robot position marked with yellow circles on the map and the UWB anchor marked with red squares. The robot positions in the gazebo scene and the demonstration map can easily be seen that the UWB-based AMCL algorithm found the correct position, while the original AMCL algorithm found an incorrect position in Figure 5(b). This position was also a high scoring region during resampling, but the original AMCL probably did not find the correct position because the particles were out at the correct position. In summary, the UWB-based AMCL algorithm reduces the probability of losing particles with the correct poses and has better robustness.

Figure 6.

The gazebo scene of the schematic diagram.

Experiment and result analysis

Environmental map and equipment parameters

In order to verify the effectiveness of the global localization of the improved AMCL algorithm, the experimental analysis was carried out and a mobile robot turtlebot2 was adopted. The UWB modules used were the LinkTracKP manufactured by $N o o p l o o p$ , and the laser was UTM-30LX made by $H O K U Y O$ .

In Figure 7(a), the real experimental environment consisted of the indoor environment and the corridor environment. The charging station was set up in the indoor room. The real scene size of the map was about $12 m \times 9.65 m$ . The indoor environment was complex, diverse and feature-rich, and for a robot with a correct initial position, the robot could work very well. There were also similar features in Figure 7(a). If the robot was unpredictable to get lost, it would be very difficult to recover its global pose. In the Figure 7(b), a global grid map of the real scene was built by Gmapping. The charging station was pre-set and localized accurately in the global coordinate system. As we could see, there were many similar features like square areas in the global grid map.

Figure 7.

Experimental indoor environment and grid map. (a) The real experimental environment. (b) The grid map built by Gmapping.

Figure 8 shows the whole process of how to recover its global pose after turtlebot2 was lost. The robot continuously obtained the relative distance data from tag of UWB modules and accurate heading angles from IMU sensor. While turtlebot2 was judged to be lost, the UWB-based AMCL algorithm began to run. Finally, the robot localized itself accurately within a short time.

Figure 8.

The whole process of improved UWB-based AMCL algorithm. (a) 0s, (b) 3.50s, (c) 6.35s, and (d) 9.78s. AMCL: adaptive Monte Carlo localization; UWB: ultra-wide-band.

The ranging accuracy of UWB

In the UWB modules’ ranging principle, we mentioned that the UWB modules could have a large impact due to TOF and obstacles, so here we tested the accuracy of UWB ranging in static and dynamic condition without the impact of obstacles and the impact of different obstacles on the UWB ranging accuracy respectively. The results of this experiment facilitated us to correct for the noise of obstacles in the map. In addition, a dynamic factor was provided to adjust the UWB distance accuracy at different distances.

Figure 9 shows the distance accuracy in the static case when the actual distance of the UWB modules was $1 m$ , $3 m$ and $5 m$ respectively.

Figure 9.

UWB ranging accuracy without obstacle effects.

It could be easy to see that the robot was less accurate at shorter distances from the charging station due to the TOF, for example, the distance was only displayed by UWB modules near $0.4 m$ between the two and nearer than that value, it was not detected due to the short flight time. In addition, the distance between the two was within $0.4 m \sim 2 m$ , the error differed from the real value; the distance between the two was within $2 m \sim 4 m$ , the error between the robot and UWB was controlled within $0.15 m$ ; above $4 m$ , the UWB modules could submit very good accuracy, the error was basically within $0.10 m$ . In summary, it was easy to conclude that the UWB modules could provide a measurement of distance with good accuracy in a promenade environment, and therefore UWB was well suited for use in a promenade environment to help robot localization.

When ranging, the obstruction of an obstacle could cause an increase in ranging error. When the obstruction was close to the robot or charging station, the effects of the obstacles were very high. When the distance was farther away, the electromagnetic waves of the UWB could easily cross over and had less effects. Considering that the use of our mobile robot was mainly in indoor, we defaulted to the obstruction being very close to our equipment. The obstacle was considered to be close to the robot. In addition, we set the charging station $5 m$ from the obstacle and the robot $1 m$ from the obstacle, and the line between the charging station and the robot was perpendicular to the geometric segment of the obstacle.

Table 1 shows the impact of common obstacles in indoor environments on the UWB modules. Among them, wooden board and cardboard have essentially no effect on the UWB ranging accuracy, which comes from the error of the UWB modules. The greatest impact was from solid walls, where a wall could cause a maximum error in ranging of around $30 cm$ . So we focused on the solid walls on the map and placed obstacle noise near the walls of the partitions in the gallery and indoor environment in Figure 7(a) to cover all possible places where the robot could be.

Table 1.

The ranging errors of UWB affected by different obstacles.

	Thickness of barrier	Maximum error
Solid walls	20 cm	30 cm
Glass walls	3 cm	10 cm
Cardboard or wood	5 m	10 cm

UWB: ultra-wide-band.

Results of the improved global localization

Here we tested the global localization of the original AMCL algorithm and the UWB-based AMCL algorithm separately. We compared the robot movements in three ways: first, the robot was stationary in place and performs a mandatory No-Motion update. Second, the robot only performed a rotational motion in place to trigger the PF to work. Third, we controlled the robot to move randomly around the map to trigger the PF to work. Each scenario was measured $30$ times and the time taken for the particles to converge to the final particle population was recorded, regardless of whether the final pose was correct or incorrect. In addition, we also set up two separate scenarios with a higher number of particles and a lower number of particles for the experiments.

As shown in Table 2, the maximum number of particles was set to $2000$ and the minimum number of particles was set to $500$ . From the data in Table 2, it could be seen that the original AMCL algorithm had a poor success rate in converging to the correct position with no motion or just rotating in place, and a good success rate in finding the position only when the robot was controlled to move randomly, but in either case the convergence time was longer.

Table 2.

Comparison between algorithms when the max number of particles is 2000 and the min number is 500.

	No-Motion		OnlyRotate		RandomMove
	GetRate^a	AvgTime^b	GetRate	AvgTime	GetRate	AvgTime
Original AMCL	0.267	42.87 s	0.6333	45.61 s	0.867	39.82 s
UWB-based AMCL	0.600	13.59 s	0.833	14.78 s	0.967	13.53 s

AMCL: adaptive Monte Carlo localization; UWB: ultra-wide-band.

^a Number of times correct localization/number of all times.

^b Average time-consuming.

Compared to the original AMCL, the UWB-based AMCL algorithm had a good probability of recovering the pose without motion or with rotation only, especially when the robot was controlled for random motion. In addition, the convergence time to the final pose was about three times more efficient in terms of average time spent, which significantly reduced time and improved efficiency.

As shown in Table 3, the maximum number of particles was set to $500$ and the minimum number of particles was set to $200$ , and in combination with the grid map in Figure 7(a), the environment was large and the number of particles is clearly insufficient for the original AMCL, which was particularly likely to lead to particle scarcity, although the time efficiency was about $22 %$ higher than the average time in Table 2. This did not lead to a failure of localization, so the original AMCL algorithm for global localization needed to balance the number of particles with the size of the scene.

Table 3.

Comparison between algorithms when the max number of particles is 500 and the min number is 200.

	No-Motion		OnlyRotate		RandomMove
	GetRate^a	AvgTime^b	GetRate	AvgTime	GetRate	AvgTime
Original AMCL	0.133	32.86 s	0.333	33.79 s	0.7333	29.35 s
UWB-based AMCL	0.433	11.81 s	0.667	12.16 s	0.900	11.27 s

AMCL: adaptive Monte Carlo localization; UWB: ultra-wide-band.

^a Number of times correct localization/number of all times.

^b Average time-consuming.

Compared to the original AMCL algorithm, the UWB-based AMCL algorithm had a lower probability of recovering the localization without the motion and with rotation only, but still had a good success rate. In addition, there was still a good success rate in the case of controlled random robot movements. In terms of time efficiency, the improvement was small, with a reduction of about $2 s$ . This was also as expected, as the UWB-based AMCL algorithm took most of the time to traverse all the grids to filter the area we need, which varied with the size of the map scene and the CPU, and was about $3 \sim 4 s$ in our experiment.

Conclusion

In this article, we propose a global localization algorithm based on improved UWB-based AMCL for quick and robust kidnap recovery of mobile robot. Two UWB modules are used to obtain the rough distance data, which can be easily installed inside the robot and the charging station. Based on the distance date given by tag of UWB modules, we propose an occupied raster map with obstacle noise based on the original occupied raster map and the ranging characteristics of UWB, which facilitates mobile robot to localize a more accurate particle generation area during global localization. Then based on the rough distance data, the global localization process of AMCL algorithm is further improved, and the convergence of the generated random particles of the whole map is improved to the convergence of the generated random particles of the local map, which solves the problem that the original AMCL global localization takes too much long time and the global localization especially in a similar scenario is totally wrong. From the experiments of gazebo simulation and a real scenario, our global localization algorithm based on improved UWB-based AMCL not only significantly helps to improve the chances of the robot global pose recovery from lost or kidnapped state, but also enables the robot global pose recovery with a smaller number of randomly generated particles, thus reducing the time to recover its accurate global localization. The algorithm is also more effective especially for kidnap recovery in a similar and large scenario.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received financial support for the research, authorship, and/or publication of this article: This project is supported by National Key Research and Development Program of China under Grant No. 2019YFB1310004 and National Natural Science Foundation of China under Grant No. 61973336.

ORCID iD

Rui Lin

Wei-wei Zhao

References

Akai

. Reliable Monte Carlo localization for mobile robots. Computer Science - Robotics 2022; 1–29.

Moura

Rizzo

Serrano

. BIM-based localization and mapping for mobile robots in construction. In: 2021 IEEE international conference on autonomous robot systems and competitions (ICARSC), Santa Maria da Feira, Portugal, 28–29 April 2021, pp. 12–18. IEEE.

Alavi

Pahlavan

. Modeling of the TOA-based distance measurement error using UWB indoor radio measurements. IEEE Commun Lett 2006; 10(4): 275–277.

Cadena

Carlone

Carrillo

, et al. Past, present, and future of simultaneous localization and mapping: toward the robust-perception age. IEEE Trans robot 2016; 32(6): 1309–1332.

Paull

Saeedi

Seto

, et al. AUV navigation and localization: a review. IEEE J Ocean Eng 2103; 39(1): 131–149.

Levinson

Thrun

. Robust vehicle localization in urban environments using probabilistic maps. In: 2010 IEEE international conference on robotics and automation, Anchorage, USA, 3–7 May 2010, pp. 4372–4378. IEEE.

Dissanayake

Newman

Clark

, et al. A solution to the simultaneous localization and map building (SLAM) problem. IEEE Trans Robot Autom 2001; 17(3): 229–241.

Durrant-Whyte

Bailey

. Simultaneous localization and mapping: part I. IEEE Robot Autom Magazine 2006; 13(2): 99–110.

Mur-Artal

Montiel

JMM

Tardos

. Orb-SLAM: a versatile and accurate monocular SLAM system. IEEE Trans Robot 2015; 31(5): 1147–1163.

10.

Bloesch

Omari

Hutter

, et al. Robust visual inertial odometry using a direct EKF-based approach. In: 2015 IEEE/RSJ international conference on intelligent robots and systems (IROS), Hamburg, Germany, 28 September–2 October 2015, pp. 298–304. IEEE.

11.

Ravankar

Emaru

, et al. A hybrid topological mapping and navigation method for large area robot mapping. In: 2017 56th annual conference of the Society of Instrument and Control Engineers of Japan (SICE), Kanazawa, Japan, 19–22 September 2017, pp. 1104–1107. IEEE.

12.

Perera

Collins

. Novel embedded system based species recognition system for pest control. Int J Comput Digit Syst 2016; 5(5): 387–393.

13.

Alonso

Llorca

DFF

Gavilan

, et al. Accurate global localization using visual odometry and digital maps on urban environments. IEEE Tran Intell Transp Syst 2012; 13(4): 1535–1545.

14.

Xie

Nashashibi

Parent

, et al. A realtime robust global localization for autonomous mobile robots in large environments. In: 2010 11th international conference on control automation robotics & vision, Singapore, 7–10 December 2010, pp. 1397–1402. IEEE.

15.

Dellaert

Fox

Burgard

, et al. Monte Carlo localization for mobile robots. In: Proceedings 1999 IEEE international conference on robotics and automation (Cat. No. 99CH36288C), Detroit, USA, 10–15 May 1999, pp. 1322–1328. IEEE.

16.

Fox

Burgard

Thrun

. Active Markov localization for mobile robots. Robot Auton Syst 1998; 25(3–4): 195–207.

17.

Fox

. Adapting the sample size in particle filters through KLD-sampling. Int J Robot Res 2003; 22(12): 985–1003.

18.

Bosse

Zlot

. Map matching and data association for large-scale two-dimensional laser scanbased SLAM. Int J Robot Res 2008; 27(6): 667–691.

19.

Bailey

. Mobile robot localisation and mapping in extensive outdoor environments. Citeseer 2002; 70–92.

20.

Olson

. M3RSM: many-to-many multi-resolution scan matching. In: 2015 IEEE international conference on robotics and automation (ICRA), Seattle, USA, 26–30 May 2015, pp. 5815–5821. IEEE.

21.

Hess

Kohler

Rapp

, et al. Real-time loop closure in 2D lidar SLAM. In: 2016 IEEE international conference on robotics and automation (ICRA), Stockholm, Sweden, 16–21 May 2016, pp. 1271–1278. IEEE.

22.

Ding

Feng

. Deepmapping: unsupervised map estimation from multiple point clouds. In: Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, Long Beach, USA, 15–20 June 2019, pp. 8650–8659. IEEE.

23.

Fahima

Abdelkrim

. Multispectral visual odometry using SVSF for mobile robot localization. Unmanned Syst 2022; 10(03): 273–288.

24.

Zhao

Huang

Liu

. Localization of indoor mobile robot using minimum variance unbiased FIR filter. IEEE Trans Autom Sci Eng 2018; 15(2): 410–419.