  Robotic motion-planning problems, such as a UAV flying fast in a
partially-known environment or a robot arm moving around cluttered objects,
require finding collision-free paths quickly. Typically, this is solved by
constructing a graph, where vertices represent robot configurations and edges
represent potentially valid movements of the robot between these
configurations. The main computational bottlenecks are expensive edge
evaluations to check for collisions. State of the art planning methods do not
reason about the optimal sequence of edges to evaluate in order to find a
collision free path quickly. In this paper, we do so by drawing a novel
equivalence between motion planning and the Bayesian active learning paradigm
of decision region determination (DRD). Unfortunately, a straight application
of existing methods requires computation exponential in the number of edges in
a graph. We present BISECT, an efficient and near-optimal algorithm to solve
the DRD problem when edges are independent Bernoulli random variables. By
leveraging this property, we are able to significantly reduce computational
complexity from exponential to linear in the number of edges. We show that
BISECT outperforms several state of the art algorithms on a spectrum of
planning problems for mobile robots, manipulators, and real flight data
collected from a full scale helicopter.
