Decentralized vehicle routing in a stochastic and dynamic environment with customer impatience

Marco Pavone, Nabhendra Bisnik, Emilio Frazzoli, Volkan IslerROBOCOMM 2007 · OpenReview

Abstract

Managing a fleet of mobile robots to service time-sensitive, stochastic tasks is a critical challenge in autonomous systems. This paper investigates the problem of "customer impatience," where service requests expire if not fulfilled within a certain timeframe. We derive the minimum number of robots required to guarantee a target success rate and propose a decentralized routing strategy. By combining Voronoi partitioning with stochastic Traveling Salesperson Problem (TSP) logic, the proposed approach achieves near-optimal performance in dynamic environments.

Introduction

In robotic applications such as environmental monitoring, search and rescue, or security, service requests (demands) are often dynamic and time-sensitive. A key constraint is customer impatience: if a robot fails to reach a demand location quickly enough, the mission fails. The primary research questions involve determining the optimal fleet size ($m$) to ensure a success probability of at least $1 - \epsilon$ and developing a decentralized coordination strategy that avoids the need for a central controller.

Methodology

The proposed solution decomposes the complex routing problem into several manageable components:

The Critical Time Concept

To handle probabilistic requirements, the authors map the success target (servicing $1-\epsilon$ of requests) to a deterministic "critical time" ($T_{crit}$). A policy that ensures every location is visited within $T_{crit}$ of a request's appearance guarantees the desired success probability.

Decentralization via Voronoi Diagrams

To achieve decentralized control, the environment is partitioned into Voronoi cells. Each robot manages its own cell, using a gradient descent law to move "virtual generators" until the environment is divided into equitable cells of equal area. This allows the system to self-organize using only local information from neighboring agents.

Voronoi partitioning using virtual generators for decentralized coordination.

Multiple-Vehicle TSP Policy

Within its assigned Voronoi cell, each agent follows a stochastic TSP logic. The agent waits for demands to accumulate and then executes a TSP tour to service them. This decoupling of partitioning ("where to be") from routing ("how to visit") is essential for scalability.

Experimental Validation

The strategy was validated through stochastic simulations. Demands were modeled as a spatio-temporal Poisson process with intensity $\lambda$ in a unit-area planar region. The authors tested both Uniform and Exponential distributions for demand lifetimes to evaluate the robustness of the $T_{crit}$ approach.

Results and Discussion

A key finding in the heavy-load analysis is the quadratic scaling of efficiency: virtual waiting time increases linearly with arrival rate ($\lambda$) but decreases quadratically with the number of agents ($m$). This suggests that adding a small number of robots can significantly alleviate congestion in high-demand scenarios.

Simulations confirmed that for a target "lost demand" rate of 5% ($\epsilon = 0.05$), the proposed TSP policy consistently maintained the actual loss rate below the threshold.

Experimental results showing the percentage of lost demands remains below the 5% design requirement across various arrival rates.

The proposed policy provides a constant-factor approximation to the optimal strategy. Under heavy-load conditions, the required number of vehicles is at most ~2.6 times the theoretical lower bound. Furthermore, the system demonstrated stability, reaching a steady state within approximately 300 TSP tour cycles.

Conclusion and Future Work

This work provides a robust framework for decentralized vehicle routing with time-sensitive demands. While the "critical time" approach is somewhat conservative, it offers high reliability and mathematical tractability. Future research will focus on extending the model to non-uniform spatial demand distributions ("hotspots") and improving efficiency by prioritizing demands based on their specific expiration times rather than a global threshold.

Summary updated

BibTeX
@inproceedings{pavone2007decentralized,
  author = {Marco Pavone and Nabhendra Bisnik and Emilio Frazzoli and Volkan Isler},
  title = {{Decentralized vehicle routing in a stochastic and dynamic environment with customer impatience}},
  booktitle = {ROBOCOMM},
  year = {2007},
  url = {https://openreview.net/forum?id=gWRZWhcelBVE},
}
Figure