Dynamic Vehicle Routing for Robotic Networks

The last decade has seen an increasing number of application domains where networks of uninhabited vehicles (UVs) are required to fulfill tasks that arise dynamically in time, are spatially distributed over an environment, and possibly require some type of additional on-site service. UAV systems, robotic environmental monitoring, and sensor networks are clear examples. The problem is to devise real-time routing algorithms to enable the UVs to search, identify, allocate, prioritize, and plan paths. In collaboration with E. Frazzoli (MIT), F. Bullo (UCSB), and S. Smith (U. Waterloo), I developed a novel approach for the solution to this problem, called algorithmic queueing theory, which relies upon methods from queueing theory, combinatorial optimization, and stochastic geometry (Paper). Algorithmic queueing theory consists of three basics steps: 1) queueing model of the problem and analysis of its structure; 2) establishment of fundamental limitations on performance, independent of algorithms; and 3) design of algorithms that are either optimal or constant-factor away from optimal. By using algorithmic queueing theory, I:

 
  • designed adaptive and distributed control laws for routing UVs in dynamic and uncertain environments
  • devised polynomial-time, constant-factor routing algorithms for the case where tasks have deterministic deadlines on their waiting times
  • devised polynomial-time, constant-factor routing algorithms for the case with multiple priority classes of service demands