Time complexity of sensor-based vehicle routing

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 θ( √ n.L) 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 θ( √ n) time for this case.

Original languageEnglish (US)
Title of host publicationRobotics
Subtitle of host publicationScience and Systems I
EditorsSebastian Thrun, Gaurav Sukhatme, Stefan Schaal, Oliver Brock
PublisherMIT Press Journals
Number of pages8
ISBN (Print)9780262701143
StatePublished - Jan 1 2005
EventInternational Conference on Robotics: Science and Systems, RSS 2005 - Cambridge, United States
Duration: Jun 8 2005Jun 11 2005

Publication series

NameRobotics: Science and Systems
ISSN (Print)2330-7668
ISSN (Electronic)2330-765X


OtherInternational Conference on Robotics: Science and Systems, RSS 2005
CountryUnited States

ASJC Scopus subject areas

  • Artificial Intelligence
  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Time complexity of sensor-based vehicle routing'. Together they form a unique fingerprint.

  • Cite this

    Sharma, V., Savchenko, M., Frazzoli, E., & Voulgaris, P. G. (2005). Time complexity of sensor-based vehicle routing. In S. Thrun, G. Sukhatme, S. Schaal, & O. Brock (Eds.), Robotics: Science and Systems I (pp. 297-304). (Robotics: Science and Systems; Vol. 1). MIT Press Journals.