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

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

2009-03-20

arxiv.org/abs/0903.3624v1

Computer Science

Robotics

Paper to be submitted to IEEE Transactions on Automatic Control

Scientific paper

In this paper we present distributed and adaptive algorithms for motion coordination of a group of m autonomous vehicles. The vehicles operate in a convex environment with bounded velocity and must service demands whose time of arrival, location and on-site service are stochastic; the objective is to minimize the expected system time (wait plus service) of the demands. The general problem is known as the m-vehicle Dynamic Traveling Repairman Problem (m-DTRP). The best previously known control algorithms rely on centralized a-priori task assignment and are not robust against changes in the environment, e.g. changes in load conditions; therefore, they are of limited applicability in scenarios involving ad-hoc networks of autonomous vehicles operating in a time-varying environment. First, we present a new class of policies for the 1-DTRP problem that: (i) are provably optimal both in light- and heavy-load condition, and (ii) are adaptive, in particular, they are robust against changes in load conditions. Second, we show that partitioning policies, whereby the environment is partitioned among the vehicles and each vehicle follows a certain set of rules in its own region, are optimal in heavy-load conditions. Finally, by combining the new class of algorithms for the 1-DTRP with suitable partitioning policies, we design distributed algorithms for the m-DTRP problem that (i) are spatially distributed, scalable to large networks, and adaptive to network changes, (ii) are within a constant-factor of optimal in heavy-load conditions and stabilize the system in any load condition. Simulation results are presented and discussed.

Affiliated with

Also associated with

No associations

Rating

Distributed and Adaptive Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Distributed and Adaptive Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed and Adaptive Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-636425