Autonomous robotic exploration with region-biased sampling and consistent decision making

Autonomous exploration technology of mobile robots has been widely applied in various fields. Amongst the main application is active mapping [1]. Its main task is to determine the next expected movement position of the robot, and finally achieve the shortest collision-free path in the global scope to obtain the most unknown environmental information. The robotics autonomous three-dimensional reconstruction [2] has similar goals. In addition, autonomous exploration has also been applied to disaster relief [3], terrain exploration [4] and other fields. Because the environment of these tasks is unknown and changeable, the implementation process requires closely integrated excellent navigation and decision making [5‐7].

This paper mainly focuses on the autonomous exploration of active mapping tasks which aims to improve the exploration efficiency under ensuring that the robot completes environment mapping. The important measures are the length of the exploration path, the exploration time or even computing consumption. In the process of exploration, the determination of navigation targets is the most critical step, which is a complex task, including searching for frontiers and decision-making of exploration order. Afterwards, the robot performs path planning and moves. For searching, the existing methods can be divided into two categories, which are sampling-based and boundary-based. Both algorithms update entire map constantly in real time. The sampling-based method is widely used because of effectively avoiding falling into search dead areas. However, the existing methods usually global sampling and lack regional tendency due to excessive pursuit of probability completeness. This leads to a waste of computing resources and storage, which is unacceptable on low-cost hardware. For decision making, in the existing approaches, the robot preferentially navigates to the point with the smallest value of the utility function which usually considering path length, information gain, positioning accuracy and so on. However, the real-time updating of these utility function values causes the robot to frequently change navigation goals, leading to repeated exploration. In this paper, we propose a consistent decision making method to avoid the decrease of exploration efficiency caused by the indecision. In addition, we emphasize the importance of the pruning of searched frontiers, and present an efficient technical framework for autonomous exploration in unknown environments. Three main contributions are summarized as following. The structure of this paper is as follows. In “Related work”, the review of related research progress in autonomous exploration is given. To facilitate the research, “Problem formulation” carries on the mathematical modeling of the autonomous exploration problem. Then “Proposed method” proposes the detailed method of autonomous exploration. In “Simulation” and “Real-world deployment”, the simulation results and practical experiment are discussed. Finally, “Conclusion” states the conclusions and discusses the future development research direction.

At present, there have been some autonomous exploration schemes which use mobile robots to map unknown environments. Some of the works focus on exploring the space quickly [8, 9], as this paper does. Meanwhile, other methods place more emphasis on accurate reconstruction [10, 11]. The functional modules of autonomous exploration are often subdivided into simultaneous localization and mapping (SLAM), frontier points searching (Search), exploration decision making (Decision) and motion planning (Planning).

The goal of Search is to generate frontier points. the algorithms for generating frontier points mainly include boundary-based and sampling-based methods. The boundary-based search algorithm generates points to be explored by detecting the boundary, represented by Frontier Detector (WFD) [12], Fast Frontier Detector (FFD) [12], and edge detection algorithms for graphics and images. WFD is based on Breadth-First Search (BFS) and only scans known instead of unknown regions. The work in FFD uses lidar information to find the edge of the map to obtain possible forward detection points without processing the map information. Senarathne et al. [13] give proof and experimental support to these two algorithms, and further optimized them. Senarathne and Wang [14] apply the digital image processing technology of edge detection for boundary search. In each step of map update, the modified part of the map is processed, and the boundary information is managed and extracted in an incremental manner. Nevertheless, the computational complexity of image processing is still large. The sampling-based exploration algorithm is represented by the rapidly exploring random tree (RRT) and its derivative algorithms. Umari and Mukhopadhyay [15] apply RRT to search for frontier points. The main idea was to randomly sample on the map and use independently grown trees to speed up the search for frontier points. If the edge of the tree falls on the unknown area and the free area at the same time, the unknown points adjacent to the free area are the frontier points. Qiao et al. [16] change the way of storing trees to improve the exploration efficiency of narrow environments. All the above methods search globally and iteratively, without effective mechanisms to reduce storage and computing consumption. The method in [17] utilizes the semantic information of the environment as the heuristics to guide the robot exploration. However, it is premised on collecting enough data sets for training, and its generalization is poor.

After the robot obtains the frontier points, it needs Decision module to decide which point to go first. Robot usually makes decisions based on the value of the utility function. Makarenko et al. [18] pioneer the use of information entropy to represent maps, and proposed to use navigation cost, information gain, and positioning accuracy to construct utility functions. The following researchers continued to conduct in-depth research based on this. Isler et al. [2] propose a new probabilistic volume map for 3D reconstruction to quantify the visibility of voxels. The work in [5] combines the fast online re-planning function of planning based on trajectory optimization with the idea of maximizing the exploration gain in the sensor field of view to improve the decision-making speed of real-time exploration. Meng et al. [19] samples the viewpoints and used the heuristic TSP solver to calculate the visiting order of the frontier points, and visited the frontier points in turn. However, none of the above-mentioned exploration decision algorithms consider the problem of repeated exploration in real-time decision-making. The method [20] proposes a temporal memory-based RRT (TM-RRT) to make robot decisions more firm. But decision updates become slow because robots are assigned a fixed amount of time.

Some works focuses on active SLAM during exploration, which aims to improve the location accuracy and mapping quality [21, 22]. Other works improve the Planning method [23, 24] to make the planned trajectory satisfy the dynamic feasibility of robots or meet some trajectory optimization requirements. The method [25] considers the predicted actuation of a vehicle and uses nonlinear model predictive control (NMPC) to follow a generated path. As an extension of single robotic exploration, some works focus on multi-robot cooperative exploration system [26‐28], which cast their eyes on solving task allocation or communication problem. There are also some robots use different sensors [24, 29] from the using in this paper. All the above methods have contributed to the development of the field of autonomous robotic exploration, but their focus is different from that of this article. In summary, an excellent exploration often requires shorter time, low energy consumption (short paths), and low computational and memory consumption. SLAM and Planning have been widely studied, while there are few researches on the Search and Decision.

The environment is modeled using occupancy grid map \({\mathcal {M}}\) which is a metric map. The basic idea of occupancy grid Map is to represent the environment map as uniformly distributed cells. According to the state of the cells, the Occupancy Grid Map can be divided into known cells \(S_{\textrm{known}}\) and an unknown cells \(S_{\textrm{unknown}}\). Known cells are further divided into free cells \(S_{\textrm{free}}\) and occupied cells \(S_{\textrm{occupied}}\) which indicate obstacle. We represent the grid set of \({\mathcal {M}}\) as \(S={s(1),s(2),s(3)\ldots s(N)}\), and every grid stores the value of occupied probability. The occupancy probability of each grid is expressed as information entropy:where \(C=1,2,3\ldots ,\) and P(s(c)) is the occupancy probability of grid s(c) in the occupancy grid map. Then the information entropy of the area to be explored \(W={w(1), w(2), w(3)\ldots w(N)}\) can be expressed as:The higher the average entropy of the area w(i), the higher the uncertainty of the area’s information which reflects the potential increase of map information. It represents the attractiveness of the mobile robot.

Usually, The robot decides which area to explore first according to the utility function value of the frontier points. The utility function needs to consider the navigation cost \(U_N\), the information gain \(U_I\) [30] and decision-consistent cost \(U_C(i)\). The navigation cost is the expected distance for the robot to reach the frontier points. To simplify the calculation, the navigation cost can be modeled as a Euclidean distance between the current position of the robot and the position of frontiers. The information gain is the average entropy of the area W to be explored. Consistency is evaluated using the methods presented in “Decision making with consistency”. Each time the robot selects the frontier with the smallest utility value as the next target:In the exploration process, the goal is to improve the exploration efficiency of the robot as much as possible when the map entropy is reduced to the expectations. Moreover, we hope to reduce the energy consumption of the robot, which means that the total path of the robot’s walking is as small as possible:where T is the total exploration time. \(C_{{\mathcal {M}}}\) is the map entropy budget for completing the exploration and mapping.

We propose a technical framework for autonomous exploration and mapping in 2D environment. As shown in Fig. 1, the Search module randomly samples on the map constructed by the SLAM module. The searched frontier points are inputted to the Prune module which is a pre-processing before decision. The frontier points outputted by the Prune module will be used for the next Decision module. After making a decision, the robot will select the best forward frontier with the smallest value of the utility function as the target and send it to the Planning module.

After testing WFRRT exploration effectiveness in the simulation, we deploy it in a real robotic exploration system using Kobuki mobile robot. For perception, RPLidar A1 laser range scanner is used which provides range measurements of up to 6 m with a coverage area of \(360^{\circ }\). We use Gmapping [34] for SLAM module. A star [36] and TEB [35] are used as the global and local planner. Intel NUC i7 is used as Kobuki’s computing unit for processing all the modules. A personal laptop is used to monitor robot status and visualize the map by RVIZ.

We construct real-world experiments in two scenarios. One is the laboratory scene, as shown in Fig. 9. It is about \(52~\text {m}^2\) and is separated to different fields of view with cardboard boxes. The sampling area is set to \(8~\text {m}*10~\text {m}\). The whole exploration process take around 153.38 s and the Kobuki robot travels 24.49 m. The final number of nodes is 4218. Another scene is an area enclosed by fences and cube boxes in a robot experimental venue. Another scene is an area enclosed byfences and cube boxes in a robot experimental venue, as shown in Fig. 8. The area is approximately \(82~\text {m}^2\). The sampling area is set to \(15~\text {m}*20~\text {m}\). The robot’s dynamic parameters are as follows: maximum linear velocity \(0.3~\text {m}/\text {s}\), maximum linear acceleration \(0.3~\text {m}/\text {s}^2\), maximum angular velocity \(0.5~\text {rad}/\text {s}\) and maximum angular acceleration \(0.2~\text {rad}/\text {s}^2\).

To describe the experiment process in more detail, we record the video during the experiment and capture some pictures of first person view (FPV) and third person view (TPV) at some key positions, as shown in Fig. 8. Due to the larger and more spacious venue, we relax the dynamic restrictions. In this experiment, we set the maximum linear velocity of the mobile robot to \(0.5~\text {m}/\text {s}\), the maximum linear acceleration to \(1.0~\text {m}/\text {s}^2\), the maximum angular velocity to \(1.0~\text {rad}/\text {s}\), and the maximum angular acceleration to \(1.0~\text {rad}/\text {s}^2\). To adapt bigger environment, the map resolution is adjusted to 0.15. The robot move 19.22 m to complete the mapping. During this period, a total of 3594 nodes grow. The implementations of the WFRRT exploration show successful attempts in exploring unknown regions.

In this paper, we propose an autonomous robotic exploration system with region-biased sampling and consistent decision making, which is called WFRRT. The core is (1) rapidly random tree search method based on wave characteristics, which can suppress the growth of random trees in areas that have already been explored (called the safety zone in this article) to save memory and computational consumption, and (2) decision-making with allocation consistency. Consistency means that every time the robot makes a new decision on the order of exploration frontiers, it takes into account historical decision results and global optimality. It has two benefits. First, it can help the robot avoid frequent changes in direction leading to an increase in exploration time. Second, by encoding the states of robots and frontiers into the FSOTSP, the global optimality of access order can be maintained. In addition, we verify the necessity of the Prune module via experiments.

The proposed exploration method has been tested in simulation and real-world deployment. Results have shown it performs better than conventional RRT exploration and state-of-the-art TMRRT algorithms in terms of memory consumption, exploration duration and travel distance. In the future, we will conduct further research on the mathematical interpretability of the framework of autonomous exploration and motion planning. Another noteworthy aspect is that WFRRT can be extended to multi-robotic collaborative exploration systems.