# Data-Driven Test Scenario Generation for Cooperative Maneuver Planning on Highways
## 2 Materials and Methods
### Simulation Environment
#### 2.4.2 Cooperative Behavior Planner  
The scenario generation approach presented in Section 2.1 needs a cooperative solution for each traffic scenario in order to evaluate if it benefits from cooperative behavior and can therefore be regarded as a valid test scenario. However, it is not easy to prove that a maneuver planner works sufficiently well for this purpose. One option is to use a procedure that centrally optimizes the global utility for all vehicles and inherently finds the best solution within the selected discretization level for every planning problem. In order to model the maneuver planning level of a vehicle, a tree structure is used that contains all possible states of a scenario. Starting from the beginning of the scenario, the root node, all vehicles perform actions over a discrete time step, which leads to the next node in the next time step. Each node contains the movement state of all vehicles. In this way, the tree expands through time until the end of the planning horizon \(t_{end}\). Figure 2 shows this approach using an example scenario with one vehicle. The optimal solution of the scenario within the selected discretization in time and actions is the sequence of nodes that causes the lowest costs according to the cost function presented in Section 2.3. Due to the exponential growth of tree states:  
\[n_{states}=A^{mt_{end}/\Delta t} \tag{2}\]  
with number of actions \(A\), number of vehicles \(m\) and number of time steps \(t_{end}/\Delta t\) the search tree becomes too large to calculate each state. Therefore, a tree search method is used to find the best solution for the scenario with the least possible computation effort. In a previous work [27], we solved the scenarios by applying the Monte Carlo Tree Search Method (MCTS). However, since there is no guarantee for the optimality of the solution in the MCTS procedure, an A* algorithm is used instead. The A* algorithm aims to find the best sequence of nodes from the start node to a goal node. Therefore, it expands iteratively the nodes of the tree, as depicted in Figure 2, by performing one possible action for each vehicle in the scenario, which again leads to a new node. Each node \(n\) is associated with costs \(g(n)\) according to the metric described in Section 2.3 applied to all previous actions up to the start node. Furthermore, a node is evaluated by a heuristic \(h(n)\) which estimates the minimum costs to reach a goal node from the respective node \(n\). The decision of which node to expand is based on the function \(f(n)=g(n)+h(n)\). The algorithm puts each new node in a queue sorted by the minimum value of \(f(n)\). At each iteration, the node with the lowest value is taken from the queue and being expanded. The new successor nodes are sorted into the queue and again the node with the lowest value of \(f(n)\) is chosen. This procedure continues until a goal node has the lowest \(f\) value. If \(h(n)\) is guaranteed to underestimate the real costs to reach a goal node, the path to the chosen goal node represents the least-cost sequence of nodes and therefore the optimal solution. Since the algorithms purpose is to operate the vehicles with smallest possible costs over the length of a scenario, all nodes that lie on the planning horizon \(t_{end}\) are valid goal nodes. The definition of the vehicles' possible actions as well as the derivation of \(h(n)\) are described in the following. For a more detailed description of the A* search algorithm, please refer to ([28], p. 93 ff.). Figure 2: Structure of the search tree. As described in Section 2.1, the results of the cooperative behavior planning are compared to those of the reference planner. To ensure that the differences between the two methods result from intelligent planning and not from an unequal action space, the actions must be constrained by the same limits. In the IIDM model, the parameter \(a\) represents the upper limit for positive accelerations.