A sampling algorithm for reducing the number of collision checking in probabilistic roadmaps

Abstract

Probabilistic Roadmap (PRM) methods are successful algorithms for solving the motion planning problem for robots with many degrees of freedom. One of the challenges in these methods is the existence of narrow passages in the configuration space. To solve this problem, numerous sampling methods have been introduced in the literature. One of the issues of these methods is the large number of collision checking required to find a solution. In this paper, a sampling algorithm for reducing the number of collision checking is introduced. The proposed algorithm makes full use of all samples created in a configuration space. The basic idea is to generate new samples around a sample, only if there is contrast between the sample's class (collision or free) and its predicted class, which is the estimation of that sample's class by all the other samples. This method will give us a desirable sampling distribution around narrow passages and small obstacles in the configuration space. The results illustrate that the proposed algorithm makes substantial improvements over other well-known sampling algorithms in terms of reducing the number of required collision checking in the sampling phase.