Adaptive Neighbor Connection for PRMs, A Natural Fit for Heterogeneous Environments and Parallelism

used robotic motion planning methods that sample robot config-urations (nodes) and connect them to form a graph (roadmap) containing feasible trajectories. Many variants propose different strategies for each of the algorithmic steps. Planning in hetero-geneous environments and/or on parallel machines necessitates dividing the problem into regions where decisions on what strategies to use have to be made for each region. In particular, there are many ways to select connection candidates, and choosing the appropriate strategy is problem and region dependent. Thus, hand-selecting the best method per region becomes intractable. We present a general connection framework that adaptively combines multiple neighbor finding strategies to handle het-erogeneous environments and better facilitate parallelism. Our framework learns which strategy to use by examining their success rate and cost. Thus, it frees the user of the burden of selecting the best strategy and allows the selection to change as different regions may require different strategies. 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 hand choosing the best method for each one, and in some cases hand selecting the wrong strategy is quite detrimental. We show that our method is able to adapt to changing sampling density and learns different strategies for each region when the problem is partitioned for parallelism. I