  Robots operate in environments with varying implicit structure. For instance,
a helicopter flying over terrain encounters a very different arrangement of
obstacles than a robotic arm manipulating objects on a cluttered table top.
State-of-the-art motion planning systems do not exploit this structure, thereby
expending valuable planning effort searching for implausible solutions. We are
interested in planning algorithms that actively infer the underlying structure
of the valid configuration space during planning in order to find solutions
with minimal effort. Consider the problem of evaluating edges on a graph to
quickly discover collision-free paths. Evaluating edges is expensive, both for
robots with complex geometries like robot arms, and for robots with limited
onboard computation like UAVs. Until now, this challenge has been addressed via
laziness i.e. deferring edge evaluation until absolutely necessary, with the
hope that edges turn out to be valid. However, all edges are not alike in value
- some have a lot of potentially good paths flowing through them, and some
others encode the likelihood of neighbouring edges being valid. This leads to
our key insight - instead of passive laziness, we can actively choose edges
that reduce the uncertainty about the validity of paths. We show that this is
equivalent to the Bayesian active learning paradigm of decision region
determination (DRD). However, the DRD problem is not only combinatorially hard,
but also requires explicit enumeration of all possible worlds. We propose a
novel framework that combines two DRD algorithms, DIRECT and BISECT, to
overcome both issues. We show that our approach outperforms several
state-of-the-art algorithms on a spectrum of planning problems for mobile
robots, manipulators and autonomous helicopters.
