# Selecting Remote Driving Locations for Latency Sensitive Reliable Tele-Operation
## 3 Selecting Driving Locations for Multiple Paths
### Selecting the Smallest Number of Remote Drivers under Latency Constraint
Suppose that a driving location covers 98 base stations in the \"middle\". If we choose the driving location because it covers the most base stations, then the path is broken into three pieces. So we need two more driving locations to cover each \"end\" of the path. Thus, we need three driving locations to cover the entire path. However, if there are two driving locations that can cover the first 50 base stations and the last 50 base stations, respectively, then we only need two driving locations. In short, we count the covered base stations from the ends of the paths. After we select the driving location that covers the most base stations, we add the driving location into the solution set, \(D\). Then, we remove the base stations that are covered by the driving location, which results in _shortened_ paths in \(P\). We repeat this process until we do not have any path that is not covered by \(D\). The details can be found in Algorithm 1. ERDSMP is a simple extension of RDSMP. The purpose of ERDSMP is to choose a set of driving locations, of which the size is the same as that of RDSMP, but the average distance between the selected driving locations and the base stations is lower than that of RDSMP. The definition of the average distance between a driving location set \(D\subseteq\mathcal{F}\) and the set of base stations \(B\subseteq\mathcal{B}\) is as follows. \[Dist_{avg}(D,B)=\frac{1}{|B|}{\sum_{b\in B}}\Big{(}\min_{d\in D}dist(d,b)\Big{)} \tag{3}\]  
In short, we want to find a driving location set \(D\) that solves the problem of (2) and has as small a value of \(Dist_{avg}(D,B)\) as possible. For that matter, ERDSMP slightly modifies RDSMP. Basically, RDSMP is a simple greedy algorithm, in which we choose the first driving location that covers the most base stations. However, other choices of the first selected driving location may provide a better result. Thus, we first find a set of driving locations, \(I\), that cover the base stations from each ends of the paths just like RDSMP. Then, instead of choosing the driving location that covers the most base stations, we just take each driving location from \(I\), then run RDSMP from that on. This procedure provides \(|I|\) different sets of driving locations. Among them, we choose the set of driving locations that has the smallest average distance between the driving locations and the base stations. As an example, consider Figure 3. In Figure 3, RDSMP chooses \(D=\{d_{2},d_{3},d_{5}\}\). However, \(d_{1}\) also covers \(B_{1}\). Actually, \(I=\{d_{1},d_{2},d_{5}\}\) are the set of driving locations that cover the first base stations of the two paths from both ends. So in ERDSMP, we take each \(I\) as the first selected driving location and run RDSMP for the remaining paths base stations. This gives another feasible set of driving locations, \(D^{\prime}\)= \(\{d_{1},d_{3},d_{5}\}\), which have \(d_{1}\) as a firstly selected driving location. Since \(D^{\prime}\) has the smaller average distance than \(D\), ERDSMP chooses \(D^{\prime}\). Basically, \(D^{\prime}\) reduces the average distance compared to \(D\). It is clear that the average distance of \(D^{\prime}\) is always equal or less than that of \(D\). The description of ERDSMP is given in Algorithm 2. ```
1:Input: \((P,\mathcal{F},L)\)
2:Output: \(D\)
3:\(P\): Src-Dst Path List
4:\(\mathcal{F}\): Set of candidate driving locations
5:\(L\): Latency Threshold
6:\(D\): Solution Set
7:\(B\leftarrow\) all the base stations in \(P\)
8:\(C\leftarrow\emptyset\)
9:for\(d\in\mathcal{F}\)do
10:if there is any base station, \(b\in B\), such that \(dist(d,b)\leq L\)then
11:\(C\gets C\cup\{d\}\)
12:\(D\leftarrow\emptyset\)
13:while\(P\) is not empty do
14:for\(d\in C\)do
15:\(S(d)\leftarrow\) the set of base stations in \(P\) that \(d\) covers
16:\(d\leftarrow\underset{d\in\mathcal{C}}{\arg\max}\ |S(d)|\)
17: Shorten the paths in \(P\) by removing the base stations in \(S(d)\)
18:\(D\gets D\cup\{d\}\)
19:\(C\gets C-\{d\}\)
20:return D
```  
**Algorithm 1** RDSMP.