Distributed Coverage Control by Robot Networks in Unknown Environments Using a Modified EM Algorithm

Authors: Mohammadhosein Hasanbeig, Lacra Pavel

Abstract:

In this paper, we study a distributed control algorithm for the problem of unknown area coverage by a network of robots. The coverage objective is to locate a set of targets in the area and to minimize the robots’ energy consumption. The robots have no prior knowledge about the location and also about the number of the targets in the area. One efficient approach that can be used to relax the robots’ lack of knowledge is to incorporate an auxiliary learning algorithm into the control scheme. A learning algorithm actually allows the robots to explore and study the unknown environment and to eventually overcome their lack of knowledge. The control algorithm itself is modeled based on game theory where the network of the robots use their collective information to play a non-cooperative potential game. The algorithm is tested via simulations to verify its performance and adaptability.

Keywords: Distributed control, game theory, multi-agent learning, reinforcement learning.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1131047

References:

[1] S. Dhillon, K. Chakrabarty, S. Iyengar, “Sensor Placement for Grid Coverage under Imprecise Detections”, in Proc. Intl. Conf. on Information Fusion, pp. 1571-1587, 2002.
[2] D. Ucinski, “Measurement Optimization for Parameter Estimation in Distributed Systems”, CRC Press, 1999.
[3] Li, W., Cassandras, C.G., “Distributed Cooperative coverage Control of Sensor Networks”, 44th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC ’05), pp. 2542-2547, 2005.
[4] J. R. Spletzer and C. J. Taylor, “Dynamic Sensor Planning and Control for Optimally Tracking Targets”, International Journal of Robotics Research, vol. 22, no. 1, pp. 7-20, 2003.
[5] T. Nakamoto, H. Ishida, and T. Moriizumi, “Active Odor Sensing System”, in Proc. Intl. Symposium on Industrial Electronics, vol. 1, pp. SS128-SS133, 1997.
[6] J.R. Frost and L.D. Stone, “Review of Search Theory: Advances and Applications to Search and Rescue Decision Support”, Technical Report CG-D-15-01, U.S. Coast Guard Research and Development Center, Gronton, CT, 2001.
[7] T. Heng, Y. Kuno, and Y. Shirai, “Active Sensor Fusion for Collision Avoidance”, in Proc of the IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, vol. 3, pp. 1244-1249, 1997.
[8] Rahili, S., Ren, W., “Game Theory Control Solution for Sensor Coverage Problem in Unknown Environment”, 53rd IEEE Conference on Decision and Control (CDC), pp.1173-1178, 2014.
[9] W. Yatao and L. Pavel,“A Modified Q-Learning Algorithm for Potential Games”, Proceedings of the 19th IFAC World Congress, vol.19, pp. 8710-8718, 2014.
[10] J. Marden and A. Wierman, “Distributed Welfare Games with Applications to Sensor Coverage”, 47th IEEE Conference on Decision and Control, pp. 1708-1713, 2008.
[11] Pavel, L.,“Game Theory and Evolutionary Games”, ECE1657, University of Toronto, Toronto, 2014.
[12] H. Bayram and H. Bozma, “Multi-robot Communication Network Topology via Centralized Pairwise Games”, 2013 IEEE International Conference on Robotics and Automation, 2013.
[13] Chung, T.H., Gupta, V., Burdick, J.W., Murray, R.M.,“On a Decentralized Active Sensing Strategy using Mobile Sensor Platforms in a Network”, 43rd IEEE Conference on Decision and Control (CDC), pp.1914-1919, Vol. 2, 2004.
[14] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage Control for Mobile Sensing Networks”, IEEE Transactions on Robotics and Automation, vol. 20, no. 2, pp. 243-255, 2004.
[15] J. Cortes, S. Martinez and F. Bullo, “Spatially-distributed Coverage Optimization and Control with Limited-range Interactions”, ESAIM: Control, Optimisation and Calculus of Variations, vol. 11, no. 4, pp. 691-719, 2005.
[16] A. Kwok and S. Martinez, “Deployment Algorithms for A Power-constrained Mobile Sensor Network”, IEEE International Conference on Robotics and Automation, 2008.
[17] J. R. Marden and J. S. Shamma, “Revisiting Log-linear Learning: Asynchrony, Completeness and Payoff-based Implementation”, Games and Economic Behavior, vol. 75, no. 2, pp. 788-808, 2012.
[18] A. P. Dempster, N. M. Laird, and D. B. Rubin, “Maximum Likelihood from Incomplete Data via The EM Algorithm”, Journal of the Royal Statistical Society Series B, vol. 39, no. 1, pp. 1-38, 1977.
[19] V. Lakshmanan and J. S. Kain, “A Gaussian Mixture Model Approach to Forecast Verification”, Weather and Forecasting, vol. 25, pp. 908-920, 2010.
[20] Y. Lim and J. S. Shamma, “Robustness of Stochastic Stability in Game Theoretic Learning”, ACC, pp. 6145-6150, 2013.
[21] Akaike, H., “A New Look at The Statistical Model Identification”, IEEE Transactions on Automatic Control, vol.19, no.6, pp. 716-723, 1974
[22] N. Ueda, R. Nakano, Z. Ghahramani and G. Hinton, ”Split and Merge EM Algorithm for Improving Gaussian Mixture Density Estimates”, The Journal of VLSI Signal Processing, vol. 26, no. 12, pp. 133-140, 2000.