1500 IEEE ROBOTICS AND AUTOMATION LETTERS, VOL. 5, NO. 2, APRIL 2020
An Efficient Sampling-Based Method for Online
Informative Path Planning in Unknown Environments
Lukas Schmid , Michael Pantic , Raghav Khanna , Lionel Ott , Roland Siegwart , and Juan Nieto
Abstract—The ability to plan informative paths online is essential
to robot autonomy. In particular, sampling-based approaches are
often used as they are capable of using arbitrary information gain
formulations. However, they are prone to local minima, resulting in
sub-optimal trajectories, and sometimes do not reach global cover-
age. In this letter, we present a new RRT*-inspired online informa-
tive path planning algorithm. Our method continuously expands a
single tree of candidate trajectories and rewires nodes to maintain
the tree and refine intermediate paths. This allows the algorithm
to achieve global coverage and maximize the utility of a path in a
global context, using a single objective function. We demonstrate
the algorithm’s capabilities in the applications of autonomous in-
door exploration as well as accurate Truncated Signed Distance
Field (TSDF)-based 3D reconstruction on-board a Micro Aerial
Vehicle (MAV). We study the impact of commonly used information
gain and cost formulations in these scenarios and propose a novel
TSDF-based 3D reconstruction gain and cost-utility formulation.
Detailed evaluation in realistic simulation environments show that
our approach outperforms sampling-based state of the art methods
in these tasks. Experiments on a real MAV demonstrate the ability
of our method to robustly plan in real-time, exploring an indoor
environment with on-board sensing and computation. We make
our framework available for future research.
Index Terms—Motion and path planning, aerial systems,
perception and autonomy, reactive and sensor-based planning.
I. INTRODUCTION
I
N RECENT years, mobile robots and in particular, MAVs
have shown increasingly high levels of autonomy and can be
employed in an ever-growing number of applications. A crucial
component to leveraging their full potential is the ability to
autonomously plan and execute informative paths in a priori
unknown environments.
In particular, sampling-based methods are widely used, as
various information gains can be directly computed from the
Manuscript received September 10, 2019; accepted January 8, 2020. Date of
publication January 24, 2020; date of current version February 4, 2020. This
work was supported in part by the National Center of Competence in Research
on Digital Fabrication and in part by the Microsoft Swiss Joint Research Center.
This letter was recommended for publication by Associate Editor M. Morales and
Editor N. Amato upon evaluation of the reviewers’ comments. (Corresponding
author: Lukas Maximilian Schmid.)
L. Schmid, M. Pantic, R. Khanna, R. Siegwart, and J. Nieto are with the
Autonomous Systems Lab, Department of Mechanical and Process Engineer-
ing, ETH Zürich, 8092 Zürich, Switzerland (e-mail: schmluk@mavt.ethz.ch;
mpantic@ethz.ch; raghav.khanna@mavt.ethz.ch; rsiegwart@ethz.ch; jnieto@
ethz.ch).
L. Ott is with the The University of Sydney, Sydney, NSW 2006, Australia
(e-mail: lionel.ott@sydney.edu.au).
This letter has supplementary downloadable material available at http://
ieeexplore.ieee.org, provided by the authors.
Digital Object Identifier 10.1109/LRA.2020.2969191
Fig. 1. Qualitative comparison of our method (left) and RH-NBVP [1] (right)
on a real MAV. The trajectories are colored from red at t =0min to green at
t = 3 min. Our method explores the full room and passes the obstacle in the
bottom center, while RH-NBVP leaves a hole in the floor. Our gain focuses on
areas of high expected error, leading the MAV to revisit surfaces and resulting
in better resolved corners and flatter walls.
map without imposing additional constraints on the choice of
gain formulation. These methods have proven successful in
a variety of scenarios, including volumetric exploration [1],
surface inspection [2], object search [3], weed classification [4],
infrastructure modeling [5], and 3D reconstruction [6].
In the informative path planning (IPP) problem, a robot is
required to generate a path that maximizes the information
gathered, i.e. maximizes an objective function, about its envi-
ronment. To solve the IPP problem when the environment is
unknown, robots are required to identify promising paths online
based on the limited information available at each time step.
This requires paths to be continuously adapted to the current
map. Furthermore, the robot needs to reason over a potentially
large map space to escape local minima and strive for globally
optimal plans. In many cases, both tasks need to be performed
with the limited computational resources available on-board the
robot. Since the operational time of mobile robots is typically
limited by the battery life, efficient computation of informative
trajectories is of major importance.
Traditional sampling-based online IPP approaches, based on
repeatedly expanding a rapidly-exploring random tree (RRT)
[1], [3], [7]–[9], iteratively sample feasible paths from the cur-
rent robot pose, storing them in a tree structure, and execute
the beginning of the best branch. However, these approaches
have two important disadvantages. First, large parts of the tree
2377-3766 © 2020 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See https://www.ieee.org/publications/rights/index.html for more information.
Authorized licensed use limited to: Newcastle University. Downloaded on May 31,2020 at 13:29:41 UTC from IEEE Xplore. Restrictions apply.