Reducing the Collision Checking Time in Cluttered Environment for Sampling-Based Motion Planning

In the Sampling-based motion planning, the collision checking procedure called many times and this operation takes the most planning time. The time spend in the collision checking increases with the number of obstacles. This paper aims to reduce the number of calls of the collision checking procedure in environment containing high number of obstacles. Our approach shows that the complexity of collision checking does not depend on the number of obstacles. The idea is to perform a pre-procedure that localizes the obstacles by segmenting the workspace into a grid and save it in a matrix form. This information is used in the collision checking procedure. We have used the Probabilistic Roadmaps (PRM) motion planner with a punctual robot and polygonal obstacles in 2D environment. Simulation results show the efficiency of our algorithm in reducing the complexity of collision checking and minimizing the planning time.