Abstract
This paper studies connectivity maintenance of robotic networks that communicate at discrete times and move in continuous space. We propose a distributed coordination algorithm that allows the robots to decide whether a desired collective motion breaks connectivity. We build on this procedure to design a second coordination algorithm that allows the robots to modify a desired collective motion to guarantee that connectivity is preserved. These algorithms work under imperfect information caused by delays in communication and the robots’ mobility. Under very outdated information, the proposed algorithms might prevent some or all of the robots from moving. We analyze the correctness of our algorithms by formulating them as games against a hypothetical adversary who chooses system states consistent with observed information. The technical approach combines tools from algebraic graph theory, linear algebra, and nonsmooth analysis.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Boyd, S.: Convex optimization of graph Laplacian eigenvalues. In: Proceedings of the International Congress of Mathematicians, pp. 1311–1319, Madrid, August 2006
Bullo, F., Cortés, J., Martínez, S.: Distributed Control of Robotic Networks. Applied Mathematics Series. Princeton University Press, September. Manuscript under contract. http://www.coordinationbook.info (2008)
Clarke, F.H.: Optimization and Nonsmooth Analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. Wiley, New York (1983)
Cortés, J., Martínez, S., Bullo, F.: Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions. IEEE Trans. Automat. Contr. 51(8), 1289–1298 (2006)
de Gennaro, M.C., Jadbabaie, A.: Decentralized control of connectivity for multi-agent systems. In: IEEE Conf. on Decision and Control, pp. 3628–3633, San Diego, December 2006
Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23, 298–305 (1973)
Godsil, C.D., Royle, G.F.: Algebraic graph theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001)
Jadbabaie, A., Lin, J., Morse, A.S.: Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Automat. Contr. 48(6), 988–1001 (2003)
Jaromczyk, J.W., Toussaint, G.T.: Relative neighborhood graphs and their relatives. Proc. IEEE 80(9), 1502–1517 (1992)
Ji, M., Egerstedt, M.: Distributed control of multiagent systems while preserving connectedness. IEEE Trans. Robot. 23(4), 693–703 (2007)
Kim, Y., Mesbahi, M.: On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian. IEEE Trans. Automat. Contr. 51(1), 116–120 (2006)
Lewis, A.S.: Nonsmooth analysis of eigenvalues. Math. Program. 84, 1–24 (1999)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1997)
Martínez, S., Bullo, F., Cortés, J., Frazzoli, E.: On synchronous robotic networks - Part I: models, tasks, and complexity. IEEE Trans. Automat. Contr. 52(12), 2199–2213 (2007)
Olfati-Saber, R., Fax, J.A., Murray, R.M.: Consensus and cooperation in networked multi-agent systems. Proc. IEEE 95(1), 215–233 (2007)
Peleg, D.: Distributed Computing. A Locality-Sensitive Approach. Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2000)
Savla, K., Notarstefano, G., Bullo, F.: Maintaining limited-range connectivity among second-order agents. SIAM J. Control Optim. 48, 187–205 (2009)
Schuresko, M.D.: CCLsim. a simulation environment for robotic networks. http://www.soe.ucsc.edu/~mds/cclsim (2008)
Schuresko, M.D., Cortés, J.: Safe graph rearrangements for distributed connectivity of robotic networks. In: IEEE Conf. on Decision and Control, pp. 4602–4607, New Orleans, 12–14 December 2007
Spanos, D.P., Murray, R.M.: Motion planning with wireless network constraints. In: American Control Conference, pp. 87–92, Portland, June 2005
Wu, C.W.: Algebraic connectivity of directed graphs. Linear Multilinear Algebra 53(3), 203–223 (2005)
Zavlanos, M.M., Pappas, G.J.: Controlling connectivity of dynamic graphs. In: IEEE Conf. on Decision and Control and European Control Conference, pp. 6388–6393, Seville, December 2005
Zavlanos, M.M., Pappas, G.J.: Distributed connectivity control of mobile networks. In: IEEE Conf. on Decision and Control, New Orleans, 12–14 December 2007
Zavlanos, M.M., Pappas, G.J.: Flocking while preserving network connectivity. In: IEEE Conf. on Decision and Control, New Orleans, 12–14 December 2007
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Schuresko, M., Cortés, J. Distributed Motion Constraints for Algebraic Connectivity of Robotic Networks. J Intell Robot Syst 56, 99–126 (2009). https://doi.org/10.1007/s10846-009-9328-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-009-9328-8