Narrow passages identification for Probabilistic Roadmap Method

With narrow passages in robot working space, the Probabilistic Roadmap Method (PRM) is hard to arrive at an efficient path due to unreasonable milestones in limited space. This paper presents a hybrid sampling strategy in the PRM framework to improve the distributions of road signs. It proposes the Randomized Star Builder (RSB) to identify narrow passages in the workspace, and uses the hybrid strategy to sample road signs in the corresponding configuration space. The density of points in the roadmap is then increased in the narrow passages. Moreover, global roadmaps using Uniform Sampler are also configured to rationalize the milestone distribution so as to improve the path planning efficiency. A robot system of multiple degree-of-freedoms is exemplified in simulations to show the effectiveness of the proposed algorithm.

1 Introduction

In robot path planning, Probabilistic Roadmap Method has extensively been used as an effective sampling method [1]–[5]. Classic PRM [6] first randomly configures sampled points in the working space of the robot to describe its possible locomotion in it. Starting from the initial point, a neighbor point is reached by a searching method, such as k-nearest neighborhood method, and connected to the roadmap as well as its affiliated configurations until a roadmap of enough density is reached. A free path of no collision from the initial position to the goal position can consequently be acquired.