Shortest path set induced vertex ordering and its application to distributed distance optimal formation path planning and control on graphs

Jingjin Yu, Steven M. LaValle

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

Abstract

For the task of moving a group of indistinguishable agents on a connected graph with unit edge lengths into an arbitrary goal formation, it was shown that distance optimal paths can be computed to complete with a tight convergence time guarantee [30], using a fully centralized algorithm. In this study, we establish the existence of a more fundamental ordering of the vertices on the underlying graph network, induced by a fixed goal formation. The ordering leads to a simple distributed scheduling algorithm that assures the same convergence time. The vertex ordering also readily extends to more general graphs - Those with arbitrary integer capacities and edge lengths - for which we again provide guarantees on the convergence time until the desired formation is achieved. Simulations, accessible via a web browser, confirm our theoretical developments.

Original languageEnglish (US)
Title of host publication2013 IEEE 52nd Annual Conference on Decision and Control, CDC 2013
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2775-2780
Number of pages6
ISBN (Print)9781467357173
DOIs
StatePublished - Jan 1 2013
Event52nd IEEE Conference on Decision and Control, CDC 2013 - Florence, Italy
Duration: Dec 10 2013Dec 13 2013

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0191-2216

Other

Other52nd IEEE Conference on Decision and Control, CDC 2013
CountryItaly
CityFlorence
Period12/10/1312/13/13

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'Shortest path set induced vertex ordering and its application to distributed distance optimal formation path planning and control on graphs'. Together they form a unique fingerprint.

Cite this