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 http://resolver.caltech.edu/CaltechAUTHORS:20111122-095750180
Full text not available from this repository.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20111122-095750180
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.
|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.|
|Subject Keywords:||Autonomous systems; cooperative control; decentralized control; dynamic vehicle routing; multivehicle systems|
|Other Numbering System:|
|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.|
|Deposited By:||Jason Perez|
|Deposited On:||22 Nov 2011 19:02|
|Last Modified:||22 Nov 2011 19:02|
Repository Staff Only: item control page