A Cost-Effective Approach to Smooth A* Path Planning for Autonomous Vehicles

Path planning for wheeled mobile robots is a critical component in the field of automation and intelligent transportation systems. Car-like vehicles, which have non-holonomic constraints on their movement capability impose additional requirements on the planned paths. Traditional path planning algorithms, such as A^*, are widely used due to their simplicity and effectiveness in finding optimal paths in complex environments. However, these algorithms often do not consider vehicle dynamics, resulting in paths that are infeasible or impractical for actual driving. Specifically, a path that minimizes the number of grid cells may still be too curvy or sharp for a car-like vehicle to navigate smoothly.This paper addresses the need for a path planning solution that not only finds a feasible path but also ensures that the path is smooth and drivable. By adapting the A^* algorithm for a curvature constraint and incorporating a cost function that considers the smoothness of possible paths, we aim to bridge the gap between grid based path planning and smooth paths that are drivable by car-like vehicles. The proposed method leverages motion primitives, pre-computed using a ribbon based path planner that produces smooth paths of minimum curvature. The motion primitives guide the A^* algorithm in finding paths that are optimal in terms of both length and curvature. With the proposed modification on the A^* algorithm, the planned paths can be constraint to have a minimum turning radius much larger than the grid size. We demonstrate the effectiveness of the proposed path planning algorithm in different unstructured environments. In a two-stage planning approach, first the modified A^* algorithm finds a grid-based path and the ribbon based path planner creates a smooth path within the area of grid cells. The resulting paths are smooth with small curvatures independent of the orientation of the grid axes and even in presence of sharp obstacles.

I. Introduction

Autonomous vehicle applications in unstructured environments include rescue, construction site, parking lots etc. and in many of these applications, the vehicle perceives its surrounding and creates a map of the environment using SLAM [1 , 2] . To reach its target, dedicated planning algorithms are required. A review on path planning approaches can be found in [3 , 4 , 5] . There are numerous approaches simultaneously dealing with the non-holonomic constraints of the vehicle and solving the path search problem in the unstructured, possibly not fully known, environment. These solutions range from classic geometric approaches based on Reeds and Shepp [6] to game-theoretic and AI based approaches [7] . A popular solution is the RRT path planner [3 , 2 , 8] . All these approaches face the challenge of high computational effort with complex environment structures. An alternative to these are grid based path planning algorithms. At the cost of disregarding the vehicles movement restrictions, grid based search algorithms can provide fast solutions even in complex environments. One of the most famous is the A ^* algorithm.