Gradient-based optimization for multi-resource spatial coverage problems

Nitin Kamra, Yan Liu
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, PMLR 161:1885-1894, 2021.

Abstract

Resource allocation for coverage of geographical spaces is a challenging problem in robotics, sensor networks and security domains. Conventional solution approaches either: (a) rely on exploiting spatio-temporal structure of specific coverage problems, or (b) use genetic algorithms when targeting general coverage problems where no special exploitable structure exists. In this work, we propose the coverage gradient theorem, which provides a gradient estimator for a broad class of spatial coverage objectives using a combination of Newton-Leibniz theorem and implicit boundary differentiation. We also propose a tractable framework to approximate the coverage objectives and their gradients using spatial discretization and empirically demonstrate the efficacy of our framework on multi-resource spatial coverage problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v161-kamra21a, title = {Gradient-based optimization for multi-resource spatial coverage problems}, author = {Kamra, Nitin and Liu, Yan}, booktitle = {Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence}, pages = {1885--1894}, year = {2021}, editor = {de Campos, Cassio and Maathuis, Marloes H.}, volume = {161}, series = {Proceedings of Machine Learning Research}, month = {27--30 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v161/kamra21a/kamra21a.pdf}, url = {https://proceedings.mlr.press/v161/kamra21a.html}, abstract = {Resource allocation for coverage of geographical spaces is a challenging problem in robotics, sensor networks and security domains. Conventional solution approaches either: (a) rely on exploiting spatio-temporal structure of specific coverage problems, or (b) use genetic algorithms when targeting general coverage problems where no special exploitable structure exists. In this work, we propose the coverage gradient theorem, which provides a gradient estimator for a broad class of spatial coverage objectives using a combination of Newton-Leibniz theorem and implicit boundary differentiation. We also propose a tractable framework to approximate the coverage objectives and their gradients using spatial discretization and empirically demonstrate the efficacy of our framework on multi-resource spatial coverage problems.} }
Endnote
%0 Conference Paper %T Gradient-based optimization for multi-resource spatial coverage problems %A Nitin Kamra %A Yan Liu %B Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2021 %E Cassio de Campos %E Marloes H. Maathuis %F pmlr-v161-kamra21a %I PMLR %P 1885--1894 %U https://proceedings.mlr.press/v161/kamra21a.html %V 161 %X Resource allocation for coverage of geographical spaces is a challenging problem in robotics, sensor networks and security domains. Conventional solution approaches either: (a) rely on exploiting spatio-temporal structure of specific coverage problems, or (b) use genetic algorithms when targeting general coverage problems where no special exploitable structure exists. In this work, we propose the coverage gradient theorem, which provides a gradient estimator for a broad class of spatial coverage objectives using a combination of Newton-Leibniz theorem and implicit boundary differentiation. We also propose a tractable framework to approximate the coverage objectives and their gradients using spatial discretization and empirically demonstrate the efficacy of our framework on multi-resource spatial coverage problems.
APA
Kamra, N. & Liu, Y.. (2021). Gradient-based optimization for multi-resource spatial coverage problems. Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 161:1885-1894 Available from https://proceedings.mlr.press/v161/kamra21a.html.

Related Material