text: A well-known weakness of the probabilistic path planners is the so-called narrow passage problem, where a region with a relatively low probability of being sampled must be explored to find a solution path. Many strategies have been proposed to alleviate this problem, most of them based on biasing the sampling distribution. When kinematic constraints appear in the problem, the configuration space typically becomes a non-parametrizable, implicit manifold. Unfortunately, this invalidates most of the existing sampling bias approaches, which rely on an explicit parametrization of the space to explore. In this paper, we propose and evaluate three novel strategies to bias the sampling under the presence of narrow passages in kinematically-constrained systems.
  @cite_24: In this paper we present a method to control random sampling in motion planning algorithms. The principle of the method is to use online the results of a probabilistic planner to describe the free space in which the planning takes place, by computing a principal component analysis (PCA). This method identifies the locally free directions of the free space. Given that description, our algorithm accelerates the progression along these favored directions. In this way, if the free space appears as a small volume around a sub-manifold of a high-dimensional configuration space, the method overcomes the usual limitations of probabilistic motion planning algorithms and finds a solution quickly. The presented method is theoretically analyzed and experimentally compared with known motion planners.
  @cite_5: We propose a general framework for sampling the configuration space in which randomly generated configurations, free or not, are retracted onto the medial axis of the free space. Generalizing our previous work, this framework provides a template encompassing all possible retraction approaches. It also removes the requirement of exactly computing distance metrics thereby enabling application to more realistic high dimensional problems. In particular, our framework supports methods that retract a given configuration exactly or approximately onto the medial axis. As in our previous work, exact methods provide fast and accurate retraction in low (2 or 3) dimensional space. We also propose new approximate methods that can be applied to high dimensional problems, such as many DOF articulated robots. Theoretical and experimental results show improved performance on problems requiring traversal of narrow passages. We also study tradeoffs between accuracy and efficiency for different levels of approximation, and how the level of approximation effects the quality of the resulting roadmap.
  @cite_9: Probabilistic roadmap (PRM) planners have been successful in path planning of robots with many degrees of freedom, but sampling narrow passages in a robot's configuration space remains a challenge for PRM planners. This paper presents a hybrid sampling strategy in the PRM framework for finding paths through narrow passages. A key ingredient of the new strategy is the bridge test, which reduces sample density in many unimportant parts of a configuration space, resulting in increased sample density in narrow passages. The bridge test can be implemented efficiently in high-dimensional configuration spaces using only simple tests of local geometry. The strengths of the bridge test and uniform sampling complement each other naturally. The two sampling strategies are combined to construct the hybrid sampling strategy for our planner. We implemented the planner and tested it on rigid and articulated robots in 2-D and 3-D environments. Experiments show that the hybrid sampling strategy enables relatively small roadmaps to reliably capture the connectivity of configuration spaces with difficult narrow passages.
summary: To detect narrow passages, the bridge-test @cite_9 focuses on the generation of pairs of samples in collision where the central point between these samples is collision-free. Even if the configurations could be generated easily, this test implicitly assumes that the linear interpolation between two samples is also a valid configuration, which is not the case when the configuration space is an arbitrary manifold. The assumption is also taken by the approaches that use linear interpolation to displace the random samples toward the medial axis of the free configuration space @cite_5 . Moreover, approaches that use linear dimensionality reduction of the nodes already in the RRT to bias the sampling @cite_24 are also affected by this issue.