## 2 Motion-Planning Graph-Based Algorithm
### Computing the Lateral Positions of the Nodes  
Firstly, the lateral positions of the nodes for the candidate vehicle trajectories are calculated. In the calculation, the limitation of the lateral acceleration is incorporated to avoid the skidding of the vehicle and uncomfortable trajectories. Since the lateral acceleration increases as the lateral position of the node increases, the inequality \(|c_{max,i}|\geq f(x_{l,i},y_{l,i},\psi_{initial,i})\) for the limitation must be satisfied.Moreover, limitations on the lateral position \(y_{min}\leq y_{i}\leq y_{max}\) is considered. Taking into consideration these limitations, the set of possible lateral positions can be computed \((\mathcal{Y})\). In Figure 2 an example of the limitations can be seen. As it can be seen, the lateral position of \(n^{th}\) node cannot be selected to the value of \(y_{max}\) since the lateral acceleration between the two nodes are higher than the previously defined maximum. However, the lateral position of the 1 st node is limited with the road-specific constraint \((y_{min})\).  
Secondly, the positions of the nodes in the given segment is determined. The main aspect during the computation of the lateral positions is to consider different types of maneuvers (e.g., overtaking another vehicle, avoiding an obstacle). In order to achieve this, the positions are computed using the lateral accelerations. The set of \(a_{cp,max,i}\) can be computed (\(\mathcal{A}_{cp}\)). In the following step, the lateral positions are calculated as:  
\[y_{i}\in\mathcal{Y},\quad a_{cp,i}=min(\mathcal{A}_{cp})+\frac{i(max(\mathcal{ A}_{cp})-min(\mathcal{A}_{cp}))}{N},\quad c_{max,i}=f(x_{i},y_{i},\psi_{initial,i}) \quad i=1..N, \tag{4}\]  
where \(N\) gives the number of nodes connected to the other node. Acceleration values are determined equidistantly. Using the computed lateral accelerations, the lateral positions of the given nodes can be calculated. The computation can be made along the whole prediction horizon. Using this method, the limitations on the lateral acceleration value can be guaranteed. Assuming that the vehicle moves into one direction in the given prediction horizon, this results in a directed graph, projected on the road:  
\[G=(V,\bar{E}), \tag{5}\]  
where (\(V\)) gives the nodes, which are connected with the edges \(\bar{E}\). In Figure 3 an example is shown. In this case, the number of nodes connect to another is set to 5. The gray lines show the edges of the graph, and the blue curves are the feasible trajectories, which are computed by the predictive optimization method. The red curves are also the feasible trajectories, but these trajectories take place in the second layer of the graph (second step in the longitudinal direction).  
Figure 3: An example for the graph.  
Figure 2: Limitations during the graph generation.  
In Figure 3 feasible trajectories can be found between the nodes. Since the initial yaw angle plays an important role during the trajectory planning, axis \(z\) represents the yaw angle of the vehicle at the end point of the designed trajectory. The lateral acceleration for each segment can be determined and this lateral acceleration series can be considered as an upper bound of the lateral acceleration of the whole trajectory.