An Adaptive Path Planning Method for Curved Roads via Three-Dimensional Space-Aware Profiling Maps

In modern transportation, autonomous driving technology has emerged as a significant innovation, offering improved safety, efficiency, and convenience. One of its core technologies is path planning, which creates an optimal route for vehicles in various traffic situations, ensuring they arrive safely and efficiently. However, existing path planning methods suffer from inflexible and inefficient road sampling, and limitations in path expression due to curve models. In this paper, we introduce a novel path planning framework that operates from a coarse-to-optimal approach. We first introduce an adaptive sampling method to construct a three-dimensional (3D) space-aware profiling map in the Frenet frame to quantify abstract traffic scenarios. This cost map guides the generation of waypoints by incorporating obstacle distributions in the $s$ -direction and cost values in the $l$ -direction. We then design a cost function to obtain the coarse path by considering ride comfort, anti-deviation from the center of the road, and path safety. Finally, a new path model is re-established based on the Taylor series, and a quadratic programming approach is employed to fine-tune the coarse path to attain the optimal path. Experimental results show that the proposed adaptive sampling method can dynamically adjust the sampling strategy according to the change in the number and distribution of obstacles on the road, significantly improving the sampling effectiveness rate to 100%, 99.85%, 99.68% and 99.61% for one-obstacle, two-obstacle, three-obstacle, and four-obstacle scenarios. Compared with the conventional method, the generated path length is shortened by 3.48% and 8.42%, and the maximum heading angle is reduced by 18.68% and 30.21% in the scenarios with obstacles of the same and different sizes.

SECTION I. Introduction

Autonomous driving is reshaping both our modes of transportation and our travel experience. It has the potential to improve traffic efficiency, reduce congestion, and ensure driving safety [1]. As the technology advances, and finds more practical applications, autonomous driving is expected to play an increasingly significant role in future transportation systems [2]. Central to an autonomous driving system are function modules such as perception, decision-making, planning, and vehicle control [3], as depicted in Figure 1. Recent advances in sensor technology have facilitated the utilization of robust multi-sensory perception systems [6]. This perception module integrates various data sources like high-definition (HD) maps, cameras, radars, lasers, the global positioning system (GPS), and the inertial measurement unit (IMU) to perform tasks like location pinpointing, object detection, and tracking. The decision-making phase interprets this information to predict trajectories and determine various driving strategies such as overtaking, lane changing, nudging, and vehicle following according to the signal stream from the perception module. Once the driving strategy is decided, the planning module will devise a collision-free trajectory considering the kinematics and dynamics constraints of the vehicle. The final step involves calculating the steering wheel, accelerator, and brake pedal control signals based on the planned path information, enabling the vehicle to track the trajectory [7].

FIGURE 1.

An illustration of the autonomous driving system’s architecture [4], [5].

The planning module not only bridges the decision-making and control modules but also serves as a fallback mechanism when the control module fails to track the path correctly [8]. By re-planning the trajectory, the system ensures the autonomous vehicle stays on course towards the intended destination. Therefore, we can consider the efficacy of the planning module as a barometer for the intelligence and success of an autonomous driving system [9]. Inside the planning module are two core components: the global planner and the local planner [10], [11]. The global planner determines the optimal path from the origin to the destination taking into account elements like road structure, traffic signs, and the flow of traffic. It focuses on long-term planning strategies [12]. In contrast to the global planner, the local planner focuses on the vehicle’s immediate environment and generates short-term paths in real-time scenarios [13]. This paper focuses on the local planning task.

Methods for local planning tasks can be divided into two main branches: spatio-temporal joint (STJ) trajectory planning and spatio-temporal decoupled trajectory planning, also called path-velocity decomposition (PVD) trajectory planning [14]. The spatio-temporal joint trajectory planning considers time and space dimensions and computes feasible trajectories in a three-dimensional spatio-temporal space. It performs well in various scenarios, similar to experienced drivers. However, the detailed nature of STJ planning demands substantial time and computational power, making it less suitable for real-time responses in complex driving situations. The PVD-based trajectory planning technique separates a complex three-dimensional trajectory planning challenge into two distinct parts: a two-dimensional path planning problem and a one-dimensional velocity planning problem. This approach effectively reduces the computational complexity associated with trajectory planning, guarantees real-time performance, and is widely used in practice. In addition, the PVD-based methods can also deal with static and dynamic obstacles separately. Path planning focuses on static obstacles and speed planning is aimed at dynamic obstacles by adjusting the speed. Our research introduces a novel path-planning method within the PVD framework.

Although numerous algorithms for on-road path planning have emerged since the DARPA Grand Challenge (2004, 2005) and the Urban Challenge (2007) [15], many predominantly address issues associated with straight-road scenarios. They often overlook the complexities of road curvature and the relationship between the road’s layout and the autonomous vehicle [16]. In actual urban settings, the majority of road segments possess curves. Even seemingly straight stretches can be complicated by factors like roadside parking, unauthorized encroachments, and road maintenance, introducing undulations within the drivable spaces. Recognizing this, the research in this paper emphasizes path planning tailored for curved roads.

A. Motivations

The uniform sampling road method has been widely utilized in path planning [17]. Its core concept is to discretize the path space into a series of uniformly distributed sampling points, which are then connected by interpolation to create a smooth path [18]. This approach reduces the complexity of path-planning problems and improves computational efficiency. However, it is important to note that this method has limitations. As depicted in Figure 2, when all other conditions are kept constant and the number of waypoints sampled in the $l$ direction is changed, the routing for the first two obstacles’ avoidance is similar. In Figure 2 (a), where there are 11 sampled waypoints in the $l$ -direction, starting from the third obstacle, the planned path chooses to avoid obstacles from the left side. On the other hand, in Figure 2 (b), with 12 sampled waypoints in the $l$ -direction, starting from the third obstacle, the planned path circumvents obstacles from the right side. Therefore, this method is highly sensitive to the sampling resolution of waypoints, and even slight variations in the sampling resolution can lead to significantly different path-planning results. In the following sections, we refer to this uniform sampling road method as the conventional sampling method.

FIGURE 2.

The conventional sampling method.

This is because the conventional method samples road scenarios without explicit purpose or subjective awareness, simply conducting uniform sampling of the road scenarios. As a result, the final planned path also exhibits some randomness in choosing the direction to bypass obstacles. Therefore, in practice, the selection of sampling parameters heavily relies on expert experience or manual tuning, and once determined, they will remain fixed and cannot be modified. This approach is impractical, as fixed discretization parameters are difficult to adapt to the ever-changing traffic conditions. Moreover, when setting the sampling parameters, the distribution of obstacles on the road is not taken into account, leading to sampled waypoints potentially falling on or being too close to obstacles. Consequently, a large number of collision-prone paths can be anticipated without the need for collision checking. This inefficiency would waste computational resources during subsequent collision detection steps and fail to provide a comprehensive solution space for selecting the optimal path in the following stages. The advisable approach involves dense sampling in regions where optimal paths are likely to exist, sparse sampling in regions near obstacles, and avoidance of sampling in regions occupied by obstacles.

B. Contributions

In order to overcome the limitations of the current sampling method, we propose a novel adaptive path-planning method for curved roads in this paper. Our main contributions can be summarised as follows:

• We present a practical path-planning framework. The driving space is initially discretized using a customized adaptive sampling algorithm to obtain waypoints. Subsequently, a set of paths is generated by connecting the sampled waypoints with piecewise quintic polynomials. A coarse solution for the optimal path is then obtained based on a defined cost function. To address the potential lack of smoothness at the connection points of the piecewise curves and ensure that the final path is not restricted by the shape description of quintic polynomials, a Taylor expansion is employed to model the path. Finally, a quadratic program (QP) based smoother is utilized to refine and optimize the coarse solution, resulting in the generation of the optimal path.

• We propose an adaptive algorithm to increase the flexibility of sampling and dynamically adjust the sampling parameters according to different traffic scenarios. This algorithm transforms the Cartesian frame into the Frenet frame to effectively describe the vehicle’s motion on curved roads. In the Frenet frame, an obstacle influence analysis is conducted to understand their impact on the autonomous vehicle’s navigation. Based on this analysis, the driving space is discretized and sampled in the $l$ -direction, while the $s$ -direction is discretized and sampled considering the distribution position of obstacles. Finally, a custom gate matrix is utilized to effectively control the output of sampling points.

• We demonstrate the performance of our proposed path planning algorithm by comparing it with existing methods. Experimental results indicate that, compared with conventional approaches, our adaptive path planning algorithm can dynamically adjust the sampling parameters of the driving space based on the distribution of road obstacles. This improves the efficiency of generating candidate paths and provides a more effective solution space for selecting the optimal path. Moreover, the generated optimal path is shorter and smoother than those obtained using the conventional method.

C. Organization

The rest of this paper is organized as follows: Section II presents a review of related works; Section III presents the framework of the proposed adaptive path planning algorithm; Section IV provides an in-depth explanation and illustration of the proposed algorithm; Section V presents the evaluation and validation results, comparing the proposed method with the conventional approaches, and Section VI concludes the paper and explores potential directions for future research.

SECTION II. Related Work

The methodologies employed by path planning in autonomous driving can be categorized as two independent and separate branches of research: the learning-based branch and the algorithm-based branch [19]. Table 1 summarizes the current main works in these two branches.

TABLE 1 Comparison of Path Planing Techniques

Learning-based methodologies leverage extensive offline learning from vast data to generate inference models, enabling them to generate path planning results and even vehicle control commands based on input sensor data. Among these algorithms, deep learning is a prevalent technique [20], [21]. Deep learning effectively learns the mapping relationship between input sensor data and output paths by training neural network models on large-scale training data. Furthermore, reinforcement learning is another commonly adopted approach [22], [23]. Through interactive exploration with the environment, reinforcement learning algorithms experiment with different actions and learn from reward signals provided by the environment to optimize path-planning strategies progressively. The strength of learning-based algorithms is their ability to adaptively adjust path planning strategies to different environments and driving needs through offline training [24], [25]. However, learning-based algorithms also face challenges such as large data requirements, long training times, and poor interpretability [26].

Algorithm-based methodologies receive driving environment information from the perception module and driving strategies from the decision module. They utilize explicitly defined rules and algorithms to output an optimal planned path. In addition, this kind of method has been widely adopted in the automotive industry. Unlike learning-based methods, algorithm-based methods are typically easier to interpret and understand. Path planning is based on explicit rules and algorithms, providing explanations and logical reasoning for path selection [27]. Additionally, algorithm-based methods can adapt to different scenarios and requirements by designing and adjusting algorithm parameters. On the contrary, learning-based methods may require retraining or fine-tuning models for different scenarios and environments, limiting their generality and flexibility [28]. The algorithm-based methodologies can be further divided into four categories: artificial potential field-based methods, graph search-based methods, random sample-based methods, and discrete optimization-based methods [29], [30].

Artificial potential field-based methods establish a destination’s attractive field and obstacles’ repulsive field according to the concept of potential energy in physics [31]. The attractive field guides the autonomous vehicle toward the target location, while the repulsive field helps the vehicle avoid obstacles. By properly defining the forms and parameters of the attraction and repulsion forces, these methods enable the vehicle to autonomously plan a path that avoids obstacles in the environment [32]. Orozco-Rosas et al. combined membrane computing with a genetic algorithm and the artificial potential field method to generate a safe and navigable path. Compared with the conventional artificial potential field method, this method can plan a path within less time [33]. Rasekhipour et al. combined the artificial potential field method with optimal control for path planning, ensuring the generated path can effectively handle various obstacles and road constructs [34]. Liu et al. combined the potential field method with the sigmoid curve approach and redesigned the attractive and repulsive fields. The results showed that this method achieves better vehicle stability and ride comfort than the traditional potential field-based method [35]. Although artificial potential field methods have the advantage of avoiding obstacles in simple environments, they also have some limitations, especially in complex environments. For example, they may encounter local minima-related issues or difficulties in narrow driving spaces. Therefore, in more complex environments and for high-precision path-planning requirements, artificial potential field methods are often combined with other algorithms or techniques to improve the effectiveness and reliability of the path-planning process.

Graph search-based methods discretize the road space using grid or lattice cells and then employ search algorithms to find the optimal trajectory [36]. Common search algorithms used in this context include Dijkstra, A*, D* and their variants [37], [38]. Sedighi et al. combined the visibility diagram algorithm with the hybrid A* algorithm to shorten the time required to find the globally optimal path [39]. Aine et al. proposed using multiple heuristic functions to replace the single heuristic function in the A* algorithm. This allows for a balance between path optimality and search efficiency. However, the generated path may not satisfy the kinematic constraints of the vehicle [40]. Zheng et al. incorporated the jump point search technique to enhance node exploration and search speed of the A* algorithm. An angle evaluation cost function is also introduced to the existing A* algorithm’s cost function. By considering the number of inflection points, the algorithm aims to identify the path with the fewest changes in direction, thus facilitating the rapid identification of an optimal path [41]. While numerous researchers have effectively enhanced search efficiency and reduced the time needed to find the optimal path, these paths may not satisfy the non-holonomic constraints of vehicles and exhibit poor path smoothness. A further post-smoothing procedure is needed to ensure its feasibility for on-road driving scenarios. However, it should be noted that while smoothing the path, the collision-free characteristic obtained during the search may not be preserved and that additional adjustments and modifications are essential to ensure the safety of the path for vehicle navigation. Additionally, these algorithms often result in high computational costs due to the need for map reconstruction and search at each step in dynamic environments.

Random sample-based methods involve randomly sampling a set of candidate points in the driving space and connecting them to form a graph-based representation of the environment. The most representative methods in this category are Rapidly Exploring Random Tree (RRT) and Probabilistic Road Map (PRM) [42], [43]. RRT explored the space by extending the tree towards unexplored regions, while PRM constructed a roadmap by connecting collision-free sampled points. Karaman et al. proposed RPM* and RRT* algorithms and demonstrated the asymptotic optimality of the proposed methods [44]. Taheri et al. proposed the Fuzzy Greedy Rapidly Exploring Random Tree (FG-RRT) algorithm based on the RRT algorithm, which reduces the number of nodes and decreases the computational complexity of the algorithm [45]. Li et al. employed RRT* to search for an approximate path and then utilized QP numerical optimization to refine the path to satisfy the constraints of the vehicle model [46]. Random sampling-based search algorithms have strong search capabilities, but their inherent excessive randomness in sampling often leads to infinite or unpredictable convergence times and a repetitive selection of identical random intermediate states, resulting in paths that are often unstable and redundant. This is not acceptable for autonomous driving, especially at high speeds. Moreover, the random distribution of sampling points leads to paths with inadequate smoothness, necessitating post-processing techniques to enhance path smoothness and ensure continuous curvature.

Discrete optimization-based methods systematically sample structured road networks by discretizing the road into evenly spaced waypoints along the vehicle’s forward directions. These sampled waypoints are then connected using certain parametrized curve models, such as splines, spirals, polynomials, or piecewise lines, to form a set of candidate paths. Finally, the optimal path is selected based on a predefined cost function and relevant hard constraints [47]. Chen et al. proposed a path and velocity planning method for collision avoidance based on a segmented three-dimensional quartic Bezier curve [48]. Huang et al. employed polynomials to formulate the paths and redesign a cost function to quantitatively evaluate the safety of candidate paths considering the size of static obstacles [49]. Li et al. developed a progressively constrained dynamic optimization (PCDO) method for multi-vehicle lane-changing scenarios. The PCDO method proves to be efficient in streamlining the establishment of an online computation look-up table [50]. Compared to the other three methods, the discrete optimization method converges faster to local optima or higher-quality solution sets and has been widely used.

In summary, the aforementioned approaches, including learning-based methods, artificial potential field methods, graph search-based methods, and random sample-based methods, exhibit limitations such as limited interpretability, being stuck in local optima, and high computational requirements. Since the discrete optimization-based methods have a better real-time performance than the other methods, we base our work on discrete optimization-based methods.

SECTION III. Overview of the Framework

The overview of our method is illustrated in Figure 3. Our method is designed to improve the path planning module of on-road autonomous driving. This framework focuses solely on spatial path planning and does not involve time-related speed planning. The proposed framework follows a hierarchical architecture comprising four functional layers. Initially, the traffic scenarios in the Cartesian frame are transformed into the Frenet frame. Typically, in the Frenet frame, the direction along the road center line is the $s$ -axis and the direction perpendicular to the road center line is the $l$ -axis. As a result, the Frenet frame conveniently transforms curved road scenarios into straight road scenarios. In addition, the Frenet frame enables an intuitive description of the spatial relationship between the autonomous vehicle and the road. For instance, based on the current $s$ -coordinate, the vehicle’s accumulated distance along the road can be determined, while the $l$ -coordinate provides information about the vehicle’s lateral deviation from the road center.

FIGURE 3.

Framework of the proposed adaptive path planning method.

Subsequently, we formulate the impact of obstacles on the autonomous vehicle’s trajectory and generate a 3D space-aware profiling map in the Frenet frame. Given the performance of obstacle avoidance heavily relies on the sampling strategy in the $l$ -direction, we project the 3D space-aware profiling map onto the $l$ -axis to obtain the obstacle influence curve in that direction. Furthermore, by analyzing the distribution of obstacles along the $l$ -axis, we construct gate matrices, which determine the number of samples taken in the $l$ -direction by combining the obstacle influence curves. Due to the relatively minor impact of the $s$ -direction on obstacle avoidance, we simplify the sampling operation in this direction by primarily relying on the distribution of obstacles in this direction. In the optimal path generation phase, a first-coarse-to-optimal architecture is employed. Initially, a set of collision-free paths is obtained through a collision check process. Subsequently, a custom cost function is utilized to select the coarse solution for the optimal path. Finally, a QP-based smoother is proposed to fine-tune the coarse path.

SECTION IV. Algorithm Illustration

A. Frenet and Cartesian Frames

Figure 4 illustrates the spatial relationship of the ego vehicle in both the Cartesian frame and the Frenet frame. Point $Q(x,y)$ represents the current position of the ego vehicle in the Cartesian frame, and point $P$ is the projection of point $Q$ onto the reference line (i.e., the road center line). The distance between point $P$ and point $Q$ denotes the lateral displacement $l$ . The accumulated curve distance from the starting point of the reference line to projection point $P$ represents the longitudinal displacement $s$ . Therefore, the coordinates of the ego vehicle’s current position(i.e., point $Q$ ) in the Frenet frame can be expressed as $(s, l)$ . The $r_{\text {ev}}$ is the radius of the bounding box’s circumcircle, and the bounding box information is from the perception module.

FIGURE 4.

Transformation from Frenet frame to Cartesian frame.

In the Cartesian frame, the spatial state of the ego vehicle can be described as $\left [{x_{x}, y_{x}, \theta _{x}, \kappa _{x}}\right]$ , where $x_{x}$ and $y_{x}$ represent the vehicle’s coordinates at point $Q$ , $\vec {n}_{r}$ and $\vec {t}_{r}$ denote the unit normal and tangent vectors of the reference line at point $P$ , and $\vec {n}_{x}$ and $\vec {t}_{x}$ are the unit normal and tangent vectors of the vehicle’s planned path at point $Q$ . Moreover, point $O$ is the intersection point of the reverse extension lines of $\vec {t}_{x}$ and $\vec {t}_{r}$ . $\theta _{x}$ denotes the angle between $\vec {t}_{x}$ and the $x$ -axis. $\theta _{r}$ denotes the angle between $\vec {t}_{x}$ and the $x$ -axis. $\kappa _{x}$ is the curvature at point $Q$ . $\kappa _{r}$ is the curvature at point $p$ . In the Frenet frame, the spatial state of the vehicle can be represented by the vector $\left [{s, l, l^{\prime }, l^{\prime \prime }}\right]$ , where $l^{\prime }$ represents the first derivative of $l$ with respect to $s$ (i.e., $l^{\prime }=\frac {d l}{d s}$ ), and $l^{\prime \prime }$ represents the second derivative of $l$ with respect to $s$ (i.e., $l^{\prime \prime }=\frac {d l^{\prime }}{d s}$ ).

The relationship between the coordinate transformations of the ego vehicle in the Cartesian and Frenet frames can be described by the following equation.\begin{align*} \begin{cases} \displaystyle x_{x}= x_{r}-l \sin \theta _{r} \\ \displaystyle y_{x}= y_{r}+l \cos \theta _{r} \\ \displaystyle \theta _{x}= \arctan \left ({\frac {l^{\prime }}{1-k_{r} l}}\right)+\theta _{r} \in [-\pi, \pi] \\ \displaystyle k_{x}= \left ({\left ({l^{\prime \prime }+\left ({k_{r}^{\prime } l+k_{r} l^{\prime }}\right) \tan \Delta \theta }\right) \frac {\cos ^{2}\Delta \theta }{1-k_{r} l}+k_{r}}\right) \frac {\cos \Delta \theta }{1-k_{r} l} \end{cases} \\ \, \tag{1}\end{align*} where $\Delta \theta = \theta _{x} - \theta _{r}$ .

B. 3D Space-Aware Profiling Map Establishment

When sampling the driving area, it is crucial to avoid random and targetless approaches, or mechanically dividing the road equally. Instead, we should consider the current traffic scene information, such as the position of the ego vehicle, the distribution and sizes of obstacles, etc. Consequently, we propose an adaptive sampling method. The initial stage involves modelling the abstract driving scenario and transforming the qualitative description of the driving scene into a quantitative cost map.

This paper takes into account the following three factors to establish the cost map for the current traffic scenario. Firstly, positions closer to obstacles should be assigned higher cost values. Secondly, obstacles closer to the ego vehicle should contribute to higher cost values in their respective areas. Thirdly, the size of obstacles also influences the magnitude of their impact on the corresponding regions. The cost value of the driving scenario $f(s, l)$ can be modelled using equation 2:\begin{equation*} f(s, l)=\sum _{i=0}^{n}\left ({e^{g_{i}(s, l)} \cdot h_{i}(s, l)}\right) \tag{2}\end{equation*} where $i$ is the index of obstacles and $n$ is the number of obstacles.

$g_{i}(s, l)$ represents the impact of obstacles on the driving area, where higher values indicate lower driveability areas:\begin{equation*} g_{i}(s, l)=-w_{0} \sqrt {\left ({s-s_{\text {ob}}^{i}}\right)^{2}+\left ({l-l_{\text {ob}}^{i}}\right)^{2}} \tag{3}\end{equation*} where $w_{0}$ is the weight coefficient which affects the significance of $g_{i}(s, l)$ in $f(s, l)$ and $(s_{\text {ob}}^{i},l_{\text {ob}}^{i})$ is the coordinates of obstacle $i$ in the Frenet frame.

$h_{i}(s, l)$ represents the impact value of obstacle $i$ on the ego vehicle’s navigation:\begin{equation*} h_{i}(s, l)=\frac {w_{1} r_{\text {ob}}^{i} r_{\text {ev}}}{w_{2} \sqrt {\left ({s_{\text {ego}}-s_{\text {ob}}^{i}}\right)^{2}+\left ({l_{\text {ego}}-l_{\text {ob}}^{i}}\right)^{2}}} \tag{4}\end{equation*} where $r_{\text {ob}}^{i}$ is the radius of the circumference of the bounding box around the obstacle $i$ , calculated with respect to $r_{\text {ev}}$ ; $(s_{\text {ego}},l_{\text {ego}})$ is the current coordinates of ego vehicle in the Frenet frame, $w_{1}$ is the weight of coefficient which influences the importance of the size of obstacles in cost value and $w_{2}$ is the weight of coefficient which impacts the consequence of the distance between obstacle $i$ and ego vehicle.

C. Space Discretization

In this stage, the driving space will be sampled in both the $s$ -direction and $l$ -direction based on the 3D space-aware profiling map. Moreover, the generation of $l$ -direction path points will be regulated by the proposed gate matrix, as shown in Figure 5.

FIGURE 5.

Space discretization overview.

1) $S$ -Direction Sampling

In contrast to the conventional approach of evenly partitioning a segment of road, the spatial discretization method proposed in this paper considers the distribution of obstacles when sampling in the $s$ -direction. Firstly, we obtain the $s$ -coordinates of the obstacles and coarsely divide the road into segments. Then, we take into account the distance between adjacent obstacles in the $s$ -direction. If the distance is greater than the threshold $S_{r}$ , we perform interpolation sampling using $\Delta q$ between the neighbouring obstacles to ensure reasonable sampling spacing and sufficient sampling depth in the $s$ -direction, as shown in Equation 5.\begin{align*} & \mathbf {A}=\left [{s_{\text {ob}}^{0}, \cdots s_{\text {ob}}^{i-1}, s_{\text {ob}}^{i}, s_{\text {ob}}^{i}+\Delta q, s_{\text {ob}}^{i}+2\Delta q,}\right. \\ & \left.{\qquad \cdots, s_{\text {ob}}^{i+1}, \cdots, s_{\text {ob}}^{n}}\right], \\ & {\, \text {s.t. }}\begin{cases} \displaystyle s_{\text {ob}}^{i}-s_{\text {ob}}^{i-1}< S_{r}; \\ \displaystyle s_{\text {ob}}^{i+1}-s_{\text {ob}}^{i}>S_{r} \end{cases} \tag{5}\end{align*} $\mathbf {A}$ is a matrix that contains the coordinates of sampling waypoints in the $s$ -direction.

2) Gate Matrix

The gate matrix $\mathbf {B}$ controls the generation of waypoints in the $l$ -direction that passes through the coordinates of obstacles. Firstly, as shown in Figure 5, the road segment along the $l$ -direction is divided into $m$ regions, denoted as $\text {sq}_{i,j}$ . Then, the gate matrix $\mathbf {B}$ is assigned values based on whether the corresponding region is occupied by obstacles, as shown in Equation 7.\begin{align*} \mathbf {B}=\begin{bmatrix} b_{0,0} &\, b_{0,1} &\, \cdots &\, b_{0,j} &\, \cdots &\, b_{1, m-1} \\ b_{1,0} &\, b_{1,1} &\, \cdots &\, b_{1,j} &\, \cdots &\, b_{2, m-1} \\ \vdots &\, \vdots &\, \ddots &\, \vdots &\, \ddots &\, \vdots \\ b_{i, 0} &\, b_{i, 1} &\, \cdots &\, b_{i,j} &\, \cdots &\, b_{i, m-1}\\ \vdots &\, \vdots &\, \ddots &\, \vdots &\, \ddots &\, \vdots \\ b_{n, 0} &\, b_{n, 1} &\, \cdots &\, b_{n,j} &\, \cdots &\, b_{n, m-1}\\ \end{bmatrix} \tag{6}\end{align*} where, \begin{align*} b_{i,j} = \begin{cases}\displaystyle 1 & \text {obs}_{i} {\, \text {not in }} \text {sq}_{i, j} \\ \displaystyle 0 & \text {obs}_{i} {\, \text {in }} \text {sq}_{i, j}\end{cases} \tag{7}\end{align*} $j$ is the index of the divided regions.

3) $L$ -Direction Sampling

The process of sampling in the $l$ -direction is divided into two parts: non-obstacle regions sampling and obstacle regions sampling. The traffic scenarios of non-obstacle regions are relatively simple, hence, the $l$ -direction is uniformly partitioned with $\Delta l$ as with the conventional method. The sampling strategy in the $l$ -direction, particularly in regions with obstacles, plays a crucial role in determining the obstacle avoidance performance of autonomous vehicles. In this paper, we project the obtained 3D space-aware profiling map onto the $l$ -direction, resulting in the cost value curve of each obstacle, shown as Figure 3 (b). Based on this curve, we can calculate the sum of cost values within each region $sq_{i,j}$ , enabling us to determine the number of sampling points in each region.

The rows of matrix $\mathbf {V}$ represent the set of cost values for each region in the $l$ -direction of every obstacle.\begin{align*} \mathbf {V}=\begin{bmatrix} v_{0,0} &\quad v_{0,1} &\quad \cdots &\quad v_{0,j} &\quad \cdots &\quad v_{1, m-1} \\ v_{1,0} &\quad v_{1,1} &\quad \cdots &\quad v_{1,j} &\quad \cdots &\quad v_{2, m-1} \\ \vdots &\quad \vdots &\quad \ddots &\quad \vdots &\quad \ddots &\quad \vdots \\ v_{i, 0} &\quad v_{i, 1} &\quad \cdots &\quad v_{i,j} &\quad \cdots &\quad v_{i, m-1}\\ \vdots &\quad \vdots &\quad \ddots &\quad \vdots &\quad \ddots &\quad \vdots \\ v_{n, 0} &\quad v_{n, 1} &\quad \cdots &\quad v_{n,j} &\quad \cdots &\quad v_{n, m-1}\\ \end{bmatrix} \tag{8}\end{align*}

The cost value $v_{i,j}$ for the region $\text {sq}_{i,j}$ can be calculated using Equation 9:\begin{equation*} v_{i,j}=\int _{l_{i, j}}^{l_{i, j+1}} f\left ({s_{\text {ob}}^{i}, l}\right) \text {d} l \tag{9}\end{equation*} where the relation between $l_{i, j}$ and $l_{i, j+1}$ can be represented as Equation 10:\begin{equation*} l_{i, j}-l_{i, j+1}=\frac {2 l_{\text {rw}}}{m} \tag{10}\end{equation*}

$l_{\text {rw}}$ is the coordinate of road up boundary in $l$ direction.

The rows of matrix $\mathbf {D}$ represent the set of number of waypoints for each region in the $l$ -direction of every obstacle.\begin{align*} \mathbf {D}=\begin{bmatrix} d_{0,0} &\quad d_{0,1} &\quad \cdots &\quad d_{0,j} &\quad \cdots &\quad d_{1, m-1} \\ d_{1,0} &\quad d_{1,1} &\quad \cdots &\quad d_{1,j} &\quad \cdots &\quad d_{2, m-1} \\ \vdots &\quad \vdots &\quad \ddots &\quad \vdots &\quad \ddots &\quad \vdots \\ d_{i, 0} &\quad d_{i, 1} &\quad \cdots &\quad d_{i,j} &\quad \cdots &\quad d_{i, m-1}\\ \vdots &\quad \vdots &\quad \ddots &\quad \vdots &\quad \ddots &\quad \vdots \\ d_{n, 0} &\quad d_{n, 1} &\quad \cdots &\quad d_{n,j} &\quad \cdots &\quad d_{n, m-1}\\ \end{bmatrix} \tag{11}\end{align*}

The number of waypoints for each region can be calculated using Equation 12:\begin{equation*} d_{i,j}=\text {Round}\left({\text {U} \cdot \left ({1-\frac {v_{i,j}}{\text {max}(\mathbf {V}(i,:))}}\right)}\right) \tag{12}\end{equation*} where U is a constant which is the basic sampling resolution of each region.

Finally, the output of the number of sampling waypoints is controlled through gate matrix $\mathbf {D}$ and contained in the matrix $\mathbf {N}$ :\begin{equation*} \mathbf {N}=\mathbf {B} \odot \mathbf {D} \tag{13}\end{equation*}

As shown in Figure 6, for obstacles at different positions, this method is able to perform $l$ -direction sampling. Moreover, there are no waypoints sampled in the region occupied by obstacles. As the regions approach the obstacles, the number of sampling points decreases, while it increases in regions farther away from the obstacles. The sampling result is shown in Figure 2 (c). In the obstacle region, the sampled waypoints are distributed around the obstacles, and in the non-obstacle region, the sampled waypoints are evenly distributed along the $l$ direction. Most of the generated paths are collision-free with obstacles. These results show that this adaptive sampling method can provide a better and more effective solution set for the optimal path selection.

FIGURE 6.

Distribution of waypoints in $l$ -direction around obstacles.

D. The Coarse Path Generation

1) Path Set Generation

Given that the quintic polynomial curve model can effectively fit complex path shapes and possesses first and second-order differentiability, ensuring path continuity, we utilize it to model the coarse solution of the planned path in the Frenet coordinate system, as shown in Equation 14:\begin{equation*} z(s)=c_{0}+c_{1} s+c_{2} s^{2}+c_{3} s^{3}+c_{4} s^{4}+c_{5} s^{5} \tag{14}\end{equation*}

$c_{0}$ , $c_{1}$ , $c_{2}$ , $c_{3}$ , $c_{4}$ and $c_{5}$ are the coefficients of a quintic polynomial.

$z^{\prime }(s)$ is the derivative of Equation 14 with respect to $s$ :\begin{equation*} z^{\prime }(s)=c_{1}+2 c_{2} s+3 c_{3} s^{2}+4 c_{4} s^{3}+5 c_{5} s^{4} \tag{15}\end{equation*}

$z^{\prime \prime }(s)$ is the second-order derivative of Equation 14 with respect to $s$ :\begin{equation*} z^{\prime \prime }(s)=2 c_{2}+6 c_{3} s+12 c_{4} s^{2}+20 c_{5} s^{3} \tag{16}\end{equation*}

The matrix of coefficients can be calculated by introducing the known statuses of the waypoints at both ends of a quintic polynomial curve to Equation 17:\begin{align*} \begin{pmatrix} c_{0} \\ c_{1} \\ c_{2} \\ c_{3} \\ c_{4} \\ c_{5} \end{pmatrix}=\begin{pmatrix} 1 &\, s_{\text {s}} &\, s_{\text {s}}{ }^{2} &\, s_{\text {s}}{ }^{3} &\, s_{\text {s}}{ }^{4} &\, s_{\text {s}}{ }^{5} \\ 0 &\, 1 &\, 2\, s_{\text {s}} &\, 3\, s_{\text {s}}{ }^{2} &\, 4\, s_{\text {s}}{ }^{3} &\, 5\, s_{\text {s}}{ }^{4} \\ 0 &\, 0 &\, 2 &\, 6\, s_{\text {s}} &\, 12\, s_{\text {s}}{ }^{2} &\, 20\, s_{\text {s}}{ }^{3} \\ 1 &\, s_{\text {e}} &\, s_{\text {e}}{ }^{2} &\, s_{\text {e}}{ }^{3} &\, s_{\text {e}}{ }^{4} &\, s_{\text {e}}{ }^{5} \\ 0 &\, 1 &\, 2\, s_{\text {e}} &\, 3\, s_{\text {e}}{ }^{2} &\, 4\, s_{\text {e}}{ }^{3} &\, 5\, s_{\text {e}}{ }^{4} \\ 0 &\, 0 &\, 2 &\, 6\, s_{\text {e}} &\, 12\, s_{\text {e}}{ }^{2} &\, 20\, s_{\text {e}}{ }^{3} \end{pmatrix}^{-1}\begin{pmatrix} z\left ({s_{\text {s}}}\right) \\ z^{\prime }\left ({s_{\text {s}}}\right) \\ z^{\prime \prime }\left ({s_{\text {s}}}\right) \\ z\left ({s_{\text {e}}}\right) \\ z^{\prime }\left ({s_{\text {e}}}\right) \\ z^{\prime \prime }\left ({s_{\text {e}}}\right) \end{pmatrix} \\ \, \tag{17}\end{align*} where $s_{\text {s}}$ is the coordinate of the starting point of the curve in the $s$ -axis; $s_{\text {e}}$ is the coordinate of the ending point of the curve in the $s$ -axis.

2) Path Collision Check

We conduct collision detection and curvature verification to ensure the feasibility, safety, and compliance with the vehicle kinematics of the generated paths. To ensure the accuracy of the detection results, all the processes are performed in the Cartesian frame which is transformed from the Frenet frame using Equation 1.

The purpose of the path check is to evaluate whether each waypoint along the path satisfies the constraints. Therefore, the collision check for the path can be expressed as follows:\begin{equation*} \left ({x_{h,g}-x^{i}_{\text {ob}}}\right)^{2}+\left ({y_{h,g}-y^{i}_{\text {ob}}}\right)^{2}< \left ({r_{\text {ev}}+r^{i}_{\text {ob}}}\right)^{2} \tag{18}\end{equation*} where $(x^{i}_{\text {ob}},y^{i}_{\text {ob}})$ is the coordinates of the obstacle $i$ in the Cartesian frame; $(x_{h,g},y_{h,g})$ are the coordinates of the waypoint $h$ on the path $g$ in the Cartesian Frame; $r_{\text {ev}}$ is the radius of the circle bounding box of the ego vehicle.

The curvature of a path can be computed from Equation 1. By imposing hard constraints on path curvature, the generated path is guaranteed to comply with the vehicle’s kinematic limitations.\begin{equation*} \kappa _{h,g} \leqslant \kappa _{\max } \tag{19}\end{equation*} In Equation 19, $\kappa _{\max }$ represents the maximum allowed curvature.

3) Cost Function

After obtaining a set of candidate navigable paths, the selection of the optimal path involves some subjectivity. In this paper, the definition of the coarse path is based on three aspects: resistance to deviation from the road center line, path smoothness, and the safety of the path. A cost function is formulated to quantify the optimality of a given path, where a smaller cost value indicates better path performance.\begin{equation*} J_{g}(s)= w_{3} J_{offset}(s) + w_{4} J_{smooth}(s) + w_{5} J_{safety}(s) \tag{20}\end{equation*} where $J_{offset}$ , $J_{smooth}$ and $J_{safety}(s)$ are the cost function of the offset from the road center line, the path smoothness and the safety of the path, respectively, and $w_{3}$ , $w_{4}$ and $w_{5}$ represent the weight coefficients for anti-deviation from road center line, path smoothness and path safety, respectively.

The indicator for anti-deviation allows the vehicle to actively return to the center of the lane after avoiding obstacles, avoiding potential issues such as insufficient space for subsequent obstacle avoidance or misjudgments of other traffic participants.\begin{equation*} J_{\text {offset}}(s) = \int _{s_{\text {init}}}^{s_{\text {end}}} z^{2}(s) \text {d} s \tag{21}\end{equation*} where $s_{init}$ denotes the coordinate of the starting point of the generated coarse path in the $s$ -axis, and $s_{end}$ denotes the coordinate of the endpoint of the generated coarse path in the $s$ -axis.

The indicator for path smoothness requires the generated path to be smooth, continuous, and avoid small oscillations. A path with good smoothness reduces the difficulty of path tracking in the subsequent control module and ensures the comfort of autonomous driving.\begin{equation*} J_{\text {smooth}}(s) = \int _{s_{\text {init}}}^{s_{\text {end}}} (z^{\prime 2}(s) + z^{\prime \prime 2}(s) + z^{ \prime \prime \prime 2}(s))\text {d} s \tag{22}\end{equation*} where $z^{\prime \prime \prime }(s)$ is the third-order derivative of Equation 14 with respect to $s$ .

Although all navigable paths are collision-free, some paths are close to obstacles, while others are far away from obstacles. Additionally, some paths are close to larger obstacles, while others are close to smaller obstacles. Clearly, the safety of these paths is different. Therefore, the evaluation of path safety mainly considers the size of obstacles and the distance between obstacles and the planned path in the $l$ direction. The cost function of path safety is denoted as Equation 23:\begin{equation*} J_{\text {safety}}(s) = \sum _{i=0}^{n} \frac {r_{\text {ob}}^{i}}{\int _{s_{\text {init }}}^{s_{\text {end }}}\left |{z(s)-l_{\text {ob}}^{i}}\right | d s} \tag{23}\end{equation*}

E. The Optimal Path Generation

In the previous section, the coarse path obtained is composed of connected segments of quintic polynomial curves, which may result in discontinuities and a lack of smoothness at the connection points of adjacent curves. Additionally, the representation of the path shape is constrained by the quintic polynomial curve model. To address these two issues, in this section, we re-model the path using the Taylor series, aiming to free the expression of the optimal path from the constraints of the curve model and apply quadratic programming to polish the coarse path to obtain the optimal path.

1) Path Model Formulation

The Taylor series formula for a function $f(x)$ expanded around a point $a$ with $n$ continuous derivatives can be expressed as Equation 24:\begin{align*}f(x)= & f(a)+f^{\prime}(a)(x-a)+\frac{f^{\prime \prime}(a)}{2 !}(x-a)^2 \\ & +\frac{f^{\prime \prime \prime}(a)}{3 !}(x-a)^3+\ldots+\frac{f^{(n)}(a)}{n !}(x-a)^n+R_n(x) \\ \, \tag{24}\end{align*} where $f^{\prime}(a)$ , $f^{\prime \prime}(a)$ , $f^{\prime \prime \prime}(a)$ ,…, $f^{(n)}(a)$ are the first, second, third, up to $n$ th derivatives of the function evaluated at point $a$ , and $R_{n}(x)$ represents the remainder term, which is an infinitesimal quantity and indicates the error between the $n$ th-order Taylor series and the original function $f(x)$ .

Any function can be approximated using the Taylor series expansion, therefore, assuming the expression of the path is a function of $l$ with respect to $s$ , and this function possesses third-order differentiability, if $a=s_{k}$ , the coordinate relationship between waypoint $(k+1)$ and waypoint $k$ can be approximated as Equation 25:\begin{equation*} l(s_{k+1}) = l(s_{k}) + l^{\prime}(s_{k})\Delta s + \frac {l^{\prime \prime}(s_{k})}{2!}\Delta s^{2} + \frac {l^{\prime \prime \prime}(s_{k})}{3!}\Delta s^{3} \tag{25}\end{equation*} where $\Delta s = s_{k+1}-s_{k}$ ;

According to the definition of the derivative, $l^{\prime \prime \prime}(s_{k})$ can be also approximately represented as follows:\begin{equation*} l^{\prime \prime \prime}(s_{k}) = \frac {l^{\prime \prime}(s_{k+1})-l^{\prime \prime}(s_{k})}{\Delta s} \tag{26}\end{equation*}

It is clear that the state of waypoints $k$ , $k \in [0, N]$ can be described as $[l(s_{k}), l^{\prime}(s_{k}), l^{\prime \prime}(s_{k})]$ . Thus, through further deformation of Equation 25, the relationship between states of waypoint $k$ and waypoint $(k+1)$ can be expressed as follows:\begin{equation*} \left (x_{h, g}-x_{\mathrm{ob}}^i\right)^2+\left(y_{h, g}-y_{\mathrm{ob}}^i\right)^2 < \left(r_{\mathrm{ev}}+r_{\mathrm{ob}}^i\right)^2 \tag{27}\end{equation*} where $T$ denotes matrix transpose.

Theoretically, a path consists of a series of waypoints. By adopting this chain-based approach, this paper establishes the spatial relationship between the current waypoint and the next one, thereby constructing a new road model that is not limited by the constraints of the conventional curve model.

2) The Optimization Objective Function

To fine-tune the coarse path, the objective function first takes into account the result of the coarse path generation to ensure the optimal path is as close as possible. Meanwhile, in order to avoid the occurrence of repeated small oscillations near the coarse solution during the fitting process of the optimal path (similar to Runge’s phenomenon) the objective function also needs to consider the smoothness of the path. Additionally, similarly to the cost function in Section IV-D3, to prevent long-term lane departure after obstacle avoidance, the vehicle’s deviation from the road center line is also taken into account. The objective function is shown as Equation 28:\begin{equation*} J_{\text {op}}(s)= w_{6} J_{\text {op}}^{\text {coarse}}(s) + w_{7} J_{\text {op}}^{\text {smooth}}(s) + w_{8} J_{\text {op}}^{\text {offset}}(s) \tag{28}\end{equation*} where $J_{\text {op}}^{\text {coarse}}$ is the indicator of the gap between the coarse path and the optimal path, $J_{\text {op}}^{\text {offset}}$ is the indicator of the deviation from the road center line, $J_{\text {op}}^{\text {smoothness}}$ is the indicator of the smoothness of the optimal path, and $w_{6}$ , $w_{7}$ and $w_{8}$ are the coefficients of the above three indicators, respectively.

The indicator $J_{\text {op}}^{\text {coarse}}$ is used to minimize the gap between the coarse path and the optimal path, as shown in Equation 29:\begin{equation*} J^{\text {coarse}}_{\text {op}}(s) = \sum {(l(s_{k})-z(s_{k}))^{2}} \tag{29}\end{equation*}

The indicator $J_{\text {op}}^{\text {smoothness}}$ is used to guarantee the smoothness and continuity of the optimal path through constraining the first-order, second-order, and third-order derivatives of the function $l$ , and expects the change amplitude of the planned path in the $l$ direction to be as small as possible, and the change frequency as low as possible.\begin{equation*} J_{\text {op}}^{\text {smooth}}(s) = \sum {(l^{\prime 2}(s_{k})+l^{\prime \prime 2}(s_{k})+l^{\prime \prime \prime 2}(s_{k}))} \tag{30}\end{equation*}

The indicator $J_{\text {op}}^{\text {offset}}$ can be represented by Equation 31:\begin{equation*} J_{\text {op}}^{\text {offset}}(s) = \sum {l^{2}(s_{k})} \tag{31}\end{equation*}

3) Path Constraint

Our method focuses on constraining the starting waypoint coordinates of the planned path and the value ranges of waypoint coordinates in the $l$ direction. Assuming that cycles of the planning and control modules are synchronized, and the control module perfectly tracks the previously planned path, the starting waypoint of the planned path aligns with the current position of the autonomous vehicle, as shown in Equation 32:\begin{align*} \begin{cases} \displaystyle s_{0}=s_{\text {ev}} \\ \displaystyle l\left ({s_{0}}\right)=l_{\text {ev}} \end{cases} \tag{32}\end{align*} where $(s_{\text {ev}},l_{\text {ev}})$ are the coordinates of the ego vehicle in the Frenet frame.

As shown in Figure 2 (d), a navigable tube can be generated based on the coarse path’s routing and the distribution of obstacles. Therefore, the upper boundary $ub_{k}$ and lower boundary $lb_{k}$ of this navigable tube constitute the range of coordinates of the optimal path in the $l$ direction.\begin{align*} \begin{cases} \displaystyle l\left ({s_{k}}\right) \leqslant {ub}_{k}-\frac {w_{\text {ev}}}{2} \\ \displaystyle l\left ({s_{k}}\right) \geqslant {lb}_{k}+\frac {w_{\text {ev}}}{2} \end{cases} \tag{33}\end{align*} where $w_{\text {ev}}$ is the width of the ego vehicle.

SECTION V. Simulation Results and Analysis

In path planning research, it is commonly assumed that the map, localization of obstacles and ego vehicle, and detection information such as obstacle size, road lane, traffic lights, and traffic participant, have been successfully acquired without delving into the detailed implementation of front-end module functionalities in autonomous driving systems. To gauge the performance of spatial path planning, we compare the conventional method adopted by [51] and [52] with the adaptive method proposed in this paper. The simulations are performed in Matlab on an Intel Core i7 at 3.00 GHz. Basic parametric settings are listed in Table 2.

TABLE 2 Basic Experimental Parameters

In the simulation, we first analyze the relationship between the number of sampled waypoints and the number of generated candidate paths considering the number of obstacles, both in the conventional method and the proposed approach. In addition, we compare the efficiency of generating the navigable path solution set between the conventional method and our proposed method. Finally, we compare the optimal paths generated by the two different methods and the average run time in scenarios with the same and different obstacle sizes.

A. Sampling Performance Comparison

As shown in Figure 8, for the conventional method, the quantity of sampling points remains constant regardless of variations in the number of obstacles in the traffic scenario. In contrast, in our proposed adaptive method, the number of sampling points dynamically increases as the number of obstacles increases. When there are fewer than three obstacles, the adaptive method samples fewer waypoints than conventional methods, while it samples more waypoints when there are four obstacles. The results show that the adaptive algorithm can dynamically adjust the number of sampled waypoints based on different traffic scenarios. As obstacle quantity increases and road scenes become more complex, increasing sampling points allows for a more precise evaluation of discretized traffic scenarios and actively prepares for path planning tasks.

FIGURE 7.

Path checking process overview.

FIGURE 8.

The number of sampling waypoints varies with different numbers of obstacles.

Figure 9 compares the conventional method and the adaptive approach proposed in this paper regarding the number of generated paths when facing changes in obstacle quantity. For the conventional method, since it does not adjust the number and distribution of sampling waypoints according to variations in road scenes, the number of candidate paths remains constant. However, as depicted in Figure 8, the adaptive method generates an increasing number of candidate paths as the number of obstacles increases. Remarkably, even in road scenarios with two or three obstacles, the generated number of paths is more than that of conventional methods despite the number of sampling points being less than the number of points used by traditional methods. This is because our adaptive method can adjust the distribution of sampling waypoints in response to changes in road scenarios and effectively allocate limited sampling resources as much as possible to areas with obstacles. Consequently, this results in a more extensive and precise path set for the selection of obstacle avoidance.

FIGURE 9.

The number of generated paths varies with different numbers of obstacles.

As spatial sampling aims to provide a comprehensive and efficient solution space for coarse path selection, it requires generating paths with as many navigable road segments as possible. This paper evaluates the effectiveness of the sampling using Equation 34.\begin{equation*} E = \frac {\alpha }{\beta } \tag{34}\end{equation*} where $E$ is the effectiveness rate; $\alpha $ is the number of collision-free paths; $\beta $ is the number of all generated paths.

As shown in Table 3, as the number of obstacles increases, the conventional method produces more collision paths and significantly decreases the sampling effectiveness. When there are four obstacles, the sampling effectiveness drops to 54.14%. In contrast, as the number of obstacles increases in the road scene, the proposed adaptive method only slightly increases the number of collision paths while maintaining a sampling effectiveness of 99.61% in a traffic scenario with four obstacles. This is because, during sampling, the conventional method ignores the existence of obstacles and samples the entire road, with the increase in the number of obstacles, more and more waypoints are sampled in or near the obstacles. These waypoints generate many collision paths, which are meaningless and useless for generating optimal paths, wasting valuable computational resources. However, the adaptive method considers the distribution of obstacles in the road scene. It avoids ineffective waypoint sampling in areas occupied by or near obstacles. Hence, the paths in the generated set of paths are mainly collision-free, which fully utilises the limited computational resources and provides a sufficient solution for selecting optimal paths.

TABLE 3 Analysis of Spatial Sampling Effectiveness

B. The Optimal Path Comparison (Same Size of Obstacles)

As shown in Figure 10, due to different sampling methods, the optimal paths selected by the conventional and adaptive methods proposed in this paper are different. The conventional method avoids the third obstacle from its right side after avoiding the second obstacle, while the adaptive method avoids it from its left side. Between $15\, \mathrm {m}$ and 30 m, since the second and third obstacles are close to each other and the conventional method chooses to avoid the third obstacle from its right side, it requires a significant change in the current driving direction which leads to a decrease in smoothness. On the other hand, by choosing to avoid from its left side, the adaptive method can better maintain the current driving direction and achieve a smoother path. Since the adaptive method focuses on the area where the obstacles are located, it targets the sampling of the road according to the influence value of the obstacles. In contrast, the conventional method ignores the positional information of the obstacles, which leads to under-sampling the obstacle-occupied region. Consequently, it leads to insufficient smoothness of this section of the path. Additionally, between 30 m and 50 m, influenced by $J_{offset}$ , the conventional approach makes the path gradually move towards the road center and starts avoidance action when approaching the fourth obstacle causing slight oscillation in $y$ -direction. In contrast, although the adaptive algorithm also selects bypassing on the right side of the fourth obstacle but makes full use of the obstacle avoidance space between the two obstacles thereby avoiding excessive turning angle and ensuring smoothness simultaneously.

FIGURE 10.

Optimal path comparison (same size of obstacles).

As shown in Table 4, the optimal path planned by the conventional method has a total length of $65.75\, \mathrm {m}$ , while the path planned by the adaptive method is $62.27\, \mathrm {m}$ , which is 3.48% shorter than the path planned by the conventional method. Since the shorter the path, the faster the time to reach the destination and the less energy consumed, this indicates that the path generated by the adaptive method is more economical and efficient. Additionally, the maximum heading angle of the path planned by the conventional method is $0.91\, \mathrm {rad}$ . In contrast, the maximum heading angle of the path planned by the adaptive method is 0.74 rad, representing an 18.68% reduction compared to the conventional method. This observation suggests that the path generated by the adaptive method is smoother and can provide better ride comfort. Furthermore, the average run time for the conventional method is $231.43\, \mathrm {ms}$ . Since the adaptive method generates more candidate paths, the average run time is $238.27\, \mathrm {ms}$ , a slight increase of 2.96%.

TABLE 4 Performance Comparison of Length, Heading and Run Time (Same Size of Obstacles)

C. The Optimal Path Comparison (Different Sizes of Obstacles)

In this scenario, we set the four obstacles to different sizes. The lengths and widths of the bounding boxes, along with the obstacle collision radius $r_{\text {ob}}$ are shown in Table 5.

TABLE 5 Obstacle Parameters

As depicted in Figure 11, despite changes in obstacle dimensions, the optimal paths generated by both methods show relatively consistent routing compared with routing in Figure 10. Between $5\, \text {m}$ and $15\, \text {m}$ , where the first obstacle increases in size, the adaptive and conventional methods increase the steering angle to pass the obstacle from the right. This is because the space available to the left of the obstacle is reduced, making it unsafe to pass. In addition, when avoiding the third obstacle, the conventional method still chooses to pass from the right side of the obstacle. Due to the increase in the size of the first obstacle, the offset of the path in the negative direction of the $y$ -axis during obstacle avoidance increases. Simultaneously, the conventional method cannot automatically adjust the sampling resolution according to the traffic scenarios. The chosen avoidance position remains approximately the same even when the second obstacle becomes smaller, and as a result, between $15\, \text {m}$ and $25\, \text {m}$ , the degree of path bending increases further compared to the case of the same obstacle size. In contrast, the adaptive method selects to pass to the left of the third obstacle. This approach actively adjusts its sampling strategy based on varying scenarios. As the size of the fourth obstacle decreases, it adapts the avoidance strategy, resulting in a smoother path between $25\, \text {m}$ and $50\, \text {m}$ .

FIGURE 11.

Optimal path comparison (different sizes of obstacles).

As shown in Table 6, the total length of the optimal path generated by the conventional method is slightly increased to $66.65\, \text {m}$ . The total length of the optimal path generated by the adaptive method is $61.04\, \text {m}$ , which is reduced by 8.42%. This indicates that the adaptive method also shows better economy and efficiency in the scenario with different sizes of obstacles. Furthermore, the maximum heading of the path generated by the conventional method is $0.96\, \text {rad}$ . In comparison, the maximum heading angle of the optimal path generated by the adaptive method is $0.67\, \text {rad}$ , a significant reduction of 30.21%. Combined with the analysis of Figure 10, it can be seen that the path generated by the conventional method becomes more curved at $15\, \text {m}$ - $20\, \text {m}$ , which leads to a larger max heading, whereas, due to the reduced size of the fourth obstacle, the path generated by the adaptive method becomes smoother at $40\, \text {m}$ - $50\, \text {m}$ . Therefore, the max heading angle becomes smaller. However, in this case, the average running time of the conventional method is $231.91\, \text {ms}$ , while the adaptive method consumes $242.12\, \text {ms}$ . This is because when the obstacles become smaller, the space occupied also becomes smaller. Therefore, more sampling waypoints are generated in the navigable area, and then more candidate paths are generated, resulting in a rise in the running time by 4.40%.

Table 6 Performance Comparison of Length, Heading and Run Time (Different Sizes of Obstacles)

SECTION VI. Conclusion

In this paper, we present a novel algorithm for path planning. This algorithm involves three main components: spatial sampling, coarse path generation, and coarse path smoothing. In the spatial sampling stage, we propose a novel adaptive sampling approach. This method initially constructs a three-dimensional space-aware profiling map to evaluate the current road scene. Subsequently, based on the distribution of obstacles along the road’s longitudinal direction and the corresponding cost values of obstacles in the three-dimensional space-aware profiling map in the lateral direction, it generates lateral and longitudinal sampling waypoints, achieving the discretization of the road scene. In the coarse path generation stage, the defined cost function primarily considers the smoothness of the planned path, the resistance to deviation from the road center line, and the safety of the navigable paths. To free the optimal path from the representation constraints of the curve model and smooth the coarse path, we employ the Taylor series to reconstruct the road model and quadratic programming techniques for coarse path smoothing.

The experimental results demonstrate that the proposed adaptive sampling algorithm has the capability to dynamically adjust the sampling strategy of waypoints based on the quantity and distribution of obstacles within the road scenario. As obstacles increase, the number of sampled waypoints and generated paths increases. Moreover, the generated paths exhibit fewer collision paths, showcasing higher sampling effectiveness. This algorithm effectively provides a comprehensive and efficient solution set for subsequent coarse path generation. Furthermore, when the sizes of obstacles are the same, compared to conventional sampling methods, Despite a slight 2.96% increase in running time, the generated paths exhibit enhanced smoothness, more rational obstacle avoidance strategies, and a reduction of 3.48% in path length along with an 18.68% decrease in the maximum heading angle. In the scenario with different obstacle sizes, although the running time increases by 4.40%, the path length is shortened by 8.42%, and the maximum orientation angle is significantly reduced by 30.21%. The generated optimal path shows better economy, efficiency and smoothness.

In future work, we plan to further improve the spatial sampling effectiveness of the adaptive path planning method. The generated paths are collision-free if the sampling effectiveness can reach 100% in all scenarios. Therefore, the step of the path collision check can be omitted. This can significantly reduce the running time and improve the real-time performance of the algorithm.

ACKNOWLEDGMENT

The authors would like to express their sincere gratitude to the anonymous reviewers for their valuable comments and insightful suggestions, which have greatly improved the quality of this work.