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 -