∎

11institutetext: Akash Patel 22institutetext: 22email<EMAIL_ADDRESS>33institutetext: Björn Lindqvist 44institutetext: 44email:
<EMAIL_ADDRESS>55institutetext: Christoforos Kanellakis
66institutetext: 66email<EMAIL_ADDRESS>77institutetext: Ali-
akbar Agha-mohammadi 88institutetext: 88email:
<EMAIL_ADDRESS>99institutetext: George Nikolakopoulos
1010institutetext: 1010email<EMAIL_ADDRESS>1111institutetext:
1 The authors are with the Robotics and Artificial Intelligence Team,
Department of Computer, Electrical and Space Engineering, Luleå University of
Technology, Luleå SE-97187, Sweden. 1212institutetext: 2The author is with Jet
Propulsion Laboratory California Institute of Technology Pasadena, CA, 91109.

# REF: A Rapid Exploration Framework for Deploying Autonomous MAVs in Unknown
Environments

Akash Patel1 Björn Lindqvist1 Christoforos Kanellakis1 Ali-akbar Agha-
mohammadi2 George Nikolakopoulos1

(Received: / Accepted: date)

###### Abstract

Exploration and mapping of unknown environments is a fundamental task in
applications for autonomous robots. In this article, we present a complete
framework for deploying Micro Aerial Vehicles (MAVs) in autonomous exploration
missions in unknown subterranean areas. The main motive of exploration
algorithms is to depict the next best frontier for the robot such that new
ground can be covered in a fast, safe yet efficient manner. The proposed
framework uses a novel frontier selection method that also contributes to the
safe navigation of autonomous robots in obstructed areas such as subterranean
caves, mines, and urban areas. The framework presented in this work bifurcates
the exploration problem in local and global exploration. The proposed
exploration framework is also adaptable according to computational resources
available onboard the robot which means the trade-off between the speed of
exploration and the quality of the map can be made. Such capability allows the
proposed framework to be deployed in a subterranean exploration, mapping as
well as in fast search and rescue scenarios. The performance of the proposed
framework is evaluated in detailed simulation studies with comparisons made
against a high-level exploration-planning framework developed for the DARPA
Sub-T challenge as it will be presented in this article.

111The video link of this work can be found at https://youtu.be/nmN0Xy6EqLM

###### Keywords:

MAV Sub-T exploration framework DARPA Sub-T

##  1 Introduction and Background

Rapid exploration and mapping of unknown subterranean environments has become
significant interest in the field of autonomous deployment of robots. MAVs
have the potential in being a viable solution in terms of mines inspection
kanellakis2018towards , exploration and mapping lindqvist2021exploration ,
lindqvist2021compra , Patel2022fast  and inspection of infrastructures
mansouri2018cooperative  due to their high degree of freedom and fast
traversability. The applications of MAVs have also been discussed in
developing next generation rotor crafts for mars exploration in
patel2021design  and patel2021mcoax . Deploying MAVs for exploration and
mapping of dark, dusty and hostile mines and caving systems is particularly
challenging because at the beginning of the exploration process, the
environment is completely unknown for navigation. In order to map surrounding
for safe navigation in such environments, vision-only based navigation
techniques are insufficient ozaslan2017autonomous . The unstructured and rocky
environment of mines and caves is a major challenge that contribute in
uncertainty in sensor measurements agha2021nebula . In order to explore and
map such environments, the crucial requirements for autonomous navigation
problem are: a) detecting the frontiers, b) selecting the optimal frontier,
and c) safe navigation to such frontier in order to successfully build a map
of the environment. In order to safely navigate in an unknown environment, it
is crucial that the MAV is backed by a sophisticated on board autonomy for
Guidance, Navigation and Control (GNC).

Figure 1: DARPA Sub-T world : Exploration instance. (1) Rapid local
exploration behaviour (2) local exploration in very narrow as well as wide
cave-void like areas (3) Safe Next Best Frontier (NBF) in obstructed narrow
tunnels

In Figure 1 and Figure 2 exploration instances of the proposed method is shown
in different environments. The capability of the proposed method to handle
exploration of narrow passages as well as wide tall void like structures is
evident in Figure 2.

Figure 2: Exploration behaviour using the proposed framework in multiple
exploration scenarios in DARPA Sub-T virtual world

The framework introduced in this work selects optimal frontiers based on the
idea of continuing the exploration in one direction until there is no new
potential information to gain in the particular direction. Planning a safe
path to such selected frontiers is crucial when exploring a large environment.
The path planning method used in this work takes into account the safety
margin of such paths based on the size of the MAV and its ability to traverse
through the obstructed areas. The MAVs are also constrained in terms of their
limited time of flight. Therefore the proposed framework also accounts for
cost based frontier selection while evaluating next optimal area to visit. The
proposed framework also complements the idea of efficiently utilising the
resources of the vehicle by rapid yet safe navigation. This work presents a
rapid exploration framework for safe autonomous navigation of MAVs in caves.
The point cloud map of the explored virtual cave environment with the MAV’s
trajectory is presented in Figure 3.

Figure 3: MAV trajectory while exploring a wide-large cave environment using
the proposed approach

###  1.1 Related Works

In the original work of frontier based exploration yamauchi1997frontier , the
points lying at the boundary between known (free) space and unknown space are
defined as frontier points. In yamauchi1997frontier  a closest frontier from
the robots position is selected to move to such that the boundary at which
frontiers lie will also progress towards more unexplored space. The same
approach was also extended for the case of multiple robots, as presented in
yamauchi1998frontier . In holz2010evaluating  and julia2012comparison
frontier based exploration strategies are studied extensively for comparison
against different exploration approaches. A 3D Frontier Based Exploration Tool
(FBET) for aerial vehicles is presented in zhu20153d . The FBET framework uses
similar approach to yamauchi1997frontier  for frontiers generation and the
generated frontier are clustered for selection of candidate frontier goal
based on cost function that takes into account the cost of moving to such goal
point. A Stochastic Differential Equation (SDE) based exploration approach is
presented in shen2012autonomous . In the SDE based exploration strategy the
authors consider simulating expansion of system of particles with Newtonian
dynamics for evolution of SDE. In shen2012autonomous  the authors consider the
region showing significant expansion of particles as a region that would lead
the MAV to more unexplored space. In fraundorfer2012vision  A vision based
exploration-mapping problem solving technique is presented that also utilizes
MAV to navigate in unexplored areas using continuously updating frontiers.
Exploration of unknown environments are also extended to legged or ground
robots. Probabilistic Local and Global Reasoning on Information roadMaps
(PLGRIM) as presented in kim2021plgrim , discusses a hierarchical value
learning strategy for autonomous exploration of large subterranean
environments. The methodology presented in kim2021plgrim  uses a hierarchical
learning to address local and global exploration of large scale environments
while focusing on near optimal coverage plans. A Frontloaded Information Gain
Orienteering Problem (FIG-OP) based strategy is presented in peltzer2022fig
that uses topological maps to plan exploration paths in fixed time budget
exploration scenario. The method presented in peltzer2022fig  is tested with
ground robots in multi-kilometers subterranean environment targeted at time
constrained exploration missions. Separated from frontier-selection methods
are the methods with integrated exploration behavior in the path planning
problem, often based on trying to plan a path in order to maximize the
information gain, while minimizing distance travelled or similar metrics.
These planners generally fall under the Next-best-view approaches as in
pito1999solution bircher2016receding  dang2020autonomous  and have seen great
application success, but other methods in similar directions exists, such as
ERRT lindqvist2021exploration  takes into consideration also actuation effort
along with information gain in order to yield more efficiency towards
exploration of unknown and unstructured areas. Additionally, the Rapid
exploration method proposed in cieslewski2017rapid  is developed to maintain a
high MAV velocity, while exploring. Autonomous inspection of structures by
utilizing a frontier based algorithm, along with a Lazy Theta∗ path planner,
is presented in faria2019applying . Finally, an information driven frontier
exploration method for MAV, which uses a hybrid approach between control
sampling and frontier based is presented in dai2020fast . As state-of-the-art
exploration method presented in dharmadhikari2020motion  is tailored and
deployed in large-scale exploration mission both in simulations and real world
experiments. The developed planner is structured around motion primitives that
search for admissible paths, taking advantage of efficient volumetric mapping
with collision checks and future-safe path search that evaluates the variation
of speed along the path, while also maximizing the exploration gain for an
overall fast navigation scheme. Moreover, in selin2019efficient  an
exploration approach that combined frontiers with receding horizon next-best-
view planning has been proposed. The frontiers are part of the global planning
part, while the next-best-view is responsible for the local exploration part.
In xu2021autonomous  a dynamic exploration planner (DEP) for MAV exploration,
based on Probabilistic road map has been presented. The sampling nodes are
added incrementally and distributed evenly in the explored region, while the
planner uses Euclidean Signed Distance Function map to optimize and refine
local paths. The exploration scheme in brunel2021splatplanner  presented the
Permutohedral Frontier Filtering, which is based on bilateral filtering with
permutohedral lattices to extract the score-based spatial density of the
selected frontiers. Multiple studies have also incorporated visual servoing
based path planning and control architectures for mobile robots as presented
in dirik2020visual . The authors in donmez2018vision  have formulated gaussian
functions based control architecture for mobile robot that rely on mainly
visual information of surrounding. The authors have extended the work further
in donmez2020design  that uses decision trees as well as adaptive potential
area methods to achieve autonomous control of mobile robots in real life
applications. In the field of sampling based space mapping area the research
studies presented in donmez2017bi , uses bi RRT method to smooth the RRT path
using curve fitting methods. In donmez2017bi  the Ability to navigate from
start to goal position using the smooth path by curve fitting also addresses
the problem of actuation of robot if extended for MAV in future. More path
planning and control approaches have been discussed in a case study presented
by the authors in okumucs2020cloudware  discuss in detail the planning and
control of automated ground vehicles in industry.

Various planning algorithms have been developed for navigation of aerial
platforms in unknown environments, where in general they can be divided in
map-based or memory-less approaches or their combination. In ryll2019efficient
a hierarchical planning framework that combines map building from fused depth
data, as well as instantaneous depth data, both organized into separate K-D
trees has been proposed. The planner relies on a slower global planner to get
a goal location, which is evaluated using motion primitives against the K-D
trees with the lowest cost candidate primitive to be selected. In
zhang2019maximum  a motion planning method for fast navigation of autonomous
MAVs has been developed. The algorithm divides the environment modeling in two
parts: i) the deterministically visible area within the on board sensor range,
and ii) the probabilistically known area beyond the sensor range from a-priory
map. The planning method maximizes the likelihood of reaching a goal, where a
finite set of candidate trajectories are separated into groups and evaluated
for collisions. In matthies2014stereo  a navigation method for MAVs based on
disparity image processing has been proposed. More specifically, the disparity
image is used for direct collision checking, incorporating C-space expansion
of obstacles. The motion planning part verifies obstacle free trajectory,
projecting them into the disparity image and comparing their disparity values
with the C-space disparity values for collision checking. In
bucki2020rectangular  a memory-less planner that is partitioning free space in
pyramids, using direct depth image measurements has been demonstrated. The use
of spatial generation of pyramids of the free spaces, allows for labeling
obstacle free trajectories that lie inside the pyramids, while achieving fast
generation of large number of candidate trajectories and performs collision
checks. In ahmad20213d  the authors present a reactive navigation system for
MAV exploration. The developed algorithm is based on a two layered planning
architecture that leverages the global environment map for frontier generation
and local instantaneous sensor data for obstacle avoidance based on artificial
potential fields. In tordesillas2021faster  “FASTER” has been developed, an
optimization based planning approach for fast and safe motion in unknown
environments. The planner leads to high-speed navigation by allowing to plan
in known and unknown configuration space using a convex decomposition in a two
trajectory design approach, a fast and a safe trajectory. In
lindqvist2021reactive  a reactive navigation and collision avoidance scheme
for MAVs that combines a layer of obstacle detection based on 2D LiDAR with
NMPC constraints was proposed for agile local navigation. In
kanellakis2020look  a collection of sensor based heading regulation methods
have been proposed for aerial platform navigation along underground tunnel
areas. In this work the heading regulation methods using i) image centroid
calculation from either single image depth estimation, or dark area contour
extraction, or CNN for dark area extraction and ii) from processing 2D lidar
measurements have been described. In florence2018nanomap  a mapping for motion
planning architecture that queries for the minimum-uncertainty view of a point
in space, searching a set of recent depth measurements under noisy relative
pose transforms has been presented. This work enables the identification of
local 3D obstacles in the presence of significant state estimation
uncertainty, evaluating motion plans. Table 1 summarizes the SoA exploration
strategies, while highlighting the contribution of REF.

Table 1: Different exploration frameworks and their corresponding exploration-planning approach Framework | Exploration approach
---|---
yamauchi1997frontier  |  | Closest frontier based on euclidean distance and
---
navigation to selected frontier based on depth-first-search on grid
zhou2021fuel  |  | Incremental frontier structure and hierarchical planning for
---
trajectory generation to selected frontier
zhu20153d  |  | Maximize information gain based on travel cost to frontier
---
cieslewski2017rapid  |  | Selection of furthest frontier in FOV to maintain high speed flight &
---
switches to classical frontier approach when no frontiers exist in FOV
williams2020online  |  | Exploration derived from direct point cloud visibility
---
to reduce mapping computation
fraundorfer2012vision  |  | Compute for centroid of closest frontier cluster &
---
polar histogram based computation for cost to reach selected frontier
lindqvist2021exploration  |  | Sampling based RRT structure approach to
---
maximize information gain with minimizing actuation cost
dharmadhikari2020motion  |  | 3D acceleration sampling to compute collision free paths to
---
maximum volumetric gain vertices using motion primitives
dang2019graph  |  | Bifurcated Local and global exploration approach.
---
Sampling based graph for local exploration &
global re-positioning to closest
reinhart2020learning  |  | Learning based exploration derived from
---
graph based planning exploration planning architecture.
| [REF]
---
| Safe frontier generation for local and global exploration &
---
local frontier selection based on heading and avoidance cost &
heading regulation, height difference and travel to frontier cost
based global re-positioning when local exploration gain is low

###  1.2 Contributions

The exploration, global planning and navigation architecture of this work is
part of the development efforts within the COSTAR team agha2021nebula
,nikolakopoulos2021pushing  related with the DARPA Sub-T competition subtworld
, while it is directly applicable for cave environments. Based on the above
mentioned state-of-the-art, the key contributions to this article are listed
in the following manner.

  * •

The main contribution of this work stems from the development of safe frontier
points generation and local as well as global cost based candidate frontier
point selection method. In the presented work we extend the classical and
rapid frontier exploration approaches with the improvements concerning safety
of MAVs in field as well as maintaining agile nature of exploration. The
proposed approach focuses on local frontier selection that take into account
the position of such frontier relative to any static or dynamic obstacle in
the field of view while also minimizing yaw movement of MAV. When no such
frontier exist in the local field of view, the global re-positioning of the
MAV is triggered in order to lead the MAV to global frontiers that lead the
MAV to more unexplored space. The global re-positioning method is formulated
such that it associate cost based on the overall actuation effort required by
the MAV to move to a global frontier. The proposed global re-positioning of
the MAV considers various factors such as MAV safety, actuation cost as well
as how much of the unexplored space will be seen from a potential global
frontier. Such contribution differentiate our method from other rapid frontier
exploration approaches that directly switch to classical frontier approach,
instead in our method MAV globally re-positions itself based on multi layer
cost assignment in global frontier selection. As it will be presented, such
contribution is particularly important in multi branched tunneling or caving
system exploration scenarios.

  * •

The second contribution presented in this article is the development of
overall autonomy framework which addresses the problem of exploration, safety
margin based path planning and reactive navigation through nmpc based control
of MAVs. The dedicated risk aware path planning and potential fields based
avoidance scheme incorporated within the proposed framework allows to push the
limits of exploration in the candidate goal selection process in wide, narrow
and obstructed environments. Extensive simulations are performed for
validating the proposed framework in multiple difficult scenarios in order to
benchmark the safety, speed and versatility the presented autonomy modules.

The rest of the article is structured as follows. section 2 presents the
problem formulation considered in this work. section 3 presents the proposed
safe frontier points generation as well as intelligent goal selection with the
focus on safe yet fast autonomous exploration addressing the minimizing
actuation effort of the MAV. The section also describes the overall autonomy
framework which is the combination of exploration, global path planning as
well as nmpc based reactive navigation. In section 4, detailed analysis on
simulation experiments are presented that prove the efficacy of the proposed
scheme. Finally section 5 provides a discussion with concluding remarks of the
proposed work.

##  2 Problem Formulation

The problem considered in this work is exploration of bounded 3D space denoted
as $V\subset\mathbb{R}^{3}$. Occupancy probability based modelling is adapted
in order to model free, occupied and unknown space around the robot. The
provided framework is targeted for a direct use case in field robotics where
autonomous robots are deployed in cave and mines for rapidly mapping the
areas. In the case of exploration of bounded space, the exploration will be
considered complete when $V_{occupied}\bigcup V_{free}=V$ while
$V_{unknown}=\varnothing$. In the proposed approach, exploration process is
subject to vehicle actuation effort, limitations in time of flight as well as
risk margin for safe path generation. In order to be deployed in real
scenario, the exploration and planning framework should adapt based on the
available computational resources. The performance evaluation of the proposed
framework will be based on exploration time as well as actuation efforts of
the MAV.

##  3 Proposed Approach

The proposed approach employs a frontier based exploration technique which is
modified with the focus on making exploration fast, safe and versatile based
on available computational resources. We use occupancy grid maps as a mapping
framework, which can generate a 2D or 3D probabilistic map. A value of
occupancy probability is assigned to each cell that represents a cell to be
either free or occupied in the grid. In this work we are targeting 3D
exploration of bounded and unbounded space therefore using the baseline
framework of OctoMap hornung2013octomap  we build on top of it in order to
develop the proposed 3D occupancy checking framework used in this work. Let us
denote a voxel as $v(x,y,z)$. The voxel $v$ is subdivided into eight smaller
voxels until a minimum volume is reached. The minimum volume is same as the
octree resolution $v_{res}$. Corresponding to each sensor update if a certain
volume in the octree is measured and if it is observed to be occupied, the
node containing that particular voxel is marked as occupied. Using ray casting
operation for the nodes between the occupied node and the origin (sensor), in
the line of ray, can be initialized and marked as free. This process leaves
the uninitialized nodes to be marked unknown until the next update in the
octree. Let us denote the estimated value of the probability $P(N\ |\
z_{1:t})$ of the node $N$ to be occupied for the sensor measurement $z_{1:t}$
by:

$\displaystyle
P(N|z_{1:t})=[1+\frac{1-P(N|z_{t})}{P(N|z_{t})}\frac{1-P(N|z_{1:t-1})}{P(N|z_{1:t-1})}\frac{P(n)}{1-P(n)}]^{-1}$

where $P_{n}$ is the prior probability of node $N$ to be occupied. Let us
denote the occupancy probability as for node N to be occupied as $P_{N}^{o}$

$v(x,y,z)=\begin{cases}Free,&\text{if $P^{o}<P_{n}$}\\\ Occupied,&\text{if
$P^{o}>P_{n}$}\end{cases}$

Table 2: Description of the notations used in proposed methodology Notation | Meaning
---|---
$\mathcal{\\{F\\}}$ | All frontier set
$\mathcal{\\{O\\}}$ | Occupied nodes set
$\mathcal{\\{C\\}}$ | Valid frontiers set
$\mathcal{\\{SF\\}}$ | Safe frontiers set
$\mathcal{\\{L\\}}$ | Local frontiers set
$\mathcal{\\{G\\}}$ | Global frontiers set
$R$ | Sensor measurement range
$r$ | cleaning radius
$m$ | risk margin
$v_{res}$ | octree resolution
$V_{\beta}$ | Horizontal FOV
$V_{\beta}$ | Vertical FOV
$f_{(x,y,z)}$ | Frontier position
$C_{(x,y,z)}$ | MAV current position

Let us define the sensor range $R$ and a sphere of radius $r$ around the MAV.
This radius $r$ will be denoted as cleaning radius from here after. The after
each update in current octree, if a frontier lie inside this sphere, the
frontier is marked as seen and such frontier is deleted from
$\mathcal{\\{F\\}}$. The cleaning radius is defined such that $r\ <\ R$
therefore new frontiers will always be generated at distance $R$ and as the
MAV navigate towards frontier, the frontiers lying within the sphere of radius
$r$ are deleted and less number of frontiers need to be iterated through in
candidate goal selection process. The iterator is defined as $it$. The
meanings of the important notations used in this work is presented in Table 2.

Input: $v_{res},Current\ octree,k,r$

Output: $\\{\mathcal{F}\\}$,$\\{\mathcal{O}\\}$

1 for  _$N:Current\ octree$_ do

2 if  _$P^{o}_{N} <P_{n}$_ then

3 if  _$N.distance() <r$_ then

4 $it\leftarrow 0;$

5 for  _$Neighbours:N.getNeighbour()$_ do

6 if  _$P^{o}_{N} >P_{n}$_ then

7 $it\leftarrow 0;$

8 $break;$

9 else

10 $it\leftarrow it+1$

11 if  _$it\geq k$_ then

12 $\\{\mathcal{F}\\}.add(it\\_N);$

13 else

14 $\\{\mathcal{O}\\}.add(it\\_N);$

15 for  _$N:\\{\mathcal{F}\\}$_ do

16 if  _$(N_{adj}+N_{m*v_{res}})\notin\\{\mathcal{O}\\}$_ then

17 $\\{\mathcal{SF}\\}.add(N);$

Algorithm 1 Safe Frontier Generation

The exploration framework presented in this work is is made up of three
essential modules, namely the safe frontier point generator, the cost based
frontier point selection incorporating also collision check and finally
candidate goal publisher as presented in Figure 5.

The first module takes the Lidar point cloud as input and based on the
occupancy probability formulation as mentioned earlier, converts the sensor
measurement in order to form an octree. The octree is defined as tree data
structure in which each sub node is further divided into eight quadrants until
minimum volume is reached. The safe frontier point generator module generates
all safe frontiers based on the octree as depicted in algorithm algorithm 1.
Let us define a risk margin parameter $m$ related to the voxel grid resolution
$v_{res}$. At any instance in the exploration if node $N$ being currently
checked for to be considered as a safe frontier then we also check the
neighbouring adjacent nodes defined as $N_{adj}$ within the safety margin $m$.

In our approach we formulate an additional layer of requirement in which we
check the neighbouring Voxels of an uninitialized (Unknown) Node $N$ as
described earlier and $\forall(N_{adj}+m*v_{res})$ if $(P^{o}_{N_{adj}}\leq
P_{n})$ than the Node $N$ is considered as safe frontier node and is added to
$\mathcal{\\{SF\\}}$, where $\mathcal{\\{SF\\}}$ is a set containing all safe
frontiers. This means that a particular node $N$, it’s adjacent node $N_{adj}$
as well as all nodes in the neighbourhood of node $N$ within the range of
$m*v_{res}$ are checked and if all such nodes are seen to be free than the
node $N$ is considered to be a safe frontier. To be marked as a frontier, each
node should have at least $n$ number of minimum unknown or free adjacent
nodes. This process makes a big difference in the computational complexity of
the process because by specifying a certain risk margin $m$ and minimum
unknown or free neighbours $k$ at the start of exploration, the trade off can
be made between number of iterations and coverage quality. Another improvement
our approach presents is that by not allowing any frontier to be close enough
to an occupied node in context of risk margin, we guarantee that inaccessible
frontiers can be eliminated which are generated due to the error in
probabilistic occupancy mapping. The inaccessible frontiers are defined as the
frontiers that are not safe to reach or impossible to reach in terms of MAV
size and dynamics to pass through small openings in the map. This simply
implies that risk margin can be set in correspondence with the size of the MAV
such that the inaccessible areas can be patched and modelled as occupied in
the map. The parameters $m$ as well as $k$ are proposed with the focus of
testing the proposed approach in extremely difficult areas such as caves and
mines where safety of the robot is a major concern.

Input: $\\{\mathcal{SF}\\}$ $k$, $r$, $\alpha$ $\theta$

Output: $NBF$, $\\{\mathcal{L}\\}$, $\\{\mathcal{G}\\}$

1 for  _$N:\\{\mathcal{SF}\\}$_ do

2 if  _$N.distance() <r$_ then

3 $it\leftarrow 0;$

4 for  _$Neighbours:N.getNeighbour()$_ do

5 if  _$Neighbour.isOccupied()$_ then

6 $it\leftarrow 0;$

7 $break;$

8 else

9 $it\leftarrow it+1;$

10 if  _$it <k$_ then

11 $\\{\mathcal{SF}\\}.remove(N);$

12 else

13 $\\{\mathcal{C}\\}.add(it\\_N)$

14 for  _$N:\\{\mathcal{C}\\}$_ do

15 if  _$(\alpha <(H_{\theta})/2)\ \&\ (\gamma<V_{\beta})$_ then

16 $\\{\mathcal{L}\\}.add(it\\_N)$

17 else

18 $\\{\mathcal{G}\\}.add(it\\_N)$

19 if  _$\\{\mathcal{L}\\}\neq\varnothing$_ then

20 for  _$N:\\{\mathcal{L}\\}$_ do

21
$NBF\leftarrow\operatorname*{arg\,min}\limits_{\\{N\in\\{\mathcal{L}\\}\\}}(\mathcal{E})_{local}$

22 if  _$\\{\mathcal{L}\\}=\varnothing,\\{\mathcal{G}\\}\neq\varnothing$_ then

23 for  _$N:\\{\mathcal{G}\\}$_ do

24
$NBF\leftarrow\operatorname*{arg\,min}\limits_{\\{N\in\\{\mathcal{G}\\}\\}}(\mathcal{E})_{global}$

25 if  _$\\{\mathcal{L}\\}\bigcup\\{\mathcal{G}\\}=\varnothing$_ then

26 $it\leftarrow 0;$

27 $break;$

28 $D^{*}_{+}.ComputeHomingPath()$

29 $nMPC\leftarrow HomingPath$

Algorithm 2 Frontier Classification Based on Local or Global Exploration

As defined in algorithm 2, corresponding to each new sensor measurement we
check if a $N\in\\{\mathcal{F}\\}$ is still a frontier. We define a candidate
frontier set denoted as $\\{\mathcal{C}\\}\subset\\{\mathcal{F}\\}$ which
contains all the valid frontiers which will be examined based on the MAV’s
position. A 3D Lidar is used in the proposed method to get sensor point cloud
and thus, the framework generates frontiers in all directions surrounding the
MAV but limited in the vertical directions with field of view $V_{\beta}$. In
algorithm 2, we classify the frontier nodes in two further sets
$\\{\mathcal{L}\\},\\{\mathcal{G}\\}\bigcup\\{\mathcal{C}\\}$ named as Local
and Global set respectively. Such Local and Global sets contain frontier nodes
classified based on the selected horizontal and vertical field of view
$H_{\theta}$ and $V_{\beta}$ respectively as shown in Figure 4.

This process allows us to prioritize the unknown space lying ahead of the MAV
and if there exist no unknown space ahead of the MAV, the candidate goal is
selected based on the global cost based goal assignment.

$\forall\ f\in\\{\mathcal{L}\\}$ are computed for extracting $NBF$ such that
$\alpha\in[-\pi,\pi]$ is minimum. The frontier points from occupancy
formulations are generated in the world frame ($\mathbb{W}$) but the frontier
vector $\vec{f}$ is calculated relative to the MAV body frame
$\mathbb{\\{B\\}}$. As shown in Figure 4, the angle $\alpha$ is calculated
with respect to $\mathbb{B}$. If a frontier $f$ and MAV’s current position in
inertial frame $\mathbb{W}$ is defined as $f(x,y,z)$ and $C(x,y,z)$
respectively then the angle $\alpha$ and $\gamma$ with respect to body frame
$\mathbb{B}$ can be computed as,

$\alpha=tan^{-1}(\frac{f_{y}-C_{y}}{f_{x}-C_{x}})-\psi$ (1)

$\gamma=cos^{-1}(\frac{h}{2*(f_{z}-C_{z})})$ (2)

where, $\psi$ is the heading angle of the MAV and $h$ is the vertical height
of the footprint of 3D LiDAR field of view.

Figure 4: Frontier classification and notations used in the proposed framework

As discussed previously the algorithm 1 also outputs a list of occupied nodes
$\\{\mathcal{O}\\}$ which has occupancy probability $P^{o}$ higher than 0.5
thus considering the the cluster of occupied points lying in the field of
view, the the frontier nodes having a lesser avoidance cost are also favoured
to be the $NextBestFrontier$. The cost formulation for selecting a local or
global candidate goal is as follows. If we define the current position of the
MAV as $C(x,y,z)$ then the costs for local and global frontier selection can
be formulated as,

$(\mathcal{\zeta})_{local}=\overbrace{\frac{1}{\textbf{W}_{o}\sqrt{(p^{f}_{x}-p^{obs}_{x})^{2}+(p^{f}_{y}-p^{obs}_{y})^{2}+(p^{f}_{z}-p^{obs}_{z})^{2}}}}^{\text{Avoidance
cost}}+\\\ \overbrace{\textbf{W}_{h}*\alpha}^{\text{Heading cost}}$ (3)

$\displaystyle(\mathcal{\zeta})_{global}=\overbrace{\textbf{W}_{h}*\alpha}^{\text{Heading
cost}}+\overbrace{{\textbf{W}_{z}*({f}_{z}-C_{z})}}^{\text{Height difference
cost}}+$
$\displaystyle\overbrace{\textbf{W}_{d}\sqrt{({f}_{x}-C_{x})^{2}+({f}_{y}-C_{y})^{2}+({f}_{z}-C_{z})^{2}}}^{\text{Distance
cost}}$ (4)

Where, $\textbf{W}_{o},\textbf{W}_{h},\textbf{W}_{z}$ and
$\textbf{W}_{d}\in\mathbb{R}$ are defined as weights associated to avoidance,
heading, height difference and distance cost respectively. We define the
actuation effort $\mathcal{E}$ as a function of cost such that

$\displaystyle\mathcal{E}=f(\mathcal{\zeta}+T_{hover})$

where, $T_{hover}$ is the minimum thrust required for hovering with zero
torques about the MAV arms. Thus, by optimally selecting the next pose
reference command for the MAV the actuation effort can be minimized. The MAVs
consume high energy to produce yaw torque due to the motor saturation
constraints while also keeping the MAV hovering.

Figure 5: The proposed overall autonomy and navigation scheme

The overall autonomy scheme of the proposed work is presented in Figure 5. As
discussed earlier, the framework uses 3D LiDAR or a camera depth cloud as
point cloud input and upon point cloud filtering, the framework generates an
octree of occupied, free and unknown nodes. Using the workflow described in
algorithm 1, the framework detects frontier points and classifies set of safe
frontiers. As presented in the autonomy and navigation scheme (Figure 5),
based on local or global frontier, the risk aware global planning module plans
a collision free path to the next best frontier. The $NBF$ is then fed into
the reactive navigation and control framework to actuate the MAV to navigate
to selected frontier point. In Figure 5 APF stands for Artificial Potential
Fields that we have incorporated with Nonlinear Model Predictive Control for
collision avoidance. The baseline framework for reactive navigation and
control used in this framework is inspired from our previous work
lindqvist2021compra . The Next Best Frontier is sent to a risk aware global
planning module which is the extension of $D^{*}Lite$ algorithm but
implemented with octomap framework in this case. The global planning module
$D^{*}_{+}$ uses the modelled occupied space in order to plan a safe path to
the $NBF$. The risk margin formulation in an expandable octomap grid for
global planning is presented in detail in our previous work karlsson2021d .

##  4 Exploration Mission Experiments

In order to validate and test the performance of our proposed exploration
approach we use the M100 MAV provided in the open source Rotors Simulator
Furrer2016  framework. Next-Best-view bircher2016receding  has been widely
used for bench-marking the exploration-planning algorithms. In this work we
compare our framework with the latest version of NBV, State-of-the-Art Motion
Primitive Based planner (mbplanner) dharmadhikari2020motion  which is
developed also as part of the development efforts within DARPA Sub-T
challenge. We use a custom cave model with multiple junctions, obstructed
walls, narrow openings, steep slopes as well as tunnels with dead-ends for
simulation. The cave environment has been made open sourced for public
Patel2021 . For fair comparison all simulations are performed with same
computational unit having Intel core i7 processor and 16 GB memory on ROS
Melodic running on Ubuntu 18.04. For mbplanner also the simulations are
performed using the cave virtual world where the tuning of parameters such as
MAV velocity, mapping resolution and sampling time, was similar to the ones
used for the proposed method.

Figure 6: DARPA-Sub-T virtual world: Exploration of narrow-confined passages
as well as large cave like voids using proposed framework. In (1,2,3) the
rapid exploration-coverage nature of the proposed framework is shown. In (4)
the safe way point selection and risk aware planning to safe frontier is shown

In Figure 6 different exploration instances are shown. As described in section
3 the proposed framework (REF) also uses frontier cleaning radius and due to
which coverage of large cave like voids can also be performed while exploring.
Using the proposed framework the MAV is also able to navigate in narrow and
obstructed passages and at the end of such passages if a void like area can
also be covered efficiently. The simulation experiment is also carried out to
explore a multi-branched virtual cave environment having narrow passages
continuing in different heights for a true 3D exploration. The environment is
also made open source akoval2020 . In Figure 7 the exploration of the virtual
cave environment is shown.

Figure 7: Multi-branched large 3D virtual cave world exploration using
proposed framework

In Figure 8 and Figure 9 the explored volume and distance covered by the two
exploration frameworks is presented. Figure 8 and Figure 9 depict that our
method performs significantly close to the State-of-the-Art mbplanner in terms
of exploration volume of the cave environment and distance covered
respectively. The proposed approach achieves slightly higher explored volume
for the same mission time, this is because of the novel Next Best Frontier
selection approach as adapted in section 3. As presented in Figure 12, MAV
trajectory in our approach is significantly inline with the goal of maximizing
the movement into unknown areas while limiting repeated visits to already
mapped areas. In Table 3 the exploration volume and distance travelled by the
MAV in multiple different runs with different mission duration is presented
for both planning framework. As it is evident from Table 3 that the proposed
Rapid Exploration Framework (REF) shows higher exploration volume as well as
ground covered by the MAV in multiple different runs because of the nature of
computing next paths while navigating to current path. All missions considered
in Table 3 have same start positions for both planning framework and the MAVs
do not return to base in considered cases therefore, showing the exploration
capability comparison in given time with same configuration.

Table 3: Exploration volume and distance from multiple runs | Mission
---
Duration
| Volume
---
(REF)
| Volume
---
(Mbplanner)
| Distance
---
(REF)
| Distance
---
(Mbplanner)
100 s |  3578 $m^{3}$ | 3840 $m^{3}$ | 163 $m$ |  154 $m$
300 s | 7854 $m^{3}$ |  6958 $m^{3}$ | 284 $m$ |  236 $m$
600 s | 11367 $m^{3}$ |  8438 $m^{3}$ | 670 $m$ |  476 $m$
900 s | 14477 $m^{3}$ |  9851 $m^{3}$ | 1066 $m$ |  781 $m$
1200 s | 17524 $m^{3}$ |  12760 $m^{3}$ | 1185 $m$ |  962 $m$
Figure 8: Volumetric gain by the two methods Figure 9: Distance covered by the
two methods

However, it is also important to mention that even though the $V_{unknown}$
sampling approach in both method is different, the next way points in both
case are selected with the focus on maximizing the information gain and
exploration volume in same time.

Figure 10: REF equipped MAV explores a large and wide virtual cave environment
with different mission duration and octree resolutions.

In Figure 11 the exploration mission trajectories are shown for REF and
mbplanner with same mission duration (400 s). In Figure 11 it is evident that
the MAV covers more ground in given time using the proposed framework.

Figure 11: 400 sec mission: exploration trajectories, REF vs MB Planner. The
proposed framework (REF) covers more ground in given time while avoiding loops
in one area due to the global re-positioning functionality

Figure 12: Time based exploration : MAV trajectory (a) ours : 1 minute, (b)
ours : 10 minute, (c) ours : 15 minutes, (d) mbplanner : 1 minute, (e)
mbplanner : 10 minutes, (f) mbplanner : 20 minutes

In Figure 12 in both method the overlap in trajectory is seen. This overlap is
mainly due to the lower information gain (corresponding to mbplanner) and
$\\{\mathcal{L}\\}=\varnothing$ (corresponding to our approach) resulting in
the MAV to change direction and move to other unexplored areas. In Figure 12
it is evident that using the proposed global frontier selection strategy, the
$NBF\in\\{\mathcal{G}\\}$ is selected such that the overlap in trajectory is
minimal. In Figure 10, the MAV trajectory is tracked in $XY$ while exploring
the lava tube virtual environment. The tracked trajectory is presented for
visualizing the Look-Ahead-Move-Forward nature of the proposed exploration
framework. Due to such nature of exploration, the proposed framework is able
to efficiently map new areas within given time and thus efficiently utilizing
the resource constrained MAV’s flight time. In Figure 11, Figure 11 and Figure
10 a 400 second exploration mission is performed with different voxel
resolution. In Figure 11, Figure 11 and Figure 10 the exploration is performed
with voxel resolution 0.3, 0.5 and 0.7 $m$ respectively. It is evident that
corresponding to each voxel resolution in exploration mission, the MAV takes a
different path while exploring based on the selected $NBF$ in each iteration.
All exploration missions are performed with maximum forward velocity of the
MAV as $1.5\ m/s$. In order to map the same environment even more quickly, an
exploration mission with voxel resolution 0.9 m and mission duration 900
seconds is performed and the tracked trajectory of the MAV is presented in
Figure 10.

Figure 13: Octomap of the explored area using the proposed framework Figure
14: Octomap of the explored area using the mbplanner

##  5 Conclusions

In this article we proposed a Rapid Exploration Framework for deploying
autonomous MAVs in unknown areas such as caves and mines. We present a novel
candidate goal selection method with the focus of minimizing the actuation
effort of the MAV by employing Look Forward Move Ahead approach. We compare
the exploration scenario in the same environment with the motion primitive
based planner which is a remarkable extension to Next Best View approach. In
terms of volumetric gain and distance travelled, we achieve similar results to
that of the mbplanner. We also address the trajectory overlap issue by
introducing a simple yet efficient cost based goal selection approach that
prevents the MAV to Unnecessarily travel to previously visited areas while
also keeping the look forward move ahead approach as priority. As future
development efforts we plan to conduct some field experiments to explore
abandoned mines and underground cave structures.

## Declarations

Funding: This work has been partially funded by the European Unions Horizon
2020 Research and Innovation Programme under the Grant Agreement No. 869379
illuMINEation.
Conflict of interest: The authors have no conflicts of interest with any
related parties.
Competing Interests: Not applicable
Code or data availability: ROSbags of output data from simulated experiments
can be made available at the suggestion of the reviewers and editors.
Authors’ Contributions: Akash Patel: Development, implementation and system
integration, relating to all presented submodules and developments, main
manuscript contributors. Björn Lindqvist: Control and obstacle avoidance
modules advisory. Christoforos Kanellakis: Software integration and High level
advisory. Ali-akbar Agha-mohammadi: Advisory, development lead for Team CoSTAR
in DARPA SubT Challenge. George Nikolakopoulos: Advisory, manuscript
contributions, head of Luleå University of Technology Robotics&AI Team. All
authors have read and approved the manuscript.
Ethics approval: Not applicable.
Consent to Participate: Not applicable.
Consent to Publish: All authors comply with the consent to publish.

## References

  * (1) Agha, A., Otsu, K., Morrell, B., Fan, D.D., Thakker, R., Santamaria-Navarro, A., Kim, S.K., Bouman, A., Lei, X., Edlund, J., et al.: Nebula: Quest for robotic autonomy in challenging environments; team costar at the darpa subterranean challenge.  arXiv preprint arXiv:2103.11470 (2021)
  * (2) Ahmad, S., Mills, A.B., Rush, E.R., Frew, E.W., Humbert, J.S.: 3d reactive control and frontier-based exploration for unstructured environments.  In: 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2289–2296. IEEE (2021)
  * (3) Akash, P.: Mars lava tube world.  https://github.com/LTU-RAI/MarsLavaTubeWorld.git (2021)
  * (4) Bircher, A., Kamel, M., Alexis, K., Oleynikova, H., Siegwart, R.: Receding horizon "next-best-view" planner for 3d exploration.  In: 2016 IEEE international conference on robotics and automation (ICRA), pp. 1462–1468. IEEE (2016)
  * (5) Brunel, A., Bourki, A., Demonceaux, C., Strauss, O.: Splatplanner: Efficient autonomous exploration via permutohedral frontier filtering.  In: 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 608–615. IEEE (2021)
  * (6) Bucki, N., Lee, J., Mueller, M.W.: Rectangular pyramid partitioning using integrated depth sensors (rappids): A fast planner for multicopter navigation.  IEEE Robotics and Automation Letters 5(3), 4626–4633 (2020)
  * (7) Cieslewski, T., Kaufmann, E., Scaramuzza, D.: 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), pp. 2135–2142. IEEE (2017)
  * (8) Dai, A., Papatheodorou, S., Funk, N., Tzoumanikas, D., Leutenegger, S.: Fast frontier-based information-driven autonomous exploration with an mav.  In: 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 9570–9576. IEEE (2020)
  * (9) Dang, T., Mascarich, F., Khattak, S., Nguyen, H., Nguyen, H., Hirsh, S., Reinhart, R., Papachristos, C., Alexis, K.: Autonomous search for underground mine rescue using aerial robots.  In: 2020 IEEE Aerospace Conference, pp. 1–8. IEEE (2020)
  * (10) Dang, T., Mascarich, F., Khattak, S., Papachristos, C., Alexis, K.: Graph-based path planning for autonomous robotic exploration in subterranean environments.  In: 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3105–3112. IEEE (2019)
  * (11) DARPA: DARPA Subterranean (SubT) challenge (2020).  URL https://www.darpa.mil/program/darpa-subterranean-challenge.  Accessed: February 2021
  * (12) Dharmadhikari, M., Dang, T., Solanka, L., Loje, J., Nguyen, H., Khedekar, N., Alexis, K.: Motion primitives-based path planning for fast and agile exploration using aerial robots.  In: 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 179–185. IEEE (2020)
  * (13) Dirik, M., Kocamaz, A.F., Dönmez, E.: Visual servoing based control methods for non-holonomic mobile robot.  Journal of Engineering Research 8(2) (2020)
  * (14) Dönmez, E., Kocamaz, A.F.: Design of mobile robot control infrastructure based on decision trees and adaptive potential area methods.  Iranian Journal of Science and Technology, Transactions of Electrical Engineering 44(1), 431–448 (2020)
  * (15) Dönmez, E., Kocamaz, A.F., Dirik, M.: Bi-rrt path extraction and curve fitting smooth with visual based configuration space mapping.  In: 2017 international artificial intelligence and data processing symposium (IDAP), pp. 1–5. IEEE (2017)
  * (16) Dönmez, E., Kocamaz, A.F., Dirik, M.: A vision-based real-time mobile robot controller design based on gaussian function for indoor environment.  Arabian Journal for Science and Engineering 43(12), 7127–7142 (2018)
  * (17) Faria, M., Maza, I., Viguria, A.: Applying frontier cells based exploration and lazy theta* path planning over single grid-based world representation for autonomous inspection of large 3d structures with an uas.  J. Intell. Robotic Syst. 93(1-2), 113–133 (2019)
  * (18) Florence, P.R., Carter, J., Ware, J., Tedrake, R.: Nanomap: Fast, uncertainty-aware proximity queries with lazy search over local 3d data.  In: 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7631–7638. IEEE (2018)
  * (19) Fraundorfer, F., Heng, L., Honegger, D., Lee, G.H., Meier, L., Tanskanen, P., Pollefeys, M.: Vision-based autonomous mapping and exploration using a quadrotor mav.  In: 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4557–4564. IEEE (2012)
  * (20) Furrer, F., Burri, M., Achtelik, M., Siegwart, R.: Robot Operating System (ROS): The Complete Reference (Volume 1), chap. RotorS—A Modular Gazebo MAV Simulator Framework, pp. 595–625.  Springer International Publishing, Cham (2016).  DOI 10.1007/978-3-319-26054-9_23.  URL http://dx.doi.org/10.1007/978-3-319-26054-9_23
  * (21) Holz, D., Basilico, N., Amigoni, F., Behnke, S.: Evaluating the efficiency of frontier-based exploration strategies.  In: ISR 2010 (41st International Symposium on Robotics) and ROBOTIK 2010 (6th German Conference on Robotics), pp. 1–8. VDE (2010)
  * (22) Hornung, A., Wurm, K.M., Bennewitz, M., Stachniss, C., Burgard, W.: Octomap: An efficient probabilistic 3d mapping framework based on octrees.  Autonomous robots 34(3), 189–206 (2013)
  * (23) Juliá, M., Gil, A., Reinoso, O.: A comparison of path planning strategies for autonomous exploration and mapping of unknown environments.  Autonomous Robots 33(4), 427–444 (2012)
  * (24) Kanellakis, C., Mansouri, S.S., Castaño, M., Karvelis, P., Kominiak, D., Nikolakopoulos, G.: Where to look: a collection of methods formav heading correction in underground tunnels.  IET Image Processing 14(10) (2020)
  * (25) Kanellakis, C., Mansouri, S.S., Georgoulas, G., Nikolakopoulos, G.: Towards autonomous surveying of underground mine using mavs.  In: International Conference on Robotics in Alpe-Adria Danube Region, pp. 173–180. Springer (2018)
  * (26) Karlsson, S., Koval, A., Kanellakis, C., akbar Agha-mohammadi, A., Nikolakopoulos, G.: $d^{*}_{+}$: A generic platform-agnostic and risk-aware path planing framework with an expandable grid (2021)
  * (27) Kim, S.K., Bouman, A., Salhotra, G., Fan, D.D., Otsu, K., Burdick, J., Agha-mohammadi, A.a.: Plgrim: Hierarchical value learning for large-scale exploration in unknown environments.  In: Proceedings of the International Conference on Automated Planning and Scheduling, vol. 31, pp. 652–662 (2021)
  * (28) Koval, A., Kanellakis, C., Vidmark, E., Haluska, J., Nikolakopoulos, G.: A subterranean virtual cave world for gazebobased on the darpa subt challenge.  http://arxiv.org/abs/2004.08452 (2020)
  * (29) Lindqvist, B., Agha-mohammadi, A.a., Nikolakopoulos, G.: Exploration-rrt: A multi-objective path planning and exploration framework for unknown and unstructured environments.  arXiv preprint arXiv:2104.03724 (2021)
  * (30) Lindqvist, B., Kanellakis, C., Mansouri, S.S., akbar Agha-mohammadi, A., Nikolakopoulos, G.: Compra: A compact reactive autonomy framework for subterranean mav based search-and-rescue operations (2021)
  * (31) Lindqvist, B., Mansouri, S.S., Haluška, J., Nikolakopoulos, G.: Reactive navigation of an unmanned aerial vehicle with perception-based obstacle avoidance constraints.  IEEE Transactions on Control Systems Technology (2021)
  * (32) Mansouri, S.S., Kanellakis, C., Fresk, E., Kominiak, D., Nikolakopoulos, G.: Cooperative uavs as a tool for aerial inspection of the aging infrastructure.  In: Field and Service Robotics, pp. 177–189. Springer (2018)
  * (33) Matthies, L., Brockers, R., Kuwata, Y., Weiss, S.: Stereo vision-based obstacle avoidance for micro air vehicles using disparity space.  In: 2014 IEEE international conference on robotics and automation (ICRA), pp. 3242–3249. IEEE (2014)
  * (34) Nikolakopoulos, G., Agha, A.: Pushing the limits of autonomy for enabling the next generation of space robotics exploration missions.  Computer 54(11), 100–103 (2021)
  * (35) Okumuş, F., Dönmez, E., Kocamaz, A.F.: A cloudware architecture for collaboration of multiple agvs in indoor logistics: Case study in fabric manufacturing enterprises.  Electronics 9(12), 2023 (2020)
  * (36) Özaslan, T., Loianno, G., Keller, J., Taylor, C.J., Kumar, V., Wozencraft, J.M., Hood, T.: Autonomous navigation and mapping for inspection of penstocks and tunnels with mavs.  IEEE Robotics and Automation Letters 2(3), 1740–1747 (2017)
  * (37) Patel, A., Banerjee, A., Lindqvist, B., Kanellakis, C., Nikolakopoulos, G.: Design and model predictive control of mars coaxial quadrotor (2021)
  * (38) Patel, A., Banerjee, A., Lindqvist, B., Kanellakis, C., Nikolakopoulos, G.: Design and model predictive control of mars coaxial quadrotor.  arXiv preprint arXiv:2109.06810 (2021)
  * (39) Patel, A., Lindqvist, B., Kanellakis, C., Nikolakopoulos, G.: Fast planner for mav navigation in unknown environments based on adaptive search of safe look-ahead poses.  In: 2022 30th Mediterranean Conference on Control and Automation (MED), pp. 545–550 (2022).  DOI 10.1109/MED54222.2022.9837293
  * (40) Peltzer, O., Bouman, A., Kim, S.K., Senanayake, R., Ott, J., Delecki, H., Sobue, M., Kochenderfer, M., Schwager, M., Burdick, J., et al.: Fig-op: Exploring large-scale unknown environments on a fixed time budget.  arXiv preprint arXiv:2203.06316 (2022)
  * (41) Pito, R.: A solution to the next best view problem for automated surface acquisition.  IEEE Transactions on pattern analysis and machine intelligence 21(10), 1016–1030 (1999)
  * (42) Reinhart, R., Dang, T., Hand, E., Papachristos, C., Alexis, K.: Learning-based path planning for autonomous exploration of subterranean environments.  In: 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 1215–1221. IEEE (2020)
  * (43) Ryll, M., Ware, J., Carter, J., Roy, N.: Efficient trajectory planning for high speed flight in unknown environments.  In: 2019 International conference on robotics and automation (ICRA), pp. 732–738. IEEE (2019)
  * (44) Selin, M., Tiger, M., Duberg, D., Heintz, F., Jensfelt, P.: Efficient autonomous exploration planning of large-scale 3-d environments.  IEEE Robotics and Automation Letters 4(2), 1699–1706 (2019)
  * (45) Shen, S., Michael, N., Kumar, V.: Autonomous indoor 3d exploration with a micro-aerial vehicle.  In: 2012 IEEE international conference on robotics and automation, pp. 9–15. IEEE (2012)
  * (46) Tordesillas, J., Lopez, B.T., Everett, M., How, J.P.: Faster: Fast and safe trajectory planner for navigation in unknown environments.  IEEE Transactions on Robotics (2021)
  * (47) Williams, J., Jiang, S., O’Brien, M., Wagner, G., Hernandez, E., Cox, M., Pitt, A., Arkin, R., Hudson, N.: Online 3d frontier-based ugv and uav exploration using direct point cloud visibility.  In: 2020 IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems (MFI), pp. 263–270. IEEE (2020)
  * (48) Xu, Z., Deng, D., Shimada, K.: Autonomous uav exploration of dynamic environments via incremental sampling and probabilistic roadmap.  IEEE Robotics and Automation Letters 6(2), 2729–2736 (2021)
  * (49) Yamauchi, B.: 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’, pp. 146–151. IEEE (1997)
  * (50) Yamauchi, B.: Frontier-based exploration using multiple robots.  In: Proceedings of the second international conference on Autonomous agents, pp. 47–53 (1998)
  * (51) Zhang, J., Hu, C., Chadha, R.G., Singh, S.: Maximum likelihood path planning for fast aerial maneuvers and collision avoidance.  In: 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 2805–2812. IEEE (2019)
  * (52) Zhou, B., Zhang, Y., Chen, X., Shen, S.: Fuel: Fast uav exploration using incremental frontier structure and hierarchical planning.  IEEE Robotics and Automation Letters 6(2), 779–786 (2021)
  * (53) Zhu, C., Ding, R., Lin, M., Wu, Y.: A 3d frontier-based exploration tool for mavs.  In: 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 348–352. IEEE (2015)