Ares Lab

Wednesday, 22 October 2014
Main Menu
Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience PDF Print E-mail
M. Pavone, N. Bisnik, E. Frazzoli, V. Isler  

Consider the following scenario: a spatio-temporal stochastic process generates service requests,
localized at points  in a bounded region on the plane; these service requests are fulfilled when
one of a team of mobile agents visits the location of the request. For example, a service request
may represent the detection  of an event in a sensor network application, which needs to be
investigated on site. Once a service request has been generated, it remains active for an amount of time
which is itself a random variable, and then expires. The problem we investigate is the following:
What is the minimum number of mobile agents needed to ensure that each service request is
fulfilled before expiring, with probability at least 1 - epsilon? What strategy should they use to
ensure this objective is attained? Formulating the probability of successfully servicing requests
before expiration as a performance metric, we derive bounds on the minimum number of agents
required to ensure a given performance level, and present decentralized motion coordination
algorithms that approximate the optimal strategy. [PDF ]