Entropy-Based Framework for Dynamic Coverage and Clustering Problems
- 3 October 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 57 (1), 135-150
- https://doi.org/10.1109/tac.2011.2166713
Abstract
We propose a computationally efficient framework to solve a large class of dynamic coverage and clustering problems, ranging from those that arise from deployment of mobile sensor networks to classification of cellular data for diagnosing cancer stages. This framework provides the ability to identify natural clusters in the underlying data set. In particular, we define the problem of minimizing instantaneous coverage as a combinatorial optimization problem in a Maximum Entropy Principle (MEP) framework that we formulate specifically for the dynamic setting, and which allows us to address inherent tradeoffs such as those between the resolution of the identified clusters and computational cost. The proposed MEP framework addresses both the coverage and the tracking aspects of these problems. Locating cluster centers of swarms of moving objects and tracking them is cast as a control design problem ensuring that the algorithm achieves progressively better coverage with time. Simulation results are presented that highlight the features of this framework; these results demonstrate that the proposed algorithm attains target coverage costs five to seven times faster than related frame-by-frame methods.Keywords
This publication has 30 references indexed in Scilit:
- A Maximum Entropy Based Scalable Algorithm for Resource Allocation ProblemsAmerican Control Conference (ACC), 2007
- On Combinatorial Optimization Problems with Mobile Sites and ResourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Probability TheoryPublished by Cambridge University Press (CUP) ,2003
- Centroidal Voronoi Tessellations: Applications and AlgorithmsSIAM Review, 1999
- Constructive Nonlinear ControlPublished by Springer Science and Business Media LLC ,1997
- Facility LocationPublished by Springer Science and Business Media LLC ,1995
- A ‘universal’ construction of Artstein's theorem on nonlinear stabilizationSystems & Control Letters, 1989
- Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of ImagesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1984
- A Lyapunov-Like Characterization of Asymptotic ControllabilitySIAM Journal on Control and Optimization, 1983
- Information Theory and Statistical MechanicsPhysical Review B, 1957