Network Connectivity Control of Mobile Robots by Fast Position Estimations and Laplacian Kernel
Yusuke Ikemoto*, Kenichiro Nishimura**, Yuichiro Mizutama**, Tohru Sasaki***, and Mitsuru Jindai***
*Department of Mechanical Engineering, Faculty of Science and Technology, Meijo University
1-501 Shiogamaguchi, Tempaku-ku, Nagoya 468-8502, Japan
**Department of Mechanical and Intellectual Systems Engineering, Faculty of Engineering, University of Toyama
3190 Gofuku, Toyama-shi, Toyama 930-8555, Japan
***Graduate School of Science and Engineering for Research, University of Toyama
3190 Gofuku, Toyama-shi, Toyama 930-8555, Japan
Together with wireless distributed sensor technologies, the connectivity control of mobile robot networks has widely expanded in recent years. Network connectivity has been greatly improved by theoretical frameworks based on graph theory. Most network connectivity studies have focused on algebraic connectivity and the Fiedler vector, which constitutes a network structure matrix eigenpair. Theoretical graph frameworks have popularly been adopted in robot deployment studies; however, the eigenpairs’ computation requires quite a lot of iterative calculations and is extremely time-intensive. In the present study, we propose a robot deployment algorithm that only requires a finite iterative calculation. The proposed algorithm rapidly estimates the robot positions by solving reaction-diffusion equations on the graph, and gradient methods using a Laplacian kernel. The effectiveness of the algorithm is evaluated in computer simulations of mobile robot networks. Furthermore, we implement the algorithm in the actual hardware of a two-wheeled robot.
-  M. M. Zavlanos, M. B. Egerstedt, and G. J. Pappas, “Graph Theoretic Connectivity Control of Mobile Robot Networks,” Proc. of the IEEE, Vol.99, No.9, pp. 1525-1540, 2011.
-  I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensor networks,” IEEE Communication Magazine, Vol.40, No.8, pp. 102-114, 2002.
-  M. M. Zavlanos and G. J. Pappas, “Potential fields for maintaining connectivity of mobile networks,” IEEE Trans. on Robotics, Vol.23, No.4, pp. 812-816, 2007.
-  Y. Kim and M. Mesbahi, “On maximizing the second smallest eigenvalue of a state-dependent graph Laplacian,” IEEE Trans. on Automatic Control, Vol.51, No.1, pp. 116-120, 2006.
-  A. Ghosh and S. Boyd, “Growing Well-Connected Graphs,” Proc. of IEEE Int. Conf. on Decision and Control, pp. 6605-6611, 2006.
-  R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and Cooperation in Networked Multi-Agent Systems,” Proc. of the IEEE, Vol.95, No.1, pp. 215-233, 2007.
-  S. Martínez and F. Bullo, “Optimal sensor placement and motion coordination for target tracking,” Automatica, Vol.42, pp. 661-668, 2006.
-  S. Oh and S. Sastry, “Tracking on a graph,” Proc. of the 4th Int. Conf. on Information Processing in Sensor Networks (IPSN05), Los Angeles, CA, pp. 195-202, 2005.
-  P. Yang, R. Freeman, and K. Lynch, “Distributed cooperative active sensing using consensus filters,” Proc. of 2007 IEEE Int. Conf. on Robotics and Automation, Rome, Italy, pp. 405-410, 2007.
-  F. Zhao, J. Shin, and J. Reich, “Information-driven dynamic sensor collaboration for tracking applications,” IEEE Signal Processing Magazine, Vol.19, No.2, pp. 61-72, 2002.
-  N. E. Leonard, D. Paley, F. Lekien, R. Sepulchre, D. Fratantoni, and R. Davis, “Collective motion, sensor networks, and ocean sampling,” Proc. of the IEEE Special Issue on Networked Control Systems, Vol.95, pp. 48-74, 2007.
-  S. Simic and S. Sastry, “Distributed environmental monitoring using random sensor networks,” Proc. of the 2nd Int. Workshop on Information Processing in Sensor Networks, pp. 582-592, 2003.
-  S. Susca, S. Martinez, and F. Bullo, “Monitoring environmental boundaries with a robotic sensor network,” American Control Conf., pp. 2072-2077, 2006.
-  K. Lynch, I. Schwartz, P. Yang, and R. Freeman, “Decentralized environmental modeling by mobile sensor networks,” IEEE Trans. on Robotics, Vol.24, No.3, pp. 710-724, 2008.
-  C. Belta and V. Kumar, “Abstraction and control for groups of robots,” IEEE Trans. on Robotics, Vol.20, No.5, pp. 865-875, 2004.
-  J. Cortés, S. Martínez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” IEEE Trans. on Robotics and Automation, Vol.20, No.2, pp. 243-255, 2004.
-  J. A. Fax and R. M. Murray, “Information flow and cooperative control of vehicle formations,” IEEE Trans. on Automatic Control, Vol.49, No.9, pp. 1465-1476, 2004.
-  H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita, “Distributed mem- oryless point convergence algorithm for mobile robots with limited visibility,” IEEE Trans. on Robotics and Automation, Vol.15, No.5, pp. 818-828, 1999.
-  D. V. Dimarogonas and K. J. Kyriakopoulos, “Connectedness preserving distributed swarm aggregation for multiple kinematic robots,” IEEE Trans. on Robotics, Vol.24, No.5, pp. 1213-1223, 2008.
-  M. Ji and M. Egerstedt, “Coordination control of multi-agent systems while preserving connectedness,” IEEE Trans. on Robotics, Vol.23, No.4, pp. 693-703, 2007.
-  A. Ganguli, J. Cortes, and F. Bullo, “Multirobot rendezvous with visibility sensors in nonconvex environments,” IEEE Trans. on Robotics, Vol.25, No.2, pp. 340-352, 2009.
-  J. Cortés, S. Martínez, and F. Bullo, “Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions,” IEEE Trans. on Automatic Control, Vol.51, No.8, pp. 1289-1298, 2006.
-  M. M. Zavlanos, H. G. Tanner, A. Jadbabaie, and G. J. Pappas, “Hybrid control for connectivity preserving flocking,” IEEE Trans. on Automatic Control, Vol.54, No.12, pp. 2869-2875, 2009.
-  P. Yang, R. A. Freeman, G. J. Gordon, K. M. Lynch, S. S. Srinivasa, and R. Sukthankar, “Decentralized estimation and control of graph connectivity for mobile sensor networks,” Automatica, Vol.46, Issue 2, pp. 390-396, 2010.
-  M. Fiedler, “Algebraic connectivity of Graphs,” Czechoslovak Mathematical J., Vol.23, No.2, pp. 298-305, 1973.
-  M. C. De Gennaro and A. Jadbabaie, “Decentralized control of connectivity for multi-agent systems,” IEEE Int. Conf. on Decision and Control, pp. 3628-3633, 2006.
-  P. Chebotarev and E. V. Shamis, “The matrix-forest theorem and measuring relations in small social groups,” Automation and Remote Control, Vol.58, No.9, pp. 1505-1514, 1997.
-  A. J. Smola and R. Kondor, “Kernels and regularization on graphs,” Proc. of Computational Learning Theory and Kernel Machines: 16th Annual Conf. on Learning Theory and 7th Kernel Workshop, pp. 144-158, 2003.
-  H. Yuasa and M. Ito, “Internal Observation Systems and a Theory of Reaction-Diffusion Equation on a Graph,” IEEE Int. Conf. on System, Man, and Cybernetics, October 11-14, Vol.4, pp. 3669-3673, 1998.
-  F. Mondada, M. Bonani, X. Raemy, J. Pugh, C. Cianci, A. Klaptocz, S. Magnenat, J.-C. Zufferey, D. Floreano, and A. Martinoli, “The e-puck, a Robot Designed for Education in Engineering,” Proc. of the 9th Conf. on Autonomous Robot Systems and Competitions, Vol.1, No.1, pp. 59-65, 2009.
-  A. Astolfi, “Exponential Stabilization of a Wheeled Mobile Robot Via Discontinuous Control,” ASME J. of Dynamic Systems, Measurements, and Control, Vol.121, No.1, pp. 121-127, 1999.