The following motion coordination
problem is studied: given n mobile vehicles and n source-destination pairs
in the plane, what is the minimum time needed to transfer each vehicle from
its source to its destination, avoiding conflicts with other vehicles? In
the proposed model, vehicles do not explicitly communicate their intentions,
and only have sensory information about the current position and velocity
of their neighbors to ensure no conflicts. The environment is free of obstacles
and a conflict occurs when the distance between any two vehicles is smaller
than a velocity-dependent safety distance. The situation analyzed in which
the vehicle size is such that at least a constant fraction of the n vehicles
can be fitted inside the environment simultaneously. In the "best" case
in which the source and destination points can be chosen ideally to maximize
the transfer efficiency, it is shown that the transfer takes 
time to complete, where  is the average
distance between the source and destination points. It is shown that there
exist a "worst" case distribution of the source and destination points,
for which the transfer of vehicles takes at least  time.
The case is also analyzed in which source and destination points are generated
randomly according to a uniform distribution, and an algorithm is presented
providing a constructive upper bound on the time needed to transfer vehicles
from sources to their corresponding destinations, proving that the transfer
takes  time, with high probability,
thus recovering the best case performance. |
