Sampling-based Motion Planning Approaches for Autonomous Vehicle in Narrow Cluttered Spaces

Abstract

Autonomous vehicles are being actively developed for fully autonomous driving without driver intervention. Motion planning is one of the most key technologies in terms of driving safety and efficiency. In particular, the motion planning in constrained narrow space such as a parking lot is very challenging because it requires many changes in forward and backward directions and adjustments of position and orientation of the vehicle. In this thesis, a sampling-based motion planning algorithm is proposed based on Rapidly-exploring Random Trees (RRT, RRT*) by specifying desired orientation during the tree expansion and the rewiring step. The contribution is as follows. First, efficient sampling method is proposed for narrow-cluttered area. In this area, the probability of obtaining a sample to pass through the area due to the obstacle area is relatively low than an open area. It may also fail to extend the path if sampled position is difficult to extend from near nodes. To solve this problem, a constraint model on the tangential direction of the random sample is proposed. Second, we propose an extension method based on tangential direction constraint. In the process of expanding the tree to random samples, a large number of nodes in narrow-cluttered regions cannot pass the collision test. This increases unnecessary iteration numbers and increases memory usage. To solve this problem, we propose a node extension method based on gradient descent. The proposed algorithm has been tested in various situations and its results demonstrated much faster target path search and convergence to the optimal path than the existing nonholonomic RRT*.