# Design of a Reinforcement Learning-Based Lane Keeping Planning Agent for Automated Vehicles
## 3 Methodology  
### Monte Carlo Tree Search  
The most concerning weakness of classic uninformed search methods is not that they cannot find the optimal solution if there is one, but that they cannot operate in a real-time manner because the needed computational power is lacking. On the other hand, greedy algorithms that use heuristics to find optimal solution come with no guarantees. Thus, they likely end up in suboptimal solutions or with no solution at all. The Monte Carlo tree search algorithm mitigates these concerns thanks to its unique approach to the node selection procedure and individual nodes' value assignment. The Upper Confidence bound applied for Trees (UCT) algorithm is responsible for selecting the currently most promising nodes in every branch during the iteration process. Therefore, a bandit algorithm navigates through the tree from root to leaf, which handles the exploration-exploitation dilemma as a tunable trade-off. Consequently, the heart of MCTS is the bandit algorithm. The bandit-based approach is firstly introduced in the realm of clinical trials [32], and the research area of animal and human learning [33]. Such methods can be applied to any decision-making problem that has uncertainty. For more details on bandit algorithms, see [34]. MCTS algorithm's value assignment is unique since it determines a node's value by continuing the process from the given state until a terminal state, with a default policy. Random play based value assignment seems insufficient at first, but research papers that apply parallelization to this algorithm show that the averaged value of more random play from the given node does not result in a meaningful performance boost [35]. Thus a single random rollout is quite representative. The UCT algorithm looks as follows,  
\[\overline{X_{i}}+2C_{p}\sqrt{\frac{2\ln N_{i}}{n_{i}}}, \tag{17}\]  
where \(\overline{X_{i}}\) is the average value of the currently examined node, \(C_{p}\) is a constant that helps in the controlling of the exploitation-exploration trade-off, and \(N_{i}\) is the number of visits of the ancestor node, while \(n_{i}\) is the number of visits of the currently examined node. The MCTS algorithm has an essential advantage over its competitors, notably that it converges to the globally optimal solution if enough time is given [36]. For a more comprehensive study on MCTS, see in [37].  
This approach can be seen as a parametrizable trade-off between the uninformed and the greedy search concepts. The first part of the UCT algorithm represents exploitation. Therefore, if it chooses the next node exclusively, it behaves as a greedy algorithm. On the other hand, the second part represents exploration that leads to the node, which has the lowest visit count on the branch. Thus if it chooses the next node exclusively, it behaves like a uninformed search algorithm.  
The MCTS algorithm builds a tree-based representation of the domain by repeating the Selection, Expand, Rollout, and Backpropagation steps.  
* Selection: Selects the nodes with the highest UCT value in every selection process until a leaf node is found.
* Expand: If the examined node has not visited yet, it populates its child nodes, if there is any.
* Simulation: Executes a Monte Carlo rollout until a terminal state is found.
* Backpropagation: If a terminal state is found at the end of the simulation, the terminal state's value is backpropagated along the path from the leaf to root.  
After a certain number of iterations, the MCTS suggests an action. Thus, the action selection policy is essential. In this case, the robust-child [37] approach is utilized, which selects the action that instantiates the child node that has the most visits from all child nodes on the branch.  
In this paper, the MCTS algorithm is utilized as a benchmark for comparison to other algorithms and a training data generator for supervised learning.