Drivable Path Planning Using Hybrid Search Algorithm Based on E* and Bernstein–Bézier Motion Primitives

This article proposes a hybrid path-planning algorithm, the HE* algorithm, which combines the discrete grid-based E* search and continuous Bernstein–Bézier (BB) motion primitives. Several researchers have addressed the smooth path planning problem and the sample-based integrated path planning techniques. We believe that the main benefits of the proposed approach are: directly drivable path, no additional post-optimization tasks, reduced search branching, low computational complexity, and completeness guarantee. Several examples and comparisons with the state-of-the-art planners are provided to illustrate and evaluate the main advantages of the HE* algorithm. HE* yields a collision-safe and smooth path that is close to spatially optimal (the Euclidean shortest path) with a guaranteed continuity of curvature. Therefore, the path is easily drivable for a wheeled robot without any additional post-optimization and smoothing required. HE* is a two-stage algorithm which uses a direction-guiding heuristics computed by the E* search in the first stage, which improves the quality and reduces the complexity of the hybrid search in the second stage. In each iteration, the search is expanded by a set of BBs, the parameters of which adapt continuously according to the guiding heuristics. Completeness is guaranteed by relying on a complete node mechanism, which also provides an upper bound for the calculated path cost. A remarkable feature of HE* is that it produces good results even at coarse resolutions.

I. Introduction

Path planning is a fundamental part of any autonomous vehicle with sense-plan-act architecture. The most common scenario assumes path planning in a known environment with obstacles that has been extensively studied in survey books such as [1]–[3]. Commonly used methods compute collision-safe paths that are optimal in the sense of the shortest distance or safety but they lack feasibility and therefore require some post-processing to become drivable for a wheeled mobile robots. However, there is no guarantee that a post-processed path is also feasible. The environment is usually decomposed to cells or representative sample points by some algorithm, such as regular rectangular grid, quadtrees, random sampling-based methods and the like [3]–[6]. Among those cells, an optimal collision-free path is found that connects the current robot pose and the goal location. The most commonly used are grid-based planners (e.g., A*) that usually return optimal set of cell’s center points which may be connected by a sequence of straight lines to arrive from the start to the goal location. The resulting combined path does not have a continuous first and second derivative, i.e., it belongs to set of paths (continuity of position) and does not belong to (continuity of tangency) and (continuity of curvature). This means that by following the path the robot would have step changes in its orientation, while by following the path it would have step changes of its angular velocity. Therefore, the calculated path needs to be smoothed to become so that a wheeled robot can follow it with smooth control actions. This is especially important in occupied and crowded environments where any tracking error could result in a collision in a worst case. Several smoothing approaches were proposed as follows. A funnel algorithm is proposed by [7] to further optimize the path inside the corridor defined by the cells comprising the optimal path. For path optimization and smoothing inside the corridor a fast marching method [8] can be applied or smooth path generation using B-splines can be used as proposed by [9]. Several path smoothing ideas use a local nonlinear optimization around the path [10]–[13]. Sharp transitions on the path, e.g., corners, are often smoothed to enable continuous transitions by inserting parametric curves, such as circular arcs [14], Bezier curves [15]–[18], clothoids [19], [20], or higher-order polynomials [21], [22].