A Lyapunov Optimization-Based Approach to Autonomous Vehicle Local Path Planning Authors: Ziba Arjmandzadeh, Mohammad Hossein Abbasi, Hanchen Wang, Jiangfeng Zhang, Bin Xu Published: 2024 ABSTRACT Autonomous vehicles (AVs) offer significant potential to improve safety, reduce emissions, and increase comfort, drawing substantial attention from both research and industry. A critical challenge in achieving SAE Level 5 autonomy, full automation, is path planning. Ongoing efforts in academia and industry are focused on optimizing AV path planning, reducing computational complexity, and enhancing safety. This paper presents a novel approach using Lyapunov Optimization (LO) for local path planning in AVs. The proposed LO model is benchmarked against two conventional methods: model predictive control and a sampling-based approach. Additionally, an AV prototype was developed and tested in Norman, Oklahoma, where it collected data to evaluate the performance of the three control algorithms used in this study. To minimize costs and increase real-world applicability, a vision-only solution was employed for object detection and the generation of bird’s-eye-view coordinate data. Each control algorithm, i.e., Lyapunov Optimization (LO) and the two baseline methods, were independently used to generate safe and smooth paths for the AV based on the collected data. The approaches were then compared in terms of path smoothness, safety, and computation time. Notably, the proposed LO strategy demonstrated at least a 20 times reduction in computation time compared to the baseline methods. 1. Introduction Developments in vehicle technology, along with advancements in driver assistant systems, have contributed to the advent of autonomous vehicles (AVs) [1]. AVs are gaining traction for their potential to enhance safety and reduce environmental pollution [2,3]. This paper focuses on AV local path planning. Local path planning, along with environment perception and control, construct the building blocks of AV intelligent behavior [4]. Furthermore, in this work, we generated a dataset utilizing an autonomous 2015 Nissan Leaf S in urban driving conditions. Conversely, quite a few existing studies exploit available datasets and concentrate on highway path planning [5,6,7]. AVs encounter various scenarios, including curved roads, intersections, obstacles, ramp merging, etc., that are explored in different papers such as [6,8,9,10]. These studies aim to find a safe, comfortable, and collision-free trajectory that pursues a reference line, considering the static and dynamic obstacles. Various path planning methods are investigated in the literature [1], including sampling-based methods [11], model predictive control (MPC), and deep learning-based approaches. Sampling-based methods are widely used in tracking control problems, particularly in emulating human driving behavior. A key advantage of using sampling-based methods with Frenet coordinates is their ability to decouple lateral and longitudinal motions, which simplifies the mathematical representation of curved trajectories. Ref. [11] introduces a sampling-based method for optimal trajectory generation for the first time. Similarly, [5] utilizes a sampling-based approach within the Frenet frame for path planning while accounting for static obstacles. In [12], a sampling-based model is designed for collision-free path planning and validated through simulation. Further, sampling-based approaches using the Frenet frame generate multiple candidate trajectories at each time step and select the best one, which adds extra computation burden for practical applications. MPC resolves redundant trajectory generation in sampling-based methods by directly finding the optimal path. In addition, MPC fortunately includes system dynamics and nonlinear and physical constraints in the underlying optimization problem. Moreover, the weighted cost function of MPC enables the customization of model performance and the reduction in energy consumption, facilitating the achievement of the optimal solution. MPC is employed in [13] for AV local path planning, where collision avoidance is obtained through potential fields and Farka’s lemma. The authors in [14] design a nonlinear MPC to solve the path-planning problem and shorten the computation time. Ref. [15] investigates a two-stage path-planning strategy where, while ignoring the obstacles, a local path is generated in the first stage. The second stage then optimizes ego vehicle maneuvers by MPC. Leveraging Frenet coordinates, a collision-free path is found by a gradient decent optimizer in [16]. Then, a PI-MPC controller follows the optimal path. The study in [17] proposes a joint Cartesian–Frenet MPC methodology, where the vehicle control model is outlined in the Cartesian space and road constraints are delineated in the Frenet coordinates. Then, the joint model is tested on a delivery and a passenger vehicle. An improved particle swarm optimization-based MPC method is developed in [18] for the cooperative control of local planning and path tracking for intelligent vehicles. Despite the advantages of MPC, acceptable control performance may require a prediction horizon that renders the slow implementation of MPC for practical applications. Deep learning techniques address the high computational cost associated with sampling-based and optimization-based approaches. Unlike these methods, once a neural network is fully trained, deep learning enables rapid real-time implementation. Ref. [19] provides a comprehensive review of the latest advancements in deep learning-based path planning. Artificial neural networks are employed for various tasks such as collision avoidance, overtaking, safe navigation, and lane changing, as highlighted in studies [7,20,21,22]. However, several disadvantages emerge when applying deep learning to autonomous driving. One key issue is the lack of interpretability in neural networks, which can complicate legal accountability in the event of an accident. Additionally, deep learning algorithms require vast amounts of training data, limiting researchers to large datasets and creating challenges in obtaining or processing such data efficiently. To overcome the challenges of high computational demands in sampling-based methods and model predictive control (MPC), as well as the large data requirements and lack of interpretability in deep learning approaches, this study proposes a novel solution based on the Lyapunov Optimization (LO) strategy. LO is recognized for its fast computational capabilities [23], and its mathematical foundation makes its behavior highly interpretable. This efficiency makes LO particularly suitable for accelerating AV path planning calculations. In this study, we leverage the LO approach to explore local path planning for AVs in dense urban traffic scenarios. To evaluate the performance of the proposed LO algorithm, we also introduce MPC and a sampling-based method as benchmark approaches for comparison. Introduced in [24], the LO method is a relatively recent approach that decomposes an optimization problem into multiple subproblems, with each subproblem corresponding to a specific time step. The decomposition substantially increases the computation speed [23], while independence from other time steps relaxes the need for future information. Theorems 1 and 2 prove how the LO method closely follows the global optimal solution. Consequently, the computation complexity is diminished by downsizing the optimization problem. To the best of the authors’ knowledge, the LO method is not employed for AV local path planning, but it is used in close contexts that are reviewed in the following. The LO method uses a Lyapunov function to optimally control a dynamical system. This Lyapunov function is positive definite and increases as the system nears instability. To maintain system stability, it is crucial to minimize the drift of the Lyapunov function. Furthermore, in [24], the original work that introduced Lyapunov Optimization (LO) uses Lyapunov drift for optimal control of queuing networks. A weighted penalty term is incorporated into the Lyapunov drift, forming the drift-plus-penalty framework. This approach ensures system stability while minimizing the penalty by minimizing the drift-plus-penalty expression. To apply the LO method to our problem, we transform it into a queue stability problem, as described in Section 2.3, by constructing virtual queues. The authors in [25] employ the Lyapunov concept to investigate the problem of stability and synchronization of fractional-order complex-valued neural networks with time delay. In [26], the finite-time and fixed-time stability theorems of general fractional-order impulsive discontinuous systems through an indefinite Lyapunov functional approach are studied. In Ref. [27], the LO method is applied to traffic control, introducing a real-time global path planning technique aimed at optimizing the overall spatial utilization of the road network. The authors in [28] establish an online edge processing scheduling algorithm based on LO where unmanned aerial vehicle base stations are deployed as moving mobile edge computing servers. The proposed algorithm in [28] may face a path planning issue, which is tackled by reinforcement learning. Ref. [29] utilizes LO as a tool for exploring communication and localization of robotic networks in harsh environments, such as lunar, planetary, or subterranean environments. Lastly, the article in [30] also uses LO to deal with traffic control. This paper introduces a novel local path planning approach based on the LO algorithm, chosen for its rapid computational efficiency. The LO method transforms the optimization problem into a queue stability problem by replacing system dynamics with virtual queues. Additionally, queue backlogs are incorporated into the objective function using a positive definite Lyapunov function, forming the drift-plus-penalty term. The LO minimizes the upper bound of the drift-plus-penalty term. This upper bound is first derived from the initial theorem and further refined by the second theorem, which proves that minimizing the upper bound results in a solution that approaches the global optimum. The contributions of our work are as follows:The problem of the local path planning of an AV is solved via LO for the first time;The optimization problem is transformed into a queue stability problem in order to apply LO;The standard LO algorithm is modified to change the desired state values dynamically from one time step to another;The proposed approach drastically reduces computation time. The problem of the local path planning of an AV is solved via LO for the first time; The problem of the local path planning of an AV is solved via LO for the first time; The optimization problem is transformed into a queue stability problem in order to apply LO; The optimization problem is transformed into a queue stability problem in order to apply LO; The standard LO algorithm is modified to change the desired state values dynamically from one time step to another; The standard LO algorithm is modified to change the desired state values dynamically from one time step to another; The proposed approach drastically reduces computation time. The proposed approach drastically reduces computation time. The remaining sections of the paper are structured as follows. The problem formulation is extensively elaborated upon in Section 2. The experimental data collection is briefly explained in Section 3. In Section 4, numerical results are presented for three different scenes. Finally, the conclusions are drawn in Section 5. 2. Problem Formulation This section defines the path planning problem and presents a solution approach using a sampling-based method illustrated in the Frenet frame, along with a description of the LO technique. 2.1. Environment Figure 1 illustrates an example of a car (the blue rectangle) on the road with a reference line to follow, where each point is denoted by (x,y) in the Cartesian system. Further, (xr,yr) indicates a point on the reference line closest to the vehicle’s center of gravity (CG), while the heading angle and vehicle’s velocity are represented by θ and v, respectively. The Euler approximation method is chosen for state equation discretization due to its widespread use and simplicity. However, it can result in coarse approximations when the sampling time is too large. To mitigate this limitation, this work reduces the sampling time to a level that strikes a balance between improved accuracy and acceptable computational cost for autonomous driving applications. The dynamic equation of the vehicle can be formulated as the following [31]:(1)zk+1=zk+f(zk,ck)Δt, where subscript k is time step, Δt shows the sampling time, ck denotes input, and the vehicle’s state at k is zk=xkykθkvkT. Moreover, f(zk,ck)=vkcosθkvksinθkωkakT, where ωk is angular velocity at k, ak indicates vehicle longitudinal acceleration at k, and ck=ωkakT. Furthermore, environmental information, such as roadway waypoints, lane markings, and the positions of surrounding vehicles, is gathered through image processing using a real AV (see Section 3). 2.2. Path Planning Optimization Problem The following nonlinear, constrained optimization problem is formulated to address the local path planning challenge, prioritizing safety and comfort for passengers while maintaining the desired speed. (2a)min1NE∑k=1N(wgdDk2+wymrk+wvvkd−vk2+waak2+wyωk2+wjak−ak−12)} subject to (2b)xk+1yk+1θk+1vk+1=xkykθkvk+vkcosθkvksinθkωkakΔt,∀k, (2d)ωmin≤ωk≤ωmax,∀k,where N is the total number of time steps; E{·} denotes expectation; wgd, wym, wv, wa, wy, and wj represent weights; Dk expresses the Euclidian distance between the ego vehicle’s CG, (xk,yk) and (xr,yr) at time k. This term aims to minimize the reference position tracking error. vkd presents the desired speed at k. This term aims to minimize the speed tracking error. amin and amax are acceleration boundaries. ωmin and ωmax show angular velocity boundaries. These acceleration and angular velocity terms aim to minimize the control input. ak−ak−12 is used to minimize longitudinal jerk. The barrier function rk is fashioned for collision avoidance as follows:(3)rk=∑i=1No1ηxlx,ki+ηyly,ki,(4)lx,ki=x1i−x2e,ifx2ex2i,0,O.W.,,(5)ly,ki=y1i−y2e,ify2ey2i,0,O.W., where i is the obstacle index; e represents the ego vehicle; No shows the total number of surrounding obstacles captured by image processing; ηx and ηy are weights; lx,ki is the lateral distance of the ego vehicle from the obstacle at time k as displayed in Figure 2; ly,ki indicates the longitudinal distance from the object; x1i, x2i, y1i, and y2i are used to define the corners of the i-th obstacle’s bounding box; x1e, x2e, y1e, and y2e locate the bounding box corners of the ego vehicle. The function rk is defined such that if a collision occurs with object i, lx,ki=ly,ki=0 and ∀i:limlx,ki→0ly,ki→0rk=∞. 2.3. Reformulation For each of the states in (2b), a virtual queue is constructed as the following: (6a)Qkx=xk−xkd, (6b)Qky=yk−ykd,(6c)Qkθ=θk−θkd,(6d)Qkv=vk−vkd,where xkd, ykd, θkd, and vkd are desired state values. In detail, (xkd,ykd) are coordinates of the nearest waypoint (obtained from the reference line), θkd is the desired steering angle based on the relative position of the vehicle and the reference line, and vkd is the desired velocity. The queue length vector is defined as Qk=Qkx,Qky,Qkθ,Qkv. By combining (6) in (2b), we obtain the following: (7a)Qk+1x=Qkx+vkcosθkΔt−xk+1d+xkd=Qkx+ξkx, (7b)Qk+1y=Qky+vksinθkΔt−yk+1d+ykd=Qky+ξky,(7c)Qk+1θ=Qkθ+ωkΔt−θk+1d+θkd=Qkθ+ξkθ,(7d)Qk+1v=Qkv+akΔt−vk+1d+vkd=Qkv+ξkv,where ξkx=vkcosθkΔt−xk+1d+xkd, ξky=vksinθkΔt−yk+1d+ykd, ξkθ=ωkΔt−θk+1d+θkd, and ξkv=akΔt−vk+1d+vkd. Using the virtual queues in (6), problem (2) can be transformed into a queue stability problem (8), where (2b) is changed to the stability of the queues. (8a)min1NE∑k=1N(wgdDk2+wymrk+wvvkd−vk2+waak2+wyωk2+wjak−ak−12) subject to (8b)(2c),(2d)stability of virtual queues Qk. Subsequently, the LO is applied to (8), which establishes an adaptive control policy for local path planning. Problem (8) is decomposed into N subproblems that are solved independently, while system stability is guaranteed. 2.4. Lyapunov Optimization Model Define (9)uk=wgdDk2+wymrk+wvvkd−vk2+waak2+wyωk2+wjak−ak−12. Next, the Lyapunov function is defined as follows:(10)L(Qk)≜β12Qkx2+β22Qky2+β32Qkθ2+β42Qkv2, where β1, β2, β3, and β4 are positive constants. The Lyapunov drift is (11)Δ(Qk)≜EL(Qk+1)−L(Qk)|Qk. Finally, the drift-plus-penalty term will be as follows [32]:(12)Δ(Qk)+VEuk|Qk. At any time slot k, the Lyapunov drift-plus-penalty term has the following upper bound:(13)Δ(Qk)+VE{uk|Qk}≤B+β1QkxE{ϱkx|Qk}+β2QkyE{ϱky|Qk}+β3QkθE{ϱkθ|Qk}+β4QkvE{ϱkv|Qk}+VE{uk|Qk},where B is a positive constant shown in (A11). In addition, ϱkx, ϱky, ϱkθ, and ϱkv are defined in (A7). See Appendix A. □ In Theorem 2, we will demonstrate the minimization of the upper bound of (13), instead of its left-hand side, for each time step k leads to a suboptimal solution which is close to the global optimal objective value of (2a), denoted as p*. The convergence of the suboptimal solution to p* is controlled by coefficient V. Before diving into Theorem 2, an optimization problem is formulated to minimize the upper bound of (13) as follows:(14)minVuk+β1Qkxϱkx+β2Qkyϱky+β3Qkθϱkθ+β4Qkvϱkv,subjectto(2c)–(2d), where ak and ωk are decision variables. Note that Qkx, Qkv, Qkθ, and Qkv are constants whose values are updated after solving (14) for time step k and before running (14) for time step k+1. Moreover, when (14) is being solved for k+1, the values of states at time step k are known. Therefore, according to (A7), the values of ϱkx and ϱky are known, making terms β1Qkxϱkx and β2Qkyϱky constants. Hence, solving (14) in its current form will not lead to the minimization of Qkx and Qky. In other words, by minimizing (14), the reference line is not tracked by the ego vehicle. This issue arises from the fact that xk and yk implicitly depend on ak and ωk. To resolve the issue, we propose using vk+1 and θk+1 instead of vk and θk in ϱkx and ϱky as follows. Assume the following: (15a)QkxvkcosθkΔt≈Qkxvk+1cosθk+1Δt, (15b)QkyvksinθkΔt≈Qkyvk+1sinθk+1Δt. Utilizing (2b), vk+1 and θk+1 are substituted as (16a)Qkxvk+1cosθk+1Δt=Qkxvk+akΔtcosθk+ωkΔtΔt, (16b)Qkyvk+1sinθk+1Δt=Qkyvk+akΔtsinθk+ωkΔtΔt. Finally, leveraging (A7) and plugging (16) in the objective function of (14), we obtain (17)minVuk+Λk,subjectto(2c)–(2d) where (18)Λk=β1Qkxvk+akΔtcosθk+ωkΔtΔt+β2Qkyvk+akΔtsinθk+ωkΔtΔt+β3QkθωkΔt+β4QkvakΔt. Problem (17) minimizes the upper bound of (13) for time step k. After each time step k, the queues should be updated before running problem (17) for the next time step k+1, as presented in Algorithm 1. Figure 3 shows the flowchart of Algorithm 1. Algorithm 1: Lyapunov Optimization For all N>1, the optimal solution of (17), denoted by a^k,ω^k, and the optimal solution of (2), denoted by ak*,ωk*, satisfy the following inequality: (19)1N∑k=1NEu^k≤B1V+p*+1NVEL(Q^1),where B1 is a constant defined in (A30), p* is the optimal objective value of (2a), and u^k is obtained by (9) using a^k,ω^k. See Appendix B. □ Next, the problem is formulated for two baseline methods. Note that nonlinear problem (2) is directly tackled with a nonlinear MPC. Hence, the problem is only required to be reformulated for the sampling-based approach. 2.5. Sampling-Based Method This method employs the Frenet frame, which utilizes Frenet coordinates to describe the position of any arbitrary point along a reference path through longitudinal and lateral displacements, denoted as s and d, respectively. It is important to note that the coordinates s and d are always perpendicular to each other at every point along the reference line. The approach consists of two main steps: (i) generating multiple candidate trajectories at each step and (ii) selecting the optimal path for the ego vehicle based on a cost function. Using Frenet coordinates, we can decouple the lateral and longitudinal motion of the vehicle while simultaneously discretizing the driving state space to generate a set of target states. Based on the initial and target states, we create a series of trajectories for lateral and longitudinal motion, utilizing quintic and quartic polynomials, respectively. Additionally, a comprehensive cost function is formulated to evaluate comfort, safety, and deviation from the reference line. Furthermore, the variables s and d are represented by the following polynomials: (20)d(t)=cd0+cd1t+cd2t2+cd3t3+cd4t4+cd5t5,(21)s(t)=cs0+cs1t+cs2t2+cs3t3+cs4t4, where t is time and cdx and csx are coefficients that should be calculated. Each trajectory starts at ts and ends at te under the assumption that ts and te are known. Considering Equations (20) and (21) and their time derivatives at the start and end points, the following set of equations is achieved: (22)d(ts)d˙(ts)d¨(ts)d(te)d˙(te)d¨(te)=1tsts2ts3ts4ts5012ts3ts24ts35ts40026ts12ts220ts31tete2te3te4te5012te3te24te35te40026te12te220te3cd0cd1cd2cd3cd4cd5,(23)s(ts)s˙(ts)s¨(ts)s˙(te)s¨(te)=1tsts2ts3ts4ts5012ts3ts24ts35ts40026ts12ts220ts3012te3te24te35te40026te12te220te3cs0cs1cs2cs3cs4, which are used to find coefficients cdx and csx. To solve (22) and (23), assume ts=0 and te=τ, where τ is a positive constant. Therefore, by plugging ts=0 into (22), we obtain cd0=d(0), cd1=d˙(0), and cd2=d¨(0). Consequently, the matrix Equation (22) simplifies into three equations and three unknowns. Note that we assume d˙(te)=d¨(te)=0, while d(te) is selected such that the vehicle remains on the road. On the other hand, for (23), we have cs0=s(0), cs1=s˙(0), and cs2=s¨(0), which simplifies matrix Equation (23) to a two-by-two one. Moreover, s(ts), s˙(ts), and s¨(ts) are known from the previous step’s calculation, and the candidate trajectories are generated such that s¨(te)=0, and the s˙(te) value is selected close to the desired speed. Accordingly, at each step, several trajectories are generated based on the combination of d(te) and s˙(te) values, and the best one is selected according to the cost function in (24). The candidate trajectories are generated by changing the values of d(te)∈d(ts)−LW,d(ts)+LW,s˙(te)∈vkd−5/3.6,vkd+5/3.6, where LW is lane width. Finally, the cost function to be minimized is defined as (24a)C=Cd+Cs, (24c)Cs=Kj∑t=tsτs⃛(t)2+Ktτ+Kdvkd−s˙(t)2,where Cd and Cs indicate lateral and longitudinal costs, and Kj, Kt, and Kd are weights. The cost function aims to minimize both lateral and longitudinal jerks, reduce the lateral distance from the reference line, and ensure that the velocity matches the desired value. 3. Experimental Data Collection The data in this study were collected using a 2015 Nissan Leaf S battery electric vehicle in Norman, OK, USA. The test vehicle hardware configuration is shown in Figure 4. Environment perception sensors included Velodyne VLP-16 Puck lidar, Texas Instruments AWR1642BOOST mmWave radar, Swift Piski Multi GNSS GPS, Xsens MTi-30 IMU, and cameras. The steering wheel and two pedals were modified to achieve a drive-by-wire function. Two powerful computation stations were mounted on the trunk floor, including an Alienware R13 and a Dell T3500. Image data collected from the dashcam were utilized in this study. The camera data were broadcasted to the ROS2 Humble via a v4l2 camera driver and saved in an ROS bag. The image data were collected from Asp Ave for straight roads and 24th Ave NW for curly roads (Norman, OK, USA 73019). Three scenarios are analyzed in this study, with one straight road scenario (i.e., scenario 1) and two curly road scenarios (i.e., scenarios 2 and 3). 4. Simulation and Results This section presents the results of local path planning using the proposed LO approach alongside two baseline methods for comparison. The key advantage of LO lies in its significantly faster computation speed. Rapid processing is crucial as the computation chip is one of the most costly pieces of hardware in AV setup. Moreover, the computations were executed on a computer with a 2.40 GHz Core i7 CPU with 20 cores and 16 GB RAM. First and foremost, the Lyapunov function derivative is plotted in Figure 5 to validate the proposed approach’s convergence. The convergence is verified as the derivative of the Lyapunov function in (10) and is negative. Figure 6 displays the results of scenario 1, which is straight road path planning in a narrow urban street where the lane is partially occupied by the vehicles parked next to the curb, as Figure 6h shows. The birds-eye-view image of the path ahead is generated and depicted in Figure 6g. According to Figure 6g, the paths generated by LO and the two baseline approaches are similar without significant disparity. MPC’s path is closest to the left-side solid lines, whereas the sampling-based method’s path is closest to the right side, where vehicles are parked, while the LO result falls in between the two baseline methods. Figure 6a illustrates the x-coordinates of the three algorithms. While MPC smoothly steers left to avoid parked cars and then right to follow the reference line, both LO and the sampling-based method exhibit less smooth transitions compared to MPC. Figure 6b demonstrates that the y-coordinates of all methods overlap and the three curves align well. On the other hand, Figure 6c,f represent steering angle and angular velocity results, respectively. Sharp changes in the steering angle observed in the sampling-based method are caused by significant variations in angular speed. These fluctuations arise because the sampling-based approach does not impose limits on the angular speed input. In contrast, the MPC and LO methods produce smooth results for both steering angle and velocity. Figure 6d,e show velocity and acceleration, respectively. LO exploits the maximum allowed acceleration to increase velocity to reach the desired value, whereas MPC and the sampling-based method show similar acceleration and velocity profiles. In the end, both the sampling-based algorithm and LO maintain the desired speed, while MPC experiences deceleration. This distinct behavior in MPC is attributed to its prediction horizon. As MPC anticipates the end of the road with no additional waypoints ahead, it proactively reduces speed. Figure 7 shows the second scenario on a three-lane street with a curve to the left. Based on Figure 7g, LO stays closer to the right edge of the lane, while MPC and the sampling-based approach maintain a larger lateral gap with the vehicle on the right (the sedan in front of the pickup truck in Figure 7h). Note that the step-wise solid black line in Figure 7g is the reference line. In Figure 7a,b, LO closely follows MPC and the sampling-based method results. Furthermore, Figure 7c,f demonstrate that LO and MPC exhibit much smoother handling of steering compared to the sampling-based method. As seen in Figure 7f, the sampling-based technique shows huge fluctuations. In addition, Figure 7d,e show that all approaches attempt to approach the desired speed. However, MPC decelerates shortly after the beginning of scenario 2 as a result of predicting the ego vehicle approaching the end of the path. Figure 8 presents the results for scenario 3, which is on a three-lane street with a curve to the right. As pictured in Figure 8g, the LO trajectory closely follows MPC’s, while the sampling-based method puts more effort into following the reference line, leading to non-smooth outcomes in subplots a, c, and f in Figure 8. Further, as shown in Figure 8d,e, MPC decelerates again to avoid passing the end point of the reference line. The comparison of computation time, path smoothness, and safety among the three approaches is summarized in Table. Table 1. As shown in the table, to achieve a path generation task at a single time step, LO is at least faster than MPC by around 20 times and faster than the sampling-based method by 120 times. This computation time reduction by LO is significant. More importantly, it is achieved without safety and path smoothness compromise. The fast computation in LO, compared to MPC and the sampling-based approach, stems from the following. LO directly finds the optimal path, whereas the sampling-based method expends computational effort on analyzing multiple candidate trajectories. In comparison with MPC, LO only performs calculations for the current time step, while MPC runs the calculations for the next c steps, with c being the length of the control horizon. But only one step out of the c step calculations is executed, and then, MPC repeats everything for steps 2 to c+1, one of which will be executed next. In a sense, both MPC and the sampling-based methodology waste computation resources, generating paths that will not be realized. In contrast, all LO calculations are executed, making LO remarkably more efficient than MPC and the sampling-based method in terms of minimizing computation effort. Finally, in terms of path smoothness, LO and MPC attain a much smoother path compared to the sampling-based model. In addition, all approaches provide a safe trajectory as all paths are collision-free, and certain space margins are left against the obstacles. 5. Conclusions This paper proposes a novel approach for AV local path planning using the LO algorithm. Besides perception and control, local path planning is an essential step in AV technology. The selection of the LO algorithm has its roots in the need for rapid computation in local path planning applications. After extensive mathematical derivations, the proposed algorithm boils down to Algorithm 1. In other words, Algorithm 1 is all one needs to implement the proposed strategy in this paper. The limitation of using LO is that Theorems 1 and 2 should be proved from scratch for each new problem. In order to compare the algorithms in the real-world problem, a 2015 Nissan Leaf S is made autonomous by installing the required sensors and controllers and is used to generate data by driving around urban streets in Norman, Oklahoma. The collected data are then fed to an image processing algorithm, which in turn provides the input data for Algorithm 1. Ultimately, the proposed approach is applied to three selected scenarios, and the results are compared with those of MPC and the sampling-based method. The results demonstrate that LO completes local path planning tasks with performance comparable to MPC, while being at least 20 times faster than MPC. Lastly, future studies can exploit this work by applying it to connected autonomous vehicle problems, where each AV is controlled by an LO algorithm while all LO algorithms interact with each other.