Occupancy Grid Mapping via Resource-Constrained Robotic Swarms: A Collaborative Exploration Strategy

Abstract

This paper addresses the problem of building an occupancy grid map of an unknown environment using a swarm comprising resource-constrained robots, i.e., robots with limited exteroceptive and inter-robot sensing capabilities. Past approaches have, commonly, used random-motion models to disperse the swarm and explore the environment randomly, which do not necessarily consider prior information already contained in the map. Herein, we present a collaborative, effective exploration strategy that directs the swarm toward ‘promising’ frontiers by dividing the swarm into two teams: landmark robots and mapper robots, respectively. The former direct the latter, toward promising frontiers, to collect proximity measurements to be incorporated into the map. The positions of the landmark robots are optimized to maximize new information added to the map while also adhering to connectivity constraints. The proposed strategy is novel as it decouples the problem of directing the resource-constrained swarm from the problem of mapping to build an occupancy grid map. The performance of the proposed strategy was validated through extensive simulated experiments.

1. Introduction

Swarm Robotic Systems (SRSs) comprise multiple fully-autonomous or semi-autonomous robots that collaborate with each other in order to accomplish a task that is often too complex for an individual robot to complete on its own. Numerous works have categorized common problems and applications specific to SRS [1,2,3,4,5]. Behaviors of SRSs have been, commonly, investigated using ground-based robots, including millimeter-scale robots known as millirobots [6,7,8,9,10,11]. As well, strategies have also been specifically developed for swarms comprising aerial vehicles [12,13,14,15,16,17]. Many applications of SRS have been studied including object manipulation [2,18,19], environmental monitoring [20,21], and search and rescue [22,23,24]. In this paper, our focus is on the use of ground-based millirobots that lack extensive proximity-sensing capabilities (e.g., omnidirectional laser scanners) often seen on larger robot platforms. Namely, such SRSs are resource-constrained, having limited exteroceptive sensing (e.g., unidirectional sensors, local inter-robot proximity sensing) and, thus, mainly rely on inter-agent communications to accomplish a goal.

The specific swarm problem investigated, herein, is the mapping of an environment using millirobot-based SRSs with limited proximity-sensing capabilities. In this context, occupancy grid mapping is a potential approach that can be utilized [25]. Building such maps, however, would require robots to accurately estimate their own locations and gather significant amounts of proximity-sensing information from their environment, both of which may be non-trivial tasks for a resource-constrained SRS. Thus, in this paper, we propose the development of an exploration strategy that utilizes a resource-constrained SRS to build an occupancy grid map of an unknown environment.

Exploration of an environment via a SRS can be achieved by having each robot use random motion to disperse itself throughout the environment [5]. However, in order for robots not to “wander” away from other robots within the swarm, the environment must remain “enclosed”, or the random motion otherwise constrained in some way. The pertinent literature, investigating the use of resource-constrained swarms to build occupancy grid maps, has proposed random motion exploration to diffuse robots only throughout an enclosed environment [26,27,28]. In these works, all robots use the same random motion model to disperse themselves independently of the other robots in the swarm. Furthermore, information contained within the map is not used to influence the exploration area of the swarm.

In contrast to the abovementioned methods, herein, we propose a unique exploration strategy for a resource-constrained SRS whereby the mapping of an unknown environment may be directed to maximize new information added to an occupancy grid map. The swarm is divided into two teams: a decentralized team of mapper robots and a centralized team of landmark robots that may communicate with a central controller. The mapper robots explore the environment using a random motion model and gather information to be incorporated into the map, although they are constrained to stay nearby the team of landmark robots. The team of landmark robots, on the other hand, receive motion commands from a central controller and direct the exploration of the swarm toward a particular area of the environment.

Our strategy proposes the first use of a resource-constrained swarm, divided into two teams, to physically decouple the problems of exploration and mapping of unknown environments. The swarm’s exploration can be directed towards areas that maximize new information added to the map while still maintaining the overall scalability of the strategy to a large number of robots. Directing the swarm, toward the most promising areas to explore, is performed via planning and executing the landmark robots’ motions. Mapping of those areas is performed via a separate team of mapper robots, each following a random motion model to disperse themselves and collect information from their local environment. The swarm is, therefore, able to follow an efficient frontier-based exploration of the environment while the map is built using robots with limited exteroceptive sensing.

The strategy is novel as it allows the problem of directing a swarm to a new area of the environment to be addressed separately from the problem of exploring and mapping that new area using robots with limited environment perception abilities. This physical decoupling promotes swarm scalability as the landmark robots’ motions can be planned independently of the number of mapper robots.

2. Related Works

Herein, the pertinent literature related to exploration and mapping of unknown environments using SRSs is detailed in Section 2.1, Section 2.2, Section 2.3 and Section 2.4. A comparison of the proposed strategy to each of the categories described is provided in Section 2.5.

2.1. Metric Mapping Using Homogeneous Swarms with Limited Exteroceptive-Sensing

Metric map creation using resource-constrained swarms, as addressed herein, presents a unique challenge compared to topological map creation since generating metric maps (e.g., occupancy grid maps), generally, requires accurate environment perception and localization. Previous studies, investigating the creation of metric maps using resource-constrained swarms, have used various random-motion models to explore the environment [26,27,28]. Random-motion models specialized in either an intensive exploration of a small area or coverage of a larger area were investigated in the context of building an occupancy grid map using odometry-based localization alone [27]. Other studies have allowed the swarm to share relative proximity measurements to improve the overall swarm localization estimate. However, each robot in the swarm still uses a random motion model to disperse themselves without considering which areas of the environment may already have been explored [26,28]. In these works, the swarm’s motion is unconstrained within an enclosed environment.

In contrast to the abovementioned works, our proposed work allows the resource-constrained swarm’s exploration to be directed toward unmapped areas in the environment by dividing the swarm into a team of mapper robots and a team of landmark robots, respectively. The latter directs the decentralized mapper robots. The novelty of our proposed work is based on this division of the swarm into two teams, one to direct the swarm toward new areas and the other to map those new areas. Namely, the landmark robots are moved to unexplored areas of the environment to facilitate the building of a map as efficiently as possible. The use of a separate team of landmark robots enables the mapper robots to remain decentralized while still being directed toward the unmapped areas of the environment.

2.2. Topological Mapping Using Swarms with Limited Exteroceptive-Sensing

Topological maps are a sparse representation of an environment capturing the topological relationship of obstacles or features, similar to a roadmap [29]. In direct pertinence to our work, topological maps have been built using resource-constrained swarms whose individual robots may not be able to position themselves or incorporate sensor measurements into a map on their own (e.g., [30,31,32,33,34,35,36]). The relative simplicity of each robot and the large number of robots within these swarms prohibit the use of existing multi-robot SLAM methods.

Topological maps have been built using a swarm that navigates in an environment with many landmarks, whose density and distribution in the environment are known [30]. Similarly, the construction of physical topological maps has also been investigated, where the swarm’s topology represents the map itself [31].

There also have been approaches that build maps offline once the resource-constrained swarm has gathered data from the environment. In [32], for example, the swarm remains unlocalized and records information, such as time of encounter with an obstacle, in order to map a feature-of-interest. Alternatively, in [33,34,35], a topological map is built by having each robot move randomly through the environment and record when it encounters another swarm robot, while each robot remains unlocalized. In these studies, the location of robots encountering each other are converted into point clouds and, later, into topological maps, using metric estimation and topological data analysis (TDA) techniques [33,34,35]. Random-motion swarms and TDA techniques have also been used to extract the number of obstacles inside an unknown environment [36]. Millirobot-scale ground swarms are more commonly used in this category since extensive environment perception or accurate localization is not required. Our work, however, focuses on the creation of metric maps as opposed to topological maps using resource-constrained swarms.

2.3. Mapping Using Robotic Systems with “High-Information” Exteroceptive-Sensors

Cooperative exploration of unknown environments using SRSs has been previously investigated for swarms equipped with “high-information” sensors (e.g., omnidirectional laser scanners), where each robot can explore and map their local environment individually [37,38,39,40,41].

Such systems often use existing simultaneous localization and mapping (SLAM) methods and collaborate to map the environment faster than each robot otherwise could individually. In this regard, the cooperative exploration and mapping problem for these swarms can be seen as a subset of the more general multi-robot SLAM problem [42,43], with emphasis on the scalability of methods for SRSs [44].

In the above context, maps can be built by storing one centralized map that each robot contributes information to or by having each robot store their own individual map of the environment. Centralized maps have been used with efficient decentralized frontier-based exploration methods to quickly disperse agents throughout the environment [37]. Alternatively, each swarm robot may store their own map while exchanging information with their neighbors to merge their neighbors map with their own and better plan their own trajectories [38,39,40]. In [41], for example, decentralized exploration and distributed mapping are used in combination to map dynamic environments using teams of wall-climbing robots and a swarm of ground-level mapper robots. Our work, instead, focuses on resource-constrained swarms, whose limited sensing capabilities prohibit the member robots from building, or contributing to, a map individually. Such swarms must collaborate with each other to achieve these tasks.

2.4. Area Coverage Using Homogeneous Swarms with Limited Exteroceptive-Sensing

Area coverage of an environment has been investigated using SRS where the primary problem being addressed is the efficient exploration and coverage of a target area. Although maps of the environment are not necessarily built, the exploration strategies used to cover the environment are still of interest. In this regard many strategies have investigated the use of random motion models by each robot in the swarm to disperse the robots across the target area [45,46,47,48].

In [45], the strategy combines a random motion model based on the Lévy distribution (Lévy flight) with an artificial potential field to improve the exploration efficiency, with the potential field generating a repulsive vector between nearby robots to promote dispersion of the swarm. In [46], a control law is proposed based on pheromones to switch the random motion models between Brownian motion for local searching and Lévy flight motion for global exploration. In [47], an improved Lévy flight random motion model is proposed that adaptively changes the models step size based on the swarm’s density and is shown to provide a more uniform coverage of an environment than when using a standard Lévy flight random motion model alone. In [48], different random motion models were tested in a variety of environments using a swarm of Kilobots to reveal which motion model provided the most effective coverage of a particular environment. Our work, however, constrains the random motion of mapper robots to only cover the area surrounding landmarks, and considers how measurements taken during this random exploration can be used to build a map of the environment.

2.5. Comparison Summary

In order to summarize and compare the pertinent literature with the strategy presented herein,

Table 1. Comparison of our proposed strategy with others in the pertinent literature.

Category	Description	Pros	Cons
Proposed strategy: Heterogenous swarms with limited exteroceptive-sensing	Uses a group of landmark robots to optimally direct a separate team of mapper robots. Mapper robots follow random motion. Builds occupancy grid maps by localizing individual robots and incorporating their proximity measurements into the map.	Frontier-based optimally directed exploration of the environment: Robots maintain connectivity, allowing for accurate position estimates using cooperative localization strategies. Strategy is scalable since only the landmark robots’ motions need to be planned by a central controller. High-fidelity metric maps are built using information from relatively simple exteroceptive sensors.	Motion planning is not fully decentralized. Map building is centralized.
Homogeneous swarms with limited exteroceptive-sensing [26,27,28,45,46,47,48]	Each robot follows a random motion, and exploration of the environment occurs as a consequence of this (random) motion. Builds occupancy grid maps by localizing individual robots and incorporating their proximity measurements into the map.	Fully decentralized motion planning. Strategy is scalable. High-fidelity metric maps are built using information from relatively simple exteroceptive sensors.	Exploration is undirected and, thus, sub-optimal: Robots explore previously mapped areas. Map building is centralized. Robots may lose connectivity, which may lead to inaccurate position estimates and, thus, inaccurate maps.
Topological mapping using swarms with limited exteroceptive-sensing [30,31,32,33,34,35,36]	Robots explore the environment through random motion. Data is first collected by a swarm and later used to build a topological map (e.g., roadmap): Data collected includes time-of-encounter with other robots or obstacles.	Fully decentralized motion planning. Strategy is scalable. Minimal exteroceptive sensing required. Topological maps can be built even with no position estimates of the robots.	Large numbers of robots, that need to disperse uniformly throughout the environment, are required. Map building is centralized. Only low-fidelity map of the environment can be achieved.
Robotic systems with “high-information” exteroceptive-sensors [37,38,39,40,41]	Similar to multi-robot simultaneous localization and mapping. Directs exploration to map an area. Each robot individually builds a map of an area without relying on other robots. Strategies are made for and implemented with a few robots (e.g., 2 to 5 robots).	Frontier-based directed exploration of the environment: Efficient exploration can be achieved due to complex sensors. High-fidelity metric maps are built.	Computationally infeasible for large-sized swarms (i.e., not scalable). Requires high-information, complex and, often, large-sized sensors and, thus, large-scaled robots.

provides a short description of each of the above categories as well as a list of pros and cons related to each. As can be seen from the table, our proposed decoupling strategy for a swarm of robots provides clear advantages over existing strategies that also have limited exteroceptive sensing capabilities, including creating high-fidelity metric maps of the environment using a frontier-based optimally directed exploration strategy that maintains the overall scalability to a large number of robots.

3. Problem Formulation

As noted above, this paper focuses on the development of a generalized exploration strategy to build an occupancy grid map of an a priori unknown environment via a resource-constrained swarm robotic system (SRS). It is assumed that the environment may include a priori unknown obstacles and may not be enclosed, i.e., bordered.

The swarm is to be divided into two teams prior to the start of a task. The first is a team of $n_L$ (mobile) landmark robots that use a centralized architecture to communicate with a central controller, where each landmark robot can be denoted by the unique label, $L_j, j\in \left\{1,\dots ,n_L\right\}$. The second is a team of $n_m$ mapper robots that use a decentralized architecture and communicate with the landmark robots, where each mapper robot can be denoted by the unique label, $R_i, i\in \left\{1,\dots ,n_m\right\}$. The landmark robots are responsible for guiding the exploration of the swarm by physically positioning themselves in promising areas to explore. The mapper robots are responsible for acquiring the sensor measurements to build a map of the environment surrounding the landmark robots.

It is assumed that the mapper robots can acquire information about their local environment through on-board sensing hardware, such as laser range finders, RGB cameras. Let us denote the exteroceptive sensory measurement that acquires information (e.g., distance to obstacle) about the surrounding environment taken by mapper robot $R_i$ at time $t$ as $z_{R_i}^t$.

The swarm is assumed to be initially positioned at a (fixed home) base, ${}_{ }{}^{G}H=\left(x_H, y_H\right)$, defined by a global frame, ${}_{ }{}^{G}F$. It is also assumed that a static sensor that can actively sense the swarm could be placed at the home base prior to execution. The sensory capabilities of each robot in the swarm include their ability to uniquely identify and measure relative ranges and bearings to their neighbors within a predefined circle-of-radius, ${\rho }_{sense}$. Swarm robots within ${\rho }_{sense}$ of each other are said to be connected. Our work considers all robots, including both landmark and mapper robots, to be equipped with inter-robot sensing technology that allows them to measure distance and bearing to their neighbors. The measurement taken by mapper robot $R_i$ of some other mapper robot $R_j$ can be denoted as:

$$s_{R_i{R}_j}=\left({\widehat{d}}_{R_i{R}_j},{\widehat{b}}_{R_i{R}_j}\right),$$

(1)

where s_RiRj is the inter-robot sensing of Robot $R_j$ by Robot $R_i$: ${\widehat{d}}_{R_i{R}_j}$ and ${\widehat{b}}_{R_i{R}_j}$ are the relative distance and bearing between these robots, as observed by R_i, respectively. In practice, proximity measurements would be the sum of the true relative distance and bearing between robots, plus some additional zero-mean Normally-distributed noise:

$${\widehat{d}}_{R_i{R}_j}=d_{R_i{R}_j}+N\left(0,{\sigma }_{int}^2\right), \mathrm{and}$$

(2)

$${\widehat{b}}_{R_i{R}_j}=b_{R_i{R}_j}+N\left(0,{\sigma }_{int}^2\right)$$

(3)

where d_RiRj and b_RiRj are the true distances and bearings between the robots, and ${\sigma }_{int}^2$ is the variance of the additive Normally-distributed noise. Since all robots in the swarm are equipped with inter-robot sensing capabilities, measurements can equivalently be taken between mapper and landmark robots. All inter-robot sensing measurements taken by Robot $R_i$ of other nearby robots at time $t$ can be combined into a set and denoted as $S_{R_i}^t$:

$$S_{R_i}^t=\left\{s_{R_{i}A}\right\} \forall robots A s.t. dist\left(R_i,A\right)<{\rho }_{sense},$$

(4)

where $A$ represents a general label for either a mapper or landmark robot and the function $dist\left(R_i,A\right)$ represents the distance between mapper Robot $R_i$ and mapper or landmark Robot A.

Mapper robots continually broadcast measurements in the form of data packets that include both inter-robot distance and bearing measurements as well as distance measurements to their local environment. Namely, each data packet includes a tuple of measurements from each type of sensor mentioned above as well as the identifier of the mapper robot itself. Landmark robots receive these data packets and forward the information to a central controller along with their own inter-robot measurements, at which point the inter-robot distance and bearing measurements may be fused to obtain an estimate of the robots’ locations in the environment using cooperative swarm localization techniques [49,50,51,52,53,54,55,56,57,58,59,60]. Let us denote the data packet sent by mapper Robot $R_i$ at time $t$ as $D_{R_i}^t=\left\{S_{R_i}^t,z_{R_i}^t, i\right\}$.

Per the discussion above, the team of mapper robots is responsible for locally exploring and acquiring data packets from the area surrounding the landmark robots. The team of landmark robots, on the other hand, can communicate with a central controller and is responsible for directing the exploration of the swarm toward a particular area of the environment. One must note that, while the mapper robots explore and broadcast data packets, the landmark robots remain stationary until given motion commands by a central controller. When the landmarks receive motion commands, the mapper robots follow as they are constrained to stay nearby the landmarks. Thus, by directing the landmark robots toward a particular area of the environment, the effective exploration area of the mapper robots is indirectly controlled via the central controller.

The main problem to be addressed is, thus, exploration of the environment through optimal motion planning for both the mapper and landmark robots, in order to acquire sensor measurements and build an occupancy grid map. The occupancy grid map is a 2D matrix of cells with each cell having an associated occupancy probability denoting the probability that the cell is obstructed by an obstacle [61]. The central controller builds the map, $M$, fixed with respect to the global frame ${}_{ }{}^{G}F$, which is to be updated by the latest proximity measurements.

Per abovementioned, the swarm exploration problem comprises two main sub-tasks: mapper-robot motion planning and landmark-robot motion planning, as discussed below in Section 3.1 and Section 3.2, respectively.

3.1. Mapper-Robot Motion Planning

For the proposed strategy, the mapper robots need to explore the local area surrounding the landmark robots and ”follow” them to new areas in the environment, all the while broadcasting measurements in the form of data packets. Since the mapper robots can only sense the landmark robots within a limited radius, ${\rho }_{sense}$, their motion should be constrained to stay connected to the landmark robots within ${\rho }_{sense}$.

Due to the decentralized nature of their control, each mapper robot’s controller must independently address the following problems: (i) dispersing itself throughout the explorable area while broadcasting data packets and avoiding obstacles, and (ii) staying connected to the landmark robots, even as the latter move to new areas in the environment.

In order to avoid the mapper robots from becoming disconnected, as the landmark robots move, it may be necessary to further constrain their motion to less than the maximum sensing radius to account for cases in which the landmark robot moves outside of the sensing range before the mapper robot could react. One can define the radius of allowable exploration away from the landmark robots, ${\rho }_{explore},$ as a function of ${\rho }_{sense}$, using a safety factor, $s_f>1$:

$${\rho }_{explore}=\frac{{\rho }_{sense}}{s_f}.$$

(5)

3.2. Landmark-Robot Motion Planning

The landmark robots’ motions are planned within the central controller and transmitted to them in the form of motion commands, comprising two stages:

• Position planning: Given the current map, M, a set of positions (nodes) for the landmarks need to be determined. In our work, the positions of the landmarks indirectly dictate where exploration of the environment would occur.
• Path planning: The landmark robots’ paths, from their current positions to the next selected set of planned nodes, need to be determined, given the known obstacles and free spaces within the map. Motion commands for the execution of each path are generated and sent to the landmark robots individually by the central controller.

3.2.1. Position Planning

In the proposed strategy, the positions of the landmark robots affect where exploration of the environment will occur. In order to explore the entirety of an environment, the landmark robots must move to within exploration range, ${\rho }_{explore}$, of previously unmapped areas so that the mapper robots can explore those unmapped regions.

The positions of the landmark robots should be constrained such that they remain connected. One can define this connectivity in the context of graph theory, where the positions of the landmarks form the nodes of a graph with edges between nodes being less than ${\rho }_{sense}$ of each other. The landmark robots should, then, be constrained such that their corresponding graph remains connected. This connectivity requirement allows for the team of landmark robots to share relative proximity and bearing to each other and, thus, improve their localization estimate using cooperative strategies [49,50,51,52,53,54,55,56,57,58,59,60]. Furthermore, it ensures that the mapper robots can explore the region surrounding all the landmark robots.

In this regard, the kth set of planned landmark robot nodes, ${}_{ }{}^G\mathit{L}{}_k$, with $n_L$ nodes can be defined as

$${}_{ }{}^G\mathit{L}{}_k={\left\{{}_{ }{}^G\mathit{x}{}_{L_j}\right\}}_{j=1}^{n_L},$$

(6)

where the position of the nodes ${}_{ }{}^G\mathit{x}{}_{L_j}$ are defined with respect to the global frame, ${}_{ }{}^{G}F$. The connectivity constraint can, then, be given as

$${\left\{dist\left({}_{ }{}^G\mathit{x}{}_{L_j}, {}_{ }{}^G\mathit{x}{}_{L_{j+1}}\right)\right\}}_{j=1}^{n_L-1}\le {\rho }_{sense},$$

(7)

where $dist\left({}_{ }{}^G\mathit{x}{}_{L_j}, {}_{ }{}^G\mathit{x}{}_{L_{j+1}}\right)$ represents the Euclidean distance between consecutive landmark nodes.

Additionally, given a set of planned nodes, ${}_{ }{}^G\mathit{L}{}_k$, within a map, $M$, the area surrounding the nodes within a circle-of-radius ${\rho }_{explore}$ can be explored by the mapper robots. One can define the subset of this exploration area that has not been mapped as the information gain, $I{(}^G{\mathit{L}}_k)$. The information gain represents how much new area would potentially be added to the map if the landmark robots were to move to their respective planned nodes, ${}_{ }{}^G\mathit{L}{}_k$. Estimates of $I{(}^G{\mathit{L}}_k),$ given $M$, can be determined simply as the area of unknown occupancy grid cells within ${\rho }_{explore}$ of each planned node since it is this area that would be newly added to the map [62].

Thus, the primary problem to be addressed at this stage is to determine the best possible planned positions of the landmark robots, ${}_{ }{}^G\mathit{L}{{}_k}^{*}$. The optimization objective function for this problem could be, for example, to maximize the information gain, ${}_{ }{}^G\mathit{L}{}_k$,

$$\max I\left({}_{ }{}^G\mathit{L}{}_k\right)=f\left({}_{ }{}^G\mathit{L}{}_k, M, {\rho }_{explore}\right).$$

(8)

Above, the function $f$ describes the dependance of information gain on the positions of the planned nodes, the latest map, and the radius of exploration surrounding the landmark robots.

3.2.2. Path Planning

Once the optimal nodes for the landmark robots have been determined, the next problem at hand is to build point-to-point (PTP) paths for their motions between their current positions and next planned nodes. For each landmark robot, a path consisting of a series of intermediate points, from its current position to a planned node position, should be determined in order to avoid known obstacles in the environment. The main sub-problems to be addressed are: (i) building collision-free paths, and (ii) ensuring continuous connectivity of the landmark robot team with the mapper robots, while moving along their PTP path.

The path-planning stage should consider the decentralized controller used by the mapper robots. The speed at which the landmark robots traverse the environment may need to be adjusted to ensure that the mapper robots stay connected to the landmark robots as they move through the environment.

4. Proposed Methodology

The proposed mapping strategy requires a swarm to be divided into two distinct groups: a team of (decentralized) mapper robots that would gather information about the environment, and a team of (centralized) landmark robots that direct the mapper robots towards specific areas of the environment. A high-level overview of the proposed strategy is shown in Figure 1. Mapping the environment is an iterative process, with each iteration involving local mapping of the area surrounding the landmark robots and then, moving the landmark robots to a new area to explore. The former is achieved by constraining the motion of the mapper robots to be nearby the landmark robots and incorporating the mapper robots’ measurements into the map, as detailed in Section 4.1. Once the latest area at hand has been explored, the landmark robots move to another ‘promising’ area, as detailed in Section 4.2.

The proposed strategy allows the swarm to prioritize exploration and mapping of unknown areas in the environment. The novelty of the strategy is in the decoupling of the swarm into two teams: one to direct the swarm toward an area in the environment, and the other to acquire measurements to build the map of that area. A team of landmark robots directs the swarm toward an area of the environment that maximizes the potential for new information to be added to the map. A separate team of decentralized mapper robots gather measurements to be incorporated into the map, while staying nearby the landmark robots. This decoupling allows the landmark robots to define where exploration and mapping should occur, independent from the mapper robots.

4.1. Mapper-Robot Motion Planning

As the first stage of the proposed strategy, the local area surrounding the landmark robots is explored using a decentralized team of mapper robots. The sensing capabilities, as well as the motion controller, for the mapper robots is outlined below in Section 4.1.1. Localization of the mapper robots is, then, discussed in Section 4.1.2 and the updating process of the map is discussed in Section 4.1.3, respectively.

4.1.1. Mapper-Robot Sensing and Motion Models

The mapper robots must remain within communication range, ${\rho }_{sense}$, of the landmark robots. Our work considers all robots to be equipped with inter-robot sensing technology that allows them to measure the distance and bearing to their neighbors as defined in Section 3.

We assume that each mapper robot is equipped with an additional exteroceptive sensor capable of acquiring information from its local environment. It is measurements from this sensor that, once localized to the global frame of the map ${}_{ }{}^{G}F$, will be incorporated into the map. In our work, mapper robots are equipped with a single laser distance sensor, pointing straight ahead, capable of measuring distance to an object within range $z_{\max }$ and field-of-view ${\beta }_z$. The distance sensor measurement taken at time $t$ by Robot $R_i$ is denoted as $z_{R_i}^t$.

In order to diffuse themselves throughout the local environment surrounding the landmark robots, herein, it is assumed that the mapper robots use a random-walk behavior to decide in which direction each robot should move, similar to other random motion swarm exploration methods noted in the literature (e.g., [26,27,28,32,33,34]). In contrast these random motion exploration methods, however, the mapper robots, in our work, are constrained to stay within a fixed exploration radius of the landmark robots, ${\rho }_{explore}.$ Each mapper robot defines a random direction to follow, $\alpha$, and moves in this direction until either an obstacle is detected or it detects the nearest landmark to be further than its predefined exploration radius, ${\rho }_{explore}$. In such cases, a new direction is selected to avoid collisions or stay nearby the landmark robots. Figure 2 outlines this random motion model in the form of a finite-state machine.

4.1.2. Swarm Localization

Localization of both the mapper robots and landmark robots is performed in the proposed strategy by a central controller by fusing inter-robot sensor measurements, $s_{R_i{R}_j}$. First, though, estimates of the landmark robots’ positions, ${}_{ }{}^G\widehat{\mathit{L}}{}_k$, are obtained prior to the local exploration conducted by the mapper robots.

Accurate estimates of the landmark robots’ positions with respect to the global frame, ${}_{ }{}^{G}F$, can be obtained, without the use of onboard global positioning sensors (GPS), via a wireless tether of mobile sensors as proposed in our previous work [11]. A team of mobile sensors are positioned to indirectly connect the landmark robots to a static home base, ${}_{ }{}^{G}H$, at the swarm’s starting location. Using the inter-robot measurements from the mobile sensors, landmark robots, and static home base, an estimate of the landmark robots’ positions, ${}_{ }{}^G\widehat{\mathit{L}}{}_k$, can be obtained through the swarm localization approach proposed in our previous work [49].

An estimate of a mapper robot’s position needs to be obtained when incorporating a distance measurement, $z_{R_i}^t$, into the map. In this regard, once a mapper robot makes a distance measurement, it broadcasts a data packet to be received by the landmark robots. Thereafter, this data packet is relayed to the central controller.

The data packet contains the mapper robot’s distance measurement, $z_{R_i}^t$, as well as inter-robot distance and bearing measurements to any landmark robots within sensing range, $s_{R_i{L}_j}$. Additionally, upon receiving the data packet, the landmark robots append their own inter-robot distance and bearing measurements to the mapper robot, $s_{L_j{R}_i}$, prior to relaying the packet to the central controller. The kth data packet to arrive at the central controller is represented as $D_k=\left\{s_{R_i{L}_j}, s_{L_j{R}_i}, z_{R_i}^t, i\right\}$ and can be used to estimate the position of (mapper) Robot $R_i$, when it obtains the distance reading $z_{R_i}^t$.

Fusing the distance and bearing sensing data between the mapper robots and landmark robots, to obtain an estimate of the mapper robots’ positions, follows the approach developed in our previous work [10], and can be summarized as follows. Using both sets of inter-robot sensing data from a data packet received by the central controller, an estimate of mapper Robot $R_i$’s location with respect to the local frame of the landmark robots can be determined. Since estimates of the positions of the landmark robots with respect to the global frame have already been obtained, ${}_{ }{}^G\widehat{\mathit{L}}$, the transformation from the local frame of the landmark robots to the global frame can be obtained and used to determine the estimated position of Robot $R_i$ with respect to the global frame, ${}_{ }{}^G\widehat{\mathit{x}}{}_{R_i}$. Once an estimate of the mapper robot’s position, where it obtained a distance sensor measurement, is determined, it can be incorporated into the occupancy grid map $M$.

4.1.3. Updating the Occupancy Grid Map

The occupancy grid map, $M$, is stored and updated by the central controller using measurements obtained from the mapper robots. The map is a 2D matrix of cells with each cell at (row, column) index ($i,j)$ having an associated occupancy probability $p_{i,j}$, in the range $\left(0,1\right)$. Prior to the incorporation of any data, each cell within the initial map, $M=M_o$, has a probability of $p_o=0.5$. Based on the occupancy probability, the true state of cell can be determined through the following rule: if $p_{i,j}>p_o$, the cell is occupied; if $p_{i,j}<p_o$ the cell is free; and, if $p_{i,j}=p_o$, the cell is unknown.

The map is updated continuously as data packets are obtained from the swarm using a standard map-update method [63]. The nth packet of data containing a mapper Robot $R_i$’s distance measurement, $z_{R_i}^t$, and used to obtain the estimated position at the time of obtaining this distance measurement, ${}_{ }{}^G\widehat{\mathit{x}}{}_{R_i}$, is incorporated into the previous map, $M_{n-1}$:

$$M_n=M_{n-1}+ISM\left(z_{R_i}, {}_{ }{}^G\widehat{\mathit{x}}{}_{R_i}\right)-M_o,$$

(9)

where the function $ISM\left(z_{r_i}, {}_{ }{}^G\widehat{\mathit{x}}{}_{R_i}\right)$ represents the inverse sensor model that converts the robots distance measurement into a grid representation of occupancy.

As more data is incorporated into the map, the area within the map surrounding the landmark robots becomes better ”known”. However, since the motion of the mapper robots is random, the landmark robots must wait for an a priori unknown amount of time for them to gather sufficient data to map the entirety of their exploration area. A stopping criterion for when enough data has been collected to warrant moving the landmark robots to a new area can be defined based on how much of the expected area that can be mapped has been mapped.

The exploration area of the mapper robots is estimated simply as the area within line-of-sight and within radius ${\rho }_{explore}$ of the landmark robots. From the map, M, and using the estimated positions of the landmark robots ${}_{ }{}^G\widehat{\mathit{L}}{}_k$, within the map, the total exploration area of the mapper robots can be calculated, $m_{explore}\subset M$, assuming only unknown area within line-of-sight of the landmark robots is traversable. Any obstacles that would block line-of-sight from the landmark robots reduce the size of the exploration area accordingly. Furthermore, the subset of the total exploration area that has been mapped can be determined, $m_{known}\subset m_{explore}$. The stopping criterion can, then, be formulated as:

$$\frac{\left|m_{known}\right|}{\left|m_{explore}\right|}\ge w_s,$$

(10)

where $w_s$ is a positive constant in the range $\left[0,1\right]$ representing how much of the normalized exploration area should be mapped prior to moving the landmark robots to a new area. For example, in the case where $w_s=1$, the entirety of the estimated exploration area must be mapped prior to moving the landmark robots. It should be noted that the known and explorable areas, $m_{known}$ and $m_{explore}$, are updated as soon as new data packets are incorporated into the map. This allows the explorable area to remain accurate as new obstacles are observed since the calculation of the explorable area only considers area within the line-of-sight of the landmark robots. Figure 3 provides an illustrative procedure for incorporating measurements from the mapper robots into the map.

4.2. Landmark-Robot Motion Planning

Once the local exploration of the environment nearby the landmark robots has been completed, the landmark robots should move towards a new area of the environment that has yet to be mapped. Planning a set of destination nodes for the landmark robots is outlined in Section 4.2.1 below. Motion planning and execution of the planned path for the landmark robots is, in turn, are outlined in Section 4.2.2 below.

4.2.1. Position Planning

Landmark robots should be positioned such that the mapper robots can access previously unexplored areas and, therefore, gather data to expand the known area of the map. Before a new set of landmark robot destination nodes can be planned, distinct frontier regions in the map should be found to determine where unexplored areas can be accessed and where configurations should be planned.

The set of frontier cells within the map need to be first determined. A frontier cell, $f$, is any free cell adjacent to an unknown cell in the map. A frontier region, $F^M$, represents a set of $m$ frontier cells within the map that are adjacent to each other [64]:

$$F^M=\left\{f_1,f_2,\dots f_m\right\}.$$

(11)

Figure 4 provides an illustration of distinct frontier regions found in an occupancy grid map.

A set of planned landmark robot positions, $\mathit{q}$, with $n\le n_L$ landmark robots, can be defined as a matrix of (x, y) nodes that correspond to planned positions for each landmark robot. These nodes can also be defined with respect to the occupancy grid map as a matrix of [row, column] nodes:

$$\mathit{q}\left(n\right)=\left[\begin{array}{c}{q}_1\\ q_2\\ \dots \\ q_n\end{array}\right]=\left[\begin{array}{cc}{x}_1& y_1\\ x_2& y_2\\ \dots & \dots \\ x_n& y_n\end{array}\right]; x,y\in ℝ\Rightarrow {\mathit{q}}_{grid}=\left[\begin{array}{cc}{r}_1& c_1\\ r_2& c_2\\ \dots & \dots \\ r_n& c_n\end{array}\right];r,c\in {\mathbb{Z}}^{+}.$$

(12)

The objective of planning landmark-robot positions is to allow the mapper robots to explore and gather data from as large an unknown area as possible, such that the occupancy grid map can be expanded as much as possible. It is, therefore, useful to define a measure for the expected amount that the map will expand by.

Given some potential landmark-robot nodes, one can define the amount of new information that could be added by mapping the surrounding area as the information gain, $I\left(\mathit{q}\right)$. The mapping of the surrounding area is performed by the mapper robots, which only gather data from within a limited range of the landmark robots, ${\rho }_{explore}$. The information gain can therefore be estimated simply as the area of unknown occupancy grid cells within ${\rho }_{explore}$ and line-of-sight of each planned node since it is this area that would be newly added to map. Figure 5 below illustrates how the information gain is estimated given a potential set of landmark robot nodes. In this example $I\left(\mathit{q}\right)=0.0992$ m². The information gain is used to evaluate the performance of a particular set of nodes and is maximized for each set of nodes planned at a frontier region.

Optimally planning the position of every landmark robot is not always necessary. It may be sufficient to optimally plan only a subset of nodes if these nodes still allow the frontier region to be fully explored. A frontier region may be fully explored by fewer than the total number of landmark robots, especially, if the region is sufficiently small or there are many landmark robots available. If there are many landmark robots, optimally planning the position of every robot directly may become computationally infeasible. Therefore, the minimum number of landmark robots to explore a frontier region as well as their corresponding optimal positions need to be determined.

The proposed algorithm for finding the optimal landmark-robot nodes, at a given frontier region is a nested-loop procedure, Figure 6: The outer loop (red dashed line) seeks to find the optimal number of landmark-robot nodes by evaluating configurations with a feasible number of nodes (i.e., number of nodes no greater than the total number of landmark robots, $n_L$); and, the inner loop (blue dashed line) determines the optimal placements of the landmark-robot nodes for the number of nodes considered by the outer loop.

In this work, landmark robots explore one frontier region at a time. Once all sets of nodes are planned at each frontier region in the map, one of these sets is chosen for the landmark robots to move towards the next region, ${}_{ }{}^G\mathit{L}{}_{k+1}$. Amongst the sets of nodes for each frontier region, let the set with the highest information gain be denoted as ${\mathit{q}}_{\max }$. This set is selected as the planned set of nodes for the landmark robots to move towards the next set, ${\mathit{q}}_{\max }\to {}_{ }{}^G\mathit{L}{}_{k+1}$.

Additional nodes may be added to the selected set of nodes ${\mathit{q}}_{\max },$ until the total number of nodes equals the total number of available landmark robots, $n_L$. These additional nodes are added at the centroid of the selected set to ensure connectivity of the landmark robots. Motion from the landmark robots’ current estimated positions ${}_{ }{}^G\widehat{\mathit{L}}{}_k$ to the planned set of nodes, ${}_{ }{}^G\mathit{L}{}_{k+1}$, needs to be planned, as to be detailed in Section 4.2.2.

Outer Loop

Given a frontier region consisting of a cluster of frontier points, the outer optimization loop seeks to find the minimum number of landmark-robot nodes, $n\le n_L$, that maximizes the information gain. For a (feasible) number of landmark-robot nodes considered in this loop, the information gain is determined by finding the corresponding optimal node placement ${\mathit{q}}^{*}\left(n\right)$ using the inner optimization loop described below in inner loop section.

As detailed in Appendix A, when evaluating the information gain between two sets of landmark-robot nodes, with different number of nodes, the set with more nodes would have the larger information gain. However, as the number of nodes is increased, the area within mapping range of the nodes covers more of the frontier region which may become saturated if there are enough nodes to cover most of the unknown area surrounding the frontier. Since the size of the frontier region is finite, the unknown area within mapping range along the frontier region is also finite. A set of landmark-robot nodes would have an information gain that corresponds to some subset of this finite unknown area. As the number of nodes is increased and the frontier region becomes saturated with landmark robots, the information gain approaches a maximum value corresponding to the total unknown area within mapping range of the frontier region.

More formally, a frontier region can be defined as ”saturated” when an optimally placed set of $n$ nodes are planned such that the information gain of the optimal set of nodes, $I\left({\mathit{q}}^{*}\left(n\right)\right)$, surpasses a threshold, $w_i=\left[0,1\right]$, of the maximum information gain possible $I_{\max }$. Appendix A provides a more detailed description of determining the maximum information gain, $I_{\max }$:

$$I\left({\mathit{q}}^{*}\left(n\right)\right)\ge w_i\ast I_{\max }.$$

(13)

The threshold $w_i$ can be tuned to favour sets of nodes with more information gain at the expense of more landmark robots being used. This optimization, then, seeks to determine the minimum number of landmark-robot nodes to saturate the given frontier cluster. The optimal number of landmark-robot nodes, $n^{*}$, is, then:

$$\begin{gathered} n^{*}=\min \left(n\right)\mathrm{s}.\mathrm{t}.I\left({\mathit{q}}^{*}\left(n\right)\right)\ge w_i\ast I_{\max } \\ n\in {\mathbb{Z}}^{+}, \end{gathered}$$

(14)

where $n$ is constrained by the total number of available robots $n\le n_L$.

Determining the optimal number of landmark robots could be conducted using a simple, single-variable search engine that searches through the discrete set of integers from 1 up to the total available robots $n_L$. The search is terminated prior to reaching $n_L$, if the number of landmark robots saturates the frontier region.

Inner Loop

Given a frontier region, $F^M=\left\{f_1, f_2,\dots f_m\right\}$, and the number of landmark-robot nodes to be planned, $n$, one would need to determine the set of node positions, ${\mathit{q}}^{*}\left(n\right)$, that maximizes the information gain. However, due to the limited sensing range of the landmark robots, and therefore limited exploration range of the mapping robots, constraints must be imposed on the planned nodes. The constraints imposed on a set of $n$ nodes, $\mathit{q}\left(n\right)$, include the nodes being connected (as defined in Section 3.2.1) and the positions of all the $n$ nodes being in free space nearby the frontier $F^M$.

The inner-loop optimization solves for:

$${\mathit{q}}^{*}\left(n\right)=\max \left(I\left(\mathit{q}\left(n\right)\right)\right),$$

(15)

where the set of nodes $\mathit{q}\left(n\right)={\left[q_1, q_2,\dots q_n\right]}^T$ is subject to the following constraints:

$$\begin{array}{cc}\mathrm{Connectivity} \mathrm{constraint}:\hfill & \\ & {\left\{dist\left(q_i, q_{i+1}\right)\right\}}_{i=1}^{n-1} \le {\rho }_{sense},\hfill \end{array}$$

(16)

$$\begin{array}{cc}\mathrm{Nearby-frontier} \mathrm{constraint}:\hfill & \\ & {\left\{dist\left(q_i,F^M\right)\right\}}_{i=1}^n\le {\rho }_{explore},\hfill \end{array}$$

(17)

$$\begin{array}{cc}\mathrm{Free-space} \mathrm{constraint}:\hfill & \\ & {\mathit{q}}_{grid}\in M_{free}.\hfill \end{array}$$

(18)

Above, the distance between a node, $q_i$, and set of frontier points, $F$, (i.e., $dist\left(q_i,F\right)$) is the minimum Euclidean distance between the node and the set of frontier points. Additionally in the free-space constraint above, $M_{free}$ represents the subset of points in the occupancy grid that are known to be free (i.e., not unknown and contain no obstacles).

The nearby-frontier and free-space constraints (Equations (17) and (18), respectively) limit the placement of all the nodes to the same subset of occupancy grid cells. This subset of cells can be determined prior to beginning the optimization and can be used to specify the domain of each variable (node) to a discrete set. The connectivity constraint represents a non-linear constraint between each pair of nodes so that the landmark robots remain within inter-robot sensing range of each other.

This inner optimization loop represents a nonlinearly constrained discrete optimization problem. It is, therefore, recommended to use a combinatoric method, such as a variation of a genetic algorithm to obtain an optimal solution [65].

In this context, one method of obtaining an initial high-quality solution is to build a set of nodes sequentially, solving a single-variable discrete optimization problem consecutively until the number of required nodes is reached. Determining the position of each node involves solving a single-variable optimization problem for the occupancy grid cell with the highest information gain. Initially, the first node can be placed at the single location with the highest information gain that satisfies Equations (17) and (18). The next nodes are added by assuming all previous nodes remain fixed and, therefore, reducing the domain of the search for the next node to cells that satisfy all three above constraints, Equations (16)–(18). Figure 7 illustrates this method of finding an initial high-quality solution.

4.2.2. Path Planning

Once a set of nodes corresponding to destinations for the landmark robots has been determined, obstacle-free paths must be found between the landmark robots’ current positions and destination nodes. Additionally, the landmark robots should remain connected to each other during their motion.

An initial obstacle-free path, between the current centroid of the landmark-robot positions and centroid of the planned nodes, can be determined using an A* planner [66]. Motion commands can, then, be supplied to the landmark robots to direct them from their current position, along the planned path, toward their destination node. By having all the landmark robot use the same planned paths, rather than planning an individual path for each robot, the landmark robots remain nearby each other during their motion (i.e., connected).

5. Results

Simulated examples are included herein to illustrate the working of the proposed mapping strategy in building a 2D occupancy grid map of an unknown environment using robotic swarms. The proximity sensing and motion characteristics of our mROBerTO millirobot were used as the robots in the simulations [6,7,8]. Namely, all simulations were completed with inter-robot sensing noise variance of ${\sigma }_{int}^2=2$ mm² with a maximum range ${\rho }_{sense}=200$ mm. Additionally, each mapper robot was equipped with a simulated forward-facing 1D distance (laser) sensor on the robot. The simulated distance sensor had a max range of $z_{\max }=200$ mm, and noise of ${\sigma }_{laser}^2=9$ mm² and measured the shortest distance to an obstacle within a field-of-view of $\beta ={22}^{°}$.

In the simulations, the landmark robots had a constant speed of $v_{landmark}=60$ mm/s, while the mapper robots had a faster constant speed of $v_{mapper}=80$ mm/s in order to ensure they remained connected to the landmark robots as the swarm moved to new areas of the environment. The occupancy grid map had an individual cell size of 10 mm. The parameter, $w_s$, was set to 0.95 and described what percentage of the explorable area surrounding the landmark robots should be mapped prior to moving the landmark robots. The parameter, $w_i$, was set to 0.85 and described what percentage of the maximum information gain at a frontier should a potential set of landmark nodes have before considering the set of nodes to allow for most of the frontier to be explored (see Appendix A).

5.1. Illustrative Example—1200 × 1200 mm² Enclosed Environment

For the first simulation, discussed herein, the swarm comprised of four landmark robots and ten mapper robots and explored a 1200 $\times$ 1200 mm² enclosed environment, Figure 8. A fixed home base reference was included in the environment, located at (650, 450) mm, needed for the landmark robots to use a tether-based motion strategy to move to new areas.

The proposed exploration strategy begins by using the decentralized mapper robots to gather distance measurements around the local area surrounding the landmark robots. Once 95% of the area within exploration range of the landmark robots has been mapped ($w_s=0.95)$, the landmark robots move to the next area of the map that maximizes the amount of new information potentially added to the map, and the process repeats. This iterative procedure repeats until no more frontiers can be found in the map.

Figure 9 shows the occupancy grid maps after each iteration for a total of nine iterations. The final map is shown in Figure 9i. Figure 10 depicts the percentage of the environment mapped over time. The marked points in Figure 10 correspond to the percentage of the environment mapped after each iteration. The percentage mapped between marked points (iterations) initially increases rapidly as the local area surrounding the landmark robots is mapped. Prior to the next iteration, however, the curve flattens since during this time the landmark robots move to a new area in the environment.

5.2. 1000 × 1000 mm² Non-Enclosed Environment

In this simulation, the swarm comprised four landmark robots and ten mapper robots and explored a 1000 $\times$ 1000 mm² non-enclosed environment, Figure 11a. A fixed home base reference was included in the environment, located at (300, 400) mm, needed for the landmark robots to use a tether-based motion strategy to move to new areas.

The environment did not have walls to prevent the swarm from moving outside of the desired area to be mapped. The area outside of the true environment shown in Figure 11a was freely traversable by the swarm. In order to prevent the swarm from trying to explore regions outside of the 1000 $\times$ 1000 mm² environment, the occupancy grid was initialized to represent only a 1000 $\times$ 1000 mm² region prior to exploration. Frontiers and, therefore, planned positions of the landmark robots were always discovered inside the desired area to be mapped. Figure 11b shows the final map obtained through our proposed exploration strategy.

Despite the environment not having walls, the landmark robots were always planned by the central controller to stay inside the 1000 $\times$ 1000 mm² occupancy grid map. Since the mapper robots were constrained to stay nearby the landmark robots, none of the robots in the swarm could travel too far outside the area to be mapped.

5.3. Impact of Relative Number of Landmark Robots

In order to assess the impact of the number of landmark robots, $n_L$, on the exploration and mapping speed, we conducted a series of simulations with a fixed total number of robots in the swarm. We assigned a subset of the swarm as landmark robots, while the remaining members were designated as mapper robots. Varying the number of landmark robots, $n_L$, we determined the time required to complete the mapping of the environment and the total number of iterations needed for each simulation.

The objective of this study was to identify the relative ratio of landmark robots to total number of robots in the swarm that can achieve the fastest mapping of the environment with the fewest iterations possible. One may recall that, in our exploration strategy, each iteration involves locally exploring the area surrounding the landmark robots and, then, planning and moving the landmarks to a new frontier in the environment. It is, therefore, desirable to minimize the number of iterations in order to minimize the frequency at which the landmark robots’ motions need to be planned.

The time to complete mapping the environment and the number of iterations were each normalized and a weighted sum objective function, that combined the values from both goals, was utilized:

$$H\left(n_L\right)=w_{time}\ast T_{norm}+w_{iter}\ast I_{norm},$$

(19)

where $w_{time}$ and $w_{iter}$ represent the weights associated with the normalized completion time, $T_{norm}$, and normalized number of iterations, $I_{norm}$, respectively.

Figure 12 and Figure 13 below depict the normalized completion time and total number of iterations, as well as the objective function using weights of $w_{time}=w_{iter}=1$ for simulations conducted in the environment shown in Section 5.1 and Section 5.2, respectively. As can be noted in Figure 12 and Figure 13, as the number of landmarks is increased, the overall time taken to map an environment also increased, while the total number of iterations required decreased. When the time to complete mapping the environment and total number of iterations were weighted equally, the number of landmark robots that minimized the heuristic objective function $H\left(n_L\right)$ is approximately half the total number of robots in the swarm. Under these conditions, the environment is mapped using fewer iterations.

In order to map the environment even faster, more weight can be given to the completion time. In this case, approximately one third of the total number of robots in the swarm can be given the role of landmark robot while the rest are given the role of mapper robot. Conversely, when more than half of the robots are landmark robots, the least number of iterations would be required to complete mapping the environment, at the expense of an increased overall time to map.

During each iteration every landmark robot’s motion must be planned by a central controller and sent to the robot in the form of motion commands to be executed. Depending on the specific swarm robots utilized, it may be worth the increase in the time to map the environment, if the landmark robots’ motions need to be planned and executed less frequently.

5.4. Comparison with Random Landmark Placement

Our strategy optimizes the positions of the landmark robots to maximize new information being added to the occupancy grid map. In order to validate the effectiveness of this optimization, a comparative study, with an alternate method of planning the positions of the landmark robots, was conducted. This alternate method, hereafter, denoted the random-placement method, places landmark robots (randomly) nearby a randomly selected frontier region in the environment. It should be noted that the overall structure of the exploration strategy, namely, using mapper robots to first locally map an area surrounding the landmark robots and, then, moving the landmark robots to a new area in the environment, remains the same.

The random-placement method, first, uniformly selects a frontier region from the set of frontier regions found in the map. Next, a node, representing the planned position of one landmark robot, is randomly selected from the set of occupancy grid cells satisfying the nearby-frontier and free-space constraints (Equations (17) and (18), respectively). This ensures that the frontier region can at least be partially explored by the mapper robots. Subsequent nodes are randomly selected from the set of cells satisfying the previously mentioned constraints as well as the connectivity constraint given in Equation (15) until the total number of nodes equal the total number of landmark robots available. The random-placement method of positioning the landmark robots satisfies all of the same constraints as our proposed optimally-planned-placement method presented in Section 4.2.1.

Figure 14a,b below depict the results from exploring the environments shown in Section 5.1 and Section 5.2, respectively, using both the optimal planned positions of the landmark robots and the random placement method. The swarm comprised 20 robots in total, of which $n_L=10$ were landmark robots. As can be noted in Figure 14, optimally planning the positions of the landmark robots allows for an overall tangibly faster exploration and mapping of the environment.

6. Conclusions

This paper presents a novel collaborative exploration strategy that allows a resource-constrained swarm to build an occupancy grid map of an unknown environment. The proposed strategy divides the swarm into two teams, mapper robots and landmark robots. The mapper robots map the local environment surrounding the landmark robots. The landmark robots direct the exploration and mapping of the swarm toward a particular area of the environment by physically positioning themselves in that area. The novelty of our strategy is in the physical decoupling of a swarm into these two teams: landmark and mapper robots, respectively. This decoupling allows the problem of directing a swarm to a new area of the environment to be addressed separately from the problem of exploring that new area using robots with limited environment perception abilities. Namely, the landmark robots’ motions are planned and executed to maximize new information added to the map without impeding how the mapper robots explore the area. The mappers robots are, therefore, can still use a decentralized, scalable, random-motion model to explore the local area surrounding the landmark robots while the swarm, as a whole, follows an efficient frontier-based exploration of the environment.

In contrast, other methods, for building occupancy grid maps using resource-constrained swarms, do not direct exploration. Instead, they use random motion alone to disperse the swarm and, therefore, may explore the environment inefficiently by allowing the robots to visit previously mapped areas [26,27,28].

The positions of the landmark robots are optimized herein using a frontier-based technique to maximize new information added to the map while also adhering to connectivity constraints. These connectivity constraints ensure the landmark robots can communicate and share relative position estimates between themselves and nearby mapper robots. By ensuring connectivity between the landmark robots, their positions can be accurately estimated using the tether-based strategy presented in our previous work [11]. The landmark robots do not need to rely on external sensing infrastructure to provide them with absolute position estimates.

The proposed collaborative exploration strategy was evaluated through a series of simulated experiments. These validated the effectiveness of the proposed method in building an accurate occupancy grid map. Future work may consider the use of alternative random-motion models for the mapper robots as well as investigating the creation of global maps of an environment using map merging techniques from local maps generated solely from exploration of the nearby area surrounding landmark robots.