Extending the Limits of the Random Exploration Graph for Efficient Autonomous Exploration in Unknown Environments

Abstract

The autonomous construction of environment maps using mobile robots is a fundamental problem of robotics; this is because virtually all tasks performed by robots need a representation of the working environment to operate. Although many works have addressed this problem known as SLAM, it still remains open; since most of the solutions do not consider a planner that allows the robot to explore autonomously the working environment or the works that consider it, they have developed slow algorithms that do not guarantee a total coverage of the environment or an optimal development of the exploration, which may result in maps of poor quality or definitely not usable given this lack of information. Thus, this work presents a new exploration method based on the random exploration graph (REG), which, unlike its predecessor, defines a systematic analysis of the next positions to be explored eliminating randomness in decision-making and thus minimizing the amount of movements that the robot must make to reach them and the time required to achieve total coverage of the environment. Additionally, a series of tests carried out on the proposed method are presented, and the results obtained in classical variables such as time and distance allow to validate the efficiency of our approach.

1. Introduction

Path planning is a well-known topic in the area of robotics whose main objective is to determine the best way for a robot to navigate autonomously in a work environment. Although many areas of robotics have benefited from research in this field, one of the most recent is its application to the problem of autonomous construction of environment maps, also known as integrated exploration or active SLAM, where the basic principle of operation consists of a mobile robot that must move through an unknown environment while constructing an environment map of it.

In this context, one of the first contributions can be traced to the work of Feder et al. [1], in which the authors describe an adaptive trajectory planning technique applied to the SLAM problem, where through the minimization of the inverse of the error covariance as an objective function, the next position is determined where the robot must move with the intention of maximizing the information obtained, while it simultaneously localizes and constructs the environment map.

Commonly, the development of SLAM path planners requires dynamic and agile algorithms that can be adapted to new operating conditions in environments when obstacles are detected; with this in mind, many proposals have been developed by various researchers [2, 3, 4, 5, 6, 7, 8, 9, 10], being one of the most popular the sensor-based random tree (SRT) presented by Oriolo, Freda, and Franchi in [11]. This method is based on the random generation of robot configurations within a local security area detected by the robot’s sensors, from which a compact tree-type data structure is constructed, which represents the road map of the area explored. In this structure, the leaves represent a previously reached robot position and their respective representation of the environment segment detected by the onboard sensors in that position called local safety region (LSR).

The SRT method randomly selects free borders detected at the current position of the robot where he can continue the exploration task; in case it is not possible to find one, the robot will automatically go to its parent node to look for new areas with exploration possibility. The process ends when the backspace behavior leads the robot to the root of the tree.

However, despite the popularity of the SRT scheme, it has certain problems that should be considered. The first of them lies in the ignorance of the state of the structure that is being built, where it is not possible to know if the nodes of the structure left behind contain more areas available for exploration, and therefore the total coverage of the environment cannot be guaranteed. The second problem depends on the first one, since not knowing which areas of the environment you remain unexplored, it is necessary for the robot to go back to parent nodes to find out if it is possible to continue exploring, which causes the structure to be traveled twice, and consequently the exploration time is very high.

From the above, a new method based on the SRT is developed by Franchi and others [4] for the multirobot case known as the sensor-based random graph (SRG). This method transforms the tree structure generated by the SRT method into an exploration network when the robot finds a safe way to travel between two nodes. In this method, a probability proportional to the length of the arc of the free edges that are in the node in which the robot is located is used to determine which will be the next position to explore; in addition, the way to verify the structure to establish the way to revisit zones already explored to continue the exploration is carried out by means of the generation of a tree of minimum expansion with all the adjacent nodes of the network, choosing that of the adjacent node with the greater weight with respect to the length of the free limits of the frontiers.

The SRG method presents similar problems to those of the SRT method: although the data structure is transformed into an exploration graph, the structure is not fully exploited to make exploration more efficient, because the way of revisiting nodes to verify unexplored areas creates a tree structure, which generates a discontinuous path that forces the robot to go through the parent nodes, ignoring the versatility of the graph. In fact, if the number of adjacent nodes and the number of nodes that conforms the environment are too large, the time to complete the exploration is increased. Also, like the SRT method, the robot decides the next position to explore without considering that the randomness of the selection causes too many orientation changes, which directly affects the odometric system.

More recently, Toriz et al. [12] presented a new approach known as the random exploration graph (REG), which optimizes map coverage in the exploration process. This method is based on the working principle of the SRT method and adapts it to build an exploration graph structure. Although this method has a probabilistic nature that can cause an excess of movements in the robot to complete its task and increase the exploration time, one of its main advantages is the accumulation of knowledge acquired through the concept of border control, which stores information about areas that the robot left behind in the exploration process and that needs to be revisited to complete the exploration. This feature, plus the generated graph structure, allows an optimal return to unexplored areas to complete the exploration.

As it can be observed, the methods presented here maintain a random character to define the next position to explore, the problems found in these algorithms are the excess of time required to complete the task, and in some cases the uncertainty on the total coverage of the exploration area, which can have repercussions on partially constructed or low-quality maps, the reason why an integrated exploration strategy created from these methods would not be viable.

Thus, this work presents an approach to the problem of path planning of unknown environments based on the basic principles of the REG method; however, unlike this method, our proposal eliminates the randomness of the choice of the next frontiers to explore and, instead, relies on an analysis of the best frontier whose choice criterion is based on minimizing the amount of movements the robot has to make to reach it and maximizing the amount of information from the environment that will be acquired.

2. Extended random exploration graph

The exploration strategy presented in this research is a modified version of the REG algorithm, where the main difference lies in the way in which the robot will plan the exploration trajectory by performing a deterministic analysis of the next position to be explored; the algorithm is shown in Figure 1.

Figure 1.

Extended REG algorithm.

The initial node considered in the algorithm will be the starting and finishing node, and as in the rest of the exploration structure, it will contain a position reached by the robot (in this case it will be the initial q_init position), as well as a representation of the environment surrounding it known as the local security region (LSR) where the robot will be able to navigate without the risk of colliding with any obstacle. With this node created, the cycle controls the exploration process.

Next, in each iteration k of the algorithm, the frontiers of the nodes adjacent to the current node are evaluated with the intention of verifying which free frontier segments with possibility of exploration of these are of the current LSR. The nodes that present positive intersections in this evaluation will be updated eliminating the free frontier segments of both the neighboring node and the current node, with the intention of not considering these frontiers in a possible return of the robot to continue with the exploration. In addition, the verification of intersections between nodes is used to modify the structure of the exploration graph by adding edges between nonadjacent nodes as long as there are safe roads to travel between them (see Figure 2). The described analysis is performed by the function CURR_INTERSECTION.

Figure 2.

Modification of the exploration graph structure through the insertion of new edges between nonadjacent nodes. (a) The insertion of the edge between q_i-1 and q_i + 1 nodes is not possible (dotted red line) since there is no safe path between the nodes. (b) The insertion of the edge between the q_i-1 and q_i + 1 nodes is not possible (dotted red line) since, although there is a collision-free path between the nodes, the intersection of the LSRs does not have enough space to navigate safely between the nodes. (c) The insertion of the edge between the q_i-1 and q_i + 1 nodes is possible (dotted green line) since there is a collision-free path and enough space at the intersection of the LSRs to navigate safely.

After the analysis of the frontiers of neighboring nodes covered by the new LSR and the modification of the exploration structure with new edges, the next step is to identify the remaining free frontiers F of the current position, which is performed by the FRONTIERS function. For each of the frontiers found, if they exist, an approximation point will be determined, which will serve to prioritize the free frontiers, ranking them according to the effort required to reach them (FRONT_DET function) and choosing a new frontier to explore which has the highest hierarchy.

The approximation point is defined as the midpoint of the arc segment formed by the frontiers, if they can be covered in their entirety by the threshold defined by the LSR area (see Figure 3).

Figure 3.

Hierarchy of frontiers.

In the case that the criterion of choice of approximation point is not met, it will be redefined by taking the midpoint of the arc length proportional to the area that can be covered by the LSR, taken from the initial end of the border. With this new point chosen to continue the exploration, the frontier or segment of it, as the case may be, is removed from the group of free borders found by the REMOVE function (see Figure 4).

Figure 4.

Criterion of approximation to the new frontier to explore. (a) The robot makes an incorrect approach to the new frontier, since the new LSR of the chosen position leaves two free frontiers in opposite directions. (b) Correct choice of the next position to explore, since, although the new RSL is unable to cover the border completely, no more than one free border is left.

With the new frontier to explore chosen and the approximation point of it defined, the DISPLACE function will obtain the new q_dest position to visit to continue the exploration. This is done by taking a step of dimension α * r in the direction of the border approximation point, where the parameter α represents the defined radius of the LSR and the value r < 1 will guarantee that the new position will remain within it. Once the q_dest position is obtained, the MOVE_TO function will plan the path and take the robot to this new position.

In the q_dest position, the robot will calculate the surrounding space S_dest of this position (PERCEPTION function) and the VERIFIES function will determine precisely which is the real portion of the free frontier that was covered by this new LSR. In case the chosen frontier has not been fully covered, the remaining portion will be added to the list of free frontiers F of the previous node. Thus, if the F list of the node is not empty, its header will be added to the list of nodes with exploration possibility, also known as frontier control (see Figure 5).

Figure 5.

Frontier control. (a) Environment almost explored, where the arcs F_i and q_j represent unexplored free frontiers. (b) List of nodes not fully explored (frontiers control).

After verification and validation of the structure with the new node, the ADD function will attach it to the exploration graph, and the objects on the map being constructed will be extended with the new information collected. At this point, the destination information (q_dest and S_dest) obtained at the previous point will become the current node information (q_curr and S_curr), and the described process will start again.

When the robot fails to find a new position to explore in the current node, i.e., there are no more free frontiers, one of the nodes contained in the frontier control will be chosen to continue the exploration, where the choice of it will be determined by the A* search algorithm in bidirectional way, where a path will extend from the current node to the frontier control nodes and from the nodes in the frontier control to the current position, ending when some path P is found (see Figure 6). At this moment the index of the node on which the trajectory was found will be removed from frontier control. This task is carried out by the FIND_PATH function.

Figure 6.

Bidirectional application of the A* algorithm from the current position of the robot to the nodes with possibility of exploration, stored in the frontiers control.

The MOVE_TO function will then use the path P obtained in the previous step to take the robot to the node from where scanning will continue. In this way, the method will continue executing the described process, until there are no more free frontiers in the current node, and the frontier control list is empty; at this point, the robot will look for a path to return to the initial node from where the exploration process starts. Figure 7 shows the flow diagram of the extended REG algorithm.

Figure 7.

Flowchart of the extended REG method.

3. Experimental results

Numerous experiments were carried out with the intention of validating the accuracy and consistency of the proposal made in this investigation; in addition, typical quantitative variables used in the field of exploration methods were analyzed, such as exploration time, distance traveled, and total environmental coverage, which were compared with data obtained by other methods such as SRT [11], SRG [6], and REG [12], which allows us to explain the efficiency of our method.

With respect to the integrated exploration paradigm, our exploration approach was designed to operate under the general concept of any SLAM method; however, for the tests performed, it was determined to use the method presented in [13] given the integral way of exploiting data from the work environment.

The tests were conducted using simulated information from a pioneer P3DX differential robot, which was equipped with a Hokuyo URG-04LX range sensor with a maximum detection range of 4 meters, an angular resolution of 0.360°, and a scanning angle of 240°. The environment used for the experiments is a modified version of the corridors of the Montpellier Computer, Robotics and Micro-electronics laboratory (LIRMM) (see Figure 8).

Figure 8.

The LIRMM environment.

Figure 9 shows the exploration structure generated by the extended REG method after its application in the LIRMM environment; in it, the edges represent routes that the robot can navigate without the risk of colliding with obstacles in the environment.

Figure 9.

Generated graph structure by the proposed exploration approach.

Tables 1 and 2 show the comparative results of the time and distance variables traveled by the robot using the SRT, SRG, REG, and Extended REG exploration methods; the results were obtained on the basis of 30 tests. In these tables, it is easy to observe that the Extended REG requires approximately 25% less time than the best average time of the other three methods, and about 16% in the best average distance was reported by the other three methods. In addition, it is possible to observe that the standard deviation in both variables is very low compared to the other methods due to the deterministic way of choosing the next position to explore, which allows sustaining the affirmation that the method will always obtain the same results.

Table 1.

Time needed for the Extended REG, REG, SRT, and SRG exploration methods to explore the LIRMM environment on the basis of 30 tests

Table 2.

Distance traveled for the Extended REG, REG, SRT, and SRG exploration methods to cover the LIRMM environment on the basis of 30 tests

Moreover, since our proposal is based on the REG algorithm, one of the main benefits contained in the extension presented in this paper is the guarantee with a high degree of confidence that the environment will be fully covered in most cases, because it is possible to have a constant knowledge of the state of unexplored areas of the environment thanks to frontier control. Thus, to evaluate the coverage of the environment by the exploration method, this was divided into grids, which served to determine which of them had been explored (Table 3).

Table 3.

Surface covered of the LIRMM environment for the Extended REG, REG, SRT, and SRG exploration methods on the basis of 30 tests

Finally, the algorithm of path planning for unknown environments presented in this article was developed with the intention of being integrated to SLAM algorithms to obtain an integral tool for the construction of autonomous maps. Although the Extended REG method could be used as a control module with any SLAM algorithm, for the tests performed, it was decided to use the method developed by Pedraza et al. [13] given the similarity of approaches when applying the methods in unstructured environments. The tests and results obtained are shown in Figures 10 and 11.

Figure 10.

Consistency test of the Extended REG method applied to the SLAM problem.

Figure 11.

Map obtained with the Extended REG method applied to the SLAM problem.

4. Conclusions

In this work, a strategy was presented for the problem of exploration of environments for SLAM; the approach presented is based on the REG algorithm introduced in [12], which builds a graph-like data structure that integrally exploits the experience acquired during the exploration process to perform this task efficiently. The main contribution of the exploration proposal made in this article is the use of a simplified criterion to find the next position to explore based on the hierarchy of free borders detected in an instant of time, which allows the elimination of unnecessary movements of the robot, increasing its efficiency. The main advantage of this choice criterion is that the robot will travel short distances to the position closest to being explored, reducing the amount of time needed to reach them, which can be verified in the results of the tests performed to the method.

Also the Extended REG method is designed to be integrated in the context of a SLAM method, which facilitates the construction of environment maps simplifying the task of planning paths in unknown environments, which allows giving true autonomy to the robot responsible for obtaining the environment map eliminating the dependence on decision-making by a human operator. Finally, a series of simulations of the proposed integrated exploration strategy were carried out, which allowed us to validate our approach.