Events Calendar

Dynamic Vehicle Routing for Robotic Networks

Speaker: Marco PavoneHost: Prof. Gaurav SukhatmeDate/Time: THURSDAY, FEBRUARY 4, 2010, 3:30-5:00 PMLocation: SEAVER SCIENCE LIBRARY (SSL) 150Abstract: In the recent past considerable efforts have been devoted to the problem of routing robotic vehicles through spatially-localized service requests. In most of the literature on this problem the model is static in the sense that all of the relevant information is assumed to be known by a planner before the routing process begins. However, this assumption is too restrictive in many applications of interest.In this talk, we discuss dynamic routing problems in which new information becomes available sequentially over time. Specifically, we analyze a prototypical dynamic routing problem where a network of robotic vehicles must fulfill service requests whose time of arrival and location are stochastic, and whose service must begin before a deadline. The aim is to find a routing policy which ensures, with the minimum possible number of vehicles, that the probability of a request being successfully serviced before its deadline is larger than a desired value. By leveraging tools from control theory and queueing theory, we find optimal policies for the case in which requests are generated rarely, and we devise provably-correct and computationally-efficient policies for all other cases.In the last part of the talk we turn our attention to the distributed implementation of dynamic routing policies. The key idea we pursue is that of partitioning policies whereby the workspace is partitioned into a number of subregions equal to the number of vehicles, one vehicle is assigned to each subregion, and each vehicle executes a single-vehicle policy within its own subregion. First, we show that proper partitioning policies are indeed optimal. Then, we obtain distributed routing policies by designing provably correct, spatially-distributed algorithms for environment partitioning.Bio: Marco Pavone is a Ph.D. candidate in the Laboratory for Information and Decision Systems within the Department of Aeronautics and Astronautics at the Massachusetts Institute of Technology. He received a Laurea degree in Electrical Engineering from the University of Catania, Italy, in 2004, and received a Diploma in Computer Engineering from Scuola Superiore di Catania, Italy, in 2005. Prior to joining MIT, he worked as an Analyst for Accenture Consulting. His research interests include algorithmic and computational approaches to the design and development of decision and control architectures for complex networked and autonomous systems.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: Georgia Lum