Keywords

1 Introduction

A robot swarm can collectively accomplish tasks that an individual robot could not accomplish alone. By its own nature, a robot swarm is a self-organizing system that operates autonomously without relying on a leader robot or on external infrastructure. In addition, it possesses desirable properties such as scalability, flexibility, and fault-tolerance [4] due to redundancy and locality of sensing and communication. Because of these properties, robot swarms are ideal candidates to perform missions that require to explore and map unknown environments in which the risk that individual robots fail or are lost is high. Yet, no well-defined methodology exists for swarm mapping (i.e. for exploring and mapping with robot swarms).

Mapping has been largely explored [23] in the last decades and it is usually the first task that a robot performs when it operates in an unknown environment. Most of the mapping methods have been designed to be general, platform independent, and use-case independent. However, they have been developed mostly for single robots and they cannot be directly adopted by centralized multi-robot systems and robot swarms.

State-of-the-art methods for mapping often conflict with some characteristics of robot swarms such as locality and the absence of global knowledge [4]. First, these methods usually require external infrastructure to ensure inter-robot communication or localization (a single point of failure that hinders fault tolerance). Second, either one or a small number of robots is used, and they are expensive and heavily equipped. This condition implies that the loss of a single robot seriously affects the whole system. As a result, adapting the research on mapping to swarm robotics is not straightforward and little attention has been devoted to close the gap between the two fields.

Some important questions still need to be addressed before effective swarm mapping can be achieved: How should the swarm explore and gather information on the environment? How should the robots share and spread the information gathered? How should the information be retrieved and used to produce maps? Our work aims to shed further light on the first of these questions. More precisely, we investigate the possibility of using random walk as a strategy to explore and gather information on the environment.

We are particularly interested in using random walk exploration in swarm mapping because random walk is a simple behavior that can be easily implemented in a robot swarm. Indeed, by its own nature, random walk is flexible, scalable and robust as it does not rely on localization or communication. For these reasons, though many different exploration strategies have been proposed for single robot and centralized multi-robot systems [9, 18], random walk is still the most commonly adopted behavior for exploring with robot swarms [3, 5, 8].

In this paper, we evaluate five different variants of random walk on swarm mapping: Brownian motion, correlated random walk, Lévy walk, Lévy taxis, and ballistic motion. In our experiments, each robot individually maps the environment, driven by a random walk. Later on, the individual maps are merged to produce a single, global map of the environment. We assess the ability of the robot swarm to map the environment through the quality of the global map produced. The main original contribution we make in the paper is the evaluation of different variants of random walk in the context of swarm mapping. Moreover, to the best of our knowledge, this is the first paper in which random walk exploration, the GMapping algorithm [11, 12], and the multirobot_map_merge algorithm [13] are used together to achieve swarm mapping.

The paper is structured as follows. In Sect. 2, we discuss related work in exploration and mapping with multi-robot systems. In Sect. 3, we present the swarm mapping method that we investigate in the paper. In Sect. 4, we describe the experimental setup. In Sect. 5, we illustrate the results of the experiments. In Sect. 6, we conclude the paper and we sketch future research.

2 Related Work

Traditionally, mapping with multi-robot systems has been addressed separately in the form of two sub-problems: multi-robot simultaneous localization and mapping (multi-robot SLAM) and multi-robot exploration [22].

Multi-robot SLAM concerns the collective production of maps. The work of Saeedi et al. [23] provides a review of the methods that have been proposed on this topic. The review describes advantages, problems, and challenges of widely used methods based on the Extended Kalman Filter (EKF-SLAM), particle filters (PF-SLAM), and map merging, among others. Though current SLAM methods could be implemented in robot swarms, they would introduce constrains that would affect the flexibility of the system: centralized mechanisms or complex inter-robot interactions. The issues that one can encounter by adopting SLAM on robot swarms are described by Barca et al. [1].

The literature on multi-robot mapping often assumes an existent multi-robot exploration and oversights the relationship between exploration and SLAM. Rone et al. [22] described different exploration methods used in multi-robot mapping and their characteristics. The review presents some exploration methods that could be easily implemented in robot swarms such as potential field exploration, greedy mapping, and diffusion mapping, the last two relying on random walk behaviors.

Recent work on swarm robotics has brought attention to the impact of using different variants of random walk. For example, Dimidov et al. [3] studied the performances of different variants of random walk while exploring and searching for a static target in the environment. Schroeder et al. [24] conducted a similar research and compared different variants of random walk to cover the environment. The results of these studies highlight the relationship between the performance on the task and the ability of the swarm to explore the environment with a particular variant. Our hypothesis is that the same differences in performance should appear while performing swarm mapping with different variants of random walk. To corroborate our hypothesis, we investigate the mapping performance of a robot swarm that explores by using five different variants.

Mapping with a robot swarm has already been reported by Ramachandran [20], who evaluates the efficiency of the so-called Informed Correlated Lévy Walk (i.e. a variant of random walk). However, our research differs in both the method and objectives. First, Ramachandran proposed a method that computes the global maps online in which robots know their absolute position and communicate thanks to external infrastructure. In our method, the global maps are produced offline at the end of the experiment, the robots estimate their own position, and they do not need to communicate while exploring and mapping the environment. Second, in the experiments of Ramachandran, the code was modified when ported from simulation to the real robots. In our case, we use the same code in both. Finally, Ramachandran only evaluated the performances of Lévy walk and Informed Correlated Lévy walk. As mentioned before, we evaluate four more variants in addition to Lévy walk.

3 Swarm Mapping Method

The swarm mapping method we propose integrates three algorithms: random walk exploration, GMapping [11, 12], and multirobot_map_merge [13]. First, random walk exploration defines the behavior that the robots use for exploring the environment. Then, each robot uses the GMapping algorithm to gather information and produce an individual map of the area it has explored. Finally, multirobot_map_merge is used to merge the individual maps and to produce a global map of the environment.

We developed the swarm mapping method for a swarm of e-puck [15] robots. The random walk behaviors are implementations based on models previously proposed in the literature. GMapping and multirobot_map_merge are default implementations that we adopted from the Robot Operating System (ROS) [19]. In the following, we provide a brief description of the algorithms and their contribution to the swarm mapping method.

3.1 Random Walk Exploration

The first component of the swarm mapping method concerns the behavior that drives the robots to explore the environment.

In our study, we consider five variants of random walk: Brownian motion [6], correlated random walk [21], Lévy walk [25], Lévy taxis [16] and ballistic motion. We selected these variants because they have been reported as completely random, specialized in intensification (i.e., intensive exploration of a small area of the environment), and/or specialized in coverage (i.e., moderate exploration of a large area of the environment). Indeed, we are interested in studying the differences between intensification-oriented and coverage-oriented exploration in swarm mapping.

Despite their different exploration abilities, Brownian motion, correlated random walk, Lévy walk, and Lévy taxis share the same mathematical model [3, 16]. They can be described within a general behavior: the robot selects a direction at random and moves towards it until a new direction is selected. The characteristics of the movement for each variant are defined by the parametrization of the model. In particular, the aforementioned variants differ in the \(\rho \) and \(\mu \) parameters: the former associated to the turning angle when the robot selects a direction at random, and the later associated to the time the robot keeps moving along that direction. In our implementations, we used the parametrization described as optimal by Pasternak et al. [16] and Dimidov et al. [3] as shown in Table 1. Figure 1a describes the general behavior of Brownian motion, correlated random walk, Lévy walk and Lévy taxis.

In addition to the four variants described above, we included the ballistic motion behavior used by Francesca et al. in AutoMoDe-Vanilla [8]. The ballistic motion used in the exploration module of Vanilla drives the robots with a constant straight motion, only changing their direction when an obstacle is detected. We consider here the ballistic motion as a random walk behavior because the robots select the new direction at random. Figure 1b describes the general behavior of the ballistic motion.

Figures 1a, b also show that the five variants of random walk include a basic obstacle avoidance behavior. Brownian motion, correlated random walk, Lévy walk, and Lévy taxis integrate a repulsive force model [2] that drives the robots away from any object in their detection range. In the case of the ballistic motion, the obstacle avoidance is an intrinsic property of the behavior and it allows the robots to avoid objects in the same range as the others.

Table 1. Step length, turning angle, and specialty for the variants of random walk
Full size table
Fig. 1.
figure 1

Finite state machines of the variants of random walk

Full size image

3.2 Individual Mapping

The second component of the swarm mapping method concerns the ability of the robots to gather information and to individually map different areas of the environment.

We use the GMapping algorithm to produce an individual map for each robot in the swarm. GMapping is a single-robot, SLAM algorithm that takes sensor information and produces a two-dimensional occupancy grid of the environment. In our method, we consider a model of robot that explores, computes its own odometry (i.e. an estimation of its own displacement), and detects and locates objects in a short range. This information is sufficient for GMapping to produce a map that describes the empty and obstructed areas that the robot finds.

The odometry on each robot is first initialized with the deployment position of the robot. Then, the robot continuously estimates its position in open loop by integrating the movement commanded by the random walk behavior. Providing the robots with knowledge about their starting position does not have any effect on their ability to produce the individual maps. The information was included in order to enable the merging of the individual maps in the following step of the swarm mapping method.

3.3 Global Mapping

The third component of the swarm mapping method concerns the combination of the individual contribution of each robot in the swarm into a single global map of the environment.

In our swarm mapping method, we merge the individual maps produced by each robot into a single map by using the multirobot_map_merge algorithm. Multirobot_map_merge is originally intended for merging an arbitrary number of individual maps at run time. The maps are merged only when the robots have finished the exploration of the environment. We chose multirobot_map_merge because it has been used in previous research [13] to merge individual maps produced by multi-robot systems and GMapping.

Multirobot_map_merge has two merging modes that differ on whether the initial position of the robots is known or not, the former being more robust. On the one hand, providing the algorithm with no positioning information is a closer approach to the self-organizing nature of the robot swarms. On the other hand, we consider reasonable that the initial relative position of the robots could be known a priori when the robots are deployed in a fixed location. We consider both cases in our swarm mapping method.

4 Experimental Setup

We evaluate the swarm mapping method with a swarm of e-pucks mapping a closed environment. The robots operate in an hexagonal closed environment referred to as the arena. The time available to the robots for mapping the arena is 180 s. The arena comprises an area of \(2.30\,\hbox {m}^{2}\) and it is surrounded by walls of 0.94 m in length. On a per-experiment basis, the arena could contain none or five rectangular obstacles of \(0.02\,\hbox {m}^{2}\). We expect that differences in the object density in the arena should have an effect on the ability of the swarm to explore the environment, and therefore, in the quality of the global map. The deployment position of the robots in the arena is fixed in all the experiments: the robots are aligned along the west wall of the arena with 0.10 m between their center and the wall, and 0.09 m between each other’s center.

Figure 2 shows the arenas and robots in their deployment position for both the simulated and real environments. All the simulations are performed using ARGoS3, beta 48 [17]. In the following, we describe the reference model of the robots and the protocol we used in our experiments.

Fig. 2.
figure 2

Arenas used in the experiments and starting position of the robots

Full size image

4.1 Robot

We consider an extended version of the e-puck [10, 15]. The e-puck is a differential wheeled mobile robot with a 0.08 m diameter and maximum velocity of \(0.12\,\hbox {m}\,\hbox {s}^{-1}\) It is equipped with an embedded computer and a set of eight infrared proximity sensors. The proximity sensors are distributed around the robot and they detect objects in a range of 0.10 m. We configured the robots to avoid objects in a range of 0.08 m to let them map obstacles before avoiding them.

For the purpose of this study, we integrated ROS Indigo into the embedded computer of the robot. We developed a ROS-based controller that drives the robot by using the variants of random walk described in Sect. 3.1. The controller transforms the desired direction of movement into appropriate velocity commands for the e-puck. In parallel, the controller also computes the odometry of the robot and receives the readings from the proximity sensors. This information is passed to GMapping at runtime to enable the robot mapping.

4.2 Protocol

We evaluate the five variants of random walk along with our swarm mapping method, both in simulation and real environment.

We consider a swarm of 10 e-puck robots mapping the arena described in Sect. 4. In all experiments, we execute our method for swarm mapping to produce one global map of the arena. In simulation, the swarm mapping is executed 30 times for each variant. In the real robot experiments, the swarm mapping is executed 10 times for each variant. We repeated the experiments in the two arena configurations: with and without obstacles. We report the individual and global maps obtained in a per-experiment basis.

We assess the quality of the global maps by visual inspection. For the purpose of our experiments, the quality metric represents the completeness and representativeness of the maps when compared to a reference map. In this case, the reference map is the ideal map to be produced if the robots map perfectly the environment. We consider visual inspection a sufficient metric to qualitatively assess the exploration abilities of the robots in swarm mapping. A well-established methodology for quantitative assessment is still missing and should be the objective for future work.

5 Results

We present the qualitative analysis of the results for both simulated and real experiments. In addition, we communicate the experiences made and the insights gained while adopting GMapping and multirobot_map_merge in swarm mapping. Individual and global maps, demonstrative videos, code, and ROS parameter files are available in [14]. Figure 3 shows a sample of the maps produced in swarm mapping for each variant of random walk.

Fig. 3.
figure 3

Swarm mapping results in simulation (above) and real robot experiments (below): (a) Reference map; (b) Ballistic motion; (c) Brownian motion; (d) Correlated random walk; (e) Lévy walk; (f) Lévy taxis.

Full size image

With each variant, the robot swarm explores similarly the arena both in simulation and real environment. The main difference between simulation and real environment lies on the sensitivity of the proximity sensors: in real environment, robots are more sensitive and tend to detect and avoid obstacles from a further distance. As a result, then tend to cover more the environment. The maps created in simulation match the areas of the arena explored by the swarm, and provide usable information about its content. The maps obtained with real e-pucks, on the contrary, do not reflect the explored areas and are hardly useful. We compared the performance of the variants on the basis of the results obtained in simulation.

The results show that the ballistic motion provides maps with a better quality than the other variants. Indeed, robots using the ballistic motion tend to cover better the arena while the other variants focus more on intensification. The ballistic motion is able to provide (nearly) complete maps while the maps produced with the other variants are mostly half-complete. In both cases, the exploration behavior was not affected by the presence of obstacles in the arena. We acknowledge that these observations are however only valid in the context of closed space experiments. It is easy to convince oneself that the ballistic motion cannot work in an open space without a high risk of loosing robots.

We also found that Brownian motion, correlated random walk, Lévy walk and Lévy taxis performed similarly. In overall, the maps produced with these variants do not differ neither in completeness or representativeness. As a matter of fact, we did not find substantial differences in the coverage and intensification abilities of these behaviors. The four variants responds to the same mathematical model and hence, their behavior does not differ considerably. In this sense, we argue that the parametrization of the model considered as optimal in previous research [3] cannot be generalized and it is not optimal for the e-pucks.

We successfully integrated GMapping and multirobot_map_merge in swarm mapping. The results in simulation show that, despite their limited resources, a swarm of e-pucks performing ballistic motion can map its environment. Still, we think that porting algorithms from single robot and centralized multi-robot systems is not necessarily the best approach to achieve swarm mapping.

First, GMapping was designed to work with robots equipped with dense long-range sensors and good localization systems; swarm robots like the e-pucks provide neither of them. Although we succeeded in obtaining the maps in simulation, GMapping failed when ported to the real robots. Real e-pucks are prone to have more noisy proximity readings and considerable errors in the estimation of the odometry. Consequently, GMapping produced noisy and erroneous individual maps that eventually could not be merged in good quality global maps.

Second, multirobot_map_merge was designed to merge maps regardless how they were produced. Previous experiments with this algorithm were performed with individual maps with a higher number of features and few overlapping areas [13]. In our swarm mapping method, on the contrary, the swarm succeeded in mapping due to the redundancy of small contributions from each individual map. Each robot in the swarm only maps a small area of the environment and the random walk exploration leads to increase the overlapping in those areas. As a consequence, the multirobot_map_merge algorithm was not able to produce the global map without the deployment position of the robots. Moreover, the ROS implementation of the algorithm crashed in some experiments disregarding the exploration behavior or the environment (real or simulated). Our results show that multirobot_map_merge could be used to some extent in swarm mapping, however a more suitable option should be explored in future work.

6 Conclusions

Robot swarms are suitable for the exploration and mapping of unknown environments. Still, swarm mapping is a field under development and no well-defined methodology exists to achieve it. In this article, we investigated the possibility of using random walk exploration with GMapping and multirobot_map_merge as a method to achieve swarm mapping. The robots explored and individually mapped the environment by random walk, and then the individual maps were merged to produce one single, global map. The redundancy of the individual maps contributes to obtain a good quality representation of the environment. This method can be ported with minimal effort to other ROS-based robot swarms since it does not require complex interactions between robots.

We conducted experiments, both in simulation and real environment, with a robot swarm mapping a closed environment while using five variants of random walk: Brownian motion, correlated random walk, Lévy walk, Lévy taxis, and ballistic motion. The robot swarm was able to successfully map the environment in simulation. However, experiments in real environment were less satisfying and highlighted the necessity to find strategies to better transfer the control software from simulation to real environment. Results in simulation showed that ballistic motion produces the best maps due to the better ability of the swarm to cover the environment. Yet, these results are only valid for closed environments and could not be extended to open ones. The other variants, on the contrary, showed a dominant intensification behavior that provided mostly half-complete maps.

We conclude that the selection and parametrization of the appropriate random walk behavior for swarm mapping is a topic that requires further research. Future work will be devoted to use modular automatic design methods like AutoMoDe [8] for this purpose. We expect a twofold contribution from AutoMoDe: first, it would provide a framework to assess the selection and parametrization of the behaviors in different environments; second, it would allow to port better the control software from simulation to the real robots. With regards to the mapping method, we will investigate the possibility of adopting concepts of distributed mapping [7] into swarm mapping. Indeed, merging individual maps centralizes the mapping process and, to some extent, affects the flexibility of the system. We expect that distributed mapping will provide alternatives to produce and retrieve useful partial maps in a fully distributed way.