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

作者：Pavone Marco^*; Frazzoli Emilio; Bullo Francesco

来源：IEEE Transactions on Automatic Control, 2011, 56(6): 1259-1274.

DOI：10.1109/TAC.2010.2092850

• Autonomous systems
• cooperative control
• decentralized control
• dynamic vehicle routing
• multivehicle systems

In this paper, we present adaptive and distributed algorithms for motion coordination of a group of 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.

• 出版日期2011-6