Waisanen, Holly (Massachusetts Inst. of Tech.), Shah, Devavrat (Massachusetts Inst. of Tech.), Dahleh, Munther (Massachusetts Inst. of Tech.)

Optimal Delay in Networks with Controlled Mobility

Scheduled for presentation during the Mini-Symposium "Control of Mobile Multiagent Systems" (TuA13), Tuesday, July 25, 2006, 11:40−12:05, Room 101

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on May 27, 2023

Abstract

We consider a network in which a set of vehicles is responsible for the pickup and delivery of messages that arrive according to Poisson process with message pickup and delivery locations distributed uniformly at random in a region of bounded area A. The vehicles are required to pickup and deliver the messages so that the average delay is minimized.

In this paper, we provide lower bounds on the delay achievable by fully controlled policies, depending on the information constraint in place. We prove that for any policies in which only the source location information is known upon message arrival, the optimal average delay scaling is O(lambda(n)A/v^2n). If in addition to source location, destination locations of messages are known to the vehicles, the optimal average delay scaling can be reduced to O(lambda(n)A/v^2n^{3/2}). We note that these scaling bounds are achievable given the service policies we have previously described.