Probabilistic Roadmap Methods (PRMs) are
widely used motion planning methods that sample robot
configurations (nodes) and connect them to form a graph
(roadmap) containing feasible trajectories. Many PRM variants
propose different strategies for each of the steps and choosing
among them is problem dependent. Planning in heterogeneous
environments and/or on parallel machines necessitates dividing
the problem into regions where these choices have to be made
for each one. Hand-selecting the best method for each region
becomes infeasible. In particular, there are many ways to select
connection candidates, and choosing the appropriate strategy
is input dependent.
In this paper, we present a general connection framework
that adaptively selects a neighbor finding strategy from a
candidate set of options. Our framework learns which strategy
to use by examining their success rates and costs. It frees the
user of the burden of selecting the best strategy and allows the
selection to change over time.
We perform experiments on rigid bodies of varying geometry
and articulated linkages up to 37 degrees of freedom. Our
results show that strategy performance is indeed problem/region
dependent, and our adaptive method harnesses their strengths.
Over all problems studied, our method differs the least from
manual selection of the best method, and if one were to
manually select a single method across all problems, the
performance can be quite poor. Our method is able to adapt
to changing sampling density and learns different strategies for
each region when the problem is partitioned for parallelism.