A graph-theoretic approach on optimizing informed-node selection in multi-agent tracking control. (English) Zbl 1285.93010
Summary: A graph optimization problem for a multi-agent leader-follower problem is considered. In a multi-agent system with \(n\) followers and one leader, each agent’s goal is to track the leader using the information obtained from its neighbors. The neighborhood relationship is defined by a directed communication graph where \(k\) agents, designated as informed agents, can become neighbors of the leader. This paper establishes that, for any given strongly connected communication graph with \(k\) informed agents, all agents will converge to the leader. In addition, an upper bound and a lower bound of the convergence rate are obtained. These bounds are shown to explicitly depend on the maximal distance from the leader to the followers. The dependence between this distance and the exact convergence rate is verified by empirical studies. Then, we show that minimizing the maximal distance problem is a metric \(k\)-center problem in classical combinatorial optimization studies, which can be approximately solved. Numerical examples are given to illustrate the properties of the approximate solutions.
MSC:
| 93A14 | Decentralized systems |
| 68T42 | Agent technology and artificial intelligence |
| 90C57 | Polyhedral combinatorics, branch-and-bound, branch-and-cut |
References:
| [1] | Couzin, I. D.; Krause, J.; Franks, N.; Levin, S., Effective leadership and decision making in animal groups on the move, Nature, 433, 513-516 (2005) |
| [2] | Mech, L. D., Leadership in wolf, canis lupus, packs, Canadian Field-Naturalist, 114, 2, 259-263 (2000) |
| [3] | Tsitsiklis, J.; Bertsekas, D.; Athans, M., Distributed asynchronous deterministic and stochastic gradient optimization algorithms, IEEE Trans. Automat. Control, 31, 9, 803-812 (1986) · Zbl 0602.90120 |
| [4] | Jadbabaie, A.; Lin, J.; Morse, A. S., Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Trans. Automat. Control, 48, 6, 988-1001 (2003) · Zbl 1364.93514 |
| [5] | Tanner, H. G.; Jadbabaie, A.; Pappas, G. J., Flocking in fixed and switching networks, IEEE Trans. Automat. Control, 52, 5, 863-868 (2007) · Zbl 1366.93414 |
| [6] | Oh, S.; Schenato, L.; Chen, P.; Sastry, S., Tracking and coordination of multiple agents using sensor networks: system design, algorithms and experiments, Proc. IEEE, 95, 234-254 (2007) |
| [7] | Ren, W.; Beard, R., Distributed Consensus in Multi-Vehicle Cooperative Control (2008), Springer-Verlag: Springer-Verlag London · Zbl 1144.93002 |
| [8] | Doerr, B.; Fouz, M.; Friedrich, T., Why rumors spread so quickly in social networks, Commun. ACM, 55, 6, 70-75 (2012) |
| [9] | Ren, W.; Beard, R., Consensus seeking in multiagent systems under dynamically changing interaction topologies, IEEE Trans. Automat. Control, 50, 5, 655-661 (2005) · Zbl 1365.93302 |
| [10] | Fax, J.; Murray, R., Information flow and cooperative control of vehicle formations, IEEE Trans. Automat. Control, 49, 9, 1465-1476 (2004) · Zbl 1365.90056 |
| [11] | H.G. Tanner, On the controllability of nearest neighbor interconnections, in: Proceedings of the 43rd IEEE Conference on Decision and Control, 2004, pp. 467-472. |
| [12] | Shi, H.; Wang, L.; Chu, T., Virtual leader approach to coordinated control of multiple mobile agents with asymmetric interactions, Physica D, 213, 1, 51-65 (2006) · Zbl 1131.93354 |
| [13] | Wang, W.; Slotine, J. J.E., A theoretical study of different leader roles in networks, IEEE Trans. Automat. Control, 51, 7, 1156-1161 (2006) · Zbl 1366.93416 |
| [14] | I. Shames, A.M.H. Teixeira, H. Sandberg, K.H. Johansson, Distributed leader selection without direct inter-agent communication, in: 2nd IFAC Workshop on Estimation and Control of Networked Systems, Annecy, France, 2010, pp. 221-226. |
| [15] | M. Ji, A. Muhammad, M. Egerstedt, Leader-based multi-agent coordination: controllability and optimal control, in: Proceedings of the IEEE American Control Conference, 2006, pp. 1358-1363. |
| [16] | A. Rahmani, M. Mesbahi, On the controlled agreement problem, in: Proceedings of the IEEE American Control Conference, 2006, pp. 1376-1381. |
| [17] | Rahmani, A.; Ji, M.; Mesbahi, M.; Egerstedt, M., Controllability of multi-agent systems: from a graph-theoretic perspective, SIAM J. Control Optim., 48, 1, 162-186 (2009) · Zbl 1182.93025 |
| [18] | Lin, Z.; Francis, B.; Maggiore, M., Necessary and sufficient graphical conditions for formation control of unicycles, IEEE Trans. Automat. Control, 50, 1, 121-127 (2005) · Zbl 1365.93324 |
| [19] | Shi, G.; Hong, Y., Global target aggregation and state agreement of nonlinear multi-agent systems with switching topologies, Automatica, 45, 5, 1165-1175 (2009) · Zbl 1162.93308 |
| [20] | Shi, G.; Hong, Y.; Johansson, K. H., Connectivity and set tracking of multi-agent systems guided by multiple moving leaders, IEEE Trans. Automat. Control, 57, 3, 663-676 (2012) · Zbl 1369.93048 |
| [21] | Xiao, L.; Boyd, S., Fast linear iterations for distributed averaging, Systems Control Lett., 53, 65-78 (2004) · Zbl 1157.90347 |
| [22] | Boyd, S.; Diaconis, P.; Xiao, L., Fastest mixing Markov chain on a graph, SIAM Rev., 46, 4, 667-689 (2004) · Zbl 1063.60102 |
| [23] | Boyd, S.; Ghosh, A.; Prabhakar, B.; Shah, D., Randomized gossip algorithms, IEEE Trans. Inform. Theory, 52, 6, 2508-2530 (2006) · Zbl 1283.94005 |
| [24] | DeLellis, P.; di Bernardo, M.; Porfiri, M., Pinning control of complex networks via edge snapping, Chaos, 21, 3, 033119 (2011) · Zbl 1318.34070 |
| [25] | Vazirani, V. V., Approximation Algorithms (2003), Springer: Springer Berlin · Zbl 1005.68002 |
| [26] | Hochbaum, D. S.; Shmoys, D. B., A unified approach to approximation algorithms for bottleneck problems, J. ACM, 33, 533-550 (1986) |
| [27] | Olfati-Saber, R.; Murray, R. M., Consensus problems in the networks of agents with switching topology and time delays, IEEE Trans. Automat. Control, 49, 9, 1520-1533 (2004) · Zbl 1365.93301 |
| [28] | Hong, Y.; Hu, J.; Gao, L., Tracking control for multiagent consensus with an active leader and variable topology, Automatica, 42, 7, 1177-1182 (2006) · Zbl 1117.93300 |
| [29] | Rudin, W., Functional Analysis (1991), McGraw-Hill · Zbl 0867.46001 |
| [30] | Gonzalez, T., Clustering to minimize the maximum intercluster distance, Theoret. Comput. Sci., 38, 293-306 (1985) · Zbl 0567.62048 |
| [31] | Lusseau, D.; Schneider, K.; Boisseau, O. J.; Haase, P.; Slooten, E.; Dawson, S. M., The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behav. Ecol. Sociobiol., 54, 4, 396-405 (2003) |
| [32] | Girvan, M.; Newman, M. E.J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA, 99, 7821-7826 (2002) · Zbl 1032.91716 |
| [33] | Olfati-Saber, R.; Fax, J. A.; Murray, R. M., Consensus and cooperation in networked multi-agent systems, Proc. IEEE, 95, 1, 215-233 (2007) · Zbl 1376.68138 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
