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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st International Conference on Robot Communication and Coordination, RoboComm 2007
PublisherAssociation for Computing Machinery
ISBN (Electronic)9789639799080
DOIs
StatePublished - 2007
Externally publishedYes
Event1st International Conference on Robot Communication and Coordination, RoboComm 2007 - Athens, Greece
Duration: Oct 15 2007Oct 17 2007

Publication series

NameACM International Conference Proceeding Series

Conference

Conference1st International Conference on Robot Communication and Coordination, RoboComm 2007
Country/TerritoryGreece
CityAthens
Period10/15/0710/17/07

Bibliographical note

Publisher Copyright:
Copyright © 2011-2012 ICST

Keywords

  • Mobile Robotic Networks
  • Sensor Networks
  • Traveling Salesman Problem

Fingerprint

Dive into the research topics of 'Decentralized Vehicle Routing in a Stochastic and Dynamic Environment with Customer Impatience'. Together they form a unique fingerprint.

Cite this