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

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.

Authors:

• Mohammadhosein Hasanbeig
• Lacra Pavel

Keywords:

• Distributed control
• game theory
• multi-agent learning
• reinforcement learning.

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.