1 Introduction

Greater road safety, energy efficient and environmentally friendly vehicles, safer multitasking or increased mobility for elderly and disabled people—these are just a few terms which describe the bright future of the transport system with the conditions that: 1. High level autonomous vehicles are going to be available for everyone in need; 2. High level autonomous vehicles are going to perform without any doubts regarding their reliability. While taking into consideration such ongoing policies as the Vision Zero or Green Deal, it is clear that the demand for the autonomous vehicles is unquestionably high. However, the development of the reliable 4th and 5th level autonomous vehicles is a complex and time consuming process, which involves various social and engineering sciences based research problems related to the ethics, regulations and laws, data security, control, vehicle dynamics, artificial intelligence, etc. From the reliable autonomous performance standpoint, the engineering based research problems, which consider sensing and perception, path planning or control of the autonomous vehicles, play the most significant role. According to (Katrakazas et al., 2015), critical decision making is the key to autonomy and is realised through the path planning algorithms. Similarly, the authors in (Artunedo et al., 2019) also noted that the path planning algorithms play a crucial role, as they are responsible for ensuring safe and reliable autonomous driving in a wide range of urban scenarios. Although the significance of the autonomous vehicles’ performance in various urban scenarios was understood through various research projects a relatively long time ago (Skrickij et al., 2020), however, path planning in urban scenarios is currently still in an earlier development stage (Artunedo et al., 2019). While comparing different urban scenarios it can be stated that the lane change manoeuvre is one of the critical resources of traffic accidents (Sun et al., 2021a, 2021b) and, at the same time, one of the most important conventional parts of autonomous driving (Ding et al., 2019), which remains a problematic subject from a path planning point of view. Thus, a large amount of scholars are constantly focussing on this specific lane change path planning problem and on development of new path planning approaches. Respectively, this section further gives a concise literature review of how the path planning problem for the lane change manoeuvre is being solved by various scholars.

In the research works, a variety of different path planning approaches are applied for the lane change manoeuvre: from the classical ones (geometric, graphs search, sampling or interpolation based) to the heuristic (function optimization) and artificial intelligence based approaches (machine learning, fuzzy logic, neural networks, etc.). Regarding the application of the artificial intelligence based approaches, an interesting attempt to develop an imitation learning and mixed-integer optimization based approach is presented in (Xi et al., 2020). In their work, the authors noted that a successful lane change path planner should be able to work in real-time and due to this reason paid attention to the computational time of the approach. After simulations it was determined that with a computational time of 6 ms the proposed intelligent approach outperforms most commonly used sampling and optimization based path planning approaches. In (Ibrahim et al., 2020), an intelligent dynamic approach was proposed which within 0.072 s was able to plan a path for the lane change manoeuvre and with such real-time path planning value exceeded the standard human driver response time. There is no doubt that the real-time performance capability cannot be underrated while developing path planning approaches as other researchers also point out the importance of the real-time path planning for the lane change manoeuvre (Claussmann et al., 2019; Garrido et al., 2020; Li et al., 2020; Park et al., 2019). Another interesting application of an intelligent path planning approach is described in (Geng et al., 2018). In the named research, a path planning approach based on the neural network and genetic algorithm for imitating the lane changing operation of the human drivers is described. The experimental data of the tests, which defines how the humans drivers perform the lane change manoeuvre, were used to train the neural network. The results of the study verified that the neural network and genetic algorithm based path planning can reflect the characteristics of the operations of the human driver, while performing a safe and autonomous lane change manoeuvre. A relatively different application of the neural networks for lane change path planning is analysed in (Yang & Yao, 2021). In this case instead of human driving based information, the authors used mathematically derived data. Path planning via fuzzy logic is described in (Cherroun et al., 2019). While describing the path planning based on the Q-learning algorithm and fuzzy logic, the authors made a remark that the problem of finding appropriate membership functions and fuzzy rules is a difficult task. A comparison of machine learning algorithms for lane changing intent can be found in (Choi & Lee, 2021). Despite the fact that the use of various intelligent approaches while solving the path planning problem for the lane change manoeuvre is quite common (Gao et al., 2021; Jo et al., 2021; Song et al., 2020), it is important to note that, in the detailed comparative analysis, Claussmann et al., (2019) summarized that artificial intelligence based approaches only seem to be highly promising for the near future. In the current days, these approaches lack feedback in real driving scenarios.

While further considering the application of the heuristic approaches, mostly nature-inspired optimization algorithms, such as genetic algorithms, ant colony optimization, particle swarm optimization or bee colony optimization, are used to solve the path planning problems (Ayawli et al., 2018; Precup et al., 2021). For example, while having in mind safety and real-time performance of the autonomous vehicle during various urban scenarios, for the optimization of weight coefficients of the heading angle and the path velocity, Han et al. (2016) proposed a combination of the particle swarm optimization and the competition behaviour algorithm. The results of the simulations showed that the particle swarm optimization method and its fitness function can eliminate the perturbations of the path planning and improve a reliable real-time performance. To optimize the target speed and target steering angle during the lane change manoeuvre, in the (Song & Huh, 2021) a micro-genetic algorithm together with the model predictive control was suggested. In the suggested approach, specifically, the micro-genetic algorithm was applied, because it is able to guarantee a better real-time performance by using smaller population than the non-modified genetic algorithm. Other types of optimization algorithms, like dynamic optimization, in the research works are used more rarely. An example of the dynamic optimization based path planning for the lane change manoeuvre is provided in (Li et al., 2019a, 2019b). In the work, it was noticed that the constrained dynamic optimization approach is not directly applicable to actual on-road autonomous movement cases. According to (Ayawli et al., 2018), the main strength of the heuristic and nature-inspired optimization algorithms is that they are good at providing learning and generalization. Furthermore, they are good at solving path planning problems that are difficult dealing with using conventional approaches. However, while seeking to apply optimization-based techniques for actual real-time autonomous movement, an extensive number of weaknesses must be taken into account: slow convergence speed, premature convergence, high computing power requirement, oscillation, difficulty in choosing initial positions, and the requirement of large data set of the environment which is difficult to obtain (Ayawli et al., 2018). Thus, to apply the heuristic and nature-inspired optimization algorithms for real-time path planning, firstly named limitations should be eliminated.

The application of the classical path planning methods is the most popular between the researchers. The authors in (Yang et al., 2018) proposed a novel dynamic lane-changing path planning model by adopting time-independent polynomial equations to characterize the lane-changing trajectory curve, which can avoid the unrealistic assumptions on velocity and acceleration. More specifically—a cubic polynomial curve was adopted. According to the authors, this type of curve has the second order smoothness and, compared to higher order polynomial functions, it has fewer model parameters, so it needs less information to determine the parameters of the function. The application of the classical approaches, based on splines or various polynomial curves, is efficient from the real-time performance point of view. In (Funke & Gerdes, 2016) for the lane change manoeuvre path planning the authors applied the clothoid curves method and demonstrated that, while using this method, the autonomous vehicle can perform emergency lane changes up to the friction limits through real-time path generation. The feasibility of the planned path for the lane change manoeuvre, together with the real-time performance and efficiency, is the fundamental requirement (Dixit et al., 2018; Wang et al., 2019). An integrated application of two classical approaches—B-spline curves and rapidly exploring random trees is presented in (Sun et al., 2021a, 2021b). During this integrated application of different classical approaches, the bidirectional rapidly exploring random trees path planning method for primary path planning was used. The Cubic B-spline curve was used to optimize the planned primary path to make the path’s curvature continuous and feasible for the autonomous vehicle. It is worth mentioning that, due to its support for high dimensional complex problems, the rapidly exploring random trees approach gained immense popularity and, in the research works, currently a number of various modified rapidly exploring random trees based approaches exists (Noreen et al., 2016). While comparing the application of the classical path planning approaches for the lane change manoeuvre, the Bézier curves is the most prominent approach. The Bézier curves are good for real-time implementation, and the computational cost of designing them is lower than the clothoid curves or splines curves (Lattarulo et al., 2018). The Bézier curves are also continuous geometrically. Nonetheless, the Bézier curves approach also has its limitations: high order Bezier curves can become unstable and increases the complexity of the approach; it does not take into consideration vehicle dynamics; coordinates of the control points should also be selected properly. Thus, while developing efficient path planners, the use of the Bézier curves is mostly related to the development of possible ways of how to overcome these named limitations. For example, in order to reduce the order of the Bézier curve, the authors in (Long et al., 2019) used 3rd order Bézier curves and path for the lane change manoeuvre combined from two asymmetrical Bézier curves. In (Korzeniowski & Slaski, 2016) for a single lane change manoeuvre path planning the authors combined two symmetrical 3rd order Bezier curves, but additionally optionally supplemented those curves with a straight lane connector. A similar idea to combine symmetrical curves was also adapted in (Chen et al., 2013). In this case, while combining two symmetrical Bézier curves for the lane change manoeuvre, the authors used even lower—2nd order Bézier curves. Examples of 5th order Bezier curves application can be found in (Bae et al., 2019) and (Li et al., 2019a, 2019b). As in these two works relatively higher order Bézier curves were used, more attention was paid to the curve shapes, control points determination and smooth autonomous motion.

From the performed literature review it can be noticed that all of the different path planning approaches, applied to the lane change manoeuvre, have their own limitations, which researchers constantly try to overcome. From the performed literature review it can be also noticed that one of the main ways to overcome various limitations is to use two or more different path planning approaches at the same time and to combine the properties of these used different approaches, i.e. to develop the so-called hybrid path planning approaches. According to (Ayawli et al., 2018), possibly hybrid approaches that possess the ability to take advantage of the benefits and reduce the limitations of each of the methods involved can be considered to obtain better techniques for path planning. However, there are still various challenges while using hybrid approaches. Thus, further efforts should be made to develop and implement various hybrid path planning approaches in real-life autonomous driving scenarios. Due to the named reasons, the main aim of this work is to develop a new and efficient hybrid path planning approach, based on the Bézier curves and rapidly exploring random trees, which would have proper real-time performance and would be able plan feasible paths for the lane change manoeuvre.

The remainder of this work is organized as follows. In section II, the development of new hybrid path planning approach is described. Section III describes the experimental implementation of the proposed hybrid approach. Section IV presents the analysis and discussion part of the work. The final section presents the conclusions of the work.

2 Novel Hybrid Path Planning Approach

Derived from the general properties of the Bézier curves and rapidly exploring random trees approaches, the suggested new application principle of these approaches is defined as this—the lane change manoeuvre is planned by applying the Bézier curves approach, uncertainties of which are solved by using the rapidly exploring random trees approach. The framework of the suggested new application principle of these approaches is provided in Fig. 1. The scheme of the lane change manoeuvre is provided in Fig. 2.

Fig. 1
figure 1

Framework of the proposed hybrid path planning approach

Full size image
Fig. 2
figure 2

Scheme of the lane change manoeuvre, while the surrounding vehicle is dynamic

Full size image

According to the provided framework (Fig. 1), if there is a demand for the lane change manoeuvre or obstacle avoidance, initially, while considering the velocities of the autonomous vehicle and the surrounding vehicle, the hybrid path planner must calculate distances, required to perform the lane change manoeuvre safely. Real-time path planning for the lane change manoeuvre will start only when the requirement to reach the safe longitudinal distance is going to be satisfied. Such structure of the hybrid planner allows to perform space availability checking, as it must be done before the actual path planning begins. In the proposed hybrid planner, the lane change manoeuvre curvature is going to be generated while using the Bézier curves approach. This means that the Bézier curves approach is going to serve as a primary planner. The rapidly exploring random trees approach is going to be used as a supplementary planner in order to define the coordinates of the specific control points for the Bézier curve. In the next step, based on the generated curvature, steering angle values, which are required to steer and control the autonomous vehicle, are going to be calculated. Finally, in either case—successful or unsuccessful performance of the autonomous vehicle, outcome results are going to be used to further perform decision-making.

To start the development of the hybrid path planning approach, these assumptions are made:

  1. 1.

    Before beginning the lane change manoeuvre, the autonomous vehicle is moving in a straight line with a constant velocity (\(v_{av} = {\text{const}}.\)). The initial movement axis of the autonomous vehicle is always longitudinal. If there is an obstacle (surrounding vehicle) ahead of the autonomous vehicle, the initial and final movement axes of the autonomous vehicle and the surrounding vehicle coincide or are parallel;

  2. 2.

    The surrounding vehicle that is ahead of the autonomous vehicle can either be static (\(v_{sv} = 0\) m/s) or dynamic, i.e. moving (\(v_{sv} > 0\) m/s). The velocity of the dynamic surrounding vehicle is constant (\(v_{sv} = {\text{const}}.\)), but lower than the velocity of the autonomous vehicle (\(0 \le v_{sv} < v_{av}\));

  3. 3.

    In the case of the dynamic surrounding vehicle, it can only move in a straight line, the movement axis is always longitudinal. The movement direction of the surrounding vehicle cannot change;

Environment can be either—structured or unstructured. Widths of the driving lanes, width and velocity of the surrounding vehicle, etc., are known.

Primarily, to avoid a collision with the static or dynamic surrounding vehicle, a safe longitudinal distance between the autonomous vehicle and surrounding vehicle is determined, at which the lane change can begin:

$$S_0 = S{\,}_{\min } + S_D = \left( {v_{av} - v_{sv} } \right) \cdot t_m + \left( {v_{av} \cdot t_d } \right) + S_D$$
(1)

where \(S_{\min }\) represents the minimal allowed distance between the autonomous vehicle and surrounding vehicle.

Taking into account that the manoeuvre is performed by the autonomous vehicle, it can be stated that the assumed time length of the lane change manoeuvre \(t_m\) consists of the path planning approach performance time, which is needed to plan the path, and time, which is needed to perform the manoeuvre. According to (Chen et al., 2013), while developing the path planner it can be assumed that usual time length to perform the lane change manoeuvre varies from 5.2 s to 7.3 s. Furthermore, at this stage of the hybrid path planning approach development process, there is no possibility to anticipate the algorithm’s delay time \(t_d\) of the performance. Thus, it is assumed that the delay time \(t_d\) cannot be larger than 1 s.

Secondly, space checking in lateral direction is performed:

$$S_L = S_D + \left( {\frac{{W_{av} }}{2} + \frac{{W_{sv} }}{2}} \right)$$
(2)

If the surrounding vehicle is dynamic, the longitudinal distance after which the autonomous vehicle will catch up to the surrounding vehicle moving with a constant velocity \(v_{sv}\) and will start to overtake it, is determined:

$$S_1 = \frac{{S_0 \cdot v_{sv} }}{{v_{av} - v_{sv} }} + S_0$$
(3)

The longitudinal distance after which the autonomous vehicle has to finish the movement in a Bézier curve:

$$S_2 = \frac{{S_0 \cdot v_{sv} }}{{v_{av} - v_{sv} }} + S_{\min }$$
(4)

It is very important to clearly understand the meaning of the difference between the distances \(S_1\) and \(S_2\). In the planner it is assumed that the lane change itself must be finished after completing the longitudinal distance \(S_2\). The remaining safety distance \(S_D\) is completed with the autonomous vehicle moving, when its movement axis and the surrounding vehicle’s movement axis are parallel (Fig. 2), i.e. both vehicles are already moving in parallel straight lines. This assumption was made while seeking to avoid any unexpected collisions with the surrounding vehicle, when the lane change manoeuvre is still being performed. The results of these described equations is going to further serve as an initial data for the Bézier curves and rapidly exploring random trees approaches.

2.1 Application of the Bézier Curves Approach

The Bézier curves are parametric curves represented by the Bernstein polynomials \(B_i\) and a number of selected control points \({\textbf{P}}_i\), which define the shape of the curve. General expression of the Bézier curve can be written as:

$${\textbf{P}}\left( {t_B } \right) = \sum_{i = 1}^n {{\textbf{P}}_i B_{i,n} \left( {t_B } \right)} = \sum_{i = 1}^n {{\textbf{P}}_i \cdot \frac{n!}{{i!\left( {n - i} \right)!}}t^i \left( {1 - t_B } \right)^{n - i} }$$
(5)

where \(n\) represents the order (degree) of the Bézier curve and \(i\) represents the number of the control points for the Bézier curve \(\left( {i = n + 1} \right)\).

To efficiently apply the Bézier curves a number of various properties of this approach must be carefully taken into consideration (Long et al., 2019):

  1. 1.

    The curve always lies within the convex hull formed by the selected control points \({\textbf{P}}_i\);

  2. 2.

    The curve will follow the shape of the control polygon, which consists of the segments joining all of the selected control points \({\textbf{P}}_i\);

  3. 3.

    The curve will start at the initial control point \({\textbf{P}}_0\) and will end at the final control point \({\textbf{P}}_n\);

  4. 4.

    The first point tangent vector (at \(t_B = 0\)) will be given by \(\overline{{{\textbf{P}}_0 {\textbf{P}}_1 }}\) and the last point tangent vector (at \(t_B = 1\)) will be given by \(\overline{{{\textbf{P}}_{n - 1} {\textbf{P}}_n }}\).

The defined properties are directly related to the coordinates and the number of the control points \({\textbf{P}}_i\). Thus, it can be stated that, in this case, there are two main tasks, which need to be solved: 1. Determination of the required number of the control points \(i\), i.e. the order of the Bézier curve; 2. Determination of the coordinates for the control points \({\textbf{P}}_i\).

At this point of the development, while the required number of the control points \({\textbf{P}}_i\) is still unknown, it is only possible to determine the coordinates of the initial control point \({\textbf{P}}_0\) and final control point \({\textbf{P}}_n\). It is assumed that the initial control point \({\textbf{P}}_0\) coincides with the origin point of the 2D Cartesian coordinate system. Due to this reason, the initial control point \({\textbf{P}}_0\) of the Bézier curve can be defined as \({\textbf{P}}_0 \left( {0;0} \right)\). While the lane change manoeuvre must be finished after the autonomous vehicle completes driving the longitudinal distance \(S_2\), the coordinates of the final control point \({\textbf{P}}_n\) can be written as:

$${\textbf{P}}_n \left( {S_2 ; S_D + \frac{{W_{av} + W_{sv} }}{2}} \right)$$
(6)

While further taking into consideration the assumption that the lane change manoeuvre must be finished after the autonomous vehicle completes driving the longitudinal distance \(S_2\), and the remaining safety distance \(S_D\) is completed while the autonomous vehicle is moving in a straight line, also while regarding the property that the first point tangent vector will be given by \(\overline{{{\textbf{P}}_0 {\textbf{P}}_1 }}\) and the last point tangent vector will be given by \(\overline{{{\textbf{P}}_{n - 1} {\textbf{P}}_n }}\), it is clear that the path for the lane change manoeuvre can be planned while applying the 3rd or 5th order Bézier curves. Based on the Eq. 5, 3rd order Bézier curve is expressed as:

$$\begin{array}{*{20}c} {{\textbf{P}}\left( {t_B } \right) = \left( {1 - t_B } \right)^3 {\textbf{P}}_0 + 3 \cdot t_B \cdot \left( {1 - t_B } \right)^2 {\textbf{P}}_1 + 3 \cdot t_B^2 \cdot } \\ { \cdot \left( {1 - t_B } \right){\textbf{P}}_2 + t_B^3 \cdot {\textbf{P}}_3 } \\ \end{array}$$
(7)

Similarly, the 5th order Bézier Curve is expressed as:

$$\begin{array}{*{20}c} {{\textbf{P}}\left( {t_B } \right) = \left( {1 - t_B } \right)^5 {\textbf{P}}_0 + 5 \cdot t_B \cdot \left( {1 - t_B } \right)^4 {\textbf{P}}_1 + 10 \cdot t_B^2 \cdot \left( {1 - } \right.} \\ { - \left. {t_B } \right)^3 \cdot {\textbf{P}}_2 + 10 \cdot t_B^3 \cdot \left( {1 - t_B } \right)^2 {\textbf{P}}_3 + 5 \cdot t_B^4 \cdot \left( {1 - t_B } \right){\textbf{P}}_4 + t_B^5 \cdot {\textbf{P}}_5 } \\ \end{array}$$
(8)

The main difference between the 3rd and 5th order Bézier curves application for the lane change manoeuvre path planning is that, while applying the 3rd order curve, the beginning and end of the manoeuvre path are going to be described by two control points, respectively (beginning: \({\textbf{P}}_0 ,\,\,{\textbf{P}}_1\), end: \({\textbf{P}}_2 ,\,\,{\textbf{P}}_3\)) and while applying the 5th order curve, the beginning and end of the path are going to be described by three control points, respectively (beginning: \({\textbf{P}}_0 ,\,\,{\textbf{P}}_1 ,\,\,{\textbf{P}}_2\), end: \({\textbf{P}}_3 ,\,\,{\textbf{P}}_4 ,\,\,{\textbf{P}}_5\)). Figure 3 represents the example of the 3rd and 5th order Bézier curves application for the lane change manoeuvre path planning.

Fig. 3
figure 3

Planned paths, which are based on the 3rd and 5th order Bézier curves: a path based on the 3rd order Bézier curve; b path based on the 5th order Bézier curve; c calculated steering angle values

Full size image

From the example in Fig. 3 it can be seen that paths based on the 3rd and 5th order Bézier curves are relatively similar—they both are smooth and continuous. Although under same conditions there are no significant differences regarding the shape of the paths, the path generated by the 3rd order equation is slightly less curved (Fig. 3, parts a and b). Due to these slightly different curves of the paths, the calculated steering angle \(\delta\) values also differ (Fig. 3, part c). It can be noticed that the steering angle \(\delta\) values, calculated while applying the 3rd order Bézier curve for the lane change manoeuvre path planning, at the beginning and end of the planned path are nonzero. Due to this reason, the curvature at the beginning and end of the path, while applying the 3rd order Bézier curve, is also nonzero. In the case of the lane change manoeuvre and while considering the non-holonomic constraints of the autonomous vehicle, nonzero steering angle \(\delta\) and curvature values at the beginning and end of the path impact the fact that the path generated while applying the 3rd order Bézier curve would be not feasible and could not be executed by the autonomous vehicle in real urban environments. The described problem is not relevant while applying the 5th order Bézier curve. Thus, to ensure feasibility of the planned path for the lane change manoeuvre, further the 5th order Bézier curve is going to be applied, which requires six control points \(\left( {n = 5,\,\,i = 6,\,\,{\textbf{P}}_n = {\textbf{P}}_5 } \right)\). As the control points \({\textbf{P}}_0\) and \({\textbf{P}}_5\) are already determined, the coordinates for the rest of the control points \(\left( {{\textbf{P}}_1 \ldots {\textbf{P}}_5 } \right)\) are going to be determined while applying the rapidly exploring random trees approach.

2.2 Application of the Rapidly Exploring Random Trees Approach

To apply the rapidly exploring random trees approach, primarily the geometrical borders \({\text{E}}_i\) of the environment, in which nodes and random tree branches are going to be generated, need to be expressed. Because the rapidly exploring random trees approach is going to be applied for the control points \({\textbf{P}}_1 \ldots {\textbf{P}}_5\) determination, it can be noted that the nodes and random tree branches should be generated within the geometrical limits of the lane change manoeuvre path. As the beginning and end of the lane change manoeuvre path are already defined by the control points \({\textbf{P}}_0\) and \({\textbf{P}}_5\), the geometrical borders \({\textbf{E}}_i\) of the environment can be expressed based on these points:

$${\textbf{E}}_i = \left\{ {\begin{array}{*{20}c} {{\textbf{E}}_1 \left( {P_{0_X } ,P_{0_Y } } \right)} \\ {{\textbf{E}}_2 \left( {P_{5_X } ,P_{0_y } } \right)} \\ {{\textbf{E}}_3 \left( {P_{0_X } ,P_{5_Y } } \right)} \\ {{\textbf{E}}_4 \left( {P_{5_X } ,P_{5_Y } } \right)} \\ \end{array} } \right.$$
(9)

In this work, while applying the rapidly exploring random trees approach, the generation and expansion of the random tree starts from the initial control point \({\textbf{P}}_0\). The goal of the random tree expansion – control point \({\textbf{P}}_5\). The curve, which in general case would represent a path planned by the rapidly exploring random trees approach, is expressed as a connection of the generated random tree branches. If, due to the selected length of the random tree branches and the selected number of the nodes \(N\), the generated random tree is not going to reach the goal point \({\textbf{P}}_5\), then the curve is obtained by connecting the final node \({\textbf{P}}_F\) of the generated random tree with the goal point \({\textbf{P}}_5\). Specifically, such case, when the generated random tree is not reaching the goal point \({\textbf{P}}_5\) is further invoked and the final node \({\textbf{P}}_F\) of the generated random tree is going to be used as a basis for the control points’ \({\textbf{P}}_1 \ldots {\textbf{P}}_5\) determination. The described application of the rapidly exploring random trees approach is shown in Fig. 4.

Fig. 4
figure 4

Example of the application of the Bézier curves and rapidly exploring random trees approaches

Full size image

Because whether the generated random tree is going to reach the goal point \({\textbf{P}}_5\) depends on the selected length of the random tree branches and the selected number of the nodes \(N\), the proper selection of these parameters is an important factor when seeking to determine the control points for the Bézier curve. To ensure the accuracy of the approach operation when generating the random tree, it is assumed that the branches of the random tree are unit vectors. Due to this assumption, whether the random tree is going to reach the goal point \({\textbf{P}}_5\) depends only on the selected number of the nodes \(N\). While taking into consideration the already provided equations, it can be noticed that the geometrical borders \({\text{E}}_i\), in which the nodes and random tree branches are going to be generated, actually depend on the velocities of the autonomous vehicle \(\left( {v_{av} } \right)\) and the surrounding vehicle \(\left( {v_{sv} } \right)\). Therefore, the number of the nodes \(N\) should be selected while considering these velocities. This can be done through the parameter \(S_{\min }\). Examples of the paths, which were planned by applying the described hybrid path planning approach and assuming that the number of the nodes \(N\) is calculated as \(N = \frac{{S_{\min } }}{4}\), \(N = \frac{{S_{\min } }}{2}\), \(N = S_{\min }\), are shown in Fig. 5.

Fig. 5
figure 5

Examples of the planned paths and steering angles \(\delta\) values, required to follow planned paths: a \(N = \frac{{S_{\min } }}{4}\); b \(N = \frac{{S_{\min } }}{2}\); c \(N = S_{\min }\).

Full size image

Path planning simulations were performed while using MATLAB/Simulink software. During the simulations, the paths were planned while considering that \(v_{av} = 5\) m/s, \(v_{sv} = 0\) m/s, control points \({\textbf{P}}_0 ,\,\,{\textbf{P}}_1 ,\,\,{\textbf{P}}_2\) and \({\textbf{P}}_3 ,\,\,{\textbf{P}}_4 ,\,\,{\textbf{P}}_5\) are distant from each other by equal lengths.

When \(N = \frac{{S_{\min } }}{4}\), 11 nodes were generated; when \(N = \frac{{S_{\min } }}{2}\), 21 nodes were generated and when \(N = S_{\min }\), 41 nodes were generated. From Fig. 5 it can be seen that the number of the generated nodes \(N\) has a significant impact on the planned lane change manoeuvre path, its shape and steering angle \(\delta\) values, required to follow the planned path. Based on the provided results it can be summarized that when \(N = \frac{{S_{\min } }}{4}\) and \(N = S_{\min }\), too sudden changes in the shape of the planned path and steering angle \(\delta\) values occur, which may result in the passengers’ discomfort (Fig. 5, parts a and c). The most consistent and smooth change of the steering angle \(\delta\) values was obtained, when \(N = \frac{{S_{\min } }}{2}\) (Fig. 5, part b). While further taking into consideration that the surrounding vehicle can be either, static or dynamic, the number of the nodes \(N\) is expressed as:

$$N = \left\{ {\begin{array}{*{20}c} {\frac{{S_{\min } }}{2} \in {\text{N}}_N ,\,\,{\text{when}}\,\,v_{sv} = 0\,\,\frac{{\text{m}}}{{\text{s}}}} \\ {\frac{S_2 }{2} \in {\text{N}}_N ,\,\,{\text{when}}\,\,v_{sv} > 0\,\,\frac{{\text{m}}}{{\text{s}}}} \\ \end{array} } \right.$$
(10)

where \({\text{N}}_N\) represents the set of all natural numbers.

To determine the control points \({\textbf{P}}_1 \ldots {\textbf{P}}_5\), it is considered that the \(x\) coordinate of the generated random tree final node \({\textbf{P}}_F\) is equal to the \(x\) coordinate of the control point \({\textbf{P}}_2\). The control point \({\textbf{P}}_1\) is the middle point between the control points \({\textbf{P}}_0\) and \({\textbf{P}}_2\). As already stated, it is assumed that the control points \({\textbf{P}}_0 ,\,\,{\textbf{P}}_1 ,\,\,{\textbf{P}}_2\) and \({\textbf{P}}_3 ,\,\,{\textbf{P}}_4 ,\,\,{\textbf{P}}_5\) are distant from each other by equal lengths, i.e. the distance between the control points \({\textbf{P}}_0\) and \({\textbf{P}}_2\) is equal to the distance between the control points \({\textbf{P}}_3\) and \({\textbf{P}}_5\). The control point \({\textbf{P}}_4\) is the middle point between the control points \({\textbf{P}}_3\) and \({\textbf{P}}_5\). Thus, the final expression for all of the control points is:

$${\textbf{P}}_i = \left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}c} {{\textbf{P}}_0 \left( {0;\,\,0} \right)} \\ {{\textbf{P}}_1 \left( {\frac{{P_{F_X } }}{2};\,\,0} \right)} \\ {{\textbf{P}}_2 \left( {P_{F_X } ;\,\,0} \right)} \\ \end{array} } \\ {\begin{array}{*{20}c} {{\textbf{P}}_3 \left( {P_{5_X } - P_{F_X } ;\,\,P_{5_Y } } \right)} \\ {{\textbf{P}}_4 \left( {P_{3_X } + \frac{{P_{5_X } - P_{3_X } }}{2};\,\,P_{5_Y } } \right)} \\ {{\textbf{P}}_5 \left( {S_2 ;\,\,S_D + \frac{{W_{av} + W_{sv} }}{2}} \right)} \\ \end{array} } \\ \end{array} } \right.$$
(11)

2.3 Extension of the Proposed Hybrid Approach

The proposed hybrid path planning approach can be easily adapted for the planning of the double-lane change manoeuvre path. To extend and adapt the approach it is assumed that the path for the double-lane change manoeuvre is symmetrical. However, in this work, it is suggested to determine not the symmetry axis of the path segments but the longitudinal distance after which the autonomous vehicle would have overtaken the surrounding vehicle in a safe longitudinal distance and would be able to begin returning to the initial movement lane. This means that only the Bézier curve, planned for the lane change manoeuvre, would be mirrored. Because the designed approach has to be suitable for driving around the static and the dynamic surrounding vehicles, it is necessary to evaluate the velocities (\(v_{av}\) and \(v_{sv}\)) and lengths of the vehicles (\(L_{av}\) and \(L_{sv}\)) when determining the longitudinal distance after which the autonomous vehicle has to begin returning to the initial movement lane. The path coordinates \(x\) of returning to the initial movement lane are expressed:

$$P_{C_x } = \left\{ {\begin{array}{*{20}c} {\begin{array}{*{20}c} { - P_x \left( {t_B } \right) + L_{av} + L_{sv} + 2 \cdot S_D + 2 \cdot P_{5_x } ,\,} \\ {\,{\text{when}}\,\,v_{sv} = 0\,\frac{m}{s}} \\ \end{array} } \\ {\begin{array}{*{20}c} { - P_x \left( {t_B } \right) + v_{av} \cdot \frac{{S_0 + L_{av} + L}}{{v_{av} - v_{sv} }} + 2 \cdot P_{5_x } ,\,\,} \\ {{\text{when}}\,\,v_{sv} > 0\,\frac{m}{s}\,\,{\text{and}}\,\,\frac{{v_{av} }}{2} \ge v_{av} - v_{sv} } \\ \end{array} } \\ {\begin{array}{*{20}c} { - P_x \left( {t_B } \right) + v_{av} \cdot \frac{{S_0 + L_{av} + L}}{{2 \cdot \left( {v_{av} - v_{sv} } \right)}} + 2 \cdot P_{5_x } ,} \\ {{\text{when}}\,\,v_{sv} > 0\,\frac{m}{s}\,\,{\text{and}}\,\,\frac{{v_{av} }}{2} < v_{av} - v_{sv} } \\ \end{array} } \\ \end{array} } \right.\,\,$$
(12)

From Eq. 12, it can be seen that three different cases of returning to the initial movement lane are distinguished. When driving around the static surrounding vehicle, it is assumed that the autonomous vehicle has to begin returning to the initial movement lane when the surrounding vehicle is being overtaken by a safe longitudinal distance:

$$S_{D1} = L_{{\text{av}}} + L{\,}_{{\text{sv}}} + 2 \cdot S_D$$
(13)

When the difference between the velocities is relatively low \(\left( {\frac{{v_{av} }}{2} \ge v_{av} - v_{sv} } \right)\), the safe longitudinal distance by which the surrounding vehicle has to be overtaken:

$$S_{D2} = v_{av} \cdot \frac{{S_0 + L_{av} + L_{sv} }}{{v_{av} - v_{sv} }}$$
(14)

When the difference between the velocities is relatively large \(\left( {\frac{{v_{av} }}{2} < v_{av} - v_{sv} } \right)\), the safe longitudinal distance by which the surrounding vehicle has to be overtaken:

$$S_{D3} = v_{av} \cdot \frac{{S_0 + L_{av} + L_{sv} }}{{2 \cdot \left( {v_{av} - v_{sv} } \right)}}$$
(15)

3 Experimental Implementation

To validate the proposed hybrid path planning approach, an experimental path planning and test drives were performed. The experimental path planning and test drives were performed while using an autonomous research vehicle, shown in Fig. 6. In the autonomous research vehicle, specific sensors from Corrsys Datron with the data acquisition system (DAS-3) were used. Autonomous steering was implemented by using an automated steering device, mounted on the test vehicles steering wheel. To perform the path planning during the experimental test drives, the described hybrid path planning approach was designed in the MATLAB/Simulink software. For the control of the autonomous vehicle steering angle, the kinematic-based controller was also designed in the MATLAB/Simulink software and was used together with the hybrid path planning approach. The computer, on which the hybrid path planning approach and controller were designed, was connected in real time with the Arduino microcontroller of the automated steering device while using the universal asynchronous receiver-transmitter based communication system. To satisfy the real time communication condition and to not overload the data buffers of the used communication system, the serial signal sending rate was 10 Hz and the serial signal receiving rate was 100 Hz. The step size of the mathematical operations solver used in the controller was fixed at 0.1 s.

Fig. 6
figure 6

Autonomous research vehicle, used during the experimental test drives

Full size image

While seeking to implement and test the entire proposed hybrid path planning approach including the described extension, a path for the double-lane change manoeuvre was planned. For safety reasons, as this was the first experimental implementation of the developed hybrid path planning approach, the path planning was performed while considering that the reference velocity of autonomous vehicle is relatively low (\(v_{{\text{av}}} = 3\) m/s). The surrounding vehicle was static, i.e. not moving (\(v_{{\text{sv}}} = 0\) m/s). In order to test the feasibility of the planned double-lane change manoeuvre path, in general 4 experimental test drives were performed while autonomously moving on the planned path. During the experimental test drives, the actual velocity of the autonomous vehicle was changing between 1.5 and 4 m/s and it was controlled by a human supervisor. There were no other human interventions in the autonomous movement. All of the experimental test drives were done under equal conditions in an enclosed lot on dry asphalt, without vertical slope surface. Other technical characteristics of the autonomous research vehicle are provided in Table 1.

Table 1 Technical characteristics of the autonomous research vehicle
Full size table

4 Results and Discussion

The results of the proposed hybrid path planning approach experimental implementation and test drives are provided in Figs. 7 and 8. In Fig. 7 a path is shown, which was planned by using the hybrid approach. Figure 8 presents the data, recorded during the experimental test drives.

Fig. 7
figure 7

Double-lane change manoeuvre path, which was planned by the proposed hybrid approach

Full size image
Fig. 8
figure 8

Data, recorded during the experimental test drives: a movement on the planned path; b experimental steering angle \(\delta\) values; c experimental velocity \(v_{av}\) values

Full size image

During the experimental path planning, the rapidly exploring random trees approach in general generated 12 nodes \(N\), which were enough for the proposed hybrid approach to plan a smooth and geometrically continuous path without sharp turns (Fig. 7). From Fig. 8 (part b) it can be seen that the steering angle \(\delta\) values, required to follow the planned path, at the beginning and end of the path were equal to zero. The change of the steering angle \(\delta\) values was also smooth, consistent and relatively similar to the sinusoidal shape (Fig. 8, part b). As the surrounding vehicle was static, the distance \(S_0\) is equal to the distance \(S_1\), after which the autonomous vehicle caught up to the static surrounding vehicle and started to overtake it (\(S_0 = S_1 = 23.1\) m). Because the entire path was planned for the double-lane change manoeuvre and the surrounding vehicle was static, the mirror distance for the planned primary lane change manoeuvre path (Bézier curve + safety distance \(S_D\)) was \(S_{D1} = 12.45\) m. Such results of the experimental path planning enable to state that, during the experimental implementation, the proposed hybrid path planning approach performed as it was foreseen during the development of the approach. No unexpected negative phenomena of the approach’s performance during the path planning were noticed.

During the experimental implementation, the proposed hybrid path planning approach was able to plan a path for the double-lane change manoeuvre within 0.3259 s. While comparing the determined path planning time value with other values, described in the literature review (Ibrahim et al., 2020; Xi et al., 2020), apparently the computational time of the proposed hybrid approach is slightly longer. However, during the approach development process and while preparing for the experimental implementation of the approach, it was noticed that the computational time and real-time performance of the proposed approach actually depends on the number of the generated nodes \(N\) and velocities of the considered vehicles (\(v_{{\text{av}}}\) and \(v_{{\text{sv}}}\)). In the case of the static surrounding vehicle, the computational time depends only on the velocity of the autonomous vehicle \(v_{{\text{av}}}\). In the case of the dynamic surrounding vehicle, the computational time depends on the difference between the velocities of the autonomous and surrounding vehicles (\(v_{{\text{av}}} - v_{{\text{sv}}}\)). These remarks can be explained by the fact that, in the proposed hybrid approach, the number of the generated nodes \(N\) is based on the parameter \(S_{\min }\). Table 2 presents the relation between the computation time of the proposed hybrid approach, number of the generated nodes \(N\) and the velocity of the vehicle \(v_{av}\).

Table 2 Relation between computation time, number of the generated nodes and velocities
Full size table

From the data, provided in Table 2, it can be seen that, as the velocity \(v_{av}\) of the autonomous vehicle or the difference between the velocities \(v_{av}\) and \(v_{sv}\) increases, the number of the generated nodes \(N\) also increases. This means that the computational time of the proposed hybrid path planning approach increases as well. Nevertheless, the real-time performance of the proposed hybrid approach under relatively low velocity \(v_{av}\) cannot be underrated and considered as inefficient. Approximately, when the velocity \(v_{{\text{av}}}\) of the autonomous vehicle or the difference between the velocities \(v_{av}\) and \(v_{sv}\) does not exceed 15 m/s, the computational time of the proposed hybrid approach is less than 1 s, which is a proper value while seeking to ensure safe and efficient path planning in real-time. The noticed phenomenon that the computational time of the proposed hybrid approach is not constant and increases as the velocity \(v_{av}\) of the autonomous vehicle increases, indicates a possible drawback of the proposed approach. Thus, while further seeking to develop and improve the proposed hybrid path planning approach, one of the future research directions is a consideration of how to ensure the efficient real-time performance of the approach under relatively high velocities of the autonomous vehicle \(v_{av}\).

While further seeking to evaluate if the planned path is feasible and, therefore, considering the results of the performed experimental test drives (Fig. 8), first of all, it must be explained why the planned steering angle \(\delta\) values do not match in the time axis with the steering angle \(\delta\) values, recorded during the experimental test drives (Fig. 8, part b). The reason for this is that, during the experimental test drives, the data recording would be started slightly earlier than the autonomous movement of the vehicle would start. This resulted in different time points of the autonomous movement start, but had no actual influence on the planned path feasibility or path tracking errors. From Fig. 8 (part a) it can be seen that, during the experimental test drives, while the autonomous vehicle was moving, minor deviations from the planned path emerged (path tracking errors in y axis). During the 1st experimental test drive the autonomous vehicle deviated from the planned path by 0.41 m, during the 2nd test drive—0.3 m, the 3rd test drive—0.49 m, the 4th test drive—0.09 m. After assessing the obtained results, it can be assumed that the deviations from the planned path emerged because of the used kinematic-based controller. As the used kinematic-based controller was a non-adaptive common feedback controller, it was unable to efficiently manage the changes in the values of the autonomous vehicle velocity \(v_{av}\) (Fig. 8, part c). The use of the simple and non-adaptive controller resulted in the path tracking errors in y axis, i.e. the autonomous vehicle was not able to return to the same position of movement in y axis. It is important to note that although minor deviations emerged, the autonomous vehicle managed to execute the planned path (Fig. 8, part a). The deviations from the planned path, which would be related to the performance of the proposed hybrid path planner, i.e. sharp turns in path, improper steering angle \(\delta\) values or improper curvature, did not emerge. Thus, it can be summarized that, from the path feasibility point of view, the performance of the proposed hybrid path planner is reliable, i.e. the planned path is technically feasible and can be executed by the autonomous vehicle. These remarks regarding the feasibility of the planned points out one more future research direction, while seeking to improve the proposed hybrid approach—the performance of the proposed hybrid path planner must be further analyzed while using a more advanced control system.

In general, the results of the performed first experimental implementation allowed to identify a few more future research direction, while seeking to find out the drawbacks of the approach and to extend its application possibilities: performance of the approach must be analyzed with the dynamic surrounding vehicle, higher velocities \(v_{{\text{av}}}\) of the autonomous vehicle must be considered experimentally, different scenarios and different dimensions of the surrounding vehicle also must be taken into consideration.

5 Conclusion

In this work, the development process of a new hybrid approach for the lane change manoeuvre path planning, while taking into consideration the framework of the approach, detailed explanation of made assumptions, determination of every parameter and experimental analysis of the approaches efficiency, is described. In the proposed hybrid path planner, the Bézier curves approach was used to plan the curvature of the lane change manoeuvre path and the rapidly exploring random trees approach was used for the determination of the control points. The main contribution of this work is not only the new hybrid approach, but also a proposed way, which can be applied by other researchers while developing path planners, of how control points for the Bézier curves could be determined and the remarks regarding which of the Bézier curves’ properties should be taken into consideration, specifically from the autonomous vehicle’s point of view. The experimental implementation and analysis showed that the proposed combination of the classical planning approaches meets the most important fundamental requirements, i.e. the planned path is smooth, continuous, and technically feasible for the autonomous vehicle and efficiently performs in real-time. However, during the experimental analysis it was noticed that the real-time performance of the approach actually depends on the velocity of the autonomous vehicle. As the velocity of the autonomous vehicle increases, the computation time of the approach also increases. Due to this reason the proposed hybrid path planning approach in its current state is not prepared to be employed more widely in autonomous vehicles and requires further development. Thus, future research directions are to consider higher velocities of the autonomous vehicle and to improve the real-time performance of the approach under these higher velocities, also to consider different type of obstacles/surrounding vehicles and to apply the basics of the proposed hybrid path planning approach to other urban scenarios.