## 4 Proposed Extension to CARLA
### PGM for Modeling Complex Urban Environment
By taking DAGs into account, the joint probability distribution \(p(x)\) can be factored using Equation (2), which typically uses a much smaller set of \(\Theta\) than the general factorization (Equation (1)). The set of parameters \(\Theta\) represents all the probability distributions, \(p\left(x_{jl}\mid\mathbf{pa}_{jk}\right)\). Each parameter \(\Theta_{jkl}=p\left(x_{jl}\mid\mathbf{pa}_{jk}\right)\) defines the probability that variable \(X_{j}\) takes its \(l-th\) possible value given that the parents \(\mathbf{PA}_{j}\) of \(X_{j}\) take their \(k-th\) value. Each variable \(X_{j}\) has a set of \(d_{j}\) values. As a result, the set of potential values for a random vector is the product of the sets of possible values for each \(X\) such that the parent \(\mathbf{PA}_{j}\) of variable \(X_{j}\) takes \(D_{j}=\prod_{i/X_{i}\text{e}\mathbf{PA}_{j}}d_{i}\) different values. As the size of the model increases, the BN model derived from a set of examples becomes impractical. Therefore, we learn the BN. Generally, the process of learning a BN with DAG \(\mathcal{G}\) and parameters \(\Theta\) from a data set \(\mathcal{D}\) comprising \(n\) observations can be accomplished in two steps, Equation (3). Following the \(\mathcal{D}\) provision, the BN is learned in two stages: structural learning and parametric learning. \[\underbrace{P(\mathcal{G},\Theta\mid\mathcal{D})}_{\text{Learning}}= \underbrace{P(\mathcal{G}\mid\mathcal{D})}_{\text{Structure Learning}}\cdot \underbrace{P(\Theta\mid\mathcal{G},\mathcal{D})}_{\text{Parameter Learning}} \tag{3}\]  
Finding the \(\mathcal{G}\) that encodes the dependent structure of the data constitutes structure learning. In this research, we opt for the Hill Climbing (HC) search algorithm to learn the structure of the BN. In Algorithm 1, the initialization phases (steps 1 and 2) are followed by an HC search (step 3). HC executes local moves such as arc additions, deletions, and reversals to explore the area around the current candidate \(\mathcal{G}_{max}\) in the space of all possible DAGs aiming to locate the \(\mathcal{G}\) (if any) that raises the score Score \((\mathcal{G},\mathcal{D})\) the most over \(\mathcal{G}_{max}\). Then, in each iteration, the HC attempts to add each potential arc that is not already present in \(\mathcal{G}_{max}\), as well as to delete and reverse each arc in the current optimal \(\mathcal{G}_{max}\). For all the remaining acyclic DAGs \(\mathcal{G}^{*}\), the HC calculates \(\mathcal{S}_{\mathcal{G}^{*}}=\text{{Score}}\left(\mathcal{G}^{*},\mathcal{D}\right)\). The new candidate \(\mathcal{G}\) is the \(\mathcal{G}^{*}\) with the highest \(\mathcal{S}_{\mathcal{G}^{*}}\). If this DAG has \(\mathcal{S}_{\mathcal{G}}>S_{max}\), then \(\mathcal{G}\) becomes the new \(\mathcal{G}_{max}\), and \(S_{max}\) is set to \(S_{\mathcal{G}}\) and HC moves to the next iteration. On the other hand, if \(S_{\mathcal{G}}<S_{max}\), the HC reaches an optimum. ```
Input: a dataset \(\mathcal{D}\) from \(X\), an empty DAG \(\mathcal{G}\), a score function Score \((\mathcal{G},\mathcal{D})\). Output: the \(\mathcal{G}_{max}\) that maximizes the Score \((\mathcal{G},\mathcal{D})\). 1: Compute the score of \(\mathcal{G}\), \(S_{\mathcal{G}}=Score\ (\mathcal{G},\mathcal{D})\). 2: Set \(S_{max}=S_{\mathcal{G}}\) and \(\mathcal{G}_{max}=\mathcal{G}\)
3: Hill Climbing: repeat as long as \(S_{max}\) increases. (a) For each potential arc addition, deletion, or reversal in \(\mathcal{G}_{max}\) resulting in a DAG: (i) Compute the score of updated \(\mathcal{G}^{*}\), \(S_{\mathcal{G}^{*}}=Score\ (\mathcal{G}^{*},\mathcal{D})\) (ii) \(S_{\mathcal{G}^{*}}>S_{max}\) and \(S_{\mathcal{G}^{*}}>S_{\mathcal{G}}\), then set \(\mathcal{G}=\mathcal{G}^{*}\) and \(S_{\mathcal{G}}=S_{\mathcal{G}*}\) (b) If \(S\mathcal{G}>S_{max}\), set \(S_{max}=S_{\mathcal{G}}\) and \(\mathcal{G}_{max}=\mathcal{G}\)
```  
**Algorithm 1** Hill-climbing search algorithm for structure learning  
As a local search algorithm, the HC can get stuck in the local optima.