An official website of the United States government
We investigate the problems of maximizing k-submodular functions over total size constraints and over individual size constraints. k-submodularity is a generalization of submodularity beyond just picking items of a ground set, instead associating one of k types to chosen items. For sensor selection problems, for instance, this enables modeling of which type of sensor to put at a location, not simply whether to put a sensor or not. We propose and analyze threshold-greedy algorithms for both types of constraints. We prove that our proposed algorithms achieve the best known approximation ratios for both constraint types, up to a user-chosen parameter that balances computational complexity and the approximation ratio, while only using a number of function evaluations that depends linearly (up to poly-logarithmic terms) on the number of elements n, the number of types k, and the inverse of the user chosen parameter. Other algorithms that achieve the best-known deterministic approximation ratios require a number of function evaluations that depend linearly on the budget B, while our methods do not. We empirically demonstrate our algorithms' performance in applications of sensor placement with k types and influence maximization with k topics.
more »
« less
Sensor Selection via GFlowNets: A Deep Generative Modeling Framework to Navigate Combinatorial Complexity
The performance of sensor arrays in sensing and wireless communications improves with more elements, but this comes at the cost of increased energy consumption and hardware expense. This work addresses the challenge of selecting k sensor elements from a set of m to optimize a generic Quality-of-Service metric. Evaluating all possible sensor subsets is impractical, leading to prior solutions using convex relaxations, greedy algorithms, and supervised learning approaches. The current paper proposes a new framework that employs deep generative modeling, treating sensor selection as a deterministic Markov Decision Process where sensor subsets of size k arise as terminal states. Generative Flow Networks (GFlowNets) are employed to model an action distribution conditioned on the state. Sampling actions from the aforementioned distribution ensures that the probability of arriving at a terminal state is proportional to the performance of the corresponding subset. Applied to a standard sensor selection scenario, the developed approach outperforms popular methods which are based on convex optimization and greedy algorithms. Finally, a multiobjective formulation of the proposed approach is adopted and applied on the sparse antenna array design for Integrated Sensing and Communication (ISAC) systems. The multiobjective variation is shown to perform well in managing the trade-off between radar and communication performance.
more »
« less
- Award ID(s):
- 2033433
- PAR ID:
- 10554131
- Publisher / Repository:
- https://arxiv.org/abs/2407.19736
- Date Published:
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This article presents a new method to solve a dynamic sensor fusion problem. We consider a large number of remote sensors which measure a common Gauss–Markov process. Each sensor encodes and transmits its measurement to a data fusion center through a resource restricted communication network. The communication cost incurred by a given sensor is quantified as the expected bitrate from the sensor to the fusion center. We propose an approach that attempts to minimize a weighted sum of these communication costs subject to a constraint on the state estimation error at the fusion center. We formulate the problem as a difference-of-convex program and apply the convex-concave procedure (CCP) to obtain a heuristic solution. We consider a 1D heat transfer model and a model for 2D target tracking by a drone swarm for numerical studies. Through these simulations, we observe that our proposed approach has a tendency to assign zero data rate to unnecessary sensors indicating that our approach is sparsity-promoting, and an effective sensor selection heuristic.more » « less
-
We consider a dynamic sensor fusion problem where a large number of remote sensors observe a common Gauss-Markov process and the observations are transmitted to a fusion center over a resource constrained communication network. The design objective is to allocate an appropriate data rate to each sensor in such a way that the total data traffic to the fusion center is minimized, subject to a constraint on the fusion center's state estimation error covariance. We show that the problem can be formulated as a difference-of-convex program, to which we apply the convex-concave procedure (CCP) and the alternating direction method of multiplier (ADMM). Through a numerical study on a truss bridge sensing system, we observe that our algorithm tends to allocate zero data rate to unneeded sensors, implying that the proposed method is an effective heuristic for sensor selection.more » « less
-
We study two multi-robot assignment problems for multi-target tracking. We consider distributed approaches in order to deal with limited sensing and communication ranges. We seek to simultaneously assign trajectories and targets to the robots. Our focus is on \emph{local} algorithms that achieve performance close to the optimal algorithms with limited communication. We show how to use a local algorithm that guarantees a bounded approximate solution within $$\mathcal{O}(h\log{1/\epsilon})$$ communication rounds. We compare with a greedy approach that achieves a $$2$$--approximation in as many rounds as the number of robots. Simulation results show that the local algorithm is an effective solution to the assignment problem.more » « less
-
Given a linear dynamical system, we consider the problem of selecting (at design-time) an optimal set of sensors (subject to certain budget constraints) to minimize the trace of the steady state error covariance matrix of the Kalman filter. Previous work has shown that this problem is NP-hard for certain classes of systems and sensor costs; in this paper, we show that the problem remains NP-hard even for the special case where the system is stable and all sensor costs are identical. Furthermore, we show the stronger result that there is no constant-factor (polynomial-time) approximation algorithm for this problem. This contrasts with other classes of sensor selection problems studied in the literature, which typically pursue constant-factor approximations by leveraging greedy algorithms and submodularity of the cost function. Here, we provide a specific example showing that greedy algorithms can perform arbitrarily poorly for the problem of design-time sensor selection for Kalman filtering.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Posted Content:
- The DOI is not currently available.
