In this paper, we study the problem of designing motion strategies for a team of mobile agents, required to fulfill request for on-site service in a given planar region. In our model, each service request is generated by a spatio-temporal stochastic process; once a service request has been generated, it remains active for a certain deterministic amount of time, and then expires. An active service request is fulfilled when one of the mobile agents visits the location of the request. Specific problems we investigate are the following: what is the minimum number of mobile agents needed to ensure that a certain fraction of service requests is fulfilled before expiration? What strategy should they use to ensure that this objective is attained? This problem can be viewed as the stochastic and dynamic version of the well-known vehicle routing problem with time windows. We also extend our analysis to the case in which the time service requests remain active is itself a random variable, describing customer impatience. The customers' impatience is only known to the mobile agents via prior statistics. In this case, it is desired to minimize the fraction of service requests missed because of impatience. Finally, we show how the routing strategies presented in the paper can be executed in a distributed fashion.
Bibliographical noteFunding Information:
Acknowledgements The work of Pavone and Frazzoli was partially supported by the National Science Foundation (grants number 0325716, 0715025, 0705451, 0705453). Isler was supported in part by NSF CCF-0634823 and NSF CNS-0707939. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the supporting organizations.
- Customer impatience
- Mobile robotic networks
- Sensor networks
- Traveling salesman problem
- Vehicle routing problem with time windows