UC Santa Barbara

Autonomous mobile systems are becoming more common place, and have the opportunity to revolutionize many modern application areas. They include, but are not limited to, tasks such as search and rescue operations, ad-hoc mobile wireless networks and warehouse management; each application having its own complexities and challenging problems that need addressing. In this thesis, we explore and characterize two application areas in particular.

First, we explore the problem of autonomous stochastic surveillance. In particular, we study random walks on a finite graph that are described by a Markov chain. We present strategies that minimize the first hitting time of the Markov chain, and look at both the single agent and multi-agent cases. In the single agent case, we provide a formulation and convex optimization scheme for the hitting time on graphs with travel distances. In addition, we provide detailed simulation results showing the effectiveness of our strategy versus other well-known Markov chain design strategies. In the multi-agent case, we provide the first characterization of the hitting time for multiple random walkers, which we denote the "group hitting time". We also provide a closed form solution for calculating the hitting time between specified nodes for both the single and multiple random walker cases. Our results allow for the multiple random walks to be different and, moreover, for the random walks to operate on different subgraphs. Finally, we use sequential quadratic programming to find the transition matrices that generate minimal "group hitting time".

Second, we consider the problem of optimal coverage with a group of mobile agents. For a planar environment with an associated density function, this problem is equivalent to dividing the environment into optimal subregions such that each agent is responsible for the coverage of its own region. We study this problem for the discrete time and space case and the continuous time and space case. For the discrete time and space case, we present algorithms that provide optimal coverage control in a non-convex environment when each robot has only asynchronous and sporadic communication with a base station. We introduce the notion of coverings, a generalization of partitions, to do this. For the continuous time and space case, we present a continuous-time distributed policy which allows a team of agents to achieve a convex area-constrained partition in a convex workspace. This work is related to the classic Lloyd algorithm, and makes use of generalized Voronoi diagrams. For both cases we provide detailed simulation results and discuss practical implementation issues.