Grid Map Merging with Ant Colony Optimization for Multi-Robot Systems

Abstract

Multi-robot systems have recently been in the spotlight in terms of efficiency in performing tasks. However, if there is no map in the working environment, each robot must perform SLAM which simultaneously performs localization and mapping the surrounding environments. To operate the multi-robot systems efficiently, the individual maps should be accurately merged into a collective map. If the initial correspondences among the robots are unknown or uncertain, the map merging task becomes challenging. This chapter presents a new approach to accurately conducting grid map merging with the Ant Colony Optimization (ACO) which is one of the well-known sampling-based optimization algorithms. The presented method was tested with one of the existing grid map merging algorithms and showed that the accuracy of grid map merging was improved by the ACO.

1. Introduction

Multi-robot systems [1] have recently been in the spotlight because of the advantage that it can perform a given task more efficiently than a single robot system and can perform several tasks at the same time. For the design and construction of such a multi-robot system, various algorithms which are not required in a single robot system are required. If a multi-robot system is operated in unknown environments, it needs to conduct multi-robot simultaneous localization and mapping (SLAM) [2] to acquire the poses of multiple robots and a collective map for operating the give task cooperatively without collisions. An example of a multi-robot system for multi-robot SLAM in unknown environments is shown in Figure 1. The cooperation module which conducts global multiple path planning, relative robot pose estimation, and multiple map merging can be placed on the leader robot or a central control system. The wireless router can be located in the leader robot or another place to cover the operation area of multiple robots. The bandwidth for the wireless communication depends on the size of the operation area and the map representation method. To conduct SLAM, each robot needs sensors to acquire environmental data. Based on the SLAM result, each robot can plan a local path and move toward its own goal safely.

Figure 1.

An example of a multi-robot system in unknown environments.

The most frequently used sensor for SLAM is a light detection and ranging (LiDAR) [3] which measures ranges by targeting an object with a laser and measuring the time for the reflected light to return to the receiver. LiDAR can also be used to make digital three-dimensional representations of areas on the earth’s surface and ocean bottom, due to differences in laser return times, and by varying laser wavelengths. Because a LiDAR can provide a lot of information about the surrounding environment, it has been used widely for SLAM. An example of using a LiDAR for a mobile robot is as shown in Figure 2(a). If SLAM is conducted with a LiDAR, a map is generally represented by an occupancy grid map as shown in Figure 2(b). The white, black and gray grids represent empty, occupied and unknown areas, respectively. The size of grids can be adjusted according to the resolution of the LiDAR and the memory size in the embedded system.

Figure 2.

Occupancy grid map built by a mobile robot with a LiDAR sensor. (a) Mobile robot with a LiDAR sensor (b) Occupancy grid map.

The key algorithm in multi-robot SLAM is the grid map merging algorithm in the cooperation module in Figure 1 which accurately aligns and fuses the individual grid maps of multiple robots. Many grid map merging algorithms have been developed, and they have their own advantages over others. However, for the more accurate grid map merging, all the algorithms need an optimization method to align the individual grid maps more precisely. In this work, we propose a new approach based on a sampling-based optimization method for grid map merging. The proposed approach was successfully conducted with other grid map matching algorithms and updated the map transformation matrix between robots more accurately.

The remainder of this paper is organized as follows. In Section 2, multi-robot SLAM is briefly described. In Section 3, the definition and classification of grid map merging are described. In Section 4, the proposed approach which is a grid map merging with ACO is presented. Section 5 shows and analyzes the experimental results of the proposed approach. Finally, conclusions are given.

2. Multi-robot SLAM

SLAM is to concurrently conduct two processes which are called localization and mapping, respectively. Mapping is to acquire a map of its surrounding environments to plan a path to its own goal without collisions with structures. Localization is to estimate its own pose within the acquired map. Unfortunately, SLAM is not easy because the two processes in SLAM depend on each other. In other words, the localization process requires a map as a reference to estimate its own pose, and the mapping process requires a pose which consists of location and orientation as a reference point to represent a map. Many researches have been conducted to conduct SLAM efficiently, and several nice solutions have been recently proposed. However, SLAM is still an open problem in the context of accuracy, reliability, and computational cost.

Multi-robot SLAM is to conduct the SLAM task using multiple robots for the sake of completing localization and mapping more efficiently. An example of configuring a two-robot SLAM is shown in Figure 3. Each robot conducts SLAM with its own sensors. Based on the multiple SLAM results gathered through the communication modules, the global state has been updated.

Figure 3.

An example of configuring a two-robot SLAM.

Due to the errors in sensors for multi-robot SLAM, the global state estimation is generally conducted with probabilistic formulations. The estimation of the two-robot SLAM state in Figure 3 can be formulated as follows:

$$\begin{array}{l}P\left(x_{1:t}^1,x_{1:t}^2,\mathit{M}|z_{1:t}^1,u_{0:t-1}^1,x_0^1,z_{s:t}^2,u_{s:t-1}^2,{\Delta }_s^{21}\right)\\ =P\left(\mathit{M}|x_{1:t}^1,z_{1:t}^1,x_{s:t}^2,z_{s:t}^2\right)P\left(x_{1:t}^1|z_{1:t}^1,u_{0:t-1}^1,x_0^1\right)P\left(x_{s:t}^2|z_{s:t}^2,u_{s:t-1}^2,x_s^1,{\Delta }_s^{21}\right)\end{array}$$E1

where $x_{k:t}^i$ is the trajectory for robot $i$ at times $k,k+1,\cdots ,t$, and $\mathit{M}$ is the merged map, and $u_{k-1:t-1}^i$ is the sequence of actions executed by robot $i$, and $z_{k:t}^i$ is the sequence of observations from robot $i$, and ${\Delta }_s^{21}$ is the relative pose between two robots at time $s$ . Extended Kalman filters (EKF) [4] and Rao-Blackwellized particle filters (RBPF) [5] have been widely used as estimation methods for the probabilistic formulation. At the beginning of the estimation, the uncertainty of the state is large. But, as time goes, the uncertainty of the state has been gradually reduced if the observation measurements are acquired consistently, and data association is conducted properly. Especially, whenever loop closures [6] are conducted, the uncertainty of the state can be significantly reduced.

3. Grid map merging

The key algorithm to ensure the performance of multi-robot SLAM with LiDAR sensors is the grid map merging algorithm because even if the performance of the SLAM results of individual robots are good, the performance of multi-robot SLAM depends on the quality of the map transformation between robots. The concept of the grid map merging in multi-robot SLAM with LiDAR sensors is shown in Figure 4. Quantitatively, the grid map merging can be performed by acquiring a map transformation matrix $\mathit{T}$ (MTM) which consists of translation amounts and a rotation angle between robots as follows:

Figure 4.

The concept of the grid map merging in multi-robot SLAM with LiDAR sensors.

$$\mathit{T}\left({\Delta }_x,{\Delta }_y,{\Delta }_{\theta }\right)=\left[\begin{array}{ccc}cos{\Delta }_{\theta }& -sin{\Delta }_{\theta }& {\Delta }_x\\ sin{\Delta }_{\theta }& cos{\Delta }_{\theta }& {\Delta }_y\\ 0& 0& 1\end{array}\right]$$E2

where ${\Delta }_x,{\Delta }_y$ and ${\Delta }_{\theta }$ are the translation amounts and a rotation angle between robots, respectively.

The method to find the MTM can be categorized into direct map merging and indirect map merging according to the existence of the direct sensor measurements between robots or common objects. The direct map merging is to directly acquire the map transformation matrix by obtaining the inter-robot measurements which consist of relative distance and orientation between robots, which can be performed under a rendezvous. The indirect map merging acquires the map transformation matrix by finding and matching the overlapping areas of the individual maps of robots, which is called map matching. The detailed categorization of them and the brief descriptions of the previous works are summarized in [7, 8]. They have their own advantages, but they require commonly an optimization method to update the MTM more accurately regardless of the type of map merging.

4. Ant colony optimization for grid map merging

Given an MTM $\mathit{T}$, the objective function $\mathbf{\Phi }$ to evaluate how two individual maps ${\mathit{M}}_1$ and ${\mathit{M}}_2$ are well overlapped for the merged map optimization can be defined as follows:

$$\mathbf{\Phi }\left({\mathit{M}}_1,{\mathit{M}}_2,\mathit{T}\right)=\sum _{x=a_1}^{a_2}\sum _{y=b_1}^{b_2}{\mathit{M}}_1\left(x,y\right)·\left[\mathit{T}{\mathit{M}}_2\left(x,y\right)\right]$$E3

where $a_1\le x\le a_2$ and $b_1\le y\le b_2$ are the whole ranges of the x and y coordinates of ${\mathit{M}}_1$ and ${\mathit{M}}_2$. Because $\mathit{T}$ includes sinusoidal functions for map rotation, the objective function $\mathbf{\Phi }$ has nonlinearity and thus is hard to be solved in a closed form.

Therefore, the optimization of $\mathbf{\Phi }$ for grid map merging needs to be considered with sampling-based optimization such as MCO (Monte-Carlo Optimization) [9], PSO (Particle Swarm Optimization) [10] and ACO (Ant-Colony Optimization) [11]. They require commonly much computation due to their own iterative property. Instead, they are easy to implement regardless of the complexity or nonlinearity of the objective function. Thus, it is a reasonable approach to apply sampling-based optimization methods to the merged map optimization. This paper applies the ACO to the merged map optimization because the ACO requires the relatively smaller number of samples than the MCO and the PSO in the case of the merged map optimization. The ACO is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Artificial ants locate optimal solutions by moving through a parameter space representing all possible solutions. Real ants lay down pheromones directing each other to resources while exploring their environment. The simulated ants similarly record their positions and the quality of their solutions, so that in later simulation iterations more ants locate better solutions [12].

The ACO needs to be modified to be applied to the merged map optimization. Because an even slight variation in the rotation angle causes a largely different map merging result in grid map merging, the concept of pheromones in the ACO cannot be properly applied to finding the optimal rotation angle. Therefore, each sample in a search space consists of x and y translations except for a rotation angle. Besides, since the search space for x and y translations may be largely different, the search space for the ACO for grid map merging needs to be divided into two areas which contains the possible configurations of x and y translations respectively as shown in Figure 5.

Figure 5.

The modified search space for the ACO for grid map merging.

In general, the $i$-th ant moves from state $q$ to $r$ with probability as follows:

$$p_{\mathit{qr}}^i=\frac{{\left({\tau }_{\mathit{qr}}\right)}^{\alpha }{\left({\eta }_{\mathit{qr}}\right)}^{\beta }}{{\sum }_{z\in \mathit{\text{allowed}}q}{\left({\tau }_{\mathit{qz}}\right)}^{\alpha }{\left({\eta }_{\mathit{qz}}\right)}^{\beta }}$$E4

where ${\tau }_{\mathit{qr}}$ is the amount of pheromone deposited for transition from state $q$ to $r$. $0\le \alpha$ is a parameter to control the influence of ${\tau }_{\mathit{qr}}$, which was set to 1 in this work. ${\eta }_{\mathit{qr}}$ is the desirability of state transition $\mathit{qr}$, which is typically set to the reciprocal value of the distance. $1\le \beta$ is a parameter to control the influence of ${\eta }_{\mathit{qr}}$. ${\tau }_{\mathit{qz}}$ and ${\eta }_{\mathit{qz}}$ represent the trail level and attractiveness for the other possible state transitions.

In the original ACO, the distance is the Euclidean distance between states. But, it needs to be redefined for grid map merging. In other words, the distance is not the Euclidean distance between the nodes but a new metric to evaluate how two individual grid maps are well overlapped. For a candidate tour of the $i$-th ant, ${\Lambda }_i=\left\{q_j^i,r_k^i\right\}$ where $q_j^i$ and $r_k^i$ are respectively the j-th and the k-th sample in the areas for x and y translations, the new metric $\mathbf{\Psi }$ is defined similarly to Eq. (3) as follows:

$$\mathbf{\Psi }\left({\Lambda }_i\right)=\frac{1}{{\sum }_{x={\stackrel{\sim }{a}}_1}^{{\stackrel{\sim }{a}}_2}{\sum }_{y={\stackrel{\sim }{b}}_1}^{{\stackrel{\sim }{b}}_2}{\mathit{M}}_1\left(x,y\right)·\left[\mathit{T}\left(q_j^i,r_k^i,0\right){\stackrel{\sim }{\mathit{M}}}_2(x,y)\right]}$$E5

where ${\stackrel{\sim }{\mathit{M}}}_2$ is the transformed ${\mathit{M}}_2$ by a direct or indirect grid map merging algorithm. ${\stackrel{\sim }{a}}_1\le x\le {\stackrel{\sim }{a}}_2$ and ${\stackrel{\sim }{b}}_1\le y\le {\stackrel{\sim }{b}}_2$ are the whole ranges of the x and y coordinates of ${\mathit{M}}_1$ and ${\stackrel{\sim }{\mathit{M}}}_2$ after conducting the grid map merging algorithm. In this work, since the rotation angle is not a target of the merged map optimization with the ACO, the rotation angle in $\mathit{T}$ is set to 0.

The global pheromone is updated as follows:

$${\tau }_{\mathit{qr}}\leftarrow \left(1-\rho \right){\tau }_{\mathit{qr}}+\sum _i^{N_{\mathit{ant}}}∆{\tau }_{\mathit{qr}}^i$$E6

where ${\tau }_{\mathit{qr}}$ is the amount of pheromone deposited for a state transition $\mathit{qr}$ . $\rho$ is the pheromone evaporation coefficient. $N_{\mathit{ant}}$ is the number of ants. $∆{\tau }_{\mathit{qr}}^i$ is the amount of pheromone deposited by the i-th ant, which was set to $1/\mathbf{\Psi }\left({\Lambda }_i\right)$.

5. Experimental results

Before applying the proposed ACO to grid map merging, the spectra-based map merging (SMM) [13] algorithm was applied to find a coarse MTM. The SMM is a well-known indirect grid map merging algorithm which extracts spectral information from grid maps by the Hough transform and finds an MTM by matching the spectral information based on the cross-correlations. The individual grid maps in a multi-robot system were as shown in Figure 6. To reduce the computation time, each grid map was represented by a binary image with occupied (white) and unoccupied (black) grids.

Figure 6.

Individual grid maps in a multi-robot system. (a) Individual grid map 1, ${\mathit{M}}_1$ (b) Individual grid map 2, ${\mathit{M}}_{2.}$

Firstly, the rotation angle was coarsely estimated by the SMM. The Hough spectra and the cross-correlation between them are shown in Figure 7. The SMM estimates the rotation angle by taking the angle corresponding the maximum cross-correlation value. After rotating one of the individual grid maps by the estimated rotation angle, the SMM estimates the x and y translation amounts by taking the amounts corresponding the maximum x and y cross-correlation value. The x spectra and the x cross-correlations between them are shown in the top of Figure 8. Similarly, the y spectra and the y cross-correlations between them are shown in the bottom of Figure 8. The merged map by the rotation angle and the translation amounts estimated by the SMM is shown in Figure 9. The two individual grid maps were properly merged. But, they needs to be merged more accurately.

Figure 7.

Rotation angle estimation by the SMM.

Figure 8.

Translation amounts estimation by the SMM.

Figure 9.

The merged map by the SMM. The map 2 (green) was transformed by the SMM, and the transformed map 2 (red) was properly merged into map 1 (blue). However, they need to be merged more accurately.

The proposed ACO for grid map merging was implemented based on an open source [14]. The settings for the ACO for grid map merging were as follow. The number of iterations was set to 50. The number of samples was set to 30. The number of ants $N_{\mathit{ant}}$ was set to 100. The graphical results of the ACO for grid map merging are shown in Figure 10, which indicates that the pheromones were properly updated as time goes and found the optimal configuration of x and y translation amounts. In other word, the proposed method was successfully conducted and found the best x and y translation amounts. By the best x and y translation amounts and the rotation angle estimated by the SMM, the two individual grid maps were merged more accurately as shown in Figure 11. Comparing with Figure 9, we can say that the error in the merged grid map was reduced.

Figure 10.

ACO results for grid map merging. The red circles represent states in x and y areas. The left image represents the whole tours at each iteration. The middle image represents the best tour (the queen). The right image represents the pheromones along the tours.

Figure 11.

The updated merged map by the ACO. The two individual maps were merged more accurately.

The quantitative evaluation of the accuracy of grid map merging can be conducted with the following measure:

$$\text{Accuracy index}=\frac{{\sum }_{x={\widehat{a}}_1}^{{\widehat{a}}_2}‍{\sum }_{y={\widehat{b}}_1}^{{\widehat{b}}_2}‍{\mathit{M}}_1\left(x,y\right)·{\widehat{\mathit{M}}}_2\left(x,y\right)}{N_{\mathit{\text{overlap}}}}$$E7

where $N_{\mathit{\text{overlap}}}$ is the number of commonly occupied grids in the overlapped areas when two individual grid maps are maximally overlapped, which is a global true value and not given to robots. ${\widehat{\mathit{M}}}_2$ is the transformed ${\mathit{M}}_2$ by the ACO. ${\widehat{a}}_1\le x\le {\widehat{a}}_2$ and ${\widehat{b}}_1\le y\le {\widehat{b}}_2$ are the whole ranges of the x and y coordinates of ${\mathit{M}}_1$ and ${\widehat{\mathit{M}}}_2$.

The map merging results of the proposed grid map merging method which uses both the SMM and the ACO was quantitatively compared with those of the only SMM-based grid map merging as shown in Figure 12. Because the performance of the ACO depends on the number of ants $N_{\mathit{ant}}$, the accuracy indices of the proposed method were analyzed with various $N_{\mathit{ant}}$. As expected, the ACO improved the accuracy of grid map merging with the SMM. Although the accuracy index of the proposed method increases according to $N_{\mathit{ant}}$, the differences were not significant.

Figure 12.

The improved accuracy of the grid map merging with the ACO.

6. Conclusions

This chapter described how the ACO can be applied to the problem of grid map merging and analyzed how much the ACO improves the accuracy of grid map merging. The ACO needed to be modified to be applied to the merged map optimization. The search space for the ACO for grid map merging needs to be divided into two areas which contains the possible configurations of x and y translations respectively. The proposed method with the ACO was tested with the SMM which is a well-known indirect grid map matching algorithm. The ACO improved the accuracy of the SMM. The improved amounts increased slightly according to the number of ants in the ACO. Consequently, the modified ACO can be successfully applied to the problem of grid map merging and improve the accuracy of grid map merging.

Acknowledgments

This work was supported in part by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2019R1G1A1100597), and in part by the Grand Information Technology Research Center Program through the Institute of Information & Communications Technology and Planning & Evaluation (IITP) funded by the Ministry of Science and ICT (MSIT), Korea (IITP-2020-2020-0-01612).

Conflict of interest

There is no conflict of interest.