INCREASING THE CONNECTIVITY OF PROBABILISTIC ROADMAPS VIA GENETIC POST-PROCESSING

With reference to the motion planning problem, we present a simple strategy for improving the connectivity of probabilistic roadmaps by genetic post-processing. In particular, our objective is to increase the roadmap density in narrow passages, where many of the existing probabilistic planners perform poorly. To this end, we associate to each individual (i.e., to each robot configuration) an easily computable fitness function based on the distance between disjoint components of the roadmaps. Straightforward selection, crossover and (possibly) mutation operators are then applied to improve the quality of the population. Numerical results in different workspaces, including a well-known benchmark, show the effectiveness of the proposed strategy.