PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Marco Pavone, Emilio Frazzoli, Francesco Bullo

arXiv:0903.3624v1cs.RO

TL;DR

The paper addresses the challenge of designing distributed coordination policies for vehicle routing, where prior control policies have limited applicability in changing environments. It introduces two single-vehicle policies and extends them through partitioning; the policies achieve light-load optimality, with load-dependent heavy-load guarantees, and stabilize the system across load conditions.

  • Problem

    The paper identifies the design of distributed coordination policies as a major challenge and notes that prior control policies’ centralized assignment and lack of robustness to load changes limit their applicability in changing environments.

    Source: §I · pp. 1–2

  • Method

    The paper introduces the Divide & Conquer and Receding Horizon policies for the 1-DTRP and extends them to multiple vehicles through partitioning.

    Source: §VIII · p. 26

  • Results

    The Divide & Conquer policy is light-load optimal and approaches the heavy-load lower bound as r grows, while the Receding Horizon policy is light-load optimal and stabilizes every load condition.

    Source: C. Discussion · p. 15, B. Discussion · p. 18

  • Takeaways & Limitations

    Partitioning extends the single-vehicle policies to the multi-vehicle case.

    Source: §I · p. 3, §VIII · p. 26

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper frames vehicle routing as a dynamic, stochastic coordination problem and introduces adaptive policies for one vehicle, then extends them through partitioning to distributed multi-vehicle algorithms. The policies target optimality or stability across load conditions while addressing prior methods’ limited robustness to changing environments.

I. INTRODUCTION

  • Unlike static vehicle-routing models, the dynamic setting requires policies that evolve routes as sequential demands arrive and must also address system stability.Previously known m-DTRP control policies rely on centralized assignment and are not robust to environmental changes, particularly changes in load, limiting their applicability to ad-hoc networks in time-varying environments.Source: §I · p. 2
  • The m-DTRP models vehicles moving at bounded velocity in a convex environment to service demands with stochastic arrival times, locations, and on-site service, minimizing expected system time.System time comprises waiting plus service.Source: §I · p. 2
  • The policies are unbiased: they provide the same service quality to demands regardless of location.This is part of the paper’s stated contribution for the 1-DTRP policy class.Source: §I · p. 2
  • As r → +∞, the Divide & Conquer policy is optimal in light and heavy load and adapts to load and on-site-service changes; at r = 1, it is light-load optimal and within a factor of 2 in heavy load.At r = 1 it adapts to all problem data and does not require knowledge of the demand-generation process.Source: §I · pp. 2–3
  • The Receding Horizon policy requires no knowledge of demand generation, is optimal in light load, stabilizes every load condition, and is argued heuristically to be close to optimal in heavy load.The policy applies receding-horizon control ideas to dynamic vehicle routing.Source: §I · p. 3
  • Partitioning policies are optimal in heavy load, and combining them with the 1-DTRP algorithms yields spatially distributed, scalable, adaptive m-DTRP algorithms that stabilize every load condition and are within a constant factor of optimal in heavy load.The paper defines network changes to include changes in vehicle count, environment boundaries, demand arrival rate, and on-site service requirements.Source: §I · p. 3

II. PRELIMINARIES

The preliminaries establish tools for equitable partitioning, TSP-based routing, and multi-median placement. They also outline computational approaches and the optimization difficulty of the continuous multi-median problem.

A. Jensen’s Inequality

  • Jensen’s inequality is introduced for a convex function of a random variable, assuming the relevant expectations exist.The section also introduces probability and locational-optimization concepts used later in the paper.Source: A. Jensen’s Inequality · p. 3, §II · p. 3

B. Equitable Partitions

  • An equitable r-partition divides a region so each of its r subsets has equal integral under the specified density function or functions.The text states that a partition can be simultaneously equitable with respect to two positive measurable functions.Source: B. Equitable Partitions · pp. 3–4

C. Asymptotic and Worst-Case Properties of the Traveling Salesman Problem in the Euclidean Plane

  • The Euclidean TSP seeks a minimum-length cycle visiting every point once, and random-point tour length has an asymptotic characterization with a dimension-dependent constant.For d = 2, the constant is estimated as 0.7120 ± 0.0002; the convergence rate depends on the set's shape.Source: C. Asymptotic and Worst-Case… · p. 4
  • A deterministic TSP tour-length bound holds uniformly in the number of points, but its constant depends on the environment's shape and is generally larger than the asymptotic constant.The bound is stated for a certain environment Q.Source: C. Asymptotic and Worst-Case… · p. 4

D. Tools for solving TSPs

  • Practical implementations require online solutions of large TSPs, so the paper considers heuristics and constant-factor approximations whose effect scales the TSP constant.The text names Lin-Kernighan and Christofides’ heuristics.Source: D. Tools for solving TSPs · p. 5

E. The Continuous Multi-Median Problem

  • The continuous multi-median problem minimizes expected distance to the nearest of m points, but its objective is nonconvex and hard to solve generally.The text describes the objective as differentiable when the points are distinct and notes the discrete problem is NP-hard for d ≥ 2.Source: E. The Continuous Multi-Median Problem · p. 5

III. PROBLEM FORMULATION AND EXISTING RESULTS

The section formulates the m-DTRP as routing vehicles to service stochastic demands while minimizing steady-state system time, then reviews results in light- and heavy-load limits. It also motivates distributed, adaptive control using local information.

A. Problem Formulation

  • The problem’s basic version is the Dynamic Traveling Repairman Problem, previously introduced by Psaraftis and studied mainly by Bertsimas and van Ryzin.The paper studies its multi-vehicle form.Source: A. Problem Formulation · p. 6
  • Demands arrive through a time-invariant spatio-temporal Poisson process, with locations drawn independently from a density supported on the workspace.On-site service times are i.i.d. and have finite first and second moments.Source: A. Problem Formulation · p. 6
  • The load factor is ϱ = λ¯s/m, and stability requires ϱ < 1; light and heavy load refer to limits as ϱ approaches zero and one, respectively.System time runs from demand arrival until service completion, while waiting time subtracts on-site service time.Source: A. Problem Formulation · p. 6
  • The m-DTRP seeks a causal, stable, stationary routing policy that minimizes expected steady-state system time for demands in a bounded convex workspace.The paper considers the planar case and models vehicles as identical point masses moving at constant velocity.Source: A. Problem Formulation · p. 6
  • The paper focuses on spatially unbiased policies and seeks distributed, scalable, adaptive controls with guarantees that use local exchange between neighboring vehicles.The stated aim is to avoid requiring explicit knowledge of the network’s global structure.Source: A. Problem Formulation · p. 7

B. Existing Results for the m-DTRP

  • The analysis of the m-DTRP across all load factors is difficult, and prior work derives lower bounds and designs policies for the light- and heavy-load limits.The cited prior policies are compared with the corresponding lower bounds.Source: B. Existing Results for the m-DTRP · p. 7

1) Lower Bounds:

The section reviews limiting-case bounds and policies, emphasizing gaps in their adaptability and distribution. It motivates partitioning policies and a single-vehicle approach as building blocks for multi-vehicle control.

2) Optimal Policies for the Light Load Case:

  • Prior light-load work provides a tight bound attained asymptotically, while the SQM policy assigns demands to the nearest median and serves them FCFS before returning to the median.SQM relies on centralized assignment and the continuous m-median problem; its drawbacks include failure to stabilize as load increases and lack of adaptivity to environmental changes.Source: 1) Lower Bounds · p. 7, 2) Optimal Policies for the Light Load… · p. 8

1) Lower Bounds:

  • Existing light- and heavy-load lower bounds are tight in their respective limits, and the biased-policy bound is no greater than the unbiased-policy bound for every density f.The bounds distinguish spatially unbiased and spatially biased policies in heavy load.Source: 1) Lower Bounds · p. 7

3) Optimal Policies for the Heavy Load Case:

  • In heavy load, the unbiased TSP policy achieves its lower bound as r tends to infinity, using wedge partitions and FCFS batches serviced by available vehicles on TSP tours.The reviewed heavy-load policies do not perform well in light load and rely on a priori parameters, shared demand queues, and partitions computed from f.Source: 3) Optimal Policies for the Heavy Load… · p. 8

C. Toward Distributed, Scalable, and Adaptive Control Policies for the m-DTRP

  • For uniform spatial density, nearest-neighbor routing has 40% larger steady-state system time than optimal SQM in light load and 60% larger time than optimal BTSP in heavy load.The passage reports these simulation comparisons and says nearest-neighbor routing is not optimal in either regime.Source: C. Toward Distributed, Scalable, and… · p. 9
  • A π-partitioning policy assigns one vehicle to each of m disjoint regions, where it applies the single-vehicle policy π to demands in its region.The definition describes a family of policies and does not specify how to choose the partition.Source: C. Toward Distributed, Scalable, and… · p. 9
  • In heavy load, an unbiased partitioning policy based on a single-vehicle unbiased optimal policy is itself optimal within the stated construction.The proposed strategy first designs unbiased, scalable, adaptive single-vehicle policies, then extends them using distributed environment-partitioning algorithms.Source: C. Toward Distributed, Scalable, and… · p. 9

IV. THE SINGLE-VEHICLE DIVIDE & CONQUER POLICY

The Divide & Conquer policy partitions the region, uses its median and TSP tours to service demands, and is unbiased. In light load, it is asymptotically optimal for every partition count.

IV. THE SINGLE-VEHICLE DIVIDE & CONQUER POLICY

  • Divide & Conquer uses an equitable r-partition, moves to a subregion median, then services that region’s demands along a TSP tour starting at a random tour point.The algorithm randomly selects a subregion and uses the empirical median as its return point.Source: §IV · p. 10
  • The Divide & Conquer policy is unbiased.Source: §IV · p. 10

A. Analysis of the DC Policy in Light Load

  • As ϱ approaches zero, the Divide & Conquer policy is asymptotically optimal for every r.After an initial transient, with probability 1 the vehicle is at the empirical median with an empty demand queue; the policy then reduces to an already optimal light-load routing policy.Source: A. Analysis of the DC Policy in Light… · pp. 10–11

B. Analysis of the DC Policy in Heavy Load

The heavy-load analysis bounds the DC policy’s system time by tracking demand counts across subregions. As load approaches one, each tour services very many demands with high probability.

B. Analysis of the DC Policy in Heavy Load

  • Theorem 4.2 establishes an upper bound on the DC policy’s system time in heavy load.The analysis bounds the expected steady-state system time of a demand arriving in a subregion, then unconditions to obtain the claim.Source: B. Analysis of the DC Policy in Heavy… · pp. 11, 15
  • After a transient, a single DC-policy tour services very many demands with high probability as load approaches one.The analysis also finds that outstanding demand counts at tour starts become very large with high probability.Source: B. Analysis of the DC Policy in Heavy… · p. 11
  • The analysis indexes tours as epochs and derives recurrence bounds for outstanding-demand counts in each of the r subregions.It uses these bounds to control the steady-state number of demands in each region.Source: B. Analysis of the DC Policy in Heavy… · pp. 11–12
  • After a transient in heavy load, inter-tour travel time is negligible relative to the other terms in the demand-count recurrence.The analysis therefore ignores the travel-time term when deriving its heavy-load bound.Source: B. Analysis of the DC Policy in Heavy… · p. 12

C. Discussion

The DC policy’s design parameter r trades partition structure for performance and adaptation. The paper establishes load-dependent guarantees and discusses how the policy compares with related approaches.

C. Discussion

  • With r = 10, the DC policy is guaranteed to be within 10% of optimal performance for unbiased policies in heavy load.Source: C. Discussion · p. 15
  • As r tends to infinity, the DC policy is optimal in both light and heavy load.Its heavy-load performance reaches the lower bound for unbiased policies.Source: C. Discussion · p. 15
  • With r = 1, the DC policy is optimal in light load, within a factor of 2 of optimal in heavy load, and adaptive to all problem data.The data include arrival rate, expected on-site service, vehicle velocity, and spatial density.Source: C. Discussion · p. 15
  • For r > 1, implementation uses an r-partition equitable with respect to two measures, and the partition computation depends on the spatial density f.The paper notes that finding such a partition is trivial when f is uniform.Source: C. Discussion · p. 15
  • Unlike the DC policy with r = 1, the related generation policy is analyzed only for uniform spatial density and requires knowledge of f.The paper says the two policies have the same performance guarantees when r = 1.Source: C. Discussion · p. 16

V. THE SINGLE-VEHICLE RECEDING HORIZON POLICY

The single-vehicle Receding Horizon policy repeatedly plans a tour through outstanding demands and services a randomly selected fraction of it. Its horizon scales with the cost of servicing those demands.

V. THE SINGLE-VEHICLE RECEDING HORIZON POLICY

  • When demands are outstanding, the policy computes a TSP tour and uniformly selects a random fragment of length η times the tour length.The fragment is served starting from the endpoint closest to the vehicle’s current position.Source: §V · p. 16
  • After servicing the selected fragment, the policy repeats until no demands remain.When the entire tour is selected, service starts at the closest demand.Source: §V · p. 16
  • The policy’s horizon is not fixed; it adjusts according to the cost of servicing outstanding demands.The parameter η determines the selected fraction of the tour.Source: §V · pp. 16–17

A. Stability and Performance of the RH Policy

The RH policy is stable for every load and every 0 < η < 1, while its light-load performance is optimal. Its heavy-load performance analysis is heuristic because randomized fragment selection creates dependencies among unserviced demand locations.

A. Stability and Performance of the RH Policy

  • The RH policy requires no knowledge of the demand-generation process, including the spatial density f.The paper notes that closed-loop stability is not guaranteed for receding-horizon control in general.Source: A. Stability and Performance of the RH… · p. 17

1) Stability of the RH Policy:

2) Performance of the RH Policy:

  • In light load, the RH policy becomes identical to the DC policy and is therefore optimal..Source: 2) Performance of the RH Policy · p. 18
  • The heavy-load performance analysis is heuristic, not formally established as a tight rigorous bound, because fragment selection creates dependencies among unserviced demand locations.The paper reports that simulations match the suggested bounds and that performance improves as the horizon becomes shorter.Source: 2) Performance of the RH Policy · p. 18

B. Discussion

The discussion contrasts adaptive single-vehicle policies with multi-vehicle partitioning, whose heavy-load performance depends on how regions are balanced. It also notes that alternative partitions can lose stability or optimality guarantees.

B. Discussion

  • The RH policy is optimal in light load and stabilizes the system in every load condition.Its optimality and stability are established rigorously.Source: B. Discussion · p. 18
  • The RH policy needs no knowledge of λ, mean on-site service, vehicle velocity, or spatial density, and therefore adapts to all problem data.Source: B. Discussion · pp. 18–19
  • With η ≈ 0.2, RH is presented as the best available unbiased 1-DTRP policy that adapts to all problem data.Simulations indicate better heavy-load performance than DC with r = 1, while light-load behavior is the same.Source: B. Discussion · p. 19
  • Selecting the η-fragment by maximum reward appears to produce behavior between a pure unbiased policy and an optimal biased policy.Source: B. Discussion · p. 19

VI. ADAPTIVE AND DISTRIBUTED POLICIES FOR THE m-DTRP

  • In heavy load, a single-vehicle unbiased optimal policy can be extended to an unbiased partitioning policy optimal for the m-DTRP.The discussion also combines this result with SQM light-load optimality to motivate multi-vehicle policies using DC or RH within each region.Source: A. Optimality of Partitioning Policies… · p. 19, §VI · p. 19

A. Optimality of Partitioning Policies in Heavy Load

  • In heavy load, for a single-vehicle unbiased optimal policy π*, a π*-partitioning policy using an m-partition equitable with respect to f^(1/2) may be unstable; one equitable with respect to f is within factor m of optimality, generally not optimal.Source: A. Optimality of Partitioning Policies… · p. 20

B. Distributed Policies for the m-DTRP and Discussion

The multi-vehicle DC policy distributes vehicles across demand-balanced regions and runs a single-vehicle DC policy in each. Its guarantees and adaptivity depend on partition existence and knowledge of spatial density.

VII. SIMULATION EXPERIMENTS

The simulations examine DC policy system time relative to the lower bound under uniform and non-uniform spatial densities. As load approaches one, the observed ratios follow the theoretical bounds, while the better choice of r depends on load.

A. Heavy-Load Performance of the DC Policy

B. Heavy-Load Performance of the RH Policy

In heavy load, the RH policy follows the predicted system-time growth and appears to approach a 2× bound for both uniform and non-uniform densities. The tested η≈0.2 outperforms the adaptive DC policy with r=1, while m-DC illustrates the partitioning approach for multiple vehicles.

B. Heavy-Load Performance of the RH Policy

  • As ϱ approaches one, the RH policy’s system time follows the predicted λ|Q|/(1 − ϱ)^2 growth and appears to confirm the 2× bound for both density types.The bound is stated for all η; simulations also show optimal performance at η≈0.2.Source: B. Heavy-Load Performance of the RH… · p. 25

C. Comparison between DC policy and RH policy

D. Execution of the Multi-Vehicle DC Policy

VIII. CONCLUSION

  • The paper introduces adaptive DC and RH policies for the 1-DTRP and extends them to multiple vehicles through partitioning policies.Its stated objectives include provable stability under any load condition and distributed operation.Source: §VIII · p. 26

UNBIASED POLICIES FOR THE 1-DTRP

  • DC meets the heavy-load lower bound for unbiased 1-DTRP policies; Tables I–II compare policies with UTSP (r→∞), marking heuristic results with an asterisk.Source: §VIII · p. 26

VIII. CONCLUSION

  • The m-DC partition requires knowledge of the spatial density f, and the analysis assumes omnidirectional vehicles with first-order dynamics.The authors identify partitioning without knowledge of f and accounting for non-holonomic constraints as open extensions.Source: §VIII · p. 27
Loading 0903.3624v1…