Jafari, Saeid, Ajorlou, Amir and Aghdam, Amir G.
(2011)
*Leader localization in multi-agent systems subject to failure: A graph-theoretic approach.*
Automatica, 47
(8).
pp. 1744-1750.
ISSN 00051098

Preview |
Text (application/pdf)
336kBAghdam2011.pdf - Accepted Version |

Official URL: http://dx.doi.org/10.1016/j.automatica.2011.02.051

## Abstract

In this paper, structural controllability of a leader–follower multi-agent system with multiple leaders is studied. A graphical condition for structural controllability based on the information flow graph of the system is provided. The notions of p-link and q-agent controllability in a multi-leader setting are then introduced, which provide quantitative measures for the controllability of a system subject to failure in the agents and communication links. The problem of leader localization is introduced, which is concerned with finding the minimum number of agents whose selection as leaders results in a p-link or q-agent controllable network. Polynomial-time algorithms are subsequently presented to solve the problem for both cases of undirected and directed information flow graphs.

Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Electrical and Computer Engineering |
---|---|

Item Type: | Article |

Refereed: | Yes |

Authors: | Jafari, Saeid and Ajorlou, Amir and Aghdam, Amir G. |

Journal or Publication: | Automatica |

Date: | 2011 |

Digital Object Identifier (DOI): | 10.1016/j.automatica.2011.02.051 |

Keywords: | Multi-agent systems; Controllability; Graph theory |

ID Code: | 975175 |

Deposited By: | Danielle Dennie |

Deposited On: | 22 Jan 2013 14:35 |

Last Modified: | 18 Jan 2018 17:39 |

## References:

Aghdam, 2010 Aghdam, A. G. (2010). Robust degree of exponential stability in polynomially uncertain overlapping control systems. In Proc. of the 49th IEEE conference on decision and control (pp. 6908–6913).Ajorlou et al., 2010 A. Ajorlou, A. Momeni, A.G. Aghdam A class of bounded distributed control strategies for connectivity preservation in multi-agent systems IEEE Transactions on Automatic Control, 55 (12) (2010), pp. 2828–2833

Ajorlou et al., 2011 A. Ajorlou, A. Momeni, A.G. Aghdam Sufficient conditions for the convergence of a class of nonlinear distributed consensus algorithms Automatica, 47 (3) (2011), pp. 625–629

Choi et al., 2009 J. Choi, S. Oh, R. Horowitz Distributed learning and cooperative control for multi-agent systems Automatica, 45 (12) (2009), pp. 2802–2814

Cortes et al., 2006 J. Cortes, S. Martinez, F. Bullo Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions IEEE Transactions on Automatic Control, 51 (8) (2006), pp. 1289–1298

Dimarogonas et al., 2006 Dimarogonas, D. V., Egerstedt, M., & Kyriakopoulos, K. J. (2006). A leader-based containment control strategy for multiple unicycles. In Proc. of the 45th IEEE conference on decision and control (pp. 5968–5973).

Dion et al., 2003 J.M. Dion, C. Commault, J. Woude Generic properties and control of linear structured systems: a survey Automatica, 39 (2003), pp. 1125–1144

Frank, 2009 A. Frank Rooted k-connections in digraphs Discrete Applied Mathematics, 157 (6) (2009), pp. 1242–1254

Gavril, 1972 F. Gavril Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph SIAM Journal on Computing, 1 (1972), pp. 180–187

Gustavi et al., 2010 T. Gustavi, D.V. Dimarogonas, M. Egerstedt, X. Hu Sufficient conditions for connectivity maintenance and rendezvous in leader–follower networks Automatica, 46 (1) (2010), pp. 133–139

Ito et al., 2003 H. Ito, K. Makino, K. Arata, S. Honami, Y. Itatsu, S. Fujishige Source location problem with flow requirements in directed networks Optimization Methods and Software, 18 (4) (2003), pp. 427–435

Jafari et al., 2010 Jafari, S., Ajorlou, A., Aghdam, A. G., & Tafazoli, S. (2010). On the structural controllability of multi-agent systems subject to failure: a graph–theoretic approach. In Proc. of the 49th IEEE conference on decision and control(pp. 4565–4570).

Ji and Egerstedt, 2007 Ji, M., & Egerstedt, M. (2007). A graph–theoretic characterization of controllability for multi-agent systems. In Proc. of the American control conference (pp. 4588–4593).

Ji et al., 2009 Z. Ji, Z. Wang, H. Lin, Z. Wang Interconnection topologies for multi-agent coordination under leader–follower framework Automatica, 45 (12) (2009), pp. 2857–2863

Labbe et al., 1995 M. Labbe, D. Peeters, J.F. Thisse Location on networks ,in: M.O. Ball (Ed.) et al., Handbooks in OR&MS, Vol. 8 (1995), pp. 551–624

Lavaei et al., 2008 J. Lavaei, A. Momeni, A.G. Aghdam A model predictive decentralized control scheme with reduced communication requirement for spacecraft formation IEEE Transactions on Control Systems Technology, 16 (2) (2008), pp. 268–278

Lin et al., 2005 Z. Lin, B. Francis, M. Maggiore Necessary and sufficient graphical conditions for formation control of unicycles IEEE Transactions on Automatic Control, 50 (1) (2005), pp. 121–127

Liu et al., 2008 B. Liu, T. Chu, L. Wang, G. Xie Controllability of a leader–follower dynamic network with switching topology IEEE Transactions on Automatic Control, 53 (4) (2008), pp. 1009–1013

Liu et al., 2009 Liu, X., Lin, H., & Chen, B. M. (2009). A graph–theoretic characterization of structural controllability for multi-agent system with switching topology. In Proc. of the 48th IEEE conference on decision and control (pp. 7012–7017).

Liu et al., 2006 Liu, B., Xie, G., Chu, T., & Wang, L. (2006). Controllability of interconnected systems via switching networks with a leader. In IEEE international conference on systems, man, and cybernetics (pp. 3912–3916).

Martinez et al., 2007 S. Martinez, J. Cortes, F. Bullo Motion coordination with distributed information IEEE Control Systems Magazine, 27 (4) (2007), pp. 75–88

Martini et al., 2010 S. Martini, M. Egerstedt, A. Bicchi Controllability analysis of multi-agent systems using relaxed equitable partitions International Journal of Systems, Control and Communications, 2 (2010), pp. 100–121

Mesbahi, 2005 M. Mesbahi On state-dependent dynamic graphs and their controllability properties IEEE Transactions on Automatic Control, 50 (3) (2005), pp. 387–392

Moshtagh et al., 2009 N. Moshtagh, N. Michael, A. Jadbabaie, K. Daniilidis Vision-based distributed control laws for motion coordination of nonholonomic robots IEEE Transactions on Robotics, 25 (4) (2009), pp. 851–860

Nagamochi et al., 2001 H. Nagamochi, T. Ishii, H. Ito Minimum cost source location problem with vertex-connectivity requirements in digraphs Information Processing Letter, 80 (2001), pp. 287–294

Olfati-Saber, 2006 R. Olfati-Saber Flocking for multi-agent dynamic systems: algorithms and theory IEEE Transactions on Automatic Control, 51 (3) (2006), pp. 401–420

Partovi et al., 2010 Partovi, A., Lin, H., & Zhijian, J. (2010). Structural controllability of high order dynamic multi-agent systems. In IEEE conference on robotics automation and mechatronics (pp. 327–332).

Rahmani et al., 2009 A. Rahmani, M. Ji, M. Mesbahi, M. Egerstedt Controllability of multi-agent systems from a graph–theoretic perspective SIAM Journal on Control and Optimization, 48 (1) (2009), pp. 162–186

Rahmani and Mesbahi, 2006 Rahmani, A., & Mesbahi, M. (2006). On the controlled agreement problem. In Proc. of the American control conference (pp. 1376–1381).

Shao et al., 2007 J. Shao, G. Xie, L. Wang Leader-following formation control of multiple mobile vehicles IET Control Theory and Applications, 1 (2) (2007), pp. 545–552

Siljak, 1991 D.D. Siljak Decentralized control of complex systems Academic Press, New York (1991)

Tamura et al., 1992 H. Tamura, M. Sengoku, S. Shinoda, T. Abe Some covering problems in location theory on flow networks IEICE Transactions Fundamentals, E75-A (6) (1992), pp. 678–683

Tanner, 2004 Tanner, H. (2004). On the controllability of nearest neighbor interconnections. In Proc. of the 43rd IEEE conference on decision and control (pp. 2467–2472).

Wang et al., 2009 L. Wang, F. Jiang, G. Xie, Z. Ji Controllability of multi-agent systems based on agreement protocols Science in China Series F: Information Sciences (2009), pp. 2074–2088

Yang et al., 2008 P. Yang, R.A. Freeman, K.M. Lynch Multi-agent coordination by decentralized estimation and control IEEE Transactions on Automatic Control, 53 (11) (2008), pp. 2480–2496

Zamani and Lin, 2009 Zamani, M., & Lin, H. (2009). Structural controllability of multi-agent systems. In Proc. of the American control conference (pp. 5743–5748).

Repository Staff Only: item control page