Distance optimal formation control on graphs with a tight convergence time guarantee

Jingjin Yu, M. Lavalle

Research output: Contribution to journalConference article

Abstract

For the task of moving a set of indistinguishable agents on a connected graph with unit edge distance to an arbitrary set of goal vertices, free of collisions, we propose a fast distance optimal control algorithm that guides the agents into the desired formation. Moreover, we show that the algorithm also provides a tight convergence time guarantee (time optimality and distance optimality cannot be simultaneously satisfied). Our generic graph formulation allows the algorithm to be applied to scenarios such as grids with holes (modeling obstacles) in arbitrary dimensions. Simulations, available online1, confirm our theoretical developments.

Original languageEnglish (US)
Article number6426233
Pages (from-to)4023-4028
Number of pages6
JournalProceedings of the IEEE Conference on Decision and Control
DOIs
StatePublished - Dec 1 2012
Event51st IEEE Conference on Decision and Control, CDC 2012 - Maui, HI, United States
Duration: Dec 10 2012Dec 13 2012

Fingerprint

Formation Control
Convergence Time
Optimal Control
Optimality
Graph in graph theory
Arbitrary
Optimal Algorithm
Control Algorithm
Connected graph
Collision
Grid
Scenarios
Unit
Formulation
Modeling
Simulation

ASJC Scopus subject areas

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

Cite this

Distance optimal formation control on graphs with a tight convergence time guarantee. / Yu, Jingjin; Lavalle, M.

In: Proceedings of the IEEE Conference on Decision and Control, 01.12.2012, p. 4023-4028.

Research output: Contribution to journalConference article

@article{e6ea63e7138b4a1da0320116ef53a7bd,
title = "Distance optimal formation control on graphs with a tight convergence time guarantee",
abstract = "For the task of moving a set of indistinguishable agents on a connected graph with unit edge distance to an arbitrary set of goal vertices, free of collisions, we propose a fast distance optimal control algorithm that guides the agents into the desired formation. Moreover, we show that the algorithm also provides a tight convergence time guarantee (time optimality and distance optimality cannot be simultaneously satisfied). Our generic graph formulation allows the algorithm to be applied to scenarios such as grids with holes (modeling obstacles) in arbitrary dimensions. Simulations, available online1, confirm our theoretical developments.",
author = "Jingjin Yu and M. Lavalle",
year = "2012",
month = "12",
day = "1",
doi = "10.1109/CDC.2012.6426233",
language = "English (US)",
pages = "4023--4028",
journal = "Proceedings of the IEEE Conference on Decision and Control",
issn = "0191-2216",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Distance optimal formation control on graphs with a tight convergence time guarantee

AU - Yu, Jingjin

AU - Lavalle, M.

PY - 2012/12/1

Y1 - 2012/12/1

N2 - For the task of moving a set of indistinguishable agents on a connected graph with unit edge distance to an arbitrary set of goal vertices, free of collisions, we propose a fast distance optimal control algorithm that guides the agents into the desired formation. Moreover, we show that the algorithm also provides a tight convergence time guarantee (time optimality and distance optimality cannot be simultaneously satisfied). Our generic graph formulation allows the algorithm to be applied to scenarios such as grids with holes (modeling obstacles) in arbitrary dimensions. Simulations, available online1, confirm our theoretical developments.

AB - For the task of moving a set of indistinguishable agents on a connected graph with unit edge distance to an arbitrary set of goal vertices, free of collisions, we propose a fast distance optimal control algorithm that guides the agents into the desired formation. Moreover, we show that the algorithm also provides a tight convergence time guarantee (time optimality and distance optimality cannot be simultaneously satisfied). Our generic graph formulation allows the algorithm to be applied to scenarios such as grids with holes (modeling obstacles) in arbitrary dimensions. Simulations, available online1, confirm our theoretical developments.

UR - http://www.scopus.com/inward/record.url?scp=84874244803&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84874244803&partnerID=8YFLogxK

U2 - 10.1109/CDC.2012.6426233

DO - 10.1109/CDC.2012.6426233

M3 - Conference article

AN - SCOPUS:84874244803

SP - 4023

EP - 4028

JO - Proceedings of the IEEE Conference on Decision and Control

JF - Proceedings of the IEEE Conference on Decision and Control

SN - 0191-2216

M1 - 6426233

ER -