Path Planning and Obstacle Avoidance for Automated Driving Systems Using Rapidly-Exploring Random Tree Algorithm

This article describes a practical path planning and obstacle avoidance method for automated driving systems using the Rapidly-exploring Random Tree (RRT) algorithm. Given the initial states of a vehicle, a goal region, and the presence of obstacles, the algorithm finds a smooth path and a time series of steering angle commands required to follow that path. The proposed algorithm works when the vehicle is operated in an unknown environment where obstacles are detected by the vehicle sensors or global navigation satellite systems (GNSS). In this study, there are two main steps. The first step constructs a vehicle dynamic model that predicts the trajectory given a steering input and the current vehicle state. The second step applies the vehicle dynamic model and uses the RRT algorithm to implement path planning and obstacle avoidance function. The change of steering angle commands between adjacent time segments is restricted in a specific range so that the maneuvering is smooth. The RRT algorithm is examined by computer simulations using two types of scenarios: the vehicle navigates in a region with or without obstacles. Under both types of scenarios, the algorithm is able to find a path that can be safely followed by the vehicle and the associated time series of steering angle commands. The algorithm verified successfully in this study indicates a possibility of implementing it in real-time application using microcontrollers in a mass-production vehicle or via cloud services. Open issues and suggested areas for future research are also discussed.