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

Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment,10.1109/TAC.2010.2092850,IEEE Transactions on Automati

Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment   (Citations: 2)
BibTex | RIS | RefWorks Download
In this paper, we present adaptive and distributed al- gorithms for motion coordination of a group of vehicles. The vehicles must service demands whose time of arrival, spatial lo- cation, and service requirement are stochastic; the objective is to minimize the average time demands spend in the system. The gen- eral problem is known as the -vehicle Dynamic Traveling Re- pairman Problem ( -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 de- mands 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 par- titioned 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 poli- cies for the -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.
Journal: IEEE Transactions on Automatic Control - IEEE TRANS AUTOMAT CONTR , vol. 56, no. 6, pp. 1259-1274, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ... of algorithmic queueing theory stems from the wide spectrum of aspects, critical to the routing of robotic networks, for which it enables a rigorous study; specific examples taken from our work in the past few years include complex models for the demands such as time constraints [11], [12], service priorities [13], and translating demands [14], problems concerning robotic implementation such as adaptive and decentralized algorithms [15], ...
    • ...In [15], we study decentralized and adaptive routing policies that are optimal in light load and that are optimal unbiased algorithms in heavy load...
    • ...Then, the following results characterize the optimality of two classes of partitioning policies [15]...

    Francesco Bulloet al. Dynamic Vehicle Routing for Robotic Systems

    • ...Thefollowingtworesults,validundertheassumptionthatthe measure is uniform, characterize the optimality of two types of -partitioning policies [19]...
    • ...Light and heavy load can be defined more formally in terms of load factor; we refer the interested reader to [19]...
    • ...One can state a similar set of results for the general case where the measure is not uniform; the details are omitted in the interest of brevity and can be found in [19]...
    • ...In light of Theorem 5.1, a systematic approach to obtain multivehicle routing policies with provable performance guarantees and amenable to distributed implementation is to combine the partitioning algorithms presented in this paper with the optimalsingle-vehicleroutingpoliciesdevelopedin[19].Notethat an equitable power diagram guarantees optimal performance in heavy load, while an equitable and median Voronoi diagram provides almost ...
    • ...Wedefine the region of dominance for vehicle as the power cell , where (see Fig. 5). Then, each vehicle applies to its generator one of the previous partitioning algorithms (e.g., control law (15), if one desires performance guarantees in both light and heavy load), while simultaneously performing within its own region of dominance the optimal single-vehicle routing policies described in [19] (see Fig. 5)...

    Marco Pavoneet al. Distributed Algorithms for Environment Partitioning in Mobile Robotic ...

Sort by: