Autonomous vehicles and sensors have the potential to transform many aspects of societal infrastructure, from transportation networks and assisted living, to emergency response systems and military operations. In fact, the transformation is already occurring in areas such as reconnaissance and environmental monitoring. However, in these applications autonomous vehicles are typically deployed in small numbers, tightly coupled with human control. To realize the full potential of such systems there is a required shift towards large groups of networked and highly autonomous vehicles, capable of performing complex and evolving tasks. This shift calls for vehicles that can adapt to dynamic environments, utilizing newly acquired information to re-allocate resources, and re-plan routes.

This thesis addresses problems in distributed task allocation and in dynamic vehicle routing. In task allocation we consider a target assignment problem in which a group of vehicles must divide a set of targets (tasks) among themselves. In dynamic vehicle routing—where vehicles must complete spatially distributed tasks that arrive sequentially in time—we consider several problems. First, we consider a problem in which the vehicles have different capabilities, and each task requires a team of vehicles for its completion. Second, we consider a problem in which tasks have different levels of urgency, and thus the vehicles must prioritize the tasks, completing urgent tasks with minimal delay while simultaneously considering and completing less urgent tasks. Finally, we consider a problem in which task locations are non-stationary, and a variation wherein a vehicle must guard a boundary from approaching targets. Our technical approach to each of these problems follows the same basic steps. We show that the problem exhibits an underlying structure that can be exploited to determine fundamental limits on the achievable performance. Then, we design novel and provably efficient algorithms for solving the problem. The solutions combine aspects of combinatorial optimization, stochastic processes, and distributed control.