Optimal dynamic assignment for low earth orbit satellite constellations

Alexander Melin; R. Scott Erwin; Vijay Sekhar Chellaboina

doi:10.1109/cdc.2006.377470

Optimal dynamic assignment for low earth orbit satellite constellations

Alexander Melin, R. Scott Erwin, Vijay Sekhar Chellaboina

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

In this paper we investigate the problem of autonomous task assignment for a class of uncertain systems described by dynamic weighted bipartite graphs. Specifically, we consider the optimal assignment problem for this class of system. First, we present necessary and sufficient conditions for the existence of a perfect matching in a given bipartite graph. Next, we present an algorithm to expand the original graph to a virtual graph that guarantees the existence of a perfect matching. These results are then used to solve the optimal assignment problem for dynamic weighted bipartite graphs. Finally, we apply this algorithm to a group of low-earth orbit satellites that have the task of tracking multiple ground targets simultaneously.

Original language	English
Title of host publication	Proceedings of the 45th IEEE Conference on Decision and Control 2006, CDC
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3204-3209
Number of pages	6
ISBN (Print)	1424401712, 9781424401710
DOIs	https://doi.org/10.1109/cdc.2006.377470
State	Published - 2006
Externally published	Yes
Event	45th IEEE Conference on Decision and Control 2006, CDC - San Diego, CA, United States Duration: Dec 13 2006 → Dec 15 2006

Publication series

Name	Proceedings of the IEEE Conference on Decision and Control
ISSN (Print)	0743-1546
ISSN (Electronic)	2576-2370

Conference

Conference	45th IEEE Conference on Decision and Control 2006, CDC
Country/Territory	United States
City	San Diego, CA
Period	12/13/06 → 12/15/06

Keywords

Dynamic assignment problem
Dynamic graph topology
Dynamic task allocation
Graph theory
Linear programming

Access to Document

10.1109/cdc.2006.377470

Cite this

Melin, A., Erwin, R. S., & Chellaboina, V. S. (2006). Optimal dynamic assignment for low earth orbit satellite constellations. In Proceedings of the 45th IEEE Conference on Decision and Control 2006, CDC (pp. 3204-3209). Article 4177782 (Proceedings of the IEEE Conference on Decision and Control). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/cdc.2006.377470

@inproceedings{305f0db93a0f46b0aabb4196a88c86fb,

title = "Optimal dynamic assignment for low earth orbit satellite constellations",

abstract = "In this paper we investigate the problem of autonomous task assignment for a class of uncertain systems described by dynamic weighted bipartite graphs. Specifically, we consider the optimal assignment problem for this class of system. First, we present necessary and sufficient conditions for the existence of a perfect matching in a given bipartite graph. Next, we present an algorithm to expand the original graph to a virtual graph that guarantees the existence of a perfect matching. These results are then used to solve the optimal assignment problem for dynamic weighted bipartite graphs. Finally, we apply this algorithm to a group of low-earth orbit satellites that have the task of tracking multiple ground targets simultaneously.",

keywords = "Dynamic assignment problem, Dynamic graph topology, Dynamic task allocation, Graph theory, Linear programming",

author = "Alexander Melin and Erwin, {R. Scott} and Chellaboina, {Vijay Sekhar}",

year = "2006",

doi = "10.1109/cdc.2006.377470",

language = "English",

isbn = "1424401712",

series = "Proceedings of the IEEE Conference on Decision and Control",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "3204--3209",

booktitle = "Proceedings of the 45th IEEE Conference on Decision and Control 2006, CDC",

note = "45th IEEE Conference on Decision and Control 2006, CDC ; Conference date: 13-12-2006 Through 15-12-2006",

}

Melin, A, Erwin, RS & Chellaboina, VS 2006, Optimal dynamic assignment for low earth orbit satellite constellations. in Proceedings of the 45th IEEE Conference on Decision and Control 2006, CDC., 4177782, Proceedings of the IEEE Conference on Decision and Control, Institute of Electrical and Electronics Engineers Inc., pp. 3204-3209, 45th IEEE Conference on Decision and Control 2006, CDC, San Diego, CA, United States, 12/13/06. https://doi.org/10.1109/cdc.2006.377470

Optimal dynamic assignment for low earth orbit satellite constellations. / Melin, Alexander; Erwin, R. Scott; Chellaboina, Vijay Sekhar.
Proceedings of the 45th IEEE Conference on Decision and Control 2006, CDC. Institute of Electrical and Electronics Engineers Inc., 2006. p. 3204-3209 4177782 (Proceedings of the IEEE Conference on Decision and Control).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Optimal dynamic assignment for low earth orbit satellite constellations

AU - Melin, Alexander

AU - Erwin, R. Scott

AU - Chellaboina, Vijay Sekhar

PY - 2006

Y1 - 2006

N2 - In this paper we investigate the problem of autonomous task assignment for a class of uncertain systems described by dynamic weighted bipartite graphs. Specifically, we consider the optimal assignment problem for this class of system. First, we present necessary and sufficient conditions for the existence of a perfect matching in a given bipartite graph. Next, we present an algorithm to expand the original graph to a virtual graph that guarantees the existence of a perfect matching. These results are then used to solve the optimal assignment problem for dynamic weighted bipartite graphs. Finally, we apply this algorithm to a group of low-earth orbit satellites that have the task of tracking multiple ground targets simultaneously.

AB - In this paper we investigate the problem of autonomous task assignment for a class of uncertain systems described by dynamic weighted bipartite graphs. Specifically, we consider the optimal assignment problem for this class of system. First, we present necessary and sufficient conditions for the existence of a perfect matching in a given bipartite graph. Next, we present an algorithm to expand the original graph to a virtual graph that guarantees the existence of a perfect matching. These results are then used to solve the optimal assignment problem for dynamic weighted bipartite graphs. Finally, we apply this algorithm to a group of low-earth orbit satellites that have the task of tracking multiple ground targets simultaneously.

KW - Dynamic assignment problem

KW - Dynamic graph topology

KW - Dynamic task allocation

KW - Graph theory

KW - Linear programming

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

U2 - 10.1109/cdc.2006.377470

DO - 10.1109/cdc.2006.377470

M3 - Conference contribution

AN - SCOPUS:39649118585

SN - 1424401712

SN - 9781424401710

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 3204

EP - 3209

BT - Proceedings of the 45th IEEE Conference on Decision and Control 2006, CDC

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 45th IEEE Conference on Decision and Control 2006, CDC

Y2 - 13 December 2006 through 15 December 2006

ER -

Optimal dynamic assignment for low earth orbit satellite constellations

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this