A Caltech Library Service

Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment

Pavone, Marco and Frazzoli, Emilio and Bullo, Francesco (2011) Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment. IEEE Transactions on Automatic Control, 56 (6). pp. 1259-1274. ISSN 0018-9286.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


In this paper, we present adaptive and distributed algorithms for motion coordination of a group of m vehicles. The vehicles must service demands whose time of arrival, spatial location, and service requirement are stochastic; the objective is to minimize the average time demands spend in the system. The general problem is known as the m-vehicle Dynamic Traveling Repairman Problem (m-DTRP). The best previously known control algorithms rely on centralized task assignment and are not robust against changes in the environment. In this paper, we first devise new control policies for the 1-DTRP that: i) are provably optimal both in light-load conditions (i.e., when the arrival rate for the demands is small) and in heavy-load conditions (i.e., when the arrival rate for the demands is large), and ii) are adaptive, in particular, they are robust against changes in load conditions. Then, we show that specific partitioning policies, whereby the environment is partitioned among the vehicles and each vehicle follows a certain set of rules within its own region, are optimal in heavy-load conditions. Building upon the previous results, we finally design control policies for the m-DTRP that i) are adaptive and distributed, and ii) have strong performance guarantees in heavy-load conditions and stabilize the system in any load condition.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 2011 IEEE. Manuscript received March 31, 2009; revised May 17, 2010; accepted August 24, 2010. Date of publication November 18, 2010; date of current version June 08, 2011. This work was supported in part by the National Science Foundation under Grants #0705451 and #0705453 and in part by the Air Force Office of Scientific Research through grant AFOSR MURI #FA9550-07-1-0528. Recommended by Associate Editor I. Paschalidis.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR) MURIFA9550-07-1-0528
Subject Keywords:Autonomous systems; cooperative control; decentralized control; dynamic vehicle routing; multivehicle systems
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number12047069
Issue or Number:6
Record Number:CaltechAUTHORS:20111122-095750180
Persistent URL:
Official Citation:Pavone, M.; Frazzoli, E.; Bullo, F.; , "Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment," Automatic Control, IEEE Transactions on , vol.56, no.6, pp.1259-1274, June 2011 doi: 10.1109/TAC.2010.2092850
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:27910
Deposited By: Jason Perez
Deposited On:22 Nov 2011 19:02
Last Modified:03 Oct 2019 03:27

Repository Staff Only: item control page