MRXT: The Multi-Robot Exploration Tool

1. Introduction

In mobile robotics, the task of exploring the environment creating a useful map for navigation is essential. Creating a map usually can be separated into two different problems. First, the problem of commanding the robots to places of interest in order to perform observations and gather information about the environment. Second, the problem of building a map of the environment given the odometry and observations. The former is usually denoted exploration, whereas the latter is referred to as simultaneous localization and mapping (SLAM). Solving the SLAM problem implies the skill of incrementally building the map of the environment while simultaneously using this map to compute the robot's absolute location.

The process of exploration consists of the progressive coverage of the target area by a robot or a team of mobile robots while they gather the necessary information to create a map of the unknown target area. In this sense, exploration aims mainly at deciding the trajectories that allow us to collect this information while the SLAM algorithm creates the map. The problem is not simple at all. Since the area to cover is unknown, there exists no closed form solution to the problem, and all the solutions are based on heuristics that try to optimize one of the parameters involved in the exploration. Consequently, some techniques look at reducing the navigational costs [1, 2], and others direct the robot to the zones of maximum predicted information gain [3, 25]. More complexity appears when coordination mechanisms between the robots are considered. Another important concept is that of integrated exploration. Most classic exploration algorithms consider the maps and the robot pose as known without uncertainty. However, in real applications this is not true. Typically, the SLAM algorithm is able to estimate the map and robot pose with an associated uncertainty. For this reason we analyse algorithms that try to integrate the path planning with the SLAM in order to compute trajectories that allow the creation of a high quality map. In this sense, some actions such as closing a loop or returning to past poses may reduce the uncertainty of the robot pose and the uncertainty of the map. For example, [4] considered the uncertainty of the full state of a landmark-based EKF SLAM adding up the area of the robot position covariance and the area of the covariance for each individual landmark. They suggested a path planning technique that attempts to minimize the predicted uncertainty with the next measurements.

Exploration algorithms found in the literature are difficult to compare, since algorithms are usually tested in different scenarios under dissimilar conditions [5, 27,6, 7]. Consequently, in order to determine the best algorithms for a given scenario, it is necessary to test the set of techniques under the same conditions. Existing general simulation tools do not provide an easy way to compare and understand the variety of available exploration algorithms. In this paper, we present a new multi-robot simulation tool called MRXT (multi-robot eXploration tool). MRXT has been specifically designed with the purpose of understanding and comparing the different exploration techniques.

With all these considerations in mind, we decided to include in the application a good representation of these different kinds of exploration techniques. In this sense, multiple combinations of multi-robot exploration and SLAM algorithms with multiple parameters can be tested with this tool. Furthermore, MRXT includes different reconfigurable scenarios as well as multiple adjustable parameters regarding the robots and its sensors.

Therefore, the main contribution of this paper is to present this new tool for simulation and testing of exploration algorithms, this tool, MRXT, being the first software application completely focused on the experimentation with the problem of the autonomous multi-robot exploration and mapping of unknown environments. The paper is organized as follows. Firstly, the state of the art in robot simulation is reviewed in Section 2. Section 3 presents the application and describes all the different possibilities that MRXT offers. In Section 4, the exploration algorithms included in MRXT are explained in depth. Section 5, shows an example of how the application can be used, for instance in mobile robotics courses. Finally, the main conclusions are reported in Section 6.

2. Related Work

There exist many robotics simulation applications; however, most of them are for general purposes. Following, some of these applications are described.

Stage [8] is a 2D robotics simulator for indoor environments, which runs over Unix. Stage can simulate a team of mobile robots moving in and sensing a two-dimensional bitmap environment. It includes various sensor models like sonar, laser range finders, odometry and cameras with colour blob detection. Stage presents a standard interface with a robot control software called Player that is compatible with several commercial robotic platforms. Very few or no changes are required to move between simulation and hardware using Stage and Player. Many controllers designed for Stage have also been demonstrated to work on real robots. MobileSim ¹ is an example of simulator based on Stage for the robots from Adept MobileRobots.

Gazebo [9] is similar to Stage but in a 3D world. Like Stage is able to simulate a team of mobile robots, their sensors and objects. It also includes an accurate simulation of rigid-body physics, generating a good sensor feedback and interactions between objects. It also uses the standard Player interface.

USARSim [10] is the acronym for Unified System for Automation and Robot Simulation. It is a high-fidelity simulation of robots and environments based on the Unreal Tournament game engine. It is intended as a general purpose research tool with applications ranging from human computer interfaces to behaviour generation for groups of heterogeneous robots.

Microsoft Robotics Developer Studio (RDS) [11] is a Windows-based environment for the creation of robotic applications. RDS includes a lightweight asynchronous services-oriented runtime. Its 3D physics-based visual simulation environment allows the creation of applications without hardware.

Webots [12] is a development environment used to model, program and simulate mobile robots. With Webots the user can design complex robotic setups, with one or several, similar or different robots, in a shared environment. The properties of each object, such as shape, colour, texture, mass, friction, etc., are chosen by the user. A large choice of simulated sensors and actuators is available to equip each robot. The robot controllers can be programmed with the built-in IDE or with third-party development environments. The robot's behaviour can be tested in physically realistic worlds. The controller programs can optionally be transferred to commercially available real robots.

SimRobot [13] is a robot simulator that is able to simulate arbitrary user-defined robots in three-dimensional space. It includes a physical model which is based on rigid body dynamics. To allow an extensive flexibility in building accurate models, a variety of different generic bodies, sensors, and actuators has been implemented. Furthermore, the simulator follows a user-oriented approach by including several mechanisms for visualization, direct actuator manipulation, and interaction with the simulated world. To allow a more detailed simulation, algorithms for simulating image disturbances as well as for actuator parameter optimization are included.

Some other simulators are not so general and open and are more focused on experimenting with a clear problem in mobile robotics. For instance, [14] introduces a robotic simulator focused on the problem of path planning. In the same way, MRXT is the first simulator centred in the topic of exploration and mapping of unknown environments with teams of mobile robots.

3. Description

The tool presented in this paper was implemented in C++ and runs under Linux. In contrast to other architectures and simulators, this application has been designed in order to require a small amount of time to learn its usage. Since everything can be configured in simple menus and dialogue windows in a unique user interface, it is very easy to use. These facts make this application suited for educational courses on mobile robotics.

3.1 Main window

Basically, the application consists of a main screen that includes two different windows (presented in Figure 1). The left window represents the virtual environment where the robots evolve. The right window presents the map as it is being built by the SLAM algorithm, given all the information gathered so far. On the leftmost window the robots move as commanded by the selected exploration algorithm. The different obstacles (black lines), landmarks (green squares) as well as the team of mobile robots are displayed on it. Multiple environments are available and, as has been said before, they can be easily modified and loaded for simulation. Different virtual environments can be loaded and edited.

OPEN IN VIEWER

Figure 1.

Graphic user interface of the multi-robot exploration tool. Visual landmarks are indicated with small green squares. Walls are represented by lines. In the example, two robots are performing the exploration.

3.3 Robot settings

Figure 2 shows the dialogue window that allows to customize the properties of the robots. In order to simplify the comparison between techniques, only the case of a homogeneous team of differentially driven robots has been considered. All robots are equipped with a stereo camera, a laser range finder and odometry. The shape of the robots as well as the stereo camera, the laser and the odometry parameters can be configured in this window. As the robots move, they obtain observations on the visual landmarks, (represented as green squares in Figure 1). These observations are formed by a distance measurement and a visual descriptor. The stereo camera is employed by the visual SLAM. The model used consists of a 3D landmark detector. The range and precision of the detected landmarks change accordingly with standard stereo camera parameters [16]. Both camera measurements and odometry are corrupted by a Gaussian noise that can be configured using the dialogue in Figure 2. The odometry model used is described in [18]. We assume that the robots are not able to measure their relative positions or orientations in their workspace. In addition, communication is not restricted by any bandwidth or range and considered lossless.

OPEN IN VIEWER

Figure 2.

Robot properties configuration window

3.4 SLAM settings

The team of robots make use of a centralized multi-robot landmark-based SLAM technique in order to simultaneously create a map of the environment and localize the robots in it. In this sense, two SLAM algorithms namely the EKF-SLAM [17] and the FastSLAM [16] are included in the application with different configurable parameters. This centralized SLAM is responsible for the creation of a map of visual landmarks with their position and covariance. In this sense, as a result, the SLAM algorithm provides the exploration algorithm with the position of each robot with respect to the frame of this map, along with its uncertainty. The dialogue window to control the parameters of the SLAM is shown in Figure 3. The available configurations are:

OPEN IN VIEWER

Figure 3.

Exploration strategy configuration window

Selecting an EKF-based SLAM algorithm (Section 4.1.1).

Selecting a FastSLAM particle filter-based algorithm (Section 4.1.2).

Both algorithms have dissimilar capabilities regarding filtering out noise in odometry and measurements or their tolerance to false data associations [16]. For these reasons we included a large number of different settings that allow to test the exploration algorithms under very different conditions. These settings include:

The number of particles used by the FastSLAM approach [16].

The Mahalanobis distance used during the data association process [16].

The Euclidean distance when using the visual descriptor during the SLAM process [16].

3.6 Exploration settings

Regarding the navigation techniques for exploration, seven exploration algorithms can be selected in order to plan trajectories to cooperatively cover the entire environment. These different techniques will be explained in the Appendix. An example of the different parameters that can be adjusted for one of these algorithms is shown in Figure 4.

OPEN IN VIEWER

Figure 4.

Exploration strategy configuration window

4. Algorithms

As was mentioned in the last section, MRXT includes multiple exploration as well as SLAM algorithms. This section explains all the currently available algorithms.

Regarding exploration algorithms, Table 1 classifies the exploration techniques included in this application. As was said, the group of techniques included in the application covers all the main approaches to the problem. In this sense, the algorithms selected differ in the level of multi-robot coordination and integration with the SLAM algorithm.

OPEN IN VIEWER

Table 1.

Exploration Techniques included in MRXT classified by coordination and SLAM integration level

	Non-Coordinated	Coordinated
Non-Integrated	Nearest Frontier (Section A.1) Cost-Utility (Section A.2)	Coordinated (Section A.4) Market-based (Section A.5) Behaviour-based (Section A.3)
Integrated	Integrated (Section A.6)	Hybrid Integrated Coordinated (Section A.7)

While the exploration techniques conduct the robots to cover the area to explore, a SLAM technique is responsible for creating a map of the environment from the acquired data and provide the localization of the robots. Two SLAM techniques are included in this first version of MRXT:

These techniques build a visual landmark-based map from the simulated input of a stereo camera. As we said, since this kind of map does not provide the occupancy information required by the exploration algorithm for navigation, a secondary occupancy grid map is built using the laser range finder readings.

In the Appendix, we describe shortly the seven exploration techniques and the SLAM algorithms included in the application. The exploration techniques currently implemented are compared in Table 1.

4.1 Multi-robot Landmark-based SLAM Algorithms

4.1.1 EKF-SLAM

The multi-robot landmark-based EKF-SLAM included in the application is similar to the one presented in [17], but extending the state in order to incorporate the pose of multiple robots. In this sense, the state contains the pose of all the robots as well as the landmark positions x ^ k = [ x k r 1 , x k r 2 , ⋯ , x k r R , x m 1 , x m 2 , ⋯ , x m M ] ′ , where x k r i is the estimated pose of the ith robot in the time step k, x^mj is the position of the jth landmark, R is the number of robots and M is the number of landmarks in the map.

The EKF integrates the new readings following two stages. First, a prediction stage is carried out, where a new state x ^ k | k − 1 with its covariance matrix P k | k − 1 is predicted according to the motion model f ( x ^ k − 1 | k − 1 ) of the robots, the input u _k-1 and assuming static landmarks:

x ^ k | k − 1 = f ( x ^ k − 1 | k − 1 ) + u k − 1

(1)

P k | k − 1 = F k − 1 P k − 1 | k − 1 F k − 1 Τ + Q k − 1

(2)

where F _k−1 is the Jacobian of the motion model and Q_k-1 its noise.

Later, the sensor reading z_k is incorporated in the update stage. Given the predicted observation h ( x ^ k | k − 1 ) and innovation vector y ˜ k with covariance S_k is evaluated. Then, the Kalman gain K _k is calculated and the state x ^ k | k and its covariance P k | k is updated:

y ˜ k = z k − h ( x ^ k | k − 1 )

(3)

S k = H k P k | k − 1 H k Τ + R k

(4)

K k = P k | k − 1 H k Τ S k − 1

(5)

x ^ k | k = x ^ k | k − 1 + K k y ˜ k

(6)

P k | k = ( I − K k H k ) P k | k − 1

(7)

where H _k is the Jacobian of the observation model. This way, the uncertainty regarding the poses of the robots is reduced as well as the landmark positions.

The data association can be done by nearest neighbour approach in the physical or descriptor space. New landmarks are also added in this stage. The frequency of integration of new readings is a parameter in the application.

In this way, the state of the Kalman filter gives us the position of all the robots as well as the positions of all the landmarks that have been detected until that moment.

4.1.2 FastSLAM

FastSLAM is a probabilistic approach to the full SLAM problem. In MRXT, a multi-robot version of FastSLAM [16] is included. In contrast to the EKF which only computes the map and the current robot pose, FastSLAM tries to find the full path for each robot x 1 : k r = [ x 1 : k r 1 , x 1 : k r 2 , ⋯ , x 1 : k r R ] as well as the map x m = [ x m 1 , x m 2 , ⋯ , x m M ] ′ that best matches the observations. In this sense, the SLAM problem can be stated as:

p ( x 1 : k r , x m | u 1 : k , z 1 : k ) = p ( x 1 : k r | u 1 : k , z 1 : k ) p ( x m | u 1 : k , z 1 : k , x 1 : k r ) .

(8)

being u _1:k the control input and z_1:k the observations. As we can see, FastSLAM splits the problem into two simple problems: finding the best path, and finding the map that best matches the observations for that given path.

The way to approach the first problem is by means of analysing a set of possible solutions using a particle filter. It consists of sequential sampling, importance and resampling. The sampling phase proposes new robot poses for each particle according to the motion model of the robots. A weight is given to each particle according to the observation model. A resampling stage is used to filter the most unlikely particles in order to have an appropriate set of particles that is a good representation for the likelihood of the poses of the robots.

The solution to the second problem considers the inclusion of all the observations for each path in a map. This way, there is a map for each possible path in the particle filter. Each individual landmark is simply updated with a Lalman filter for each landmark in the map:

p ( x m | z 1 : k , x 1 : k r , w ) = ∏ j = 1 M p ( x m j , w | z 1 : k , x 1 : k r , w ) ,

(9)

where the term w refers to the particle number.

The positions of the robots and the map corresponding to the most probable particle are considered to be the solution for each sample time.

5. Simulations

As we have shown, this tool offers multiple possibilities for experimentation in exploration and mapping of unknown environments with teams of multiple mobile robots.

Therefore, it can be very useful in the academic field, for instance in basic mobile robotics courses.

As an example, next we show how the tool has been used in order to determine the best algorithm to explore and create a map for the scenario shown in figure 5 for different team sizes and using the EKF-SLAM. This scenario has dimensions of 38times26m and about 200 landmarks were positioned on the walls in the simulated environment. The speed for the robots was limited to a linear speed of 0.35m/s and an angular speed of 0.25rad/s. The SLAM update frequency was set to 2Hz.

OPEN IN VIEWER

Figure 5.

Simulated scenario

The experiments were repeated for the seven exploration algorithms and for groups from one to five robots. Several runs are repeated at each scenario with the same number of robots (50 runs in each case). Two main experiments were performed:

The exploration results regarding exploration time and map quality were obtained and are presented in Figure 6 and Figure 7. Exploration time is defined as the time in seconds needed by the robot or group of robots to explore the whole environment. Exploration is achieved when no new frontier cells are found. A frontier cell is defined as that cell in an occupancy grid that is found to be empty and lies next to an unexplored cell. [18].

OPEN IN VIEWER

Figure 6.

(a) Presents the exploration time for the different approaches when the robots start in a grouped fashion. (b) Shows the error in the visual landmarks map.

OPEN IN VIEWER

Figure 7.

(a) Presents the exploration time for the different approaches when the robots start to spread over the whole environment. (b) Shows the error in the visual landmarks map.

Figure 6(a) shows the average exploration time for each algorithm and number of robots when the robots start from a grouped configuration. From that graphic we can see that the nearest frontier approach is the best in this scenario in terms of exploration time. As we can see, the narrow corridors of the test scenario make the coordination factor not to be critical. When a robot arrives to a bifurcation already visited by another robot, all techniques are prone to make the second robot choose a different path to the one chosen by the previous robot since that path has a higher cost. A simple technique like the nearest frontier approach just based on costs works correctly here, and thus it obtains the best exploration time results. To sum up, when we compare the results in terms of time in this scenario, the techniques that look for optimizing other parameters require a higher amount of time to finish the exploration task.

Figure 6(b) shows the average error in the map of visual landmarks created by the EKF-SLAM. In that figure, it can be seen that the hybrid coordinated integrated algorithm as well as the integrated approach are the best regarding the quality of the created map. These results were expected since these are the only two techniques that integrate the SLAM uncertainty with path planning.

Another interesting property that can be observed from the graphics is that, since the exploration always begins with the robots grouped in the initial state, the exploration time in relation with the number of robots converges. In this sense, and depending on the environment to explore, there is a point where adding more robots to the team does not improve the results significantly.

Figure 7(a) shows the average exploration time for each algorithm and number of robots, for the case when the team starts to totally spread over the whole environment The results are similar to that observed in Figure 6 The nearest frontier approach also performs well in this scenario It is worth noting that in the case of a single robot, the results are exactly the same as those presented in Figure 6 As the number of robots increases, the exploration time is lower, compared to the same data in Figure 6. This result is a direct consequence of the robots being initially spread over the whole environment, and thus being more coordinated. Figure 7(b) shows the average error in the map created with an initial spread of the robots In that figure it can be seen that the results are slightly better as a consequence of the starting robot positions The hybrid coordinated integrated algorithm as well as the integrated approach are the best regarding the quality of the created map, since they integrate the SLAM uncertainty with path planning.

6. Conclusions and Future Works

In this article an application to simulate multi-robot exploration and mapping of unknown environments has been presented. This tool is documented and freely available to be downloaded in the MRXT website². MRXT allows the user to experiment with the different exploration algorithms in multiple virtual environments while changing the different parameters of the exploration and SLAM as well as the robot properties. MRXT is the first application to be completely focused on the common problem of exploration in mobile robotics, making it appropriate for educational purposes. An example of usage of the application has been shown in the paper.

As future works, we plan to make the simulator compatible with other robotics software development environments like ROS [19] in order to make easier the development of new exploration algorithms for MRXT. The inclusion of grid-based SLAM techniques in addition to the current feature-based SLAM is also an objective.