Predictive model for path planning by using k-near dynamic bridge builder and Inner Parzen Window

Robotic path planning in changing environments with difficult regions is an extremely challenge. Since the structure of configuration space (C-space) will change when obstacles move in workspace (W-space), the planner should have the capacity of building approximate structure of C-space, while avoiding intense computational complexity. Further, difficult regions will also change their positions, which requires the planner should be able to identify them fast and increase the free nodes inside them efficiently. This paper presents a novel approach for path planning in changing environments using predictive model, which is inspired by the idea of active learning. With the help of W-C nodes mapping, this predictive model is built to capture the approximate structure of C-space, while avoiding intense computational complexity. This model include two steps: K-near Dynamic Bridge Builder (K-near DBB) is proposed to identify difficult passages in the space first, and then Inner Parzen Window is adopted to sample points in these difficult regions without invoking any collision checker. Experiments are carried out with two 6-DOF manipulators, and our approach can find a path with high time efficiency and low error rate, even if the environment is complex.

I. INTRODUCTION

In static environments, complete motion planning algorithms require total understanding of robot's configuration space (C-space). However, they are rarely used in practice because they are computational infeasible [1] [2]. The generalized motion planning problem has been proved PSPACE hard [3]. Therefore, attention has turned to sampling-based algorithms that sacrifice completeness for computational feasibility. The most successful sampling-based planner is PRM [4] in static environments. The key idea behind PRM is to construct a connective graph which implicitly approximates the structure of the C-space. Nevertheless, difficult regions, i.e. the positions of narrow passages and where the boundaries of obstacles (C-obstacle) are, pose significant difficulty for PRM planners. Since uniform sampling that adopted by PRM implicity assumes C-space is uniformly complex. Therefore, in static environments, much research has focused on increasing the probability of sampling points in difficult regions [5] [6] [7] [8].