Open access peer-reviewed chapter

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

Written By

Heoncheol Lee

Submitted: April 11th, 2021 Reviewed: May 3rd, 2021 Published: May 24th, 2021

DOI: 10.5772/intechopen.98223

Chapter metrics overview

143 Chapter Downloads

View Full Metrics

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.

Keywords

  • Ant Colony Optimization
  • Intelligent Robot
  • Grid Map Merging
  • SLAM
  • Multi-Robot Systems

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.

Advertisement

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:

Px1:t1x1:t2Mz1:t1u0:t11x01zs:t2us:t12Δs21=PMx1:t1z1:t1xs:t2zs:t2Px1:t1z1:t1u0:t11x01Pxs:t2zs:t2us:t12xs1Δs21E1

where xk:tiis the trajectory for robot iat times k,k+1,,t, and Mis the merged map, and uk1:t1iis the sequence of actions executed by robot i, and zk:tiis the sequence of observations from robot i, and Δs21is 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.

Advertisement

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 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.

TΔxΔyΔθ=cosΔθsinΔθΔxsinΔθcosΔθΔy001E2

where Δx,Δyand Δθ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.

Advertisement

4. Ant colony optimization for grid map merging

Given an MTM T, the objective function Φto evaluate how two individual maps M1and M2are well overlapped for the merged map optimization can be defined as follows:

ΦM1M2T=x=a1a2y=b1b2M1xy·TM2xyE3

where a1xa2and b1yb2are the whole ranges of the xand ycoordinates of M1and M2. Because Tincludes sinusoidal functions for map rotation, the objective function Φhas nonlinearity and thus is hard to be solved in a closed form.

Therefore, the optimization of Φ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 xand ytranslations except for a rotation angle. Besides, since the search space for xand ytranslations 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 xand ytranslations 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 qto rwith probability as follows:

pqri=τqrαηqrβzallowedqτqzαηqzβE4

where τqris the amount of pheromone deposited for transition from state qto r. 0αis a parameter to control the influence of τqr, which was set to 1 in this work. ηqris the desirability of state transition qr, which is typically set to the reciprocal value of the distance. 1βis a parameter to control the influence of ηqr. τqzand ηqzrepresent 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, Λi=qjirkiwhere qjiand rkiare respectively the j-th and the k-th sample in the areas for xand ytranslations, the new metric Ψis defined similarly to Eq. (3) as follows:

ΨΛi=1x=a1a2y=b1b2M1xy·Tqjirki0M2(xy)E5

where M2is the transformed M2by a direct or indirect grid map merging algorithm. a1xa2and b1yb2are the whole ranges of the xand ycoordinates of M1and M2after 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 Tis set to 0.

The global pheromone is updated as follows:

τqr1ρτqr+iNantτqriE6

where τqris the amount of pheromone deposited for a state transition qr. ρis the pheromone evaporation coefficient. Nantis the number of ants. τqriis the amount of pheromone deposited by the i-th ant, which was set to 1/ΨΛi.

Advertisement

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,M1(b) Individual grid map 2,M2.

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 xand ytranslation amounts by taking the amounts corresponding the maximum xand ycross-correlation value. The xspectra and the xcross-correlations between them are shown in the top of Figure 8. Similarly, the yspectra and the ycross-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 Nantwas 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 xand ytranslation amounts. In other word, the proposed method was successfully conducted and found the best xand ytranslation amounts. By the best xand ytranslation 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 inxandyareas. 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:

Accuracy index=x=â1â2y=b̂1b̂2M1xy·M̂2xyNoverlapE7

where Noverlapis 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. M̂2is the transformed M2by the ACO. â1xâ2and b̂1yb̂2are the whole ranges of the xand ycoordinates of M1and 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 Nant, the accuracy indices of the proposed method were analyzed with various Nant. 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 Nant, the differences were not significant.

Figure 12.

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

Advertisement

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 xand ytranslations 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.

Advertisement

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).

Advertisement

Conflict of interest

There is no conflict of interest.

References

  1. 1. Parker E, Bekey G, and Barhen J. Current state of the art in distributed autonomous mobile robots. Distributed Autonomous Robotic Systems. 2000;4;3–12. DOI: 10.1007/978-4-431-67919-6_1
  2. 2. Lee H-C, Lee S-H, Choi M H, and Lee B-H. Probabilistic map merging for multi-robot RBPF-SLAM with unknown initial poses. ROBOTICA. 2012;30;205-220. DOI: 10.1017/S026357471100049X
  3. 3. Wikipedia. Lidar [Internet]. 2021. Available from:https://en.wikipedia.org/wiki/Lidar
  4. 4. Civera J, Grasa O G, Davison A J and Montiel J M M. 1-Point RANSAC for EKF filtering: application to real-time structure from motion and visual odometry. Journal of Field Robotics. 2010;27;609-631. DOI: 10.1002/rob.20345
  5. 5. Montemerlo M, Thrun S, Koller D and Wegbreit B. FastSLAM: A factored solution to the simultaneous localization and mapping problem. In: Proceedings of the AAAI National Conference on Artificial Intelligence; 28 July–1 August;2002; Edmonton. Alberta. Canada. pp. 593–598
  6. 6. Newman P and Ho K. SLAM-loop closing with visually salient features. In: Proceedings of the IEEE International Conference on Robotics and Automation; 18-22 April 2005;Barcelona. Spain. pp. 635-642
  7. 7. Lee H. Tomographic feature-based map merging for multi-robot systems. Electronics. 2020;9;107(1–18). DOI: 10.3390/electronics9010107
  8. 8. Lee H. Selective spectral correlation for efficient map merging in multi-robot systems. Electronics Letters, 2021(Published online with early view). DOI: 10.1049/ell2.12139
  9. 9. Rubinstein R Y, Ridder A and Vaisman R. Fast sequential Monte Carlo methods for counting and optimization; John Wiley & Sons: Hoboken, NJ, USA, 2013. DOI: 10.1002/9781118612323
  10. 10. Kennedy J and Eberhart R. Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks; 27 November–1 December; 1995; Perth. Australia. pp. 1942–1948
  11. 11. Dorigo M and Gambardella L M. Learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. 1997;1;53-66. DOI: 10.1109/4235.585892
  12. 12. Wikipedia. Ant colony optimization algorithms [Internet]. 2021. Available from:https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms
  13. 13. Carpin. S. Fast and accurate map merging for multi-robot systems. Autonomous Robots. 2008;25;305–316. DOI: 10.1007/s10514-008-9097-4
  14. 14. Mirjalili S. Ant Colony Optimization (ACO) [Internet]. 2021. Available from:https://www.mathworks.com/matlabcentral/fileexchange/69028-ant-colony-optimiztion-aco; MATLAB Central File Exchange

Written By

Heoncheol Lee

Submitted: April 11th, 2021 Reviewed: May 3rd, 2021 Published: May 24th, 2021