286 X. Geng and D. Jeffcoat
Corollary 1 Consider a multi-agent system in which each agent has the same trans-
mission range, represented with a communication graph G(k). If G(k) is strongly
connected, the reduced graph
ˆ
G(k) resulting from Algorithm 4 is also strongly con-
nected.
Proof The completely-connected bidirectional subgroups will be reduced to single
directional cycles, and the rest of the edges connecting these subgroups remain bidi-
rectional after reduction. Therefore,
ˆ
G(k) is still strongly connected.
14.5 Conclusion
In this paper, we develop a distributed algorithm by which each agent selects its
information sources (i.e., transmitting agents) based on only the local information
of its neighbors. As a result, a reduced group graph is produced. In this graph, con-
nectivity is reduced which allows agents to respond or maneuver with less compu-
tational effort and higher maneuverability. One direction in the future work will be
to explore various applications with the aid of such reduced graphs. Other prob-
lems that need to be addressed in the future include more scenarios under which the
proposed algorithm preserves the reachability of the original network.
References
1. Aho, A., Garey, M., Ullman, J.: The transitive reduction of a directed graph. SIAM J. Comput.
1(2), 131–137 (1972)
2. Jadbabaie, A., Lin, J., Morse, A.S.: Coordination of groups of mobile autonomous agents
using nearest neighbor rules. IEEE Trans. Autom. Control 48(9), 988–1001 (2003)
3. Moyles, D.M., Thompson, G.L.: An algorithm for finding a minimum equivalent graph of a
digraph. J. Assoc. Comput. Mach. 16(3), 455–460 (1969)
4. Spanos, D.P., Murray, R.M.: Robust connectivity of networked vehicles. In: 43rd IEEE Con-
ference on Decision and Control, pp. 2893–2898 (2004)
5. Lafferriere, G., Williams, A., Caughman, J., Veerman, J.J.P.: Decentralized control of vehicle
formations. Syst. Control Lett. 54, 899–910 (2005)
6. Fiedler, M.: Algebraic connectivity of graphs. Czechoslov. Math. J. 23(98), 298–305 (1973)
7. Ji, M., Egerstedt, M.: Distributed formation control while preserving connectedness. In: 45th
IEEE Conference on Decision and Control, pp. 5962–5967 (2006)
8. Olfati-Saber, R., Fax, J.A., Murray, R.M.: Consensus and cooperation in networked multi-
agent systems. Proc. IEEE 95(1), 215–233 (2007)
9. Khuller, S., Raghavachari, B., Young, N.: Approximating the minimum equivalent digraph.
SIAM J. Comput. 24(4), 859–872 (1995)
10. Ren, W., Beard, R.W.: Consensus seeking in multiagent systems under dynamically changing
interaction topologies. IEEE Trans. Autom. Control 50(5), 655–661 (2005)
11. Ren, W., Beard, R.W., Atkins, E.M.: A survey of consensus problems in multi-agent coordi-
nation. In: Proceedings of American Control Conference, pp. 1859–1864 (2005)
12. Kim, Y., Mesbahi, M.: On maximizing the second smallest eigenvalue of a state-dependent
graph Laplacian. IEEE Trans. Autom. Control 116–120 (2006)