Distributed Cooperative Coverage of Mobile Robots with Consensus-Based Connectivity Estimation

doi:10.1007/s12204-014-1500-z

Abstract

Abstract:

This paper deals with the discrete-time connected coverage problem with the constraint that only local information can be utilized for each robot. In such distributed framework, global connectivity characterized by the second smallest eigenvalue of topology Laplacian is estimated through introducing distributed minimaltime consensus algorithm and power iteration algorithm. A self-deployment algorithm is developed to disperse the robots with the precondition that the estimated second smallest eigenvalue is positive at each time-step. Since thus connectivity constraint does not impose to preserve some certain edges, the self-deployment strategy developed in this paper reserves a sufficient degree of freedom for the motion of robots. Theoretical analysis demonstrates that each pair of neighbor robots can finally reach the largest objective distance from each other while the group keeps connected all the time, which is also shown by simulations.

Key words:

coverage| distributed cooperative control| minimal-time consensus| eigenvalue estimation

摘要：

关键词:

coverage| distributed cooperative control| minimal-time consensus| eigenvalue estimation

CLC Number:

TP 13

LI Xiao-li1,2* (李晓丽), ZHAO Shu-guang1 (赵曙光), LIU Hao1 (刘浩). Distributed Cooperative Coverage of Mobile Robots with Consensus-Based Connectivity Estimation[J]. Journal of shanghai Jiaotong University (Science), 2014, 19(3): 279-286.

References

[1] Cao Y U, Fukunaga A S, Kahng A B. Cooperative mobile robotics: Antecedents and direcions[J].Autonomous Robots, 1997, 4(1): 7-27.

[2] Kan Z, Dani A P, Shea J M, et al. Network connectivity preserving formation stabilization and obstacle avoidance via a decentralized controller [J].IEEE Transactions on Robotics and Automation, 2012,57(7): 1827-1832.

[3] Wang X, Xing G, Zhang Y, et al. Integrated coverage and connectivity configuration in wireless sensor networks [C]//Proceedings of the 1st International Conference on Embedded Networked. Los Angeles, CA,USA: ACM, 2003: 28-39.

[4] Miao Z, Cui L, Zhang B, et al. Deployment patterns for k-coverage and l-connectivity in wireless sensor networks [C]//IET International Conference on Wireless Sensor Network. Beijing: IET, 2010: 73-77.

[5] Ammari H M, Das S K. Centralized and clustered k-coverage protocols for wireless sensor networks [J].IEEE Transactions on Computers, 2012, 61(1): 118-133.

[6] Yun Z, Bai X, Xuan D, et al. Optimal deployment patterns for full coverage and k-connectivity (k 6) wireless sensor networks [J]. IEEE/ACM Transactions on Networking, 2010, 18(3): 934-947.

[7] Howard A, Mataric M J, Sukhatme G S. An incremental self-deployment algorithm for mobile sensor networks [J]. Autonomous Robots, Special Issue on Intelligent Embedded Systems, 2002, 13(2): 113-126.

[8] Batalin M A, Sukhatme G S. Spreading out: A local approach to multi-robot coverage [C]//6th International Conference on Distributed Autonomous Robotic Systems (DSRS02). Tokyo, Japan: Springer, 2002:373-382.

[9] Heo N, Varshney P K. Energy-efficient deployment of intelligent mobile sensor networks [J]. IEEE Transactions on Systems, Man, and Cybernetics—Part A:Systems and Humans, 2005, 35(1): 78-92.

[10] Cortes J, Martinez S, Karatas T, et al. Coverage control for mobile sensing networks [J]. IEEE Transactions on Robotics and Automation, 2004, 20(2): 243-255.

[11] Laventall K, Cortes J. Coverage control by multirobot networks with limited-range anisotropic sensory [J]. International Journal of Control, 2009, 82(6):1113-1121.

[12] Li W, Cassandras C G. Distributed cooperative coverage control of sensor networks [C]//Proceedings of the 44th IEEE Conference on Decision and Control.Seville, Spain: IEEE, 2005: 2542-2547.

[13] Podur S, Sukhatme G S. Constrained coverage for mobile sensor networks [C]//IEEE International Conference on Robotics and Automation. New Orleans,LA, USA: IEEE, 2004: 165-172.

[14] Li J, Cui L, Zhang B. Self-deployment by distance and orientation control for mobile sensor networks [C]//2010 IEEE International Conference on Networking,Sensing and Control (ICNSC). Chicage, IL, USA:IEEE, 2010: 549-553.

[15] Ji M, Egerstedt M. Distributed coordination control of multiagent systems while preserving connectedness[J]. IEEE Transactions on Robotics, 2007, 23(4): 693-703.

[16] Dimarogonas D V, Kyriakopoulos K J. Connectedness preserving distributed swarm aggregation for multiple kinematic robots [J]. IEEE Transactions on Robotics, 2008, 24(5): 1213-1223.

[17] Zavlanos M M, Pappas G J. Potential fields for maintaining connectivity of mobile networks [J]. IEEE Transactions on Robotics, 2007, 23(4): 812-816.

[18] Ando H, Osuzuki Y, Yamashita M. Distributed memoryless point convergence algorithm for mobile robots with limited visibility [J]. IEEE Transactions on Robotics and Automation, 1999, 15(5): 818-828.

[19] Li X L, Xi Y G. Distributed connected coverage control for groups of mobile agents [J]. International Journal of Control, 2010, 83(7): 1347-1363.

[20] Razafindralambo T, Simplot-Ryl D. Connectivity preservation and coverage schemes for wireless sensor networks [J]. IEEE Transactions on Automatic Control,2011, 56(10): 2418-2428.

[21] Reich J, Misra V, Rubenstein D, et al. Connectivity maintenance in mobile wireless networks via constrained mobility [J]. IEEE Journal on Selected Areas in Communications, 2012, 30(5): 935-950.

[22] Kim Y, Mesbahi M. On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian [J]. IEEE Transactions on Automatic Control, 2006,51(1): 116-120.

[23] Yang P, Freeman R A, Gordon G J, et al. Decentralized estimation and control of graph connectivity for mobile sensor networks [J]. Automatica, 2010, 46:390-396.

[24] Horn R, Johnson C. Matrix analysis [M]. UT, USA:Cambridge University Press, 1990.

[25] Sundaram S, Hadjicostis C N. Finite-time distributed consensus in graphs with time-invariant topologies [C]//Proceedings of American Control Conference.New York, USA: IEEE, 2007: 711-716.

[26] Yuan Y, Stan G, Shi L, et al. Decentralised minimal time consensus [J]. Automatica, 2013, 49(5): 1227-1235.