Efficient formation path planning on large graphs

Max Katsev, Jingjin Yu, Steven M. Lavalle

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

Abstract

For the task of transferring a group of robots from one formation to another on a connected graph with unit edge lengths, we provide an efficient hierarchical algorithm that can complete goal assignment and path planning for 10,000 robots on a 250,000 vertex grid in under one second. In the extreme, our algorithm can handle up to one million robots on a grid with one billion vertices in approximately 30 minutes. Perhaps more importantly, we prove that with high probability, the algorithm supplies paths with total distance within a constant multiple of the optimal total distance. Furthermore, our hierarchical method also allows these paths to be scheduled with a tight completion time guarantee. In practice, our implementation yields a total path distance less than two times of the true optimum and a much shorter completion time.

Original languageEnglish (US)
Title of host publication2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Pages3606-3611
Number of pages6
DOIs
StatePublished - Nov 14 2013
Event2013 IEEE International Conference on Robotics and Automation, ICRA 2013 - Karlsruhe, Germany
Duration: May 6 2013May 10 2013

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729

Other

Other2013 IEEE International Conference on Robotics and Automation, ICRA 2013
CountryGermany
CityKarlsruhe
Period5/6/135/10/13

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Efficient formation path planning on large graphs'. Together they form a unique fingerprint.

  • Cite this

    Katsev, M., Yu, J., & Lavalle, S. M. (2013). Efficient formation path planning on large graphs. In 2013 IEEE International Conference on Robotics and Automation, ICRA 2013 (pp. 3606-3611). [6631083] (Proceedings - IEEE International Conference on Robotics and Automation). https://doi.org/10.1109/ICRA.2013.6631083