Krishna Kalyanam

Myoungkuk Park, Krishnamoorthy Kalyanam, Swaroop Darbha et al.

One often encounters the curse of dimensionality in the application of dynamic programming to determine optimal policies for controlled Markov chains. In this paper, we provide a method to construct sub-optimal policies along with a bound for the deviation of such a policy from the optimum via a linear programming approach. The state-space is partitioned and the optimal cost-to-go or value function is approximated by a constant over each partition. By minimizing a non-negative cost function defined on the partitions, one can construct an approximate value function which also happens to be an upper bound for the optimal value function of the original Markov Decision Process (MDP). As a key result, we show that this approximate value function is {\it independent} of the non-negative cost function (or state dependent weights as it is referred to in the literature) and moreover, this is the least upper bound that one can obtain once the partitions are specified. Furthermore, we show that the restricted system of linear inequalities also embeds a family of MDPs of lower dimension, one of which can be used to construct a lower bound on the optimal value function. The construction of the lower bound requires the solution to a combinatorial problem. We apply the linear programming approach to a perimeter surveillance stochastic optimal control problem and obtain numerical results that corroborate the efficacy of the proposed methodology.

Sai Krishna Kanth Hari, Sivakumar Rathinam, Swaroop Darbha et al.

Persistent monitoring missions require an up-to-date knowledge of the changing state of the underlying environment. UAVs can be gainfully employed to continually visit a set of targets representing tasks (and locations) in the environment and collect data therein for long time periods. The enduring nature of these missions requires the UAV to be regularly recharged at a service station. In this paper, we consider the case in which the service station is not co-located with any of the targets. An efficient monitoring requires the revisit time, defined as the maximum of the time elapsed between successive revisits to targets, to be minimized. Here, we consider the problem of determining UAV routes that lead to the minimum revisit time. The problem is NP-hard, and its computational difficulty increases with the fuel capacity of the UAV. We develop an algorithm to construct near-optimal solutions to the problem quickly, when the fuel capacity exceeds a threshold. We also develop lower bounds to the optimal revisit time and use these bounds to demonstrate (through numerical simulations) that the constructed solutions are, on an average, at most 0.01% away from the optimum.

Sai Krishna Kanth Hari, Sivakumar Rathinam, Swaroop Darbha et al.

We consider the problem of planning a closed walk $\mathcal W$ for a UAV to persistently monitor a finite number of stationary targets with equal priorities and dynamically changing properties. A UAV must physically visit the targets in order to monitor them and collect information therein. The frequency of monitoring any given target is specified by a target revisit time, $i.e.$, the maximum allowable time between any two successive visits to the target. The problem considered in this paper is the following: Given $n$ targets and $k \geq n$ allowed visits to them, find an optimal closed walk $\mathcal W^*(k)$ so that every target is visited at least once and the maximum revisit time over all the targets, $\mathcal R(\mathcal W(k))$, is minimized. We prove the following: If $k \geq n^2-n$, $\mathcal R(\mathcal W^*(k))$ (or simply, $\mathcal R^*(k)$) takes only two values: $\mathcal R^*(n)$ when $k$ is an integral multiple of $n$, and $\mathcal R^*(n+1)$ otherwise. This result suggests significant computational savings - one only needs to determine $\mathcal W^*(n)$ and $\mathcal W^*(n+1)$ to construct an optimal solution $\mathcal W^*(k)$. We provide MILP formulations for computing $\mathcal W^*(n)$ and $\mathcal W^*(n+1)$. Furthermore, for {\it any} given $k$, we prove that $\mathcal R^*(k) \geq \mathcal R^*(k+n)$.