Dynamic Vehicle Routing for Robotic Systems

Workshop at the 2010 American Control Conference

Baltimore, Maryland, USA, June 29, 2010, 8:30am to 5:00pm


Francesco Bullo, University of California, Santa Barbara
Ketan Savla, Massachusetts Institute of Technology
Stephen L. Smith, Massachusetts Institute of Technology

Co-organizers (not attending)

Emilio Frazzoli, Massachusetts Institute of Technology
Marco Pavone, Massachusetts Institute of Technology


The workshop will present a joint algorithmic and queueing approach to the design of cooperative control and task allocation strategies for networks of uninhabited vehicles (UVs). The key novelty is the introduction of stochastic, combinatorial and queueing aspects in the context of distributed coordination of multi-agent networks. The proposed work builds upon our recent breakthroughs in the design of dynamic vehicle routing (DVR) algorithms; these algorithms lead vehicles to complete dynamically-generated tasks with random locations and characteristics.

We will present recent work on coordination, planning and routing algorithms for the efficient discovery and timely servicing of tasks that are not known a priori. As in queueing theory, task arrival is modeled as a stochastic process, and queueing-style algorithms are required to enable UVs to search, identify, allocate, prioritize, plan paths, and form teams. DVR algorithms are typically based on a combination of receding-horizon resource allocation, distributed optimization, combinatorics and control.

Workshop Material

A printed and bound copy of the following matereial will be provided to all workshop attendees:

Structure, Schedule and Speakers

8:00am-8:25am Coffee
8:25am-8:30am Welcome and Introduction
8:30am-9:00am Lecture #1: Introduction to dynamic vehicle routing (pdf)     FB
9:05am-9:50am Lecture #2: Prelims: graphs, TSPs, and queues (pdf) SLS
9:55am-10:40am Lecture #3: The single-vehicle DVR problem (pdf) KS
10:40am-11:00am   Break
11:00am-11:45am Lecture #4: The multi-vehicle DVR problem (pdf) FB
11:45am-1:10pm Lunch Break
1:10pm-2:10pm Lecture #5: Extensions to vehicle networks (pdf) FB, KS
2:15pm-3:00pm Lecture #6: Extensions to different demand models (pdf) SLS
3:00pm-3:20pm Coffee Break
3:20pm-4:20pm Lecture #7: Extensions to different vehicle models (pdf) KS
4:25pm-4:40pm Lecture #8: Extensions to different task models (pdf) SLS
4:45pm-5:00pm Final open-floor discussion

Lunch break will be 11:45am-1:10pm. Coffee will be served at 8:00am and 3:00pm. We will also have a break at 10:40-11:00am.