Sage Journals: Discover world-class research

Abstract

Autonomous exploration is a widely studied fundamental application in the field of quadrotor, which requires them to automatically explore unknown space to obtain complete information about the environment. The frontier-based method, one of the representative works on autonomous exploration, drives autonomous determination by the definition of frontier information so that complete information about the environment is available to the quadrotor. However, existing frontier-based methods are able to accomplish the task but still suffer from inefficient exploration, and how to improve the efficiency of autonomous exploration is the focus of research nowadays. Slow frontier generation affecting real-time viewpoint determination and insufficient determination methods affecting the quality of viewpoints are typical of these problems. Therefore, to overcome the aforementioned problems, this article proposes a two-level viewpoint determination method for frontier-based autonomous exploration. First, a sampling-based frontier detection method is presented for faster frontier generation, improving the immediacy of environmental representation compared to traditional traversal-based methods. Second, the access to environmental information during flight is considered for the first time, and an innovative heuristic evaluation function is designed to decide on high-quality viewpoint as the next local navigation target in each exploration iteration. Extensive benchmark and real-world tests are conducted to validate our method. The results confirm that our method optimizes the frontier search time by 85%, the exploration time by around 20%–30%, and the exploration path by 25%–35%.

Keywords

Autonomous exploration frontier search heuristic viewpoint evaluation

Introduction

In recent years, researchers have proposed various autonomous exploration methods. Frontier-based autonomous exploration methods have been widely studied for their complete coverage. Yamauchi¹ defined the frontier as the boundary between the known safe area and the unknown area. As shown in Figure 1, the frontier-based approach moves toward the frontiers and continues to explore unknown areas until complete environmental information is obtained under local perceptual constraints. The key to efficient autonomous exploration is the optimal selection of viewpoints.

Figure 1.

The connotation of the frontier-based exploration method: quadrotor continues to explore unknown areas with frontiers.

The frontier-based viewpoint decision method in autonomous exploration consists of two main steps: (1) frontier search: search for the frontier in the exploration area; (2) frontier evaluation: evaluate the frontier information and select the optimal point as the viewpoint.

Several frontier search methods have been proposed in recent years. The first such method aims to search for the frontier according to the global map.¹ Although all the frontiers in the map can be searched, this method consumes a large number of computing resources, resulting in a slow search. The second method aims to focus only on the frontier of the local map within the detection range of the sensor.² It can shrink the frontier search area and is currently the most common frontier search method. However, in the non-frontier areas of the local map, this method consumes a large amount of computing resources and limits the efficiency of autonomous exploration. The third method aims to accelerate the search through random sampling in the global map to find the frontier.³ However, the extracted frontier is incomplete, which is not conducive to decision-making and subsequent exploration.

In addition, most existing frontier evaluation methods are greedy, that is, they select the nearest frontier or the frontier with the most unknown environment as the target point. Furthermore, the two methods can be combined to build a heuristic function and select the optimal frontier.⁴ However, these frontier methods do not consider the environmental gain during flight, which accounts for 90% of the time in the exploration process, resulting in repeated explorations and low autonomous exploration efficiency.

Motivated by the aforementioned factors, this article proposes an efficient heuristic autonomous exploration method by considering the environmental gain during flight. First, an efficient two-level frontier search method is proposed, which uses random sampling to search for the frontier seed points and expands them into clusters. Then, the observation points (both position and yaw) for each cluster are identified. Finally, a heuristic frontier evaluation function containing the environmental gain cost term is proposed, which allows the quadrotor to obtain more environmental information during flight.

Our approach optimizes the frontier search speed so that the viewpoints can be determined accurately by reflecting the environment in more real time. Besides, the information gain during flight gets attention to improve the overall exploration speed and path length. Our main contributions are as follows:

An efficient frontier search method is proposed, which randomly samples the frontier seed points and extracts complete frontier information.

A viewpoint evaluation heuristic function is designed to select the best viewpoint which considers the environmental information gain during flight.

A yaw angle planning method which is more suitable for autonomous exploration was focused and designed for the first time to obtain more environmental information gain during flight.

Related work

Autonomous exploration is the key technology of unmanned systems. It aims to drive a quadrotor to map an unknown environment and obtain environmental information using its own sensors, which can be used to inspect civil infrastructure⁵ or to search for people or objects, for example, in search-and-rescue scenarios.⁶ No matter what the application scenario is, the purpose of autonomous exploration is generally summarized into two categories: some focus on how to reconstruct objects more accurately, such as environment maps or various buildings, while others pursue faster efficiency to finish the coverage of the exploration space. And this article belongs to the latter, which studies how to complete the exploration mission of unknown environments faster, thereby obtaining complete environmental information as quickly as possible.

Stachniss⁷ classified autonomous exploration strategies into sampling-based autonomous exploration and frontier-based autonomous exploration. Sampling-based exploration randomly generates a set of viewpoints to explore the given space. However, this approach is excessively reliant on the quality of the random viewpoints, resulting in low exploration coverage and a long exploration time. Consequently, frontier-based exploration has been widely studied owing to its higher exploration efficiency. The essence of frontier-based exploration is frontier search, which can be divided into two stages: frontier detection and frontier evaluation.

Frontier detection

Yamauchi¹ defined the frontier as the boundary between the free area and the unknown areas on the map, where the closest frontier is always set as the exploration target. The initial frontier search method aims to find the frontiers from the global map. Although it can obtain comprehensive frontier information, it requires a long search time when exploring large-scale maps. To reduce the frontier search time, researchers have proposed various methods. Dai et al.⁸ used the easy-to-expand and easy-to-search features of the octree to build task maps to reduce the search time. Zhang et al.² delimited local maps based on the sensor detection range, thereby reducing the forward search time significantly. To reduce repeated calculations in front search, Tang et al.⁴ used a wavefront algorithm that searches for the front within the scope of the local map and labeled each cell to improve the performance of the front search.

Although the aforementioned methods reduce the time consumed by the frontier search, they require a long time to detect cells in non-frontier areas (other areas apart from the frontier). To address this problem, Zhong et al.³ randomly scattered some points on the global map and then gathered the points that meet the frontier conditions into a cluster. Although this method reduces the consumption of computing resources in non-frontier areas, such a frontier search is not comprehensive and cannot carry sufficient information, resulting in few frontiers in complex environments. Therefore, Zhong et al.³ and Tang et al.⁴ proposed a more efficient frontier search method. It drastically reduces the frontier search time and allows quadrotor to explore the environment at a higher speed so as to improve autonomous exploration efficiency.

Viewpoint evaluation

Researchers have also conducted numerous studies on frontier evaluation. First, Yamauchi¹ proposed direct selection of the nearest frontier of the quadrotor as the navigation point. Although this method is simple and the calculation time is short, it involves a many repeated explorations, which reduces the exploration efficiency. Cieslewski et al.⁹ proposed a frontier selection method that prioritizes the selection of a frontier consistent with the motion direction of the quadrotor as the next viewpoint. Alexis^10
–12 further extended the strategy by considering location uncertainties, the importance of exploring different objects, and inspection tasks, then evaluated the sampling viewpoints. Dharmadhikari et al.¹³ considered the dynamic constraints in frontier evaluation. Zhang et al.³ adopted the same method; however, when there are no frontiers on the local map, it will go back to the previous viewpoint and continue to search for the frontier. Although this method can drastically reduce the energy consumption of the quadrotor, it will cause many repeated explorations. Gonzalez-Banos and Latombe¹⁴ used cost functions to calculate the minimum cost of each frontier and selected the cost function with the smallest value as the next optimal viewpoint. Deng et al.¹⁵ proposed various environmental frontier-based information gain methods that calculate information gains and select exploration paths through map optimization. However, the information gain calculation involves massive memory consumption and high computational complexity. Zhou et al.¹⁶ constructed a global frontier traverse sequence by the distance between frontiers.

The aforementioned methods only consider the environmental gain near the viewpoint of the candidate; however, autonomous exploration is a motion process. Therefore, the environmental gain that can be obtained by the quadrotor during flight is crucial. Accordingly, this study improves on the previous method¹⁶ by proposing a simple and efficient expression of the environmental gain during flight and employs a heuristic function to select the best viewpoints.

Yaw planning

Yaw planning, whether it is in autonomous flight for the purpose of obstacle avoidance or in autonomous exploration, does not seem to be the focus of research. For example, after generating a trajectory, the classic local planner¹⁷ simply uses the tangent direction of the trajectory as the corresponding yaw so that quadrotor with the limited field of view (FoV) can fly safely. Besides, Zhou et al.¹⁶ proposed a more complex yaw angle generation method and employed it in autonomous exploration. After obtaining the trajectory and the yaw of the target point, it performs discrete sampling at the same interval and uses a gradient-based optimization method to generate the yaw at each sampling time during trajectory. This yaw planning method only ensures flight safety while making the change of the quadrotor’s yaw smoother and is not helpful for obtaining environmental information during flight. Therefore, this article will focus on this usually overlooked detail, hoping to obtain environmental information more efficiently in autonomous exploration through more scientific yaw planning.

System overview

This article proposes a frontier-based autonomous exploration method that focuses on the viewpoint decision, which can drastically reduce the frontier search time and accelerate the exploration. This method involves two parts. The first part is the frontier detection module that randomly samples candidate points in the local map using the rapidly-exploring random tree (RRT) algorithm and obtains all the frontiers using the wavefront algorithm. It significantly reduces the search time and improves the information processing speed of unmanned systems. After all the frontier clusters are obtained and the viewpoints for each cluster are generated, the viewpoints are evaluated using a heuristic function to generate the best viewpoint as the next target. The heuristic function is constructed by combining the cost of the environmental gain during flight, energy cost, and distance cost. The path to the next target is generated when the best viewpoint is decided. Furthermore, a simple and efficient yaw planning method is proposed to optimize the ability of the quadrotor to obtain as much environmental information as possible on the way to the best viewpoint. Repeat the above process, when there is no frontier in the exploration space required in advance, it means that the exploration is finished. An overview of our method is shown in Figure 2.

Figure 2.

Overview of our method.

Frontier detection

Frontier seed sampling

The 3D grid map is used as the basis of the method, which is a simple volumetric 3D representation of the environment V. Each cube of the grid map is called a voxel (cell) v, which may be $f r e e$ , $o c c u p i e d$ , or $u n k n o w n$ . The free voxels form the free space $V_{f r e e} \subset V$ , the occupied voxels form the occupied space $V_{o c c} \subset V$ , and the unknown voxels form the unknown space $V_{u n} \subset V$ . The entire space is a union of the three subspaces $V \equiv V_{f r e e} \cup V_{o c c} \cup V_{u n}$ . The grid map composed of voxel cells is continuously updated and maintained at a certain frequency through historical depth information collected by sensors. The aim is to fast generate frontier information based on the 3D grid map to drive exploration. The frontier, as mentioned before, is the special voxel cell that is located between the free cell and the unknown cell. Therefore, the frontiers need to be continuously updated fast enough as the grid map changes, which is the basis for frontier-based autonomous exploration.

To reduce the frontier search time, the computational consumption in non-frontier areas must be reduced. Unlike most methods that generate frontier points one-by-one through loop traversal and check, this article simplifies the frontier search into frontier seed point detection, that is, the detection of any point in the frontier area.

Inspired by RRT-like sampling-based algorithm, this study employed the similar random sampling method to improve the frontier seed detection efficiency. Initially, a local map is built according to the sensor information of each frame, and the number of random points is then set according to the size of the local map. After the random points $p_{1}, p_{2}, …, p_{M}$ are scattered, they are retrieved to find the frontier seed that meets the frontier conditions and add the seed to the frontier seed point list. The number of the seed points M is carefully set according to the size of local map and the online computing capability. For stability of performance, M is often set to 1/5–1/10 of the number of voxels in the local map. The specific steps are as follows:

Build a local grid map according to the FoV of sensor, set the number of scattered points according to their size, and randomly scatter the points, set as $p_{1}, p_{2}, …, p_{M}$ .

Traverse each random point.

Define the points that meet the frontier conditions as frontier seeds $p_{s, 1}, p_{s, 2}, …, p_{s, n}$ and store them in the frontier seed list.

A schematic diagram is shown in Figure 3 (for convenience of description, it is represented by a 2D map).

Figure 3.

Frontier seed generation. Frontier seeds will be sampled in the local map under FoV, and the historical frontiers (blue and green area) will be maintained if they are not observed).

Frontier expansion and clustering

After the list of frontier seeds is obtained, the wavefront algorithm⁴ is employed to expand it and generate clusters. The specific steps are as follows:

First, extract the point from the frontier seed list and add it to the expand list.

Then, traverse the point in the expand list, get its 26 neighbor 3D grids and the number of 26 is calculated by 3(X-axis) * 3(Y-axis) * 3(Z-axis) − 1(itself). Then it will be deleted from the expand list.

Check its neighbor points. If there are points that meet the frontier conditions, they will be added to the expand list; otherwise, they will be added to the checked list to prevent duplicate detection.

Repeat steps (2) and (3) until the expand list is empty; then, the complete frontier area corresponding to the frontier seed is obtained.

Finally, the frontiers will be divided into clusters by obstacles.

A schematic diagram is shown in Figure 4.

Figure 4.

Frontier expansion and clustering.

Results

Using a computer (Intel i7 8th), the proposed frontier detection method is compared with the traditional frontier search method,¹ which detects the potential frontiers in global range, and an incremental frontier construction classical method called FUEL,¹⁶ which loops and finds the frontiers in local range on maps with different sizes. The comparison results are presented in Table 1 and Figure 5. The exploration area is calculated by the number of known and occupied cell voxels with the uniform sizes. And the frontier search time is the cumulative sum of each time.

Table 1.

Frontier search time comparison.

Exploration area (m³)	Frontier Search Time (s)
Exploration area (m³)	Traditional¹	FUEL¹⁶	Ours
96	0.008	0.0040	0.0004
150	0.009	0.0089	0.0002
200	0.011	0.0076	0.0017
400	0.014	0.0110	0.0028
1000	0.022	0.0075	0.0016
3500	0.35	0.0091	0.0024

Figure 5.

Frontier detection comparison results in simulations. The stars are an example of the comparison of the search time of the two methods under the same exploration area.

From the aforementioned results, it is clear that our method and FUEL¹⁶ require less time for the frontier search, which does not increase with the exploration area in contrast to the traditional method that traverses the global map to search for frontiers. The reason why the traditional method is not effective is that it finds in the global range every time, causing unnecessary repeated frontier search.

Although FUEL¹⁶ only traverses the local map, it involves many unnecessary calculations. The pentagram shown in Figure 5 represents the average frontier search time in this completely autonomous exploration mission. As can be seen from Table 1, the proposed frontier detection method is 85% faster than FUEL.¹⁶

Heuristic viewpoint evaluation

After multiple frontier clusters have been searched, the final best viewpoint will be decided as the next local target by further evaluation.

The autonomous exploration method based on a heuristic function is adopted in this study. It uses the yaw change of quadrotor to represent the environmental information gain during flight. The heuristic function is constructed by combining the cost of the environmental gain during flight, the energy cost, and the distance cost to select the best viewpoint. Through the rational selection of the best viewpoint, the quadrotor can obtain more environmental information in the same time and improve the autonomous exploration efficiency.

Heuristic function design

Environmental information refers to the size of the map as well as its structure. The environmental information gain can be interpreted as the gain achieved by converting an unknown map into a known map within a certain period of time.

The quadrotor explores unknown spaces using their cameras to collect environmental information. However, the camera has a limit FoV, and it can only obtain a part of the environmental information during the flight of the quadrotors. Therefore, in this study, the yaw difference information is used to represent the environmental gain during flight to maximize the in-flight environmental gain with a more flexible yaw planning strategy.

Cost of environmental information gain during flight

After the frontier search is completed, multiple frontier clusters will be obtained, and the corresponding viewpoints of each frontier cluster is defined as the average point of the frontier

(x_{obv}, y_{obv}, z_{obv}) = (x_{center}, y_{center}, z_{center}) = \frac{(\sum_{i = 0}^{m} x, \sum_{i = 0}^{m} y, \sum_{i = 0}^{m} z)}{num}

where $(x_{center}, y_{center}, z_{center})$ denote the average point of a frontier; $\sum_{i = 0}^{m} x, \sum_{i = 0}^{m} y, \sum_{i = 0}^{m} z$ denote the sum of the coordinates of the frontier points; and $num$ denotes the number of frontier points in each frontier cluster.

As shown in Figure 6, the average point of each frontier cluster is selected as the viewpoint. The viewpoint contains not only the location information $(x_{obv}, y_{obv}, z_{obv})$ but also the yaw angle $θ$ . Then, according to the FoV of the camera carried by the quadrotors, the angle which can obtain the most frontier points is selected as the yaw angle of the viewpoint.

Figure 6.

Diagram for environmental information. It shows the frontier gain when the quadrotor reaches the viewpoint.

θ_{n,opt} = max {θ_{num}, θ \in (- π, π)}

where $θ_{n,opt}$ is the yaw angle of the viewpoints corresponding to each frontier cluster.

The difference value of the yaw angle is modeled as the environmental information gain during flight. In some cases, there may be multiple yaw angles where the same number of leading points can be observed. The yaw angle with the greatest difference from the current angle is selected as the yaw angle of the viewpoint, which allows the quadrotor to obtain more environmental information in the process of arriving at the viewpoint. Therefore, the environmental information gain in the flight evaluation function is expressed as follows

J_{θ} = | θ_{uav} - θ_{n, opt} |

where $λ_{θ}$ denotes the environmental gain parameter and $θ_{uav}$ is the current yaw.

Energy cost

Ignoring obstacles, the current state of the unmanned aerial vehicle (UAV) and the position of each viewpoint are taken as the initial and final state, respectively. Then, the path for the quadrotor is generated to arrive at the viewpoint. The energy consumption corresponding to the transition from the initial state to the final state is modeled as the energy cost.

Suppose that the initial state is $s_{s} = (p_{x}, p_{y}, p_{z}, v_{x}, v_{y}, v_{z})$ and that the end state is $s_{e} = (p_{e x}, p_{e y}, p_{e z}, 0, 0, 0)$ . Pontryagin’s minimal value principle is used to solve the optimal input and optimal energy loss.

The energy loss is defined as follows

J_{k} = \frac{1}{T} \int_{0}^{T} j_{k} {(t)}^{2} d t

where T represents the transition time from the initial state s_s to the final state s_e .

The state equation is expressed as follows

\dot{s} = f_{s} (s_{k}, u_{k}) = (v_{k}, a_{k}, j_{k})

where u_k is the control input and $f_{s}$ is a state transition function with arguments v_k (velocity), a_k (acceleration), and j_k (jerk).

The objective function is obtained using the minimal value principle

J =h(s(T))+ \int_{0}^{T} g (s (t), u (t)) \cdot d t

where $h (s (T))$ is the value of the cost of an end state, $g (\cdot)$ is transition cost function, and $\int_{0}^{T} g (s (t), u (t)) \cdot d t$ is the maximal value of an intermediate state.

The Hamiltonian function and the co-state function according to the objective function J are expressed as follows

H (s, u, λ) = g (s, u) + λ^{T} f (s, u)

The Hamiltonian function is used to solve the partial derivative of the state quantity $(p, v, a)$ , thereby yielding the solution of the co-state function

λ (t) = \frac{1}{T} [\begin{matrix} - 2 α \\ 2 α t + 2 β \\ - α t^{2} - 2 β t - 2 γ \end{matrix}]

where $α, β, γ$ are all constants; the co-state function $λ (t)$ values are introduced into the optimal solution and the optimal control input $u^{*} (t)$ is

u^{*} (t) = j^{*} (t) = arg min_{u (t)} H (s^{*} (t), u (t), λ (t))

The Pontryagin’s minimal value principle is usually used to solve the optimal boundary value problem, and in the text, it is innovatively used to quantify the energy cost from the current state to the next viewpoint. The integration of $j^{*} (t)$ produces the optimal cost function value as the energy cost

J_{cos t} = \int_{0}^{T} j^{*} (t) d t

The energy cost, which is freshly used in viewpoint determination, acts more as a tie breaker to avoid cyclic back and forth movement of the UAV in pursuit of larger yaw angle changes during viewpoint determination.

Distance cost

Taking the distance from the quadrotors to the viewpoint as an element of the evaluation function in the exploration process can enable the quadrotors to preferentially explore the nearby frontier in the exploration process. This study uses the Euclidean distance to define the distance of the quadrotor to the viewpoint

J_{dis} = \sqrt{Δ x^{2} + Δ y^{2} + Δ z^{2}}

where $λ_{d i s}$ denotes the distance gain parameter, and $\sqrt{Δ x^{2} + Δ y^{2} + Δ z^{2}}$ is the Euclidean distance for the quadrotor to reach its frontier position.

Heuristic function

The heuristic function consists of the distance cost, the energy cost, and the cost of the environmental information gain during flight based on the yaw difference. The formula is expressed as follows

eva_fuc = λ_{dis} / J_{dis} + λ_{cos t} / J_{cos t} + λ_{θ} \cdot J_{θ}

Calculate the heuristic function value of all the viewpoints and select the viewpoint with the largest gain as the best viewpoint.

By the performance of simulations and real-world tests in next section, the exploration flights will become more aggressive when increasing $λ_{θ}$ appropriately and more smooth when boosting the weight of energy and distance cost.

Yaw planning

After determining the best viewpoint, as shown in Figure 2, the hybrid A* algorithm¹⁸ is used to generate the path so that the UAV can safely reach the best viewpoint. Benefiting from the differentially flat of quadrotors, the yaw can be planned separately from the path. To better obtain the environmental information gain from the change in the yaw angle during the process of reaching the target, this article proposes a simplified, flexible, and efficient yaw planning method.

The initial yaw is the current state of the quadrotor ${yaw}_{s}$ . The yaw of the target is ${yaw}_{e}$ , and the yaw difference $Δ yaw$ is expressed as follows

Δ yaw = {yaw}_{e} - {yaw}_{s}

To obtain the most environmental information in the process of navigating to the viewpoint, the planning yaw ${yaw}_{plan}$ must set to the maximum

{yaw}_{plan} = {\begin{matrix} Δ yaw & abs | Δ yaw | > abs | 2 π - Δ yaw | \\ 2 π - Δ yaw & abs | Δ yaw | < abs | 2 π - Δ yaw | \end{matrix}

Then, the yaw $d_{yaw}$ corresponding to each time on the trajectory is calculated according to the total time $t_{all}$ and the sampling time t_s of the planning path

d_{yaw} = {yaw}_{s} + {yaw}_{plan} \cdot \frac{t_{s}}{t_{all}}

The total time $t_{all}$ is the total time of the path generated by hybrid A*, and the sampling time t_s is generally set to 0.1s to guarantee the smooth yaw angle transformation. Therefore, the yaw that can obtain more environmental gain during flight is generated, and $d_{yaw}$ is the ideal yaw angle corresponding to each sampling time during path execution. The yaw planning method is shown in Figure 7.

Figure 7.

Yaw planning method.

Experiments and results

Simulations

An office scenario and a large building floor scenario were considered to validate our method through simulations by comparing it with FUEL¹⁶ and the rapid frontier method.⁹

In all the tests, the dynamic limits were set as $V_{max}$ = 2.0 m/s and $ξ_{max}$ = 0.9 rad/s for all the methods. The FoVs of the sensors were set as [80×60] deg with a maximum range of 4.5 m. In both the scenarios, each method was run 10 times with the same initial configuration. Exploration time and path length are recorded to quantitatively compare the performance of both methods. The coverage within the time, which is calculated based on the cumulative volume of $f r e e$ and $o c c u p i e d$ voxels, is also recorded by curves to shown the change during exploration presented in Figure 9.

Office environment: First, the three methods are compared in a space with a size of 20 × 30 × 1.5 m³, as shown in Figure 8. The fastest exploration progress of each method in all the tests and the corresponding statistics are summarized in Table 2, which indicates that our method achieves a much shorter exploration time with a smaller time variance. As can be seen, the overall exploration path of our method is significantly shorter.

Large building floor: The methods are also compared quantitatively in a large building floor environment as shown in Figure 8. The size of the explored space was 50 × 70 × 1.5 m³. The resulting statistics and exploration progress are presented in Table 2.

Figure 8.

Benchmark comparison of the proposed method (red), rapid frontier method⁹ (blue), and FUEL¹⁶ (black) in simulations: (a) office and (b) building floor.

Figure 9.

Exploration progress of three methods: (a) office and (b) building floor.

Table 2.

Comparison of exploration results of three methods.

		Explorationtime(s)			Exploration path length(m)
Scene		Ave	Max	Min	Ave	Max	Min
Office	FUEL	176	177	173	221	229	216
	Rapid	178	185	172	249	275	229
	Ours	149	150	148	183	186	181
Building floor	FUEL	675	679	670	1006	1009	990
	Rapid	975	984	965	1501	1551	1453
	Ours	607	621	594	914	923	905

The simulations show that the proposed method optimizes the frontier detection time by 85%, the exploration time by around 30%, and the exploration path by about 66%.

Real-world exploration tests

To further validate the applicability of our method, extensive real-world experiments are conducted in an indoor maze scenario and an outdoor forest scenario using our method and FUEL.¹⁶

To verify the stability of our method, each group of real-world comparison experiments were conducted five times at almost the same time (exclude some accidental factors, such as the influence of light and temperature on the hardware) with the same configuration. In all the field experiments, a self-developed quadrotor platform (Figure 10) is used to complete the autonomous exploration mission. The quadrotor employs a visual-inertial state estimator¹⁹ to estimate the pose of the quadrotor. In addition, a minimum snap controller²⁰ was employed to track the desired trajectories.

Figure 10.

Quadrotor platform in the experiments.

All the modules (decision-making, motion planning, state estimation, and control) were run online using Manifold-2C on an Intel i7-8550U processor with 8 GB RAM and 256 GB SSD. In all the tests, the dynamic limits are set as $V_{max}$ = 1.0 m/s, $a_{max}$ = 0.8 m/s², and $ξ_{max}$ = 0.9 rad/s.

Indoor maze

An experiment was carried out many times in a crowded and cluttered indoor maze (Figure 11) with a size of 12 × 8 × 1.5 m³, and the best performance of each method is recorded for comparison.

Figure 11.

Indoor maze.

As can be seen from Figure 12, in the small, cluttered, and challenging indoor scene, owing to the effective use of the environmental gain during flight, our method can significantly reduce the exploration time and path length.

Figure 12.

Performance of two methods in indoor maze: (a) our method (red line is the exploration path) and (b) FUEL¹⁶ (blue line is the exploration path).

Outdoor forest

As shown in Figure 13, a complex outdoor forest with a size of 20 × 16 × 1.5 m³ was chosen to further validate the effectiveness of our method in large scenarios.

Figure 13.

Outdoor forest.

It is challenging for quadrotors to achieve an autonomous exploration mission in a dense forest. It involves critical requirements for the visual–inertial state estimator as well as for the controller. As shown in Table 3, the effect of our proposed method can consistently outperform the state-of-art frontier-based method in the typical indoor–outdoor environment faced by the autonomous exploration task.

Table 3.

Comparison of real-world tests.

		Exploration Time (s)			Exploration path length (m)
Scene		Ave	Max	Min	Ave	Max	Min
Indoor maze	FUEL	34.45	41.08	30.24	28.09	34.54	25.65
Indoor maze	Ours	28.30	32.27	25.81	23.29	27.90	22.35
Outdoor forest	FUEL	113.30	132.38	104.72	110.59	135.73	103.17
Outdoor forest	Ours	96.15	116.04	89.66	91.67	113.91	88.52

As shown in Figure 14, our approach can explore unknown environments and obtaining complete environmental information with less time and paths. The results show that our method can improve the exploring efficiency by about 20% compared to the state-of-art frontier-based method. The details of the experiments can be found at https://youtu.be/fzqtmecK31k.

Figure 14.

Performance of two methods in outdoor forest: (a) our method (red line is the exploration path) and (b) FUEL¹⁶ (blue line is the exploration path).

Conclusion

Although existing frontier-based autonomous exploration methods are efficient, they suffer from slow frontier search and ignore the role of the flight process in viewpoint determination.

To address the aforementioned problems, a more efficient two-level viewpoint determination method is proposed, which includes frontier detection and viewpoint evaluation. A sample-based frontier search method was presented to accelerate the detection of the environment. In addition, a heuristic evaluation function, which involves a fresh cost of the environmental gain during flight, was designed to select the next best viewpoint.

The rapid frontier search method obtains accurate perception of the local environment and facilitates efficient decision-making for subsequent viewpoints. Considering the environmental gain during flight, the selection of the best viewpoints and yaw planning strategies is optimized to improve the efficiency of the environmental information acquisition, resulting in a significant reduction in the exploration time and path length.

Comparative experiments conducted in different exploration areas verified that the proposed frontier search method is approximately 85% faster than the methods presented in the studies by Yamauchi¹ and Zhou et al.¹⁶

Furthermore, both simulations and real-world tests in different scenarios confirmed that our method optimizes the exploration time by 20%–30% and the exploration path by 25%–35%.

Footnotes

Author contributions

TZ contributed to the algorithm design and writing of this article; JY contributed to the algorithm implementation and writing of this article; JL and MP contributed to the result analysis and revision of the manuscript.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received financial support for the research, author-ship, and/or publication of this article: This research was supported by National Natural Science Foundation of China (NSFC) (61603297) and Natural Science Foundation of Shaanxi Province (2023JC-YB-503) Foundation.

ORCID iD

Jiajie Yu

References

Yamauchi

. A frontier-based approach for autonomous exploration. In: Proceedings 1997 IEEE international symposium on computational intelligence in robotics and automation CIRA’97. ‘towards new computational principles for robotics and automation’, Monterey, CA, USA, 10–11 July 1997, pp. 146–151. IEEE.

Zhang

Chu

Liu

, et al. A novel informative autonomous exploration strategy with uniform sampling for quadrotors. IEEE Trans Ind Electron 2021; 69(12): 13131–13140.

Zhong

Chen

, et al. Information-driven fast marching autonomous exploration with aerial robots. IEEE Robot Autom Lett 2021; 7(2): 810–817.

Tang

Liang

, et al. Autonomous 3D exploration of indoor environment based on wavefront algorithm. In: 2020 IEEE international conference on networking, sensing and control (ICNSC), Nanjing, China, 30 October–02 November 2020, pp. 1–6. IEEE.

Greenwood

Lynch

Zekkos

. Applications of UAVs in civil infrastructure. J Infrastruct Syst 2019; 25(2): 04019002.

Shakhatreh

Sawalmeh

Al-Fuqaha

, et al. Unmanned aerial vehicles (UAVs): a survey on civil applications and key research challenges. IEEE Access 2019; 7: 48572–48634.

Stachnis

. Robotic mapping and exploration. Heidelberg: Springer Berlin Heidelberg, 2009. pp. 1–35.

Dai

Papatheodorou

Funk

, et al. Fast frontier-based information-driven autonomous exploration with an MAV. arXiv 2020, arXiv preprint arXiv:2002.04440.

Cieslewski

Kaufmann

Scaramuzza

. Rapid exploration with multi-rotors: a frontier selection method for high speed flight. In: 2017 IEEE/RSJ international conference on Intelligent Robots and Systems (IROS), Vancouver, BC, Canada, 24–28 September 2017, pp. 2135–2142. IEEE.

10.

Bircher

Kamel

Alexis

, et al. Receding horizon “Next-Best-View” planner for 3D exploration. In: 2016 IEEE international conference on robotics and automation (ICRA), Stockholm, Sweden, 16–21 May 2016, pp. 1462–1468. IEEE.

11.

Papachristos

Khattak

Alexis

. Uncertainty-aware receding horizon exploration and mapping using aerial robots. In: Vancouver: 2017 IEEE international conference on robotics and automation (ICRA), Singapore, 29 May 2017–03 June 2017, pp. 4568–4575. IEEE.

12.

Dang

Papachristos

Alexis

. Visual saliency-aware receding horizon autonomous exploration with application to aerial robotics. In: 2018 IEEE international conference on robotics and automation (ICRA), Brisbane, QLD, Australia, 21–25 May 2018, pp. 2526–2533. IEEE.

13.

Dharmadhikari

Dang

Solanka

, et al. Motion primitives-based path planning for fast and agile exploration using aerial robots. In: 2020 IEEE international conference on robotics and automation (ICRA), Paris, France, 31 May–31 August 2020, pp. 179–185. IEEE.

14.

Gonzalez-Banos

Latombe

. Navigation strategies for exploring indoor environments. Int J Rob Res 2002; 21(10): 829–848.

15.

Deng

Duan

Liu

, et al. Robotic exploration of unknown 2D environment using a frontier-based automatic-differentiable information gain measure. In: 2020 IEEE/ASME international conference on advanced intelligent mechatronics (AIM), Boston, MA, USA, 06–09 July 2020, pp. 1497–1503. IEEE.

16.

Zhou

Zhang

Chen

, et al. FUEL: fast UAV exploration using incremental frontier structure and hierarchical planning. IEEE Robot Autom Lett 2021; 6(2): 779–786.

17.

Zhou

Wang

, et al. Ego-planner: an ESDF-free gradient-based local planner for quadrotors. IEEE Robot Autom Lett 2020; 6(2): 478–485.

18.

Dolgov

Thrun

Montemerlo

, et al. Practical search techniques in path planning for autonomous driving. Ann Arbor 2008; 1001(48105): 18–80.

19.

Qin

Cao

Pan

, et al. A general optimization-based framework for global pose estimation with multiple sensors. http://arxiv.org/abs/1901.03642.2019.

20.

Mellinger

Kumar

. “Minimum snap trajectory generation and control for quadrotors” In: 2011 IEEE international conference on robotics and automation, Shanghai, China, 09–13 May 2011, pp. 2520–2525. IEEE.

A heuristic autonomous exploration method based on environmental information gain during quadrotor flight

Abstract

Keywords

Introduction

Related work

Frontier detection

Viewpoint evaluation

Yaw planning

System overview

Frontier detection

Frontier seed sampling

Frontier expansion and clustering

Results

Heuristic viewpoint evaluation

Heuristic function design

Cost of environmental information gain during flight

Energy cost

Distance cost

Heuristic function

Yaw planning

Experiments and results

Simulations

Real-world exploration tests

Conclusion

Footnotes

Author contributions

Declaration of conflicting interests

Funding

ORCID iD

References