In recent years, the intelligence level of autonomous driving systems has gradually increased, stepping towards higher-level autonomous driving [1]. As the module that directly determines the vehicle’s motion state, the trajectory planner is a core component of the autonomous driving system and a key research area for achieving vehicle autonomous intelligence. With the advancement of real-world testing of autonomous vehicles and the deepening of trajectory planning research, the interaction modes among AVs have garnered more attention. The interaction between AVs is a phenomenon where their motion trajectories influence each other due to the exclusivity of road time-space resources. The classical AV trajectory planning model is “planning after prediction” [2]: prediction algorithms, as upstream processes, predict the motion trajectories of surrounding traffic participants. These trajectories are input into the trajectory planning module and are considered as dynamic obstacles or unreachable positions. In such models, only unilateral avoidance behavior of the ego vehicle is considered, while the response of other traffic participants to the ego vehicle’s actions, as well as the resulting mutual interactions among all traffic participants, are ignored. The waiting and avoidance behaviors of other participants towards the ego vehicle are difficult to manifest in this algorithmic process, leading to trajectories that are likely overly conservative [3].

To resolve conservatism in trajectory planning, the relationship between prediction and planning must be considered. Multi-agent systems, a technique specializing in the interaction behavior of autonomous agents, are increasingly being utilized by researchers to study autonomous driving problems [4,5]. In multi-agent approaches, game theory is a reasonable and suitable method for modeling the decisions and interactions of autonomous vehicles, because the concept of equilibrium in games captures the optimal actions of each vehicle under multi-vehicle interactions. Equilibrium is a stable solution for all players where each player, taking into account the utility influenced by others, chooses the optimal response and cannot benefit by unilaterally changing its decision. Presently, there have been studies on game-based trajectory planning of AVs, which involve different types of equilibrium concepts, including Nash equilibrium [6], generalized Nash equilibrium (GNE) [7], and Stackelberg equilibrium [8]. By endogenously considering the interactions between vehicles, game-theoretic methods have advantages over non-game-theoretic methods in many tasks with strong interactions, such as overtaking [9], lane changing [10–12], intersection management [13,14], and racing [7]. However, these studies require the overly strong assumption that other vehicles’ objective functions are known by the ego vehicle, which is problematic in real-world scenarios. Some studies attempt to solve this problem through intention inference algorithms [15,16]. Moreover, each vehicle separately searches for equilibrium (namely, plans trajectories for every vehicle), which however lacks coordination. On the one hand, this method reduces the algorithm’s real-time performance by causing redundant computation in decision-making. On the other hand, it cannot ensure that all vehicles converge to the same equilibrium, which results in misjudgments about the actions of other vehicles and damages the algorithm’s safety.

We believe V2X is the key technology to resolve the aforementioned problems. CAVs can share states [17], intentions and decisions through V2X, which provides the possibility to design a coordinated and distributed solution for trajectory planning games. In addition, distributed solutions can avoid redundant computation and guarantee an equilibrium consensus among CAVs. Though there has already been some research utilizing distributed game-theoretic frameworks for CAVs, they seldom focus on trajectory-level planning. For example, [18] uses a cooperative evolutionary game and a distributed algorithm to jointly optimize vehicle routing and traffic signal timing but ignores constraints and dynamics at the trajectory level. Besides, [19] employs a decomposed non-cooperative game to decide acceleration/deceleration and steering in lane changing, but it can merely offer CAVs with a set of discrete choices for movement. In addition, [20] proposes a distributed trajectory planner for a two-vehicle cooperative game, which, however, does not consider coupled constraints and hence cannot ensure safety in collision avoidance. Meanwhile, [21] designs a non-cooperative differential game method for autonomous convoy control problems with distributed state feedback control based on neighbors’ information. However, this method relies on centralized solving of the coupled Riccati equations, thus is not distributed in computation. Furthermore, in the multi-agent system field closely related to CAV research, [22] formulates the multi-agent trajectory planning problem as a potential game and proposes a distributed iLQR algorithm that divides the centralized potential game into multiple local subproblems. However, this method requires each agent to solve the control of all its neighbors, limiting computational efficiency, and its applicability is constrained by the assumptions of the potential game.

To overcome these problems, this paper focuses on traffic scenarios where the penetration rate of CAVs is 100% and equipped with roadside units (RSUs). We model the trajectory planning problem as a GNE problem with collision avoidance modeled as coupled constraints, and propose a semi-decentralized VE-based planner (SVEP) for CAVs. In the proposed method, CAVs and RSU alternately optimize the trajectory and the multipliers for collision avoidance constraints so as to handle coupled constraints and solve the game semi-distributedly. Each vehicle only solves its own decision variables, which ensures real-time performance and scalability. A consensus mechanism for Lagrange multipliers is designed in SVEP so that each vehicle can converge to the same VE, thus enhancing safety. To our knowledge, this is the first study that solves a CAV trajectory planning game with coupled constraints semi-distributedly. Our contributions are as follows.

• First of all, we model the trajectory planning problem of CAVs as a game with coupled constraints to enhance the safety of trajectories and respect the autonomy of each vehicle.

• Then the concept of interaction fairness is proposed for the trajectories based on our model. Through sensitivity analysis, we show that an interaction-fair GNE is in fact a VE.

• We propose SVEP, a semi-decentralized and VE-based planner for CAVs. By designing a solving method decomposed to each CAV and the RSU, the algorithm has the features of fast computation speed, a small communication payload, and high scalability. The algorithm enables CAVs to solve for a concordant equilibrium, thereby enhancing the safety of trajectories.

• Finally, we conduct simulations in an intersection scenario with various numbers of vehicles and different driving routes to assess the running time, success rate, and equilibrium concordance rate. It shows that the computational efficiency and safety of SVEP are at an advanced level.

A preliminary version of this work was presented at [23]. While this journal version makes the following improvements: (1) We provide a more comprehensive and detailed derivation process to enhance the modeling and equilibrium analysis of the trajectory planning game, thereby improving clarity and ensuring theoretical rigor; (2) Next, we explicitly consider and elaborate on the specific communication process in the algorithm design, and evaluate the influence of communication time on the computational efficiency of SVEP through experimental and theoretical analysis; (3) At last, we analyze the dimensions in the computation of SVEP compared with those of trajectory planning algorithms based on GNE without V2X (e.g., ALGAMES [24] and iLQGames [25]). Thus, the advantages of SVEP in computational efficiency and scalability are elucidated theoretically and validated by the experimental results.

The remainder of this paper is organized as follows: Sec. 2 presents the formulation of the game-based CAV trajectory planning problem. Sec. 3 introduces the solution concept of the formulated game model, presents the concept of fair interaction from an economic perspective in particular, and analyzes the characteristics of the equilibrium of fair interaction. Sec. 4 provides the algorithm design and analysis for SVEP. Sec. 5 conducts simulation experiments and result analysis to study the performance of the proposed SVEP from the perspectives of computational efficiency and safety. Sec. 6 concludes the paper and discusses future directions.

Notations.0 denotes a vector with all elements being 0. The operator\(\operatorname{vec}(\cdot )\) is defined as the concatenation of column vectors or scalars\(a_{1},\dots ,a_{l}\), i.e.,\(\operatorname{vec}(a_{1},\dots ,a_{l})=(a_{1}^{\mathrm{T}},\dots ,a_{l}^{\mathrm{T}})^{\mathrm{T}}\). For a vector-valued function\(f(x)\),\(J_{f}(x)\) represents the Jacobian matrix of\(f(x)\). For a multivariate function\(g(x)\),\(\nabla _{x} g(x)\) denotes the gradient of\(g(x)\). For a vectorx and a matrixA,\(\|x\|^{2}_{A}=x^{\mathrm{T}}Ax\).\(A\odot B\) represents the Hadamard product of matricesA andB.\(\mathcal{N}_{C}\) denotes the normal cone of setC, intC represents the interior point set of setC, and\(|C|\) denotes the cardinal number of setC. Other main notations used in this paper are shown in Table 1, Table 2 and Table 3.

We consider a two-way traffic scenario equipped with an RSU without traffic signals, where the penetration rate of CAVs is 100%. We consider the trajectory planning problem ofn CAVs, where the set of all CAVs is denoted as\(\mathcal{N}=\{1,2,\dots ,n\}\) with\(i\in \mathcal{N}\) representing a single CAV. Fig. 1 gives an example of a trajectory planning problem in an intersection scenario, where\(n=5\) CAVs need to plan their trajectories.

The traffic scenario and trajectory planning problem illustration. The points marked along the path indicate the position components of the trajectory, with darker colors representing later time steps. The RSU can communicate with all CAVs.

Full size image

As mentioned in Sec. 1, game-based trajectory planners may lead to computational efficiency and safety problems when each vehicle independently solves its subjective game without coordination. In connected traffic environments, the RSU serves as fixed infrastructure with strong communication capabilities and can communicate with all CAVs in the scene. Therefore, we use the RSU to coordinate the trajectories of all CAVs in the scene during the trajectory planning process of each CAV. To achieve this, the RSU receives decision information from each CAV through V2X and provides each CAV with coordination results and information about other vehicles needed for decision-making. In this mode, CAVs only communicate with the RSU and do not need to communicate directly with other CAVs. To reduce communication payload and planning complexity, the RSU only coordinates the CAVs that need to interact. The reason for vehicle interaction is the exclusivity of road time-space resources, i.e., the necessity for vehicles to avoid collisions. Therefore, interaction is only necessary between vehicles that need to avoid collisions. Therefore, the information about other CAVs required for each CAV’s planning only includes information about CAVs that directly interact with it, i.e., information about vehicles that may collide directly. The RSU will determine the interaction relationship between vehicles to decide how to distribute the collected vehicle data. In the scenario illustrated in Fig. 1, the proximity to other CAVs is used as the criterion for determining the interaction, and the interaction relationship can be represented as an undirected graph, as shown in Fig. 2a. Denote this interaction graph as\(\mathcal{G}=\{\mathcal{N},\mathcal{E}\}\), where\(\mathcal{E}\) is the set of edges.\((i,j)\in \mathcal{E}\) if and only if CAVsi andj have an interaction relationship, and\((i,i)\notin \mathcal{E}\).\(\mathcal{G}\) may be a connected or disconnected graph, depending on the interaction situation. The CAVs that directly interact with CAVi are called the neighbors of CAVi. The neighbor set of CAVi is defined as\(\mathcal{N}_{i}=\{j\in \mathcal{N}|(i,j)\in \mathcal{E}\}\), where\(i\notin \mathcal{N}_{i}\). For any CAV\(i \in \mathcal{N}\), its information is only shared with any of its neighbors\(j\in \mathcal{N}_{i}\), and its information sharing is done through the RSU. The communication topology is shown in Fig. 2b.

Examples of interaction and communication in the traffic scenario. (a) Interaction graph of CAVs. (b) Communication topology of CAVs and the RSU.

Full size image

We use a receding horizon formulation for the problem setup.T denotes the discrete prediction horizon, with the discrete time steps\(k=1,\dots ,T\). Within the prediction horizon, denote the state and control vectors of CAVi at timek as\(x_{i}(k)\in \mathbb{R}^{l_{x}}\) and\(u_{i}(k)\in \mathbb{R}^{l_{u}}\), respectively. The specific form of the state and control is determined by the kinematic model. The trajectory to be planned for CAVi is a sequence ofT discrete-time states and controls\(s_{i}=\operatorname{vec}(s_{i}(1),s_{i}(2),\dots ,s_{i}(T))\), where

Then, we design the objective function\(J_{i}(s_{i})\) of CAVi. Given a reference trajectory\(x_{ref,i}(k)\) at time steps\(k=2,\dots ,T\), the objective of CAVi is to minimize the deviation of\(x_{i}(k)\) from\(x_{ref,i}(k)\), as well as to minimize the control input\(u_{i}(k)\) at time\(k=1,\dots ,T-1\). The objective function of CAVi is designed as a convex quadratic function below.

where\(Q_{i}\),\(Q_{i,f}\), and\(R_{i}\) are the weight matrices, all being positive definite diagonal matrices.

Next, we model the constraints that CAVi must comply with in trajectory planning. Let\(s_{\mathcal{N}_{i}}=\operatorname{vec}(s_{j}),\forall j\in \mathcal{N}_{i}\) denote the strategy profile of the neighbors of CAV\(i \in \mathcal{N}\). The private constraints ofi include dynamics constraints\(f_{i}(s_{i})=\boldsymbol{0}\), box constraints\(b_{i}(s_{i})\leq \boldsymbol{0}\), and lane constraints\(m_{i}(s_{i})\leq \boldsymbol{0}\), while the coupled constraints include collision avoidance constraints with neighbors\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\leq \boldsymbol{0}\). Define the strategy set constrained by private constraints

and by coupled constraints

The specific form of these constraints is modeled as follows.

1.Dynamics constraints: We use the kinematic bicycle model [26], as shown in Fig. 3. The state of CAVi at time stepk, denoted by\(x_{i}(k)=\operatorname{vec}(p_{x,i}(k),p_{y,i}(k),v_{i}(k),\psi _{i}(k)) \in \mathbb{R}^{4}\), consists of thex andy coordinates, velocity, and yaw angle, while the control\(u_{i}(k)=\operatorname{vec}(a_{i}(k),\delta _{i}(k))\in \mathbb{R}^{2}\) consists of acceleration and front wheel steering angle. The continuous-time dynamics equations are

whereL is the longitudinal length of a CAV. Let (5) be denoted as\(\dot{x}_{i}=f_{\mathrm{c},i}(x_{i},u_{i})\). We discretize (5) using the fourth-order Runge-Kutta method to obtain the discrete-time dynamic equation (6).

where the discrete period\(T_{s}\) is the time difference between adjacent discrete time steps. Then, the nonlinear dynamics constraints\(\tilde{f}_{i}(s_{i})=\boldsymbol{0}\) of CAVi are defined as

Finally, we only keep the first-order term of the Taylor expansion of the dynamics constraints\(\tilde{f}_{i}(s_{i})\) at the nominal value\(\bar{s}_{i}\) to obtain a simpler linear dynamics constraint\(f_{i}(s_{i})=\tilde{f}_{i}(\bar{s}_{i})+J_{\tilde{f}_{i}}(\bar{s}_{i}) \cdot (s_{i}-\bar{s}_{i})\), where\(\bar{s}_{i}\) is the nominal value given by initialization.

An illustration of the kinematic bicycle model.

Full size image

2.Box constraints: According to the prediction horizon of the decision variable\(s_{i}\) given by (1), the speed\(v_{i}(k)\), acceleration\(a_{i}(k)\), and front wheel steering angle\(\delta _{i}(k)\) of CAVi at timek are subject to the following box constraints

3.Lane constraints: To achieve more accurate modeling than the commonly used Euclidean distance-based methods, we use the intersection between the circumscribed ellipse of the vehicle’s rectangular plan view and the lane boundary line\(\Gamma _{\ell }\) to determine whether the vehicle is off-lane, as shown in Fig. 4, where\(\ell \in \mathscr{L}\) is the index of the lane boundary line. By using the ellipse, we can ensure that the vehicle and the lane boundary line maintain a sufficient distance, taking into account the vehicle’s shape and orientation, which includes an adjustable safety margin.

An illustration of lane constraint. The rectangle is the plan view of the CAV, and the ellipse is an adjustable circumscribed ellipse of the rectangle. We judge whether the CAVi crosses the lane boundary line based on whether the tangent line of the ellipse and the lane boundary line\(\Gamma _{\ell }\) intersect.

Full size image

Let the expression of the circumscribed ellipse be

For a rectangle with lengthL and widthW, let\(L/W=(U/V)^{q}\), whereq is a parameter that adjusts the shape of the ellipse. From the fact that the rectangle vertex\((L/2,W/2)\) lies on the ellipse, we can obtain

To simplify the form of the lane constraint, we linearize the lane boundary line to obtain the linear equation\(ax+by+c=0\) in the world coordinate framew. Since the ellipse equation (9) is expressed in the vehicle coordinate frame with the center of the vehicle as the origin and the vehicle longitudinal direction as thex-axis, we need to solve for the expression of the lane boundary line in the vehicle coordinate frame. The position and orientation of the world coordinate framew and the vehicle coordinate framei are shown in Fig. 4. Take any point\(P_{1}\) on the line. In the world coordinate framew, the two-dimensional coordinates of\(P_{1}\) are\({}^{w}\boldsymbol{p}=(x_{1},y_{1})\), and the homogeneous coordinates are\({ }^{w} \tilde{\boldsymbol{p}}=(x_{1},y_{1},1)^{\mathrm{T}}\). In the vehicle coordinate framei of the CAVi, let the expression of the line be\(d\check{x}+e\check{y}+f=0\), and the homogeneous coordinates of\(P_{1}\) are\({ }^{i} \tilde{\boldsymbol{p}}=(\check{x}_{1},\check{y}_{1},1)^{\mathrm{T}}\). At timek, the coordinate transformation matrix\({ }^{w} T_{i}\) of the vehicle coordinate framei relative to the world coordinate framew is

According to the coordinate transformation formula

we obtain the coordinates of\(P_{1}\) in the vehicle coordinate framei

From the fact that the coefficients of\(ax_{1}+by_{1}+c=0\) and\(d\check{x}_{1}+e\check{y}_{1}+f=0\) are equal, we obtain

Substituting the line equation\(d\check{x}+e\check{y}+f=0\) into the ellipse equation yields

The line and the ellipse do not intersect if and only if the above quadratic function has no real roots, and they are tangent if and only if the quadratic function has a unique real root. From the discriminant

we obtain the lane boundary constraint

In addition to the ellipse-line relationship, it is necessary to restrict the position of CAVi to the inner side of the lane boundary line, i.e.,\(d_{i,\ell }(s_{i}(k))=ap_{x,i}(k)+bp_{y,i}(k)+c\leq 0\). Finally, the nonlinear lane constraint is defined as\(\tilde{m}_{i}(s_{i}) = \operatorname{vec}(c_{i,\ell }(s_{i}(k)),d_{i, \ell }(s_{i}(k)))\leq \boldsymbol{0},\forall k = 2,\dots ,T, \forall \ell \in \mathscr{L}\). Using the same linearization method as the dynamics constraints, we obtain the linear lane constraint\(m_{i}(s_{i})\).

4.Collision avoidance constraints: CAVi and all its neighbors\(j\in \mathcal{N}_{i}\) are subject to collision avoidance constraints. In the collision avoidance constraints, the rectangular shape of the vehicles is also taken into account. The blue dashed curve in Fig. 5 encloses the maximum range of the center position of CAVj when it may collide with CAVi, which is formed by vertically aligning the diagonal of the rectangle of CAVj with the boundary of CAVi. Compared with the existing methods based on the Euclidean distance of the vehicle center (the orange circle in Fig. 5), the superellipse can give a more accurate collision risk area, thus reducing the conservatism of the collision avoidance constraints, and the superellipse also allows independent adjustment of the lateral and longitudinal safety margins of the vehicle. For conventional vehicle size ratios, we find that the 6th-order superellipse (the red superellipse in Fig. 5) can cover the critical collision range well.

An illustration of collision avoidance constraints. The superellipse (red solid curve) used in this paper covers the collision area (blue dashed curve) more accurately than the common circle (orange solid curve), reducing the conservatism of the collision avoidance constraints.

Full size image

The expression of the superellipse centered at the origin and longitudinally along thex-axis shown in Fig. 5 is

whereL,W, and\(D=\sqrt{L^{2}+W^{2}}\) respectively represent the length, width, and diagonal length of the rectangle.

Similar to the lane constraints, a coordinate transformation from the world coordinate frame to the vehicle coordinate frame is needed to make the axis of the superellipse parallel to the coordinate axis, thus simplifying the expression. In the world coordinate framew, the homogeneous coordinates of CAVj at time stepk are\({ }^{w} \tilde{\boldsymbol{p}}_{j}(k)=(p_{x,j}(k),p_{y,j}(k),1)^{\mathrm{T}}\). The coordinates in the vehicle coordinate framei calculated by the coordinate transformation formula (12) are as follows.

Then, at time stepk, the collision avoidance constraint between CAVsi andj denoted as\(h_{i,j}(s_{i}(k),s_{j}(k))\leq 0\) takes the following form

We make CAVj also use (20) as the collision avoidance constraint when considering its interaction with CAVi, ensuring that the collision avoidance constraints ofi andj take the same form.

Throughout the prediction horizon, the collision avoidance constraint between CAVsi andj is defined as

Therefore, the collision avoidance constraint between CAVi and all its neighbors is given by

where\(j_{1},\dots ,j_{|\mathcal{N}_{i}|}\) is a permutation of all elements in\(\mathcal{N}_{i}\). The linearized equation of\(\tilde{h}_{i}(s_{i},s_{\mathcal{N}_{i}}) \) in (22) is\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\).

Finally, the interactive trajectory planning problem considered in this paper is: Given the information sharing structure\(\mathcal{G}\), subject to the private constraint\(s_{i}\in S_{i}\) and the coupled constraint\(s_{i}\in X_{i}(s_{\mathcal{N}_{i}})\), how each CAVi determines its trajectory\(s_{i}\) so as to optimize its objective function\(J_{i}(s_{i})\). Here, the trajectory planning problem of CAVs is formulated as a non-cooperative game. Although the objective function\(J_{i}(s_{i})\) is formally independent of the decisions of other CAVs\(s_{-i}=\operatorname{vec}(s_{1},\dots ,s_{i-1},s_{i+1},\dots ,s_{n})\), the CAVs in the neighbor set\(\mathcal{N}_{i}\) will restrict the decision\(s_{i}\) of CAVi through the coupled constraint\(s_{i}\in X_{i}(s_{\mathcal{N}_{i}})\), thus affecting the minimum value of\(J_{i}(s_{i})\). Due to the existence of coupled constraints, the problem is a GNE problem (GNEP) and is defined as Problem 1. We assume each CAV has a feasible trajectory.

Problem 1

The trajectory planning GNEP is denoted by a tuple\(G=(\mathcal{N},\mathcal{G},(S_{i})_{i\in \mathcal{N}},(X_{i})_{i\in \mathcal{N}},(J_{i})_{i\in \mathcal{N}})\), where\(\mathcal{N}\) is the set of CAVs,\(\mathcal{G}\) is the interaction graph of CAVs,\(S_{i}\) and\(X_{i}\) are the strategy constraint sets of CAVi determined by private (3) and coupled (4) constraints, respectively, and\(J_{i}\) is the objective function of CAV\(i \in \mathcal{N}\). Each CAVi obtains the information of its neighbors\(j\in \mathcal{N}_{i}\) and coordination information through the RSU, and solves the minimization problem

The solution to Problem 1 is a GNE, where each agent’s decision\(s_{i}\) is the best response to\(s_{\mathcal{N}_{i}}\). The definition of a GNE is as follows.

Definition 1

The GNE of Problem 1 is a strategy profile\(s^{*}=\operatorname{vec}\left (s_{1}^{*}, \dots , s_{n}^{*}\right )\) satisfying

In this problem, the objective function\(J_{i}(s_{i})\) and the coupled constraint\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\) are continuously differentiable. Then, the first-order necessary conditions (i.e., the KKT conditions) for the GNE of Problem 1 is given by the following Lemma 1, which has also been shown in [27, Theorem 4.6].

Lemma 1

If\(s^{*}\)is the GNE of Problem 1,then for any\(i\in \mathcal{N}\),there exists a Lagrange multiplier vector\(\lambda _{i}^{*}\),such that

where\(\mathcal{N}_{S_{i}}\)represents the normal cone of the set\(S_{i}\),and the gradient operator ∇follows the denominator layout.

Note that, in Sec. 2, by linearization, the constraints in Problem 1 are all linear constraints. In addition, the cost function is quadratic with a positive definite Hessian matrix. Therefore, we conclude the convexity of Problem 1 as stated in Lemma 2. That is, for any given\(i\in \mathcal{N}\) and\(s_{\mathcal{N}_{i}}\), Problem 1 is a convex optimization problem.

Lemma 2

In Problem 1,for any\(i \in \mathcal{N}\),\(J_{i}(s_{i})\)is a convex function;for any\(i \in \mathcal{N}\)and any\(s_{\mathcal{N}_{i}}\),\(S_{i}\)and\(X_{i}(s_{\mathcal{N}_{i}})\)are closed convex sets.

From the modeling, it is known that for any\(i \in \mathcal{N}\) and any\(s_{i} \in \operatorname{int}\mathbb{R}^{(l_{x}+l_{u})(T-1)}\), the domain of Problem 1 is\(\mathcal{D}=\operatorname{dom} f_{i}(\cdot ) \cap \operatorname{dom} b_{i}( \cdot ) \cap \operatorname{dom} m_{i}(\cdot ) \cap \operatorname{dom} h_{i}( \cdot , s_{\mathcal{N}_{i}}) \cap \operatorname{dom} J_{i}(\cdot )= \mathbb{R}^{(l_{x}+l_{u})(T-1)}\). Moreover, as described in Sec. 2, Problem 1 has feasible solutions, which means that there exists an interior point in\(\mathcal{D}\) satisfying all constraints. Since all inequality constraints in Problem 1 are affine, according to [28, (5.27)], Problem 1 satisfies the refined Slater’s constraint qualification. This property is formally stated in Lemma 3.

Lemma 3

(Refined Slater’s constraint qualification):In Problem 1,for any\(i \in \mathcal{N} \)and any\(s_{\mathcal{N}_{i}} \in \mathbb{R}^{(l_{x}+l_{u})(T-1)|\mathcal{N}_{i}|}\),there exists\(s_{i} \in \operatorname{int}\mathbb{R}^{(l_{x}+l_{u})(T-1)}\)such that

According to [28, Chapter 5.2.3], based on Lemmas 2 and3, for any given\(s_{\mathcal{N}_{i}}\), strong duality holds in Problem 1. Under these conditions, KKT conditions are necessary and sufficient conditions for primal and dual optimal solutions, which means that the\(\lambda _{i}^{*}\) satisfying the KKT conditions (25) is the optimal solution to the dual problem. Inspired by [28, Chapter 5.6.3], it can be proven that\(\lambda _{i}^{*}\) is the local sensitivity of\(J_{i}(s_{i}^{*})\) to perturbations\(w_{i}\) in\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\). From an economic perspective, this property means that\(\lambda _{i}^{*}\) constitutes the shadow price of collision-free road space resources, and directly reflects the value of safety to CAVi. We will elaborate on the economic significance in a later part of this section.

To illustrate the local sensitivity of\(J_{i}(s_{i}^{*})\) to perturbations of the constraint\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\), we need to impose a perturbation\(w_{i}\) on the right-hand side of the constraint\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\leq \boldsymbol{0}\). Corresponding to the vector definition of the coupled constraint\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\) in (21) and (22), we give the definitions of the Lagrange multiplier\(\lambda _{i}\) and the perturbation\(w_{i}\) as

where\(\forall l=1,\dots ,|\mathcal{N}_{i}|\), we have

Here,\(\lambda _{i,j_{l}}^{*}(k)\) and\(w_{i,j_{l}}(k)\) are the multiplier and the perturbation associated with the collision avoidance constraint\(h_{i,j_{l}}(s_{i}(k),s_{j_{l}}(k))\) between CAVi and\(j_{l}\) at time stepk.

For any given\(i\in \mathcal{N}\) and\(s_{\mathcal{N}_{i}} \), the perturbed problem is formulated as

Let the optimal value of problem (29) be\(p(w)=\min J_{i}(s_{i}), \mathrm{s.t.}\ h_{i}(s_{i},s_{\mathcal{N}_{i}}) \leq w_{i}, s_{i}\in S_{i}\). Then it can be proven that\(p(w_{i})\) and\(\lambda _{i}^{*}\) satisfy Theorem 1.

Theorem 1

Let\(\lambda _{i}^{*}\)be the multiplier vector satisfying the KKT conditions (25).Then\(\lambda _{i,j}^{*}=- \frac{\partial p(\boldsymbol{0})}{\partial w_{i,j}}\).

Proof

Let the Lagrangian dual function be\(d(\lambda _{i})= \min _{s_{i}\in S_{i}} J_{i}(s_{i})+\lambda _{i}^{\mathrm{T}} h_{i}(s_{i}, \bar{s}_{\mathcal{N}_{i}})\). By the strong duality condition,\(\lambda _{i}^{*}\) is the optimal solution to the dual problem of the problem (29) when\(w_{i}=\boldsymbol{0}\). For any feasible solution\(s_{i}\) of the problem (29), since\(S_{i}\) is not perturbed, we still have\(d(\lambda _{i}^{*})\leq J_{i}(s_{i})+\lambda _{i}^{*\mathrm{T}} h_{i}(s_{i}, \bar{s}_{\mathcal{N}_{i}})\). Therefore, we have

Consider the perturbation\(\hat{w}_{i}=\operatorname{vec}(0,\dots ,0,\alpha ,0,\dots ,0) \in \mathbb{R}^{ (T-1)|\mathcal{N}_{i}|}\), where\(\hat{w}_{i,j}(k)=\alpha \in \mathbb{R}\) and other components are zero. Then,

From (30), when the perturbation\(w_{i}=\hat{w}_{i}\), any feasible solution\(s_{i}\) of the problem (29) satisfies\(p(\boldsymbol{0})\leq J_{i}(s_{i})+\lambda _{i}^{*\mathrm{T}} \hat{w}_{i}=J_{i}(s_{i})+ \alpha \lambda _{i,j}^{*}(k)\). Since\(p(\hat{w}_{i})\) is the optimal value of the objective function, it satisfies\(p(\boldsymbol{0})\leq p(\hat{w}_{i})+\alpha \lambda _{i,j}^{*}(k)\), then we have

Using this inequality, we obtain

Taking the limit of the above equation yields

Hence,

i.e.,\(\lambda _{i,j}^{*}=- \frac{\partial p(\boldsymbol{0})}{\partial w_{i,j}}\). □

Theorem 1 illustrates the sensitivity meaning of\(\lambda _{i}^{*}\). It is noticed that\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\leq \boldsymbol{0}\) represents the scarcity of collision-free road space resources.\(J_{i}(s_{i})\) is the cost of CAVi, and thus\(-J_{i}(s_{i})\) can be interpreted as the payoff of CAVi. It is seen that\(\lambda _{i,j}^{*}\) equals the marginal rate of increase in the payoff of CAVi when increasing the collision-free road space resource with CAVj, which is called the marginal revenue product in economics, or the rate of decrease in payoff when the resource decreases, under the condition that other conditions remain unchanged. Since road space resources are not tradable, the multiplier\(\lambda _{i}^{*}\) of\(h_{i}\) is the shadow price of collision-free road space resources and directly reflects the value of safety to vehiclei.

To obtain fair interaction among CAVs, the shadow prices of collision-free road space resources for each pair of mutually yielding CAVs should be equal, meaning that both CAVs bear the same rate of payoff decrease to avoid collisions.Hence, an interaction-fair GNE is defined when the following is satisfied:

Some existing studies also provide insights into achieving fairness using equal Lagrange multipliers. For example, [29] explores a Stackelberg game in which the leader sets constraints for the followers and ensures their compliance through incentives, such as taxation or subsidies. The Lagrange multipliers are shown to be the incentive level required to respect the constraints, so equal multipliers imply nondiscriminatory incentives. This game can be applied to the issue of government control of environmental pollution levels. Similarly, [30] interprets the Lagrange multipliers of shared constraints in a GNEP as the prices charged by an administrator to anonymous players. Since players are indistinguishable to the administrator, charging nondiscriminatory prices, i.e., making multipliers equal, is a reasonable approach. Besides, [31] studies a GNE-based autonomous energy management approach in an integrated energy system, where the input energy system is limited by the capacities of electrical feeders and gas pipelines, thus forming global coupled constraints. In this case, the multipliers are the shadow prices charged by energy providers to various residential energy hubs, so identical shadow prices imply fairness. Overall, in existing studies, the Lagrange multipliers of globally shared coupled constraints represent the cost charged by a central entity to all players. In contrast, this paper focuses on bilateral interactions’ coupled constraints between each pair of CAVs, which only apply to the collision-avoidance counterparts. Accordingly, fairness is also formed between each pair of CAVs, not imposed uniformly by the center entity on all CAVs. Therefore, the issues and concepts explored in this paper have structural differences from the aforementioned studies.

Next, we explain that the GNE of Problem 1 satisfying (31) is a VE. To illustrate this point, we first define the variational equilibrium [27]. Define the strategy profile of all CAVs as\(s=\operatorname{vec}(s_{1},\dots ,s_{n})\in \mathbb{R}^{(l_{x}+l_{u})(T-1)n}\), and the pseudo-gradient as

The definition of VE is given by Definition 2.

Definition 2

For the GNE Problem 1, if\(\forall i\in \mathcal{N}\),\(J_{i}\left (s_{i}\right )\) is a convex function, and\(\forall i\in \mathcal{N}\),\(\forall s_{\mathcal{N}_{i}} \),\(S_{i}\) and\(X_{i}\left (s_{-i}\right )\) are closed convex sets, and there exists a closed convex setK such that\(\forall i \in \mathcal{N}\),\(X_{i}\left (s_{-i}\right )=\left \{ s_{i}|\left (s_{i}, s_{-i} \right ) \in K\right \}\), then the solution to the following variational inequality (VI) problem (33) is also a solution to Problem 1: Find\(s^{*}\in K\) such that

The solution to the VI (33) is called a variational equilibrium.

In this problem,\(X_{i}\left (s_{-i}\right )=X_{i}(s_{\mathcal{N}_{i}})\). By Lemma 2,\(S_{i}\) is a closed convex set, thus its Cartesian product\(S=\prod _{i=1}^{n} S_{i}\) is also a closed convex set.\(h_{i}\) is a linear constraint, so its epigraph is a closed convex set ofs, and the intersection of the epigraphs\(X=\{s|h_{i}(s_{i},s_{\mathcal{N}_{i}})\leq 0,\forall i\in \mathcal{N}\}\) is a closed convex set ofs. Hence, the closed convex set\(K=S\cap X\) satisfies the condition required by Definition 2, proving that Problem 1 satisfies the conditions of Definition 2.

In the following, we use the KKT conditions to explain that the interaction-fair GNE is a VE. Let each CAV consider the unrepeated concatenation of\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\) as\(h(s)\leq \boldsymbol{0}\). Since\(h_{i,j}(s_{i}(k),s_{j}(k))=h_{j,i}(s_{j}(k),s_{i}(k))\), and the collision avoidance constraints of any other two CAVs do not appear in the decision problem (23) of CAVi, replacing\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\leq \boldsymbol{0}\) with\(h(s)\leq \boldsymbol{0}\) does not affect the solution. For such a problem with globally shared coupled constraints, the KKT conditions of VI have been analyzed in [32], that is, if\(s^{*}\) is the solution of the VI, then there exists\(\lambda ^{*}\) satisfying

In\(\nabla _{s_{i}} h(s^{*})\), terms unrelated to\(s_{i}^{*}\) are zero. Thus, only the coupled constraints betweeni and its neighbors need to be retained. Hence,\(\nabla _{s_{i}} h(s^{*})\cdot \lambda ^{*}=\sum _{j\in \mathcal{N}_{i}} \nabla _{s_{i}} h_{i,j}(s_{i}^{*},s_{j}^{*})\cdot \lambda _{i,j}^{*}\). Besides, since\(h_{i,j}(s_{i}(k),s_{j}(k))=h_{j,i}(s_{j}(k),s_{i}(k))\), and\(h(s)\) only contains unique collision avoidance constraints,\(h(s)\) only includes either\(h_{i,j}(s_{i}(k),s_{j}(k))\) or\(h_{j,i}(s_{j}(k),s_{i}(k))\), and they correspond to the same Lagrange multiplier, i.e.,\(\lambda _{i,j}^{*}=\lambda _{j,i}^{*}\). Then, explicitly writing out the coupled constraints betweeni and each neighbor\(j\in \mathcal{N}_{i}\), we obtain the KKT conditions of the VI corresponding to the original problem are as shown in Theorem 2.

Theorem 2

If\(s^{*}\)is the solution to the VI (33),then\(\forall i\in \mathcal{N}\),there exists a Lagrange multiplier vector\(\lambda _{i}^{*}\),such that\(\forall i\in \mathcal{N}, \forall j \in \mathcal{N}_{i}\),

Next, we explain the relationship between the KKT conditions (25) of the GNE and the KKT conditions (35) of the VI (33). Theorem 4.8 of [27] analyzed the case of globally shared coupled constraints. But for Problem 1 considered in this work, the coupled constraints\(h_{i,j}(s_{i},s_{j}), j\in \mathcal{N}_{i}\) only exist in the problems of CAVi andj. Accordingly, in the KKT conditions (25) of the GNE and the KKT conditions (35) of the VI (33), only CAVi and\(j\in \mathcal{N}_{i}\) have multipliers\(\lambda _{i,j},\lambda _{j,i}\) associated with\(h_{i,j}(s_{i},s_{j})\). Therefore, the multiplier equality condition\(\lambda _{1}=\dots =\lambda _{n}\) in Theorem 4.8 of [27] is equivalent to\(\lambda _{i,j}=\lambda _{j,i}, j\in \mathcal{N}_{i}\) in the context of this work. The relationship between the KKT conditions (25) and (35) is given by Theorem 3.

Theorem 3

For the GNE Problem 1,the relationship between the KKT conditions (25)of the GNE and the KKT conditions (35)of the VI (33)is as follows.

(1)If\(s^{*}\)is a solution to the VI (33)such that the KKT conditions (35)hold for\(\lambda _{1}^{*},\dots ,\lambda _{n}^{*}\).Then\(s^{*}\)is a GNE,and the KKT conditions of the GNE (25)are satisfied with\(\lambda _{i,j}=\lambda _{j,i}=\lambda _{i,j}^{*}=\lambda _{j,i}^{*}, \forall i\in \mathcal{N}, \forall j\in \mathcal{N}_{i}\).

(2)If\(s^{*}\)is a GNE,such that the KKT conditions of the GNE (25)are satisfied with\(\lambda _{i,j}^{*}=\lambda _{j,i}^{*},\forall i\in \mathcal{N}, \forall j\in \mathcal{N}_{i}\).Then\((s^{*}, \lambda _{1}^{*},\dots ,\lambda _{n}^{*})\)is a KKT point of the VI (33)and\(s^{*}\)is a solution to (33).

According to Definition 2 and Theorem 3, we conclude that a GNE of Problem 1 satisfying (31) is a VE. Therefore, the problem of finding the VE of Problem 1 is called the VE problem.

Based on the modeling and solution analysis of the trajectory planning problem for CAVs as discussed in Sec. 2, this section proposes a semi-decentralized and VE-based planner (SVEP), which has the following characteristics:

1.Fast computation speed: SVEP uses a semi-distributed computation mode where each vehicle only decides its own variables. Additionally, the interaction and information sharing structure of SVEP is such that each CAV only considers the influence of its neighbors’ decisions on its own decision, rather than the decisions of all other CAVs in the game. Therefore, compared to previous game-based trajectory planning algorithms [24,25], SVEP has fewer decision variable dimensions and coupled constraints. Besides, the core optimization problem is formulated as a quadratic programming problem. These factors enable SVEP to achieve real-time planning performance.

2.Small communication payload: In SVEP, the decision variable\(s_{i}\) of each CAV\(i\in \mathcal{N}\) is shared only among its neighbors\(\mathcal{N}_{i}\), while the objective function\(J_{i}(s_{i})\) and private constraints\(s_{i}\in S_{i}\) are not shared. The algorithm operates based on necessary information sharing, minimizing communication payload as much as possible.

3.High scalability: The semi-distributed computation mode results in a much lower computational load on the RSU compared to CAVs. The interaction structure, which considers only neighbors’ decisions, ensures that when a new CAV enters the traffic scenario, it directly affects only the problems of its neighbors, with minimal influence on the overall system.

4.1Algorithm framework

We propose a semi-distributed VE solving algorithm framework based on the augmented Lagrangian method to plan trajectories for CAVs. The advantage of using the augmented Lagrangian method is that it iteratively updates the Lagrange multipliers, thus possessing the ability to explicitly adjust the dual variables, which provides the condition for satisfying the multiplier equality property of the VE; moreover, this method can solve constrained optimization problems with a fast convergence rate.

The core idea of SVEP lies in that each CAV\(i\in \mathcal{N}\) and the RSU alternately optimize\(s_{i}\) and\(\lambda _{i}\) to meet the KKT conditions. The SVEP framework is shown in Algorithm 1, where the superscriptk of variables denotes the iteration number and the subscript\(1:n\) indicates the variables of CAVs 1 ton as input parameters. According to Theorem 3, for the VE problem1, it is only necessary to consider the concordance of the multipliers of the coupled constraints among all constraints and their corresponding multipliers, namely,\(\lambda _{i,j}=\lambda _{j,i},j\in \mathcal{N}_{i}\). Therefore, unlike the typical augmented Lagrangian method, the augmented Lagrangian function in this work consists solely of the objective function and the term of the coupled constraint\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\), as detailed in Sec. 4.2.

Framework of Semi-decentralized and Variational-Equilibrium-Based Trajectory Planner (SVEP)

Full size image

Algorithm 1 focuses on presenting the computational steps of VE, so the communication process between CAVs and the RSU is not explicitly given in this framework. The complete communication and computation steps are presented in Algorithm 2. SVEP first initializes neighbor sets\(\mathcal{N}_{i}\), Lagrange multipliers\(\lambda _{i}^{0}\), and penalty matrices\(D_{h_{i}}^{0}\) for any\(i\in \mathcal{N}\) (lines 1–2). Specifically, by (22), the dimension of\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\) is determined by the cardinality\(|\mathcal{N}_{i}|\) of the neighbor set, so the RSU first determines the neighbor set\(\mathcal{N}_{i}\) for each vehiclei according to theDetermine_Interaction_Relationship rule, and then each CAVi independently and in parallel initializes\(\lambda _{i}^{0}\) and\(D_{h_{i}}^{0}\) corresponding to\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\), where\(D_{h_{i}}^{0}\) is a diagonal positive definite matrix. The Lagrange multiplier and penalty matrix of each CAV are allowed to be initialized to different values, because SVEP designs a consensus step for the multipliers in theUpdate_Multiplier function in line 8, so that the equal multiplier property of VE is satisfied. Each CAVi then minimizes the augmented Lagrangian function to obtain its trajectory\(s_{i}^{k+1}\) (line 4). Under this condition, the convergence of the solution is judged based on the satisfaction of each CAV’s\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\). If all trajectories converge, the planning process ends (lines 5–7). Otherwise, multipliers\(\lambda _{i}^{k+1}\) are updated and coordinated (line 8), and penalty matrices\(D_{h_{i}}^{k+1}\) are increased to drive trajectory convergence (line 9). In this iterative solving part, the computation process of VE is semi-decentralized, where the computation process of each CAV, namely line 4 and line 9, are all parallel. The RSU’s steps only involve simple calculations, which minimizes the computational load on the RSU.

SVEP

Full size image

4.2Algorithm principle and process

The previous subsection has explained the overall approach and framework for solving the VE problem in this work. Next, we will elaborate on the specific computational methods of the core steps in Algorithm 1 using the augmented Lagrangian method, namelyMinimize_Augmented_Lagrangian_Function,Is_Convergent,Update_Multiplier, andUpdate_Penalty_Matrix.

1.Minimize_Augmented_Lagrangian_Function in line 4.

(a) Definition of the augmented Lagrangian function: For the problem (23) of CAVi, we deal with the coupled constraint separately. To use the augmented Lagrangian method, a slack variable\(\gamma _{h_{i}}\) is added to the coupled constraint to turn it into an equality constraint, as shown in (36).

Then the augmented Lagrangian function is defined as

where\(D_{h_{i}}\) is a diagonal positive definite penalty matrix.

(b) The elimination of\(\gamma _{h_{i}}\). When applying the augmented Lagrangian function method, the subproblem to be solved is as follows: Given\(s_{\mathcal{N}_{i}}\),\(\lambda _{i}\) and\(D_{h_{i}}\), we seek the minimal solution\(s_{i}\) and\(\gamma _{h_{i}}\) to\(L_{i}\). Actually, the optimal solution of\(\gamma _{h_{i}}\) can be expressed as a function of\(s_{i}\). By fixing\(s_{i}\), we obtain an optimization problem with respect to\(\gamma _{h_{i}}\):

The problem is a convex optimization problem with non-negative constraints. From the optimality conditions, we obtain the optimal solution

Thus, when seeking the minimal solution of\(L_{i}\), we can substitute the above optimal solution to eliminate\(\gamma _{h_{i}}\), obtaining\(h_{i}(s_{i},s_{\mathcal{N}_{i}})+\gamma _{h_{i}}=\max \{-D_{h_{i}}^{-1} \lambda _{i},h_{i}(s_{i},s_{\mathcal{N}_{i}})\}\), and the problem is transformed into an optimization problem regarding\(s_{i}\).

(c) Processing and solving the optimization problem. In thek-th iteration of the augmented Lagrangian method, given\(s_{\mathcal{N}_{i}}^{k}\), CAVi solves the following problem

Since\(\gamma _{h_{i}}(s_{i})\) characterized in (39) includes max, (40) is a non-smooth function. To convert it to a smooth function, a decision variable\(w_{h_{i}}\) is introduced to replace the term\(h_{i}(s_{i},s_{\mathcal{N}_{i}})+\gamma _{h_{i}}\), while constraints\(-w_{h_{i}}+h_{i}(s_{i},s_{\mathcal{N}_{i}})\leq \boldsymbol{0}, -w_{h_{i}}-D_{h_{i}}^{-1} \lambda _{i}\leq \boldsymbol{0}\) are imposed. This approach does not change the optimal solution. After processing, in thek-th iteration, the augmented Lagrangian function becomes

and CAVi solves the following problem

Since\(J_{i}(s_{i})\) is a convex quadratic function of\(s_{i}\) and\(D_{h_{i}}\) is a diagonal positive definite matrix,\(L_{i}^{k}(s_{i},w_{h_{i}},\lambda _{i}^{k})\) is a convex quadratic function of\(s_{i},w_{h_{i}}\). Given that both\(S_{i}\) and\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\) are linear constraints, the problem (42) is a quadratic programming problem, which can be solved using algorithms such as the interior-point method or the active set method. In addition, the constraints involved in the problem (42) formed at each iteration are re-linearized at\(s_{i}^{k}\), ensuring that the deviation between the linearized constraints and the original constraints remains within a small range.

2.Is_Convergent in line 5.

The constraint violation is defined as

(43)

When the constraint violation is below the thresholdϵ, the solution\(s^{k+1}\) converges and the iteration is terminated.

3.Update_Multiplier in line 8.

For the problem (40) in thek-th iteration, the optimal solution\(s^{k+1}_{i}\) satisfies

Comparing (44) with the stability condition in the KKT conditions of the slack problem (36)

we obtain the multiplier update formula

To get a VE, (31) must be satisfied. Therefore, the multiplier consensus step is designed as follows:

Thus, the multipliers satisfy\(\lambda _{i,j}^{k+1}=\lambda _{j,i}^{k+1}\) after each iteration.

4.Update_Penalty_Matrix in line 9.

At the end of each iteration, the penalty matrix is exponentially increased as

The effect of increasing the penalty matrix is that the penalty for not satisfying\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\) increases, driving the solution to enter the feasible region.

Based on the aforementioned descriptions, the complete SVEP algorithm process incorporating communication and computation is summarized in Algorithm 2.

4.3Dimensional analysis in computing

The dimension of decision variables and the number of coupled constraints are two key aspects influencing the algorithm’s efficiency. Benefiting from the semi-distributed framework and the information sharing structure where each CAV only considers the decisions of its neighbors, each CAV’s problem only involves local decision variables. This small-scale decision problem allows for fast solving speed. Table 4 compares the computational dimensions of SVEP with those of trajectory planning algorithms based on GNE without V2X (ALGAMES [24], iLQGames [25]), demonstrating the advantages of SVEP in terms of computational efficiency. The detailed analysis is as follows.

• Dimension of decision variables: Benefiting from the semi-decentralized computational mode, in SVEP, each CAV only decides on its own variables, thus the dimension of decision variables is lower. According to (42), the decision variables in SVEP consist of\(s_{i}\in \mathbb{R}^{(l_{x}+l_{u})(T-1)}\) and\(w_{h_{i}}\in \mathbb{R}^{(T-1)|\mathcal{N}_{i}|}\). In non-CAV algorithms like ALGAMES and iLQGames, each vehicle decides on the strategy profiles for all vehicles. Therefore, the decision variables in ALGAMES are the state and control sequences with a dimension of\((l_{x}+l_{u})(T-1)n\), while in iLQGames, the decision variables are the state sequences with a dimension of\(l_{x}(T-1)n\).

• Number of coupled constraints: A major advantage of SVEP in terms of the number of constraints is that it only considers collision avoidance constraints with neighbors. According to (22), the dimension of\(h_{i}(s_{i},s_{\mathcal{N}_{i}})\) is\((T-1)|\mathcal{N}_{i}|\). ALGAMES and iLQGames consider collision avoidance constraints with all other vehicles, with a dimension of\((T-1)(n-1)\). In addition, fewer coupled constraints also mean fewer dual variables.

From the expressions, it can be seen that the dimensions in SVEP are relatively less affected by the number of vehicles, because\(|\mathcal{N}_{i}|\leq n-1\) and\(|\mathcal{N}_{i}|\) is not an independent multiplicative term in the number of decision variables. The more vehicles there are, the greater the computational efficiency advantage of SVEP; hence, SVEP has better scalability. Besides, the number of coupled constraints is also smaller in SVEP, resulting in a smaller communication payload for SVEP.

5.1Experimental setting

As described in Sec. 2, SVEP is applicable to a two-way road environment without traffic signals, with an RSU and a 100% penetration rate of CAVs. This section conducts experiments in the environment of a two-way, two-lane intersection with a lane width of 4 m and a minimum curve boundary radius of 8 m, as shown in Fig. 6. Here, the criterion for determining neighbors is set to a distance of less than 50 m between the centers of two CAVs. The initial value of the strategy profile\(s^{0}\) and the reference trajectory\(x_{ref,i}\) for each CAV\(i\in \mathcal{N}\) are generated using quintic polynomials.

Experimental scenario and situation setup. The scenario is a signal-free intersection equipped with an RSU, and all vehicles are CAVs. The solid rectangles marked in the legend represent the area covered by the random initial positions of each CAV. CAVs follow the virtual lane constraints marked by the gray dashed lines within the intersection and travel in the direction indicated by the arrows.

Full size image

We compare SVEP with ALGAMES [24]. SVEP is implemented in Matlab, while ALGAMES provides open-source code written in Julia. Both are programming languages commonly used in scientific computing, and as a compiled language, Julia has better computational performance than Matlab. Therefore, the algorithm in this paper does not gain additional efficiency advantages due to the programming language. The vehicle dimensions and constraint parameters of ALGAMES are set the same as those of SVEP. In the planner parameters, both of them use the sameT,\(T_{s}\), andϵ, while other parameters of ALGAMES follow the default settings in its open-source implementation. The vehicle dimensions, constraint parameters, and planner parameters used by SVEP are presented in Table 5. As shown in Table 7, the success rate of ALGAMES in the merging scenario is low. We set the constraint violation threshold of ALGAMES as\(\epsilon =1\times 10^{-1}\) in the merging scenario, since otherwise, other metrics of ALGAMES in the merging scenario cannot be analyzed. The program runs on a desktop computer equipped with an Intel Core i5-10400F CPU, 16 GB of RAM, and the Windows 11 operating system.

5.2Evaluation and analysis

This subsection will use the Monte Carlo method to assess the algorithm’s computational efficiency and safety. We design four scenarios for the experiments, as shown in Fig. 6. Each scenario features an intersection with the same parameters as described in Sec. 5.1, while differing in the number, initial states, and driving directions of CAVs. These situations cover typical driving behaviors at intersections: Going straight, turning left, and turning right, as well as all types of conflicts: Crossing and merging conflicts, with three straight-driving scenarios involving crossing conflicts, whereas the merging scenario involves merging conflicts. In this figure, the solid rectangles marked in the legend represent the area covered by the random initial positions of each CAV. CAVs follow the virtual lane constraints marked by the gray dashed lines within the intersection and travel in the direction indicated by the arrows. The initial speeds of the CAVs are uniformly distributed in\([5, 15]\) m/s. For\(\forall i\in \mathcal{N}\), the value of\(D_{h_{i}}^{0}\) is set to\(D_{h_{i}}^{0} = diag(d_{h_{i}},\dots , d_{h_{i}})_{ |\mathcal{N}_{i}|}\), where\(d_{h_{i}}\sim U[0.5, 1.5]\). Next, we will evaluate the algorithm’s performance in terms of computational efficiency and safety.

The experiments use a receding horizon mode. After planning a trajectory, only the initial control\(u_{i}(1)\) is applied. The environment, using the original non-linear kinematic model, simulates the vehicle’s motion and feeds back the vehicle’s state at the next moment to the planner. Then the planner subsequently performs the next planning. The experiment includes the following two parts.

5.2.1Computational efficiency

We consider the time cost of SVEP, which consists of the computation time per vehicle, the RSU computation time, and the communication time.

(a) Computation time per vehicle: We evaluate the computational efficiency of the algorithm using the average computation time per trajectory planning for each vehicle as one of the evaluation metrics. In the scenario shown in Fig. 6, all vehicles use the same algorithm, either SVEP or ALGAMES, to plan trajectories, and 500 Monte Carlo simulations are conducted to measure the average computation time.

We take the straight-driving CAV 1, common to all scenarios, as an example. The box plot of its planner’s average computation time is shown in Fig. 7. Note that different vertical axis ranges and scales are set for the two algorithms in the figure due to significant differences in average computation time. In terms of extremums and quartiles, SVEP is more computationally efficient across all four test scenarios. The statistical results of the straight-driving scenario are a direct basis for the algorithm’s scalability. As the number of vehicles increases from 2 to 4, the median of the average computation time for SVEP and ALGAMES increases by 38.4% and 290.8%, respectively, consistent with the growth trend of dimension analyzed in Sec. 4.3. The moderate growth in computation time indicates SVEP’s adaptability to rising traffic density and scale. On the other hand, the number of vehicles that need to interact with the ego vehicle in the traffic environment is very limited, resulting in the expansion of the neighbor set being slower than the growth in the number of vehicles. This sets a natural upper limit for SVEP’s dimension of decision variables and number of coupled constraints, effectively limiting the computation time. Thus, SVEP is highly scalable, maintaining efficiency as the number of vehicles increases. The average computation time in merging scenarios indicates that SVEP is also highly efficient in planning turning trajectories and resolving merging conflicts. For SVEP, compared to the three-vehicle straight-driving scenario, the period of significant conflict in multi-vehicle trajectories in this scenario is shorter, resulting in shorter average computation times. With ALGAMES, the number of outer loop iterations reaches its limit during iteration in this scenario, explaining its longer computation time. Therefore, SVEP has better equilibrium convergence.

The average computation time of CAV 1 in straight-driving (S.D.) and merging (M.) scenarios using SVEP and ALGAMES. SVEP and ALGAMES use the left and right vertical axes, respectively, to visualize the data within their appropriate ranges.

Full size image

(b) The RSU computation time: In addition to the computation time per vehicle, SVEP also has time overheads associated with V2X, namely the computation time and communication time of the RSU. These two parts of time have also been evaluated. The mean and standard deviation of the average computation time of the RSU in each trajectory planning, measured from the above Monte Carlo experiments, are recorded in Table 6. It is seen that the average computation time of the RSU is about an order of magnitude less than that of CAVs. Therefore, the computation time of the RSU does not constitute the main part of SVEP’s running time.

(c) Communication time: We measure the communication time in the worst case, i.e., using\(k_{\max}\) iterations to complete planning in the four-vehicle straight-driving scenario. Using 32-bit floating-point numbers to store data and conducting 200 repeated experiments under 5G WiFi, the average communication time per planning is measured to be\(4.8\times 10^{-3}\) s. Theoretically, according to the 3GPP requirements for advanced driving [33], the communication time at the lowest data rate of 30 Mbps is\(1.26\times 10^{-2}\) s.

In summary, under the conditions of 5G NR-V2X, the runtime of SVEP in the four experimental scenarios is less than\(1\times 10^{-1}\) s, meeting the requirements for real-time planning. It also shows high scalability with respect to the number of CAVs, thus demonstrating potential for application in complex traffic environments and in solving large-scale trajectory planning problems.

5.2.2Safety

The success rate is defined as the proportion of experiments in which all CAVs reach their designated positions without violating any constraints. In our experiment implementation, truncation operations are used to forcibly limit\(u_{i}(k)\) within the feasible region, so the cases of constraint violations only include exceeding the speed limit, crossing lane boundary lines, and collisions. Therefore, the success rate is an appropriate metric for evaluating the safety of the algorithm. Here we use the same settings as the computational efficiency experiments to conduct 500 Monte Carlo experiments, and the success rates are shown in Table 7. SVEP maintains high safety in all experimental scenarios without violating constraints. As seen from the data in the right column, as the number of vehicles in the straight-driving scenario increases, the difficulty of planning safe trajectories also increases. The result indicates that the influence of the problem scale on the safety of SVEP is minor.

In particular, the safety advantages of SVEP are significant in the merging scenario. Note that in the merging scenario, the success rate of ALGAMES is 72.8% when the constraint violation threshold is\(\epsilon =1\times 10^{-1}\), while the success rate is 0% if\(\epsilon =1\times 10^{-3}\). The low success rate under the constraint violation threshold\(\epsilon =1\times 10^{-3}\) explains why we set\(\epsilon =1\times 10^{-1}\) for the merging scenario in Section 5.1. Due to the use of bounding ellipses instead of circles for lane constraint modeling, SVEP allows vehicles to have a sufficient feasible region for their poses under lane constraints. Turning maneuvers are more complex than straight driving, and trajectory planning on bends is more challenging, so expanding the feasible domain is important for improving the planner’s success rate on bends. The reference trajectory term\(x_{ref,i}(k)\) in the objective function has a positive effect in guiding the planner to obtain safe trajectories. Additionally, as analyzed in the computational efficiency part, SVEP has good equilibrium convergence. These factors contribute to the safety of SVEP in merging scenarios. Taking the average initial state of the merging scenario as an example, using two planners to complete the simulation, the vehicle trajectories are shown in Fig. 8a and Fig. 8b. In comparison, SVEP’s turning trajectory is smoother. In terms of control inputs, as seen from the front wheel steering angle curves in Fig. 8c and Fig. 8d, SVEP provides a steering angle that deflects only towards the required direction of turn for the vehicle, with smooth angle changes, which indicates that SVEP avoids unnecessary back-and-forth steering, reducing the risk of exceeding the lane boundaries.

Planning results using SVEP and ALGAMES. The arrow sequence shows the position and yaw angle of the vehicles every 0.4 s, with its length proportional to the velocity. (a) SVEP’s trajectory. (b) ALGAMES’s trajectory. (c) SVEP’s front wheel steering angles. (d) ALGAMES’s front wheel steering angles.

Full size image

Another important factor affecting safety is whether the equilibrium solved by each vehicle is the same, that is, whether each vehicle’s predicted decisions of other vehicles match the actual decisions. Only under this condition can the coupled constraint\(h_{i}\) perform accurate collision avoidance. Existing research has found that trajectory planning as a game problem may have multiple non-isolated or isolated equilibrium [24]. Therefore, without a coordination mechanism, each vehicle may converge to different equilibrium, leading to misjudgment of other vehicles’ decisions. We set the criterion for equilibrium concordance as the distance between predicted and actual\(u_{i}(1)\) being less than\(1\times 10^{-1}\), and define the average ratio of the number of times the planning between any pair of vehicles reaches equilibrium concordance in each experiment as the equilibrium concordance rate. The results are shown in Table 8, where for ALGAMES, we separately calculate the equilibrium concordance rate for successful cases (without vehicle collision) and failed cases (with vehicle collision). Through sharing\(s_{i}\) and coordinating\(\lambda _{i}\) by our designed Algorithm 1 (SVEP), CAVs can obtain a consistent VE. In contrast, the uncoordinated ALGAMES may lead each vehicle to converge to different equilibrium. In the same scenario, the equilibrium concordance rate is higher in successful cases than in failed cases, which means that the concordant equilibrium can promote the safety of trajectories. For failed cases, since the statistics also include the equilibrium concordance rate before unsafe control occurs, the average equilibrium concordance rate is also relatively high. Therefore, the V2X-based equilibrium coordination approach in our Algorithm 1 can indeed positively contribute to safety.

However, the equilibrium concordance rate is not the sole factor determining the success rate. The difficulty of planning safe trajectories also significantly influences the success rate. Comparing the right-column data in Table 7 and Table 8, it can be seen that the merging scenario has both low success rate and low equilibrium concordance rate, but in the straight-driving scenario, the numerical order of the equilibrium concordance rate and success rate is not the same. We believe that the main reason for the decline in success rate from 2 vehicles to 4 vehicles is the increased difficulty in solving due to intensified vehicle conflicts and the increased problem scale. On the other hand, intensified conflicts reduce the feasible region, which tends to decrease the number of equilibrium, possibly leading to an increase in the equilibrium concordance rate.

Overall, for non-CAV game algorithms, although they solve complete information games, different initialization methods or parameter settings (such as\(D_{h_{i}}^{0}\)) within the solver may lead to different equilibrium. This misjudgment of decisions is one of the causes of unsafe trajectories. Therefore, the V2X-based equilibrium coordination approach of SVEP has positive significance for enhancing safety. It should be noted that although SVEP has performance advantages in experiments, these advantages come at the cost of relying on network communication.

We focus on traffic scenarios where the penetration rate of CAVs is 100% and equipped with an RSU, and propose a semi-decentralized and VE-based CAV trajectory planner (SVEP) to resolve the computational efficiency and safety problems of previous uncoordinated game theoretic planners. By decomposing the computation process for each vehicle, the proposed planner can eliminate redundant computations for equilibrium to enhance efficiency. In addition, to enhance the safety of trajectory planning, SVEP handles collision avoidance coupled constraints based on the augmented Lagrangian method, and designs a Lagrange multiplier consensus mechanism to ensure that each CAV converges to concordant equilibrium with the help of the RSU. This mechanism also ensures that each CAV obtains an interaction-fair trajectory. In particular, this work theoretically proposes the concept of interaction fairness, and reveals that the interaction-fair GNE in this problem is a VE through sensitivity analysis. Finally, Monte Carlo experiments demonstrate that the proposed method meets the requirements of autonomous driving for real-time planning, has a small communication payload, favorable scalability, and reliable safety.