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.
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.
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