A Primal-Dual Gradient Descent Approach to the Connectivity Constrained Sensor Coverage Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912311260741632 |
|---|---|
| author | Agerman, Mathias Bock Zhang, Ziqiao Kim, Jong Gwang Sundaram, Shreyas Brinton, Christopher |
| author_facet | Agerman, Mathias Bock Zhang, Ziqiao Kim, Jong Gwang Sundaram, Shreyas Brinton, Christopher |
| contents | Sensor networks play a critical role in many situational awareness applications. In this paper, we study the problem of determining sensor placements to balance coverage and connectivity objectives over a target region. Leveraging algebraic graph theory, we formulate a novel optimization problem to maximize sensor coverage over a spatial probability density of event likelihoods while adhering to connectivity constraints. To handle the resulting non-convexity under constraints, we develop an augmented Lagrangian-based gradient descent algorithm inspired by recent approaches to efficiently identify points satisfying the Karush-Kuhn-Tucker (KKT) conditions. We establish convergence guarantees by showing necessary assumptions are satisfied in our setup, including employing Mangasarian-Fromowitz constraint qualification to prove the existence of a KKT point. Numerical simulations under different probability densities demonstrate that the optimized sensor networks effectively cover high-priority regions while satisfying desired connectivity constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04122 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Primal-Dual Gradient Descent Approach to the Connectivity Constrained Sensor Coverage Problem Agerman, Mathias Bock Zhang, Ziqiao Kim, Jong Gwang Sundaram, Shreyas Brinton, Christopher Optimization and Control 93-08 (Primary) 90-10, 49K99 (Secondary) Sensor networks play a critical role in many situational awareness applications. In this paper, we study the problem of determining sensor placements to balance coverage and connectivity objectives over a target region. Leveraging algebraic graph theory, we formulate a novel optimization problem to maximize sensor coverage over a spatial probability density of event likelihoods while adhering to connectivity constraints. To handle the resulting non-convexity under constraints, we develop an augmented Lagrangian-based gradient descent algorithm inspired by recent approaches to efficiently identify points satisfying the Karush-Kuhn-Tucker (KKT) conditions. We establish convergence guarantees by showing necessary assumptions are satisfied in our setup, including employing Mangasarian-Fromowitz constraint qualification to prove the existence of a KKT point. Numerical simulations under different probability densities demonstrate that the optimized sensor networks effectively cover high-priority regions while satisfying desired connectivity constraints. |
| title | A Primal-Dual Gradient Descent Approach to the Connectivity Constrained Sensor Coverage Problem |
| topic | Optimization and Control 93-08 (Primary) 90-10, 49K99 (Secondary) |
| url | https://arxiv.org/abs/2504.04122 |