Combining Geometric and Information-Theoretic Approaches
for Multi-Robot Exploration

The study of geometric problems that are based on visibility is a well-established field within computational geometry. The classic problems are the art gallery problem [39], watchman route problem [12], target search [22] and shortest path planning [41] in unknown environments.

Using a fixed set of positions for guarding a known $n$-sided polygonal region, i.e., a set of points from which the entire polygon is visible, is known as the classical art gallery problem. Chvatal [14] and Fisk [21] proved that $\lfloor n/3\rfloor$ guards are always sufficient and sometimes necessary to cover a polygon of $n$ sides. The minimum number of guards required for a specific polygon may be much smaller than this upper bound. However, Schuchardt and Hecker [45] showed that finding a minimum set of guards is NP-hard, even for the special case of an orthogonal polygon.

Finding the shortest tour along which one mobile guard can see the polygon completely is the watchman route problem. Chin and Ntafos [12] showed that the watchman route can be found in polynomial time in a simple orthogonal polygon. Wang et al. [48] showed that the watchman route problem is for general environments is NP-hard and presented a $\mathcal{O}(\text{polylog}n)$ approximation for the restricted case when each viewpoint is required to see a complete polygon side.

Exploring an unknown polygon is the online watchman route problem. Bhattacharya et al. [6] and Ghosh et al. [24] approached the exploration problem with discrete vision, i.e., they assume that the robot does not have continuous visibility and has to stop at different scan points in order to sense the environment. They focus on the worst-case number of necessary scan points. Their algorithm results in a competitive ratio of $(r+1)/2$, where $r$ is the number of reflex vertices in the polygon. For limited range of visibility, they give an algorithm where the competitive ratio in a polygon $P$ can be limited by $\lfloor\frac{8\pi}{3}+\frac{\pi R\times Perimeter(P)}{Area(P)}+\frac{(r+h+1)\pi R^{2}}{Area(P)}\rfloor$, where $h$ is the number of holes and $R$ is the number of reflex vertices in the polygon.

Albers et al. [2] assume that the environment is modeled by a directed, strongly connected graph and give a $d^{\mathcal{O}\log d}m$ competitive algorithm where $m$ is the number edges in the graph and $d$ is the minimum number of edges that have to be added to make the graph Eulerian. The robot’s task is to visit all nodes and edges of the graph using the minimum number $R$ of edge traversals. For a simple polygon, Hoffmann et al. [26] presented an algorithm which achieves a competitive ratio of $26.5$. For the special case of an orthogonal polygon, Deng et al. [17] presented a $\sqrt{2}$ competitive exploration strategy with one robot. We show how to extend the single robot exploration algorithm by Deng et al. [17] to the case of $p$ robots. The resulting algorithm has a competitive ratio that is a function of $p$.

The problem of visiting all the nodes in a graph in the least amount of time is known as the Traveling Salesperson Problem (TSP). Here, all nodes of the graph are known before-hand and the objective is to determine the shortest tour visiting all the nodes in the graph exactly once. Finding the optimal TSP tour for a given graph is known to be NP-hard, even for the special case where the nodes in the graph represent points on the Euclidean plane [35]. For the Euclidean version of the problem, there exist polynomial time approximation schemes [35, 4], i.e., for any $\epsilon>0$, there exists a polynomial time algorithm which guarantees an approximation factor of $1+\epsilon$.

In the graph exploration version of the problem, nodes are revealed in an online fashion. The objective is to minimize the total distance (or time) traveled. Fraigniaud et al. [23] presented an algorithm for exploration of trees using $p$ robots with a competitive ratio of $\mathcal{O}(p/\log p)$ and a lower bound of $\Omega(2+1/p)$. This lower bound was improved by Dynia et al. [19] to $\Omega(\log p/\log\log p)$. They modeled the cost as the maximal number of edges traversed by a robot and presented a $(4-2/p)$ competitive online algorithm. Higashikawa et al. [25] showed that greedy exploration strategies have an even stronger lower bound of $\Omega(p/\log p)$ and presented a $(p+\log p/1+\log p)$ competitive algorithm.

Better bounds have been achieved for restricted graphs. Dynia et al. [18] presented an algorithm that achieves faster exploration for trees restricted by a density parameter $k$ which forces a minimum depth for any subtree depending on its size. Trees embeddable in $d$-dimensional grids can be explored with a competitive ratio of $\mathcal{O}(d^{1-1/k})$. For 2-dimensional grids with only convex obstacles, Ortolf et al. [40] improved the competitive ratio to $\mathcal{O}(\log^{2}d)$. Despite these strong restrictions on the graph, the same lower bound of $\Omega(\log p/\log\log p)$ holds for all trees.

We show that the problem of exploring a polygon can be formulated as a multi-robot tree exploration problem. Our algorithm yields a competitive ratio of $\frac{2(\sqrt{2}{p}+{\log p})}{1+\log p}$ where $p$ is the number of robots.

Geometric and graph-based approaches typically assume perfect sensing with no noise. In practice, however, measurements are not perfect and we have to account for measurement noise when exploring the environment. Such exploration strategies can be broadly classified into frontier-based and information-theoretic strategies [29].

Information-Theoretic exploration strategies typically use an occupancy grid to represent the maps generated from noisy and uncertain sensor measurement [20]. An occupancy grid is a uniformly-spaced grid, with a binary random variable (per grid cell) representing the probability of the cell being occupied by an obstacle. There are many existing occupancy grid mapping techniques like gmapping [47], octomap [28], RTAB-Map [34] and ORB-slam [38]. Frontier-based exploration strategies are largely greedy in nature and drive the robots to the boundary between known and unknown spaces in the map. In occupancy grids, frontiers are cells determined to be free (probability of occupancy close to zero) which are next to grid cells that have not been observed (probability of occupancy is set to be 0.5), shown in Figure 1. Variants of this strategy have been used to perform exploration of unknown 2D [50, 8, 46] and 2.5D environments [9]. We refer the reader to the comprehensive study by Holz et al. [27] for further details.

Information-theoretic strategies seek to optimize some information measure such as entropy (uncertainty) [49, 36] in the environment, or mutual information [3] while exploring the environment. Mutual information [15] between two random variables $X$ and $Y$ is given by,

Mutual information in occupancy grid predicts how much future measurements will decrease the robot’s uncertainty associated with all grid cells. Julian et al. [30] studied the computation of mutual information for range based sensors. While these algorithms produce better maps, the planner is typically a one-step greedy algorithm or finite-horizon planners that cannot give global guarantees on the total distance traveled.

In order to overcome this, a better approach may be to combine a global planner along with a local planner. Davis et al. [16] proposed one such algorithm where the goal was to maximizes the coverage of a user-specified region while minimizing the control costs of the robot. The authors are given a start state and a goal state and minimize the probability of collision with the environment as well. Bai et al. [5] used an approach to predict mutual information using Bayesian optimization in which the long-term goal is to reduce entropy throughout the robot’s environment map, and the short-term goal is to perform the sensing action in each iteration that will maximize mutual information. Choudhury et al. [13] showed that supervised learning could be used to predict informative actions without evaluating the expected mutual information exhaustively for every possible action. Charrow et al. [10] attempted to resolve this with a heuristic that uses a global planner for a single robot to determine trajectories that maximizes the Information-Theoretic objective whilst employing a gradient-based trajectory optimization technique to locally refine the chosen trajectory such that the mutual information objective is maximized. We build on this work and present a two-level planner that maximizes information locally while giving strong global performance guarantees on the path length followed by the robots.

In this section, we prove that the competitive ratio of our algorithm is bounded with respect to the offline optimal algorithm. We divide our analysis into three steps. First, we show that the paths followed by all the robots can be mapped to navigating on a tree. Next, we bound the sum of the costs of edges in the tree with respect to the offline optimal cost. Finally, we bound the cost of our algorithm with respect to the cost of the tree. The graph created by the algorithm is a tree by construction because once a node is added to the graph it is not added to the graph again.

When $p=1$, the proposed algorithm is the same as the one given by Deng et al. [17] for orthogonal polygons without holes. They showed that the competitive ratio of this algorithm is $\sqrt{2}$. The analysis relies on showing that the robot visits the critical extensions in the clockwise order in which their associated sides appear on the boundary of the polygon. We refer the reader to Lemma 6 in [17] for a proof and detailed exposition.

Let $C_{\text{OPT}}^{p}$ denote the time taken by the optimal algorithm for $p$ robots to explore $P$. Let $C_{\text{RECT}}$ denote the time taken by the strategy from [17] for a single robot to explore $P$. We have $C_{\text{RECT}}\leq\sqrt{2}C_{\text{OPT}}$ from Theorem 3 in [17] and the assumption that the robots travel with unit speeds. Let $C_{\text{EXPLORE}}^{p}$ be the time taken by the proposed algorithm. We show that the ratio, $C_{\text{EXPLORE}}^{p}/C_{\text{OPT}}$, is constant for a given $p$. We will show this by relating both quantities with $C_{\text{TREE}}^{p}$ which is the sum of the lengths of edges in the tree created by $p$ robots. Note that $C_{\text{TREE}}^{p}$ is not the same as $C_{\text{EXPLORE}}^{p}$ since it does not take into account the backtracking that may be involved in the robots’ paths.

Thus, we show that the competitive ratio is bounded as a function of $p$. Figure 5 shows a plot of this bound as a function of $p$. We note that while the analysis only holds for the case of an orthogonal polygon without holes, the resulting algorithm can also be applied for polygons with holes. However, in such a case, the underlying graph created by the robots is not guaranteed to be a tree. Consequently, we would have to use analogous algorithms for exploring general graphs with multiple robots to yield a similar competitive ratio. In the simulations, we show the empirical performance of our algorithm in environments with holes.

The main assumption is that of unlimited sensing range. In practice, the robot has a limited sensing range. For example, the robot cannot sense a long corridor with a single observation. Thus, in addition to blocking vertices, the robot has to move to frontiers at the end of its sensing range to sense more of the environment. This increases the distance the robot would have to cover compared to the distance it would have to cover if it had an infinite sensor. The robot thus has to detect two types of frontiers, one due to blocking vertices and the other due to sensing range. The only change to the algorithm is in Line 1 where we check for blocking vertices as well as frontiers due to sensing range.

We first detect blocking vertices in a given scan (as described below). Then frontier cells are clustered together to form frontiers due to sensing range. Any frontier which has a constituent frontier cell neighboring a blocking vertex is then discarded. For a blocking vertex, the extension goal is added on its extension with a slight offset. For frontiers due to sensing range, the middle frontier cell, after clustering, is chosen as the frontier goal.

Due to the sensing uncertainty, we represent the map built by the robots as a 2D occupancy grid (OG) as opposed to a geometric map. An OG is a discretized representation of the environment where each cell represents the probability of that space being occupied. Figure 6-Right shows a representative OG. Cells with a lower probability of occupancy ($<0.5$) are designated as free cells (represented as white in the OG) and cells with a higher probability of occupancy ($>0.5$) are designated as occupied cells (represented as black in the OG). Cells which have not been observed are marked as unknown (represented as gray in the OG).

Typical sensors such as cameras and laser rangefinders have a finite angular resolution. Consider three rays from the laser as shown in Figure 6-Left. The rays intersect obstacles at the cells marked as black and all the cells the ray intersect between the robot (marked in blue) and the cell are marked as free. Due to the finite resolution of the laser ($0.395^{\circ}$ for the Hokuyo laser used in our system), the gray cells, even though they are in the field of the laser, are unobserved and this leads to gaps in observations. This leads to false frontiers being detected and hence such erroneous frontiers have to be discarded. We employ a simple heuristic of checking the size of a candidate frontier and discard those below a threshold.

Consider the robot (and the laser) located at the blue circle in Figure 6-Right. The red ray represents one of the laser rays. In order to check for blocking vertices, occupied cells with a neighboring frontier cell are shortlisted first. In the figure, the cells marked with yellow and red X are identified. A blocking vertex, as defined earlier, is a reflex vertex. We can detect a reflex vertex in an OG by checking its four neighbors. If the four neighbors are an occupied cell, an unknown cell, a free cell which is a frontier, and a free cell which is not a frontier we mark it as a blocking vertex. In Figure 6-Right, the cell marked with the yellow X is detected as a blocking vertex.

In the analysis for Algorithm 1, we assumed that we follow the shortest paths between A and B when executing the goto(A,B) subroutine. Instead, we can add local detours that will increase the information gain in order to improve the quality of the map. In order to maintain a constant competitive ratio, the robot is given a certain budget. This is known as the orienteering problem [7]. The orienteering problem seeks to find a path of length no more than a given budget, that maximizes the reward collected along the path. The reward is a function of the set of vertices visited along the path. If the reward is modular, then there exists a constant-factor approximation for the problem [7].

Our objective is to minimize the uncertainty in the map. Mutual information [10] is a suitable reward function that can be used. Mutual information measures the expected reduction in the entropy (i.e., uncertainty) of the map based on the measurements it expects to receive along the path. Mutual information is known to be submodular and monotonically increasing [32].²²2Strictly speaking, mutual information is only monotonically increasing when the number of vertices on the path is much less than the number of vertices on the graph [32]. We use the recursive greedy algorithm for submodular orienteering by Chekuri and Pal [11] to add local detours to the path. Chekuri and Pal [11] give a quasi-polynomial time recursive greedy algorithm that yields an $\mathcal{O}(\log\text{OPT})$ approximation for this problem, where OPT is the optimal reward.

The orienteering subroutine takes as input: an input graph, $G$, a start vertex, $s$, a goal vertex, $t$, a budget, $B$, a set of nodes visited, $X$ and returns a path that maximizes a submodular reward function subject to the budget. The input graph is generated by imposing a grid (add points above and below the path) on the shortest path between $s$ and $t$ as shown in Figure 7. The start vertex is the current position of the robot, and the goal vertex is the next node in the tree to be visited. We set the budget to $B=\alpha d$, where $d$ is the length of the shortest path from $s$ to $t$, and $\alpha\geq 1$ is any constant. As $\alpha$ increases, we expect the quality of the map to improve at the expense of the cost of exploration (Figure 7).

We modify the subroutine in order to save computation time by restricting the paths to be strictly moving forward, i.e, the path cannot have edges moving back towards $s$. This reduces the computation time by an order of magnitude. This is a heuristic and therefore the approximation ratio may not necessarily hold for the heuristic.

Our algorithm also works for environments which are not orthogonal when occupancy grids are used as the underlying representation. Occupancy grids, typically, are orthogonal polygons by construction. Furthermore, for environments with holes (i.e., obstacles) the algorithm would create a tree and explore this tree. While this is correct, the distance traveled by the robots can be much higher than the optimal cost and as such the competitive ratio does not hold.

In the next section, we evaluate the empirical performance of our algorithm through simulations in such scenarios.

We implemented our algorithm using ROS [43] and carried out simulations in Gazebo [31] in order to verify the correctness of the exploration algorithm in realistic environments. The five Gazebo simulation environments used (Figure 8) are not all orthogonal and simply-connected – assumptions only required for the analysis to hold. The simulated robot is a differential-drive Pioneer P3-DX robot with a 2D Hokuyo laser range finder with a maximum range of 5 meters. The robot is localized in the environment using the amcl [1] package using a pre-defined map. Mapping during exploration is done using the octomap ROS package. The laser scan is converted into a point cloud which is then fed as input to the octomap [28] node. Our implementation is available online at https://github.com/raaslab/Exploration.

Figure 9 shows various stages of exploration with four robots. The figure also shows the partial exploration tree built by the algorithm. The final trees produced while exploring all the environments are given in Figure 10. Table I shows the maximum distance traveled by a robot (in meters) during exploration for all the environments.

The cost of exploring environments 1, 3, 4, and 5 remains almost the same when the number of robots is increased from two to four. This is due to the fact that the exploration tree is not a balanced tree (Figure 10). On the other hand, in environment 2, the tree contains four or more under-exploration branches at all times. Consequently, the cost of exploration decreases significantly when four robots are used as opposed to just two.

The effect of the budget on the entropy is shown in table II. We can see that increase in budget reduces the overall entropy in the environment but at the cost of increased exploration time. We can also see that increasing the number of robots also decreases the entropy in the environment.

We carried out experiments using a Pioneer P3-DX robot mounted with a Hokuyo URG-04LX-UG01 2D laser and a Kinect2 RGBD sensor (Figure 11-Top). The laser was configured to use 180^∘ field of view with a resolution of 0.395^∘. During the exploration experiments, the robot used the 2D laser for localization on a pre-built map. The map was generated using RTAB-map [34, 33] and the localization was carried out using the amcl package from ROS. Note that having a pre-built map is not a requirement for our algorithm. The amcl localization component could be replaced by, for example, any SLAM implementation. Furthermore, the robots generated a new map during the exploration process using octomapping [28] with the Kinect2 sensor. This map (and not the pre-built map) was used as the basis for finding blocking vertices in the proposed exploration algorithm.

The mapping and localization were performed on the pioneer P3-DX robot with two onboard computers in a master/slave configuration. The slave i7 Intel NUC was dedicated to processing the Kinect2 data and the master i7Intel NUC was dedicated to running the localization and exploration algorithm. Figure 11 shows the results of an exploration experiment in a corridor environment along with the path followed by the robot. This proof-of-concept experiment shows that the algorithm can be applied in real world scenarios. A video of the system in operation is available online at https://github.com/raaslab/Exploration