DocumentCode :
3172099
Title :
Decentralized algorithms for vehicle routing in a stochastic time-varying environment
Author :
Frazzoli, Emilio ; Bullo, Francesco
Author_Institution :
Dept. of Mech. & Aerosp. Eng., California Univ., Los Angeles, CA, USA
Volume :
4
fYear :
2004
fDate :
14-17 Dec. 2004
Firstpage :
3357
Abstract :
In this paper we present decentralized algorithms for motion coordination of a group of autonomous vehicles, aimed at minimizing the expected waiting time to service stochastically-generated targets. The vehicles move within a convex environment with bounded velocity, and target generation is modeled by a spatio-temporal Poisson process. The general problem is known as the m-vehicle dynamic traveling repairperson problem (m-DTRP); the best previously known control algorithms rely on centralized a-priori task assignment and locational optimization, and are of limited applicability in scenarios involving ad-hoc networks of autonomous vehicles. In this paper, we present a new class of algorithms for the m-DTRP problem that: (i) are spatially distributed, scalable to large networks, and adaptive to network changes, (ii) are provably locally optimal in the light load case, and (iii) achieve the same performance as the best known centralized algorithms in the heavy-load, single-vehicle case. Simulation results are presented and discussed.
Keywords :
distributed algorithms; mobile robots; stochastic systems; time-varying systems; travelling salesman problems; autonomous vehicle routing; centralized a-priori task assignment; convex environment; decentralized algorithms; expected waiting time minimization; locational optimization; m-vehicle dynamic traveling repairperson problem; motion coordination; spatio-temporal Poisson process; stochastic time-varying environment; Adaptive systems; Aerospace engineering; Automotive engineering; Intelligent sensors; Mobile robots; Remotely operated vehicles; Routing; Stochastic processes; Surveillance; Unmanned aerial vehicles;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control, 2004. CDC. 43rd IEEE Conference on
ISSN :
0191-2216
Print_ISBN :
0-7803-8682-5
Type :
conf
DOI :
10.1109/CDC.2004.1429220
Filename :
1429220
Link To Document :
بازگشت