UC Santa Barbara

This thesis contains two parts. In the first part, we discuss the robotic surveillance problems, with a focus on the Markov chain-based stochastic approaches. In chapter 2, we study the problem of maximizing the return time entropy of a Markov chain, subject to graph and stationary distribution constraints. We first obtain complete characterizations for the return time distribution and show its convergence. We then establish upper and lower bounds for the return time entropy. We also provide gradients of the truncated entropy function for computational purposes. Finally, we present the numerical comparisons between the proposed and existing Markov strategies.

In chapter 3, we analyze the meeting time between a pursuer and an evader. First, by analyzing multiple random walks on a common graph as a single random walk on the Kronecker product graph, we provide a closed-form expression for the expected meeting time. This novel expression leads to necessary and sufficient graph-theoretic conditions for the meeting time to be finite. Second, we study the minimization problem for the expected capture time for the pursuer. We finally report theoretical and numerical results on basic case studies.

In chapter 4, we study the problem where the mobile robot tries to capture a strategic intruder who knows the current location and the surveillance strategy of the mobile agent. We model the scenario by a Stackelberg game and study optimal and suboptimal surveillance strategies in star, complete and line graphs. We first derive a universal upper bound on the capture probability, which is shown to be tight in the complete graph and provides suboptimality guarantees. For the star and line graphs, we characterize dominant strategies and rigorously prove the optimal surveillance plan.

In the second part, chapter 5, we study the graph-theoretic conditions for stability of positive monotone systems. We first establish necessary and sufficient conditions for the stability of linear positive systems described by Metzler matrices. Specifically, we derive two sets of stability conditions based on two forms of input-to-state stability gains, namely max-interconnection gains and sum-interconnection gains. We then extend our results to nonlinear monotone systems.