Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience

M. Pavone; N. Bisnik; E. Frazzoli; V. Isler

1st International ICST Conference on Robot Communication and Coordination

Research Article

Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience

Download521 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/ICST.ROBOCOMM2007.2220,
    author={M. Pavone and N. Bisnik and E. Frazzoli and V. Isler},
    title={Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience},
    proceedings={1st International ICST Conference on Robot Communication and Coordination},
    proceedings_a={ROBOCOMM},
    year={2010},
    month={5},
    keywords={Mobile Robotic Networks Sensor Networks Traveling Salesman Problem.},
    doi={10.4108/ICST.ROBOCOMM2007.2220}
}

M. Pavone
N. Bisnik
E. Frazzoli
V. Isler
Year: 2010
Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience
ROBOCOMM
ICST
DOI: 10.4108/ICST.ROBOCOMM2007.2220

M. Pavone¹^,*, N. Bisnik²^,*, E. Frazzoli¹^,*, V. Isler²^,*

1: Laboratory for Information and Decision Systems, and the Aeronautics and Astronautics Department, of the Massachusetts Institute of Technology, Cambridge, MA 02139, USA
2: Department of Computer Science of the Rensselaer Polytechnic Institute, Troy, NY 12180, USA

*Contact email: pavone@mit.edu, bisnin@cs.rpi.edu, frazzoli@mit.edu, isler@cs.rpi.edu

Abstract

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 − "? 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.

Keywords: Mobile Robotic Networks Sensor Networks Traveling Salesman Problem.

Published: 2010-05-16
Modified: 2010-05-16

: http://dx.doi.org/10.4108/ICST.ROBOCOMM2007.2220