# Robotics: Science and Systems I

### Time Complexity of Sensor-Based Vehicle Routing

*Vikrant Sharma, Michael Savchenko, Emilio Frazzoli, Petros G. Voulgaris*

**Abstract:** In this paper, we study the following motion
coordination problem: given n vehicles and n origin-destination pairs
in the plane, what is the minimum time needed to transfer each vehicle
from its origin to its destination, avoiding conflicts with other
vehicles? The environment is free of obstacles and a conflict occurs
when distance between any two vehicles is smaller than a
velocity-dependent safety distance. In the case where the origin and
destination points can be chosen arbitrarily, we show that the
transfer takes \Theta(\sqrt{nL}) time to complete, where L is the
average distance between the origin and destination points. We also
analyze the case in which origin and destination points are generated
randomly according to a uniform distribution, and present an algorithm
providing a constructive upper bound on the time needed to transfer
vehicles from origins to their corresponding destination, proving that
the transfer takes \Theta(\sqrt{n}) time for this case.

**Bibtex:**

@INPROCEEDINGS{ Sharma-RSS-05, AUTHOR = {Vikrant Sharma and Michael Savchenko and Emilio Frazzoli and Petros G. Voulgaris}, TITLE = {Time Complexity of Sensor-Based Vehicle Routing}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2005}, ADDRESS = {Cambridge, USA}, MONTH = {June}, DOI = {10.15607/RSS.2005.I.039} }