## 3 Sensor Scheduling
### Stochastic approach  
The stochastic nature of scheduling surveillance reduces the predictability of sensors behavior and therefore plays an important role for military tasks. Here we assume that sites are chosen randomly based on probability \(p_{ij}\) of transition from \(i\)-th to \(j\)-th site. Then sensor scheduling can be considered as a Markov chain stochastic process and characterized by steady state probabilities \(\pi_{i}\). The goal of stochastic approach is finding such steady state probabilities that minimize maximum loss. Let \(r_{i}\) be the visit period of site \(i\). Then the penalty of information loss at site \(i\) is \(a_{i}+(r_{i}-1)b_{i,t}\) at time \(t\). Let us consider a sufficiently small planning horizon with time-invariant site dynamics, this allows us to reduce \(b_{i,t}\) to \(b_{i}\) and denote this approach as static. Visiting site \(i\) for every \(r_{i}>0\) periods is equal to spending \(\pi_{i}=1/r_{i}\) of the sensor's time at the site \(i\). The optimal schedule is achieved when \(\sum_{i}\pi_{i}=1\); i.e., all the available time is utilized. Also, sensor never stays at any site for two consecutive periods of time. Thus \(r_{i}\geq 2\) (or \(\pi_{i}\leq 0.5\)) should be satisfied for each site. Then the non-linear model for obtaining optimal stationary probabilities is formulated as  
\[\min\max_{i}\{a_{i}+\left(\frac{1}{\pi_{i}}-1\right)b_{i}\}\] (12) s.t. \[\sum_{i=1}^{n}\pi_{i}=1, \tag{13}\] \[\pi_{i}\leq 0.5,\forall i=1,\ldots,n\] (14) \[\pi_{i}\in R,\forall i=1,\ldots,n \tag{15}\]  
A heuristic is proposed to solve this nonlinear continuous problem. Utilizing constraints (14), the authors define a lower bound on the objective function value with  
\[C^{L}=\max_{i}\{a_{i}+b_{i}\}.\]  
Then, we set  
\[C=\max_{i}\{a_{i}+\left(\frac{1}{\pi}-1\right)b_{i}\}=C^{L}\]  
and calculate  
\[r_{i}=(C-a_{i})/b_{i}+1\]  
and  
\[\pi_{i}=1/r_{i}\]  
for all \(i\). Note that \(\pi_{i}=0.5\) for the sites with \(a_{i}+b_{i}=C\) and \(\pi_{i}<0.5\) for the remaining constraints. If the determined probabilities add up to one then the optimal solution is found, and the procedure terminates. If the sum of probabilities is less than one, then one can shift some \(\pi\)-s up to make \(\sum_{i}\pi_{i}=1\). In the case when \(\sum_{i}\pi_{i}>1\) the found \(C\) is infeasible and we can apply iterative procedures (such as bisection) to find \(C\) such that \(\sum_{i}\pi_{i}=1\). The static approach minimizes average penalty that is determined by steady probabilities and, thus, does not address the cases of long lasting absence at a site. Taking into account the fact that some randomoutcomes may result in extremely long penalties it is reasonable to increase the probabilities of visiting the sites that were visited long time ago. On the other hand, the probability of observing the sites, which were recently visited, should be decreased. Recall that \(y_{i,t}\) represents the last time when the site \(i\) was visited by the time \(t\). The probability of visiting a site must depend on the difference \(t-y_{i,t}\), thus it will increase probability of visiting overdue sites. To create a preference for visiting site \(i\) at time \(t\) the following adjustment factors are proposed  
\[q_{i,t}=\pi_{i}\cdot\left(\frac{t-y_{i,t}}{r_{i}}\right)^{k}\]  
It is bigger than one for overdue sites and less than one for the sites that have been visited within their expected visiting periods. The parameter \(k\) is a user-defined parameter, which determines the weight of the adjustment factor. The probabilities of visiting each site at specific time point \(t\) are based on previous history and can be computed as \(p_{i}=q_{i}/Q\), where \(Q=\sum_{i=1}^{n}q_{i}\). Finally, a hybrid method was proposed based on a combination of greedy algorithm and the stochastic method, discussed above. The first step calculates the penalty of not visiting site \(i\): \(c_{i}=a_{i}+b_{i,t}(t-y_{i,t})\).