×

zbMATH — the first resource for mathematics

Decentralized estimation and control of graph connectivity for mobile sensor networks. (English) Zbl 1205.93106
Summary: The ability of a robot team to reconfigure itself is useful in many applications: for metamorphic robots to change shape, for swarm motion towards a goal, for biological systems to avoid predators, or for mobile buoys to clean up oil spills. In many situations, auxiliary constraints, such as connectivity between team members or limits on the maximum hop-count, must be satisfied during reconfiguration. In this paper, we show that both the estimation and control of the graph connectivity can be accomplished in a decentralized manner. We describe a decentralized estimation procedure that allows each agent to track the algebraic connectivity of a time-varying graph. Based on this estimator, we further propose a decentralized gradient controller for each agent to maintain global connectivity during motion.

MSC:
93C85 Automated systems (robots, etc.) in control theory
93A14 Decentralized systems
94C15 Applications of graph theory to circuits and networks
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Belta, C.; Kumar, V., Abstraction and control for groups of robots, IEEE transactions on robotics, 20, 5, 865-875, (2004)
[2] Cortés, J.; Martínez, S.; Karatas, T.; Bullo, F., Coverage control for mobile sensing networks, IEEE transactions on robotics and automation, 20, 2, 243-255, (2004)
[3] De Gennaro, M., & Jadbabaie, A. (2006). Decentralized control of connectivity for multi-agent systems. In IEEE international conference on decision and control(pp. 3628-3633)
[4] Fax, J.A.; Murray, R.M., Information flow and cooperative control of vehicle formations, IEEE transactions on automatic control, 49, 9, 1465-1476, (2004) · Zbl 1365.90056
[5] Fiedler, M., Algebraic connectivity of graphs, Czechoslovak mathematical journal, 23, 98, 298-305, (1973) · Zbl 0265.05119
[6] Freeman, R. A., Yang, P., & Lynch, K. M. (2006a). Distributed estimation and control of swarm formation statistics. In American control conference
[7] Freeman, R. A., Yang, P., & Lynch, K. M. (2006b). Stability and convergence properties of dynamic consensus estimators. In IEEE international conference on decision and control
[8] Jadbabaie, A.; Lin, J.; Morse, A.S., Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE transactions on automatic control, 48, 6, 988-1001, (2003) · Zbl 1364.93514
[9] Kempe, D.; McSherry, F., A decentralized algorithm for spectral analysis, Journal of computer and system sciences, 74, 1, 70-83, (2008) · Zbl 1131.68074
[10] Leonard, N. E., Paley, D., Lekien, F., Sepulchre, R., Fratantoni, D., & Davis, R. (2007). Collective motion, sensor networks, and ocean sampling. In Proceedings of the IEEE special issue on networked control systems, Vol. 95 (pp. 48-74).
[11] Lynch, K.; Schwartz, I.; Yang, P.; Freeman, R., Decentralized environmental modeling by mobile sensor networks, IEEE transactions on robotics, 24, 3, 710-724, (2008)
[12] Martínez, S.; Bullo, F., Optimal sensor placement and motion coordination for target tracking, Automatica, 42, 661-668, (2006) · Zbl 1110.93050
[13] Mohar, B., The Laplacian spectrum of graphs, Graph theory, combinatorics, and applications, 2, 871-898, (1991) · Zbl 0840.05059
[14] Notarstefano, G., Savla, K., Bullo, F., & Jadbabaie, A. (2006). Maintaining limited-range connectivity among second-order agents. In American control conference (pp. 2124-2129) · Zbl 1185.37207
[15] Oh, S., & Sastry, S. (2005). Tracking on a graph. In Proc. of the fourth international conference on information processing in sensor networks, IPSN05. Los Angeles, CA
[16] Olfati-Saber, R.; Murray, R.M., Consensus problems in networks of agents with switching topology and time-delays, IEEE transactions on automatic control, 49, 9, 1520-1533, (2004) · Zbl 1365.93301
[17] Simic, S., & Sastry, S. (2003). Distributed environmental monitoring using random sensor networks. In Proceedings of the 2nd international workshop on information processing in sensor networks, Palo Alto, CA (pp. 582-592) · Zbl 1027.68944
[18] Spanos, D. P., & Murray, R. M. (2004). Robust connectivity of networked vehicles. In IEEE international conference on decision and control
[19] Spanos, D. P., Olfati-Saber, R., & Murray, R. M. (2005). Dynamic consensus on mobile networks. In IFAC world congress
[20] Susca, S., Martínez, S., & Bullo, F. (2006). Monitoring environmental boundaries with a robotic sensor network. In American control conference (pp. 2072-2077)
[21] Sussmann, H.J.; Kokotović, P.V., The peaking phenomenon and the global stabilization of nonlinear systems, IEEE transactions on automatic control, 36, 4, 424-440, (1991) · Zbl 0749.93070
[22] Trefethen, L.N.; Bau, D., Numerical linear algebra, (1997), SIAM · Zbl 0874.65013
[23] Yang, P., Freeman, R., & Lynch, K. (2007). Distributed cooperative active sensing using consensus filters. Proc. of 2007 IEEE international conference on robotics and automation, Rome, Italy, (pp. 405-410)
[24] Zavlanos, M. M., & Pappas, G. J. (2005). Controlling connectivity of dynamic graphs. In IEEE conference on decision and control (pp. 6388-6393)
[25] Zavlanos, M.M.; Pappas, G.J., Potential fields for maintaining connectivity of mobile networks, IEEE transactions on robotics, 23, 4, 812-816, (2007)
[26] Zhao, F.; Shin, J.; Reich, J., Information-driven dynamic sensor collaboration for tracking applications, IEEE signal processing magazine, 19, 2, 61-72, (2002)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.