# A Graph-Based Method for Tactical Planning of Lane-Level Driving Tasks in the Outlook Region
## 6 Computing the Optimal Lane-Level Driving Task  
Here, we aim to obtain the lane-level driving task with the shortest travel time within the outlook region. This problem can be specifically described as finding the minimum-cost path from an entry node to any available exit node in a given directed graph. The available exit nodes correspond to the exit cells of all available lanes within the outlook region, as shown in Figure 6. In this figure, Lanes 1, 2, and 3 extend beyond the outlook region, each generating an exit node, while Lane 4 merges into the adjacent lane within the outlook region, so there is no exit node generated from this lane. This is a minimum-cost path problem in a directed graph which we solve using [PERSON]'s algorithm. During one solving process, all minimum-cost paths to all exit nodes can be obtained simultaneously. Then, the real minimum-cost path among all above paths will be selected to generated the final lane-level driving task.  
The basic principle of [PERSON]'s algorithm can be described by the following equation:  
\[C_{u,~{}\overline{N}_{k}}=\min_{\begin{array}{l}p\in N_{k}\\ q\in\overline{N}_{k}\end{array}}\left\{C_{u,p}+C_{p,q}\right\}, \tag{10}\]  
where \(N_{k}\in N\) denotes all searched nodes after \(k\) steps, \(\overline{N}_{k}=N\smallsetminus N_{k}\) denotes all unsearched nodes until \(k\) steps, \(u\) denotes the origin node, \(p\) denotes any node in \(N_{k}\), \(q\) denotes any node in \(\overline{N}_{k}\), and \(C_{u,p}\) represents the cumulative cost of traveling from origin node \(u\) to node \(p\), while \(C_{p,q}\) represents the cumulative cost of traveling from node \(p\) to node \(q\). \(C_{p,q}\) is defined in Equations (3) and (5).  
According to the cost calculation method defined in Equation (10), the lane-level driving task obtained may have one issue: it contains too many lane changes. Excessive lane-change maneuvers will reduce the likelihood of the ego vehicle successfully following the driving task and may also disrupt traffic. Therefore, the factor of lane-change times is introduced into Equation (10). The revised cumulative cost is as follows:  
\[C_{u,\,\overline{N}_{k}}=\min_{\begin{array}{l}p\in N_{k}\\ q\in\overline{N}_{k}\end{array}}\big{\{}C_{u,p}+C_{p,q}+\lambda\cdot F\big{\}}, \tag{11}\]  
where \(F\) denotes the coefficient about direction; \(F=1\) when \(C_{p,q}\) represents the cost of a lateral edge and \(F=0\) when \(C_{p,q}\) represents the cost of a longitudinal edge. \(\lambda\) denotes the coefficient about the limitation of lane-change times, which is considered as a constant here. The number of lateral edges contained in \(C_{u,p}\) represents the lane-change times of the corresponding lane-level path. The more lane changes it contains, the higher extra cost it has; thus, the path will have a lower priority in the decision-making of the final lane-level driving task.  
It should be noted that the lane-level driving task with the minimum cost obtained here is the task that the vehicle is expected to follow, but in actual driving, the vehicle may not be able to change lanes in time due to interference from local traffic vehicles. An alternative path is introduced into the lane-level driving task to guide the vehicle to slow down and wait at the necessary location. The alternative path only includes lane-following maneuvers, which represents the maximum distance that the vehicle can travel in the outlook region without changing lanes and will not deviate from the navigation route, as shown in Figure 3.