In many real-world scenarios—from deploying a swarm of drones to scan a building to placing monitors in a city's water network—we face a daunting combinatorial challenge: selecting the "best" subset of locations from an astronomical number of possibilities. If you have 100 potential sensor sites and can only afford 10, there are over 17 trillion combinations to check.
Finding the absolute optimal configuration is usually NP-hard. However, researchers have discovered that most information-gathering tasks share a mathematical property called submodularity. This property allows simple, "greedy" strategies to perform remarkably well, often reaching within 63% of the theoretical optimum with a fraction of the computational effort.
The Intuition of Diminishing Returns
At its heart, submodularity is the formal mathematical expression of diminishing returns.
Imagine you are placing cameras to monitor a room. The first camera you install provides a massive amount of new information. The second camera also helps, but if its field of view overlaps with the first, the marginal information it adds is slightly less. By the time you are placing the tenth camera, the additional area it covers is likely very small because most of the room is already visible.
As Ronald Parr and Erik Halvorson explain in Planning Aims for a Network of Horizontal and Overhead Sensors, this means the utility of adding a sensor depends on what you have already deployed. Formally, a function $f$ is submodular if for every $A \subseteq B$ and an element $s \notin B$: $$f(A \cup \{s\}) - f(A) \geq f(B \cup \{s\}) - f(B)$$ In plain English: adding a sensor to a small set ($A$) helps more than adding that same sensor to a larger set ($B$).
Why the Greedy Algorithm is "Near-Optimal"
Because of this diminishing returns property, we don't need to look ahead to the final configuration to make a good choice now. We can simply use a greedy algorithm: start with an empty set, and at each step, add the single sensor that provides the highest immediate gain.
A landmark result in this field, referenced across papers like Incremental deployment of network monitors based on Group Betweenness Centrality by Shlomi Dolev and colleagues, is that for monotone submodular functions, the greedy algorithm is guaranteed to find a solution that is at least $(1 - 1/e) \approx 63.2\%$ of the optimal solution.
In practice, the performance is often much higher. Wentao Jiang and Hao Xiang demonstrated in Optimizing the Placement of Roadside LiDARs for Autonomous Driving that this greedy approach can find near-optimal roadside sensor configurations in seconds, whereas a brute-force search would take days.
From Static Placement to Active Perception
The power of submodularity extends beyond static sensor placement into active perception, where a robot must decide where to move next to gather information.
In Guest editorial: Special issue on active perception, Volkan Isler and Davide Scaramuzza 0001 highlight how robots can treat their future path as a sequence of sensor placements. By maximizing a submodular information gain function, robots can plan trajectories that avoid redundant observations.
This is particularly useful for complex tasks like:
- 3D Reconstruction: Benjamin Hepp and Matthias Nießner used submodular optimization in Plan3D to plan drone flights that maximize the surface detail of buildings while respecting battery limits.
- Target Tracking: Yash Satsangi and Shimon Whiteson developed the PartiMax algorithm, which uses submodularity to process only the most relevant 10% of video pixels, maintaining high tracking accuracy with massive speedups.
Handling Complexity: Non-Linearity and Uncertainty
While the basic greedy algorithm is powerful, real-world systems often introduce complications that break standard submodularity.
Weak Submodularity
In non-linear systems, such as quadratic measurement models, the diminishing returns property might not hold perfectly. Abolfazl Hashemi and Haris Vikalo addressed this in Submodular Observation Selection and Information Gathering for Quadratic Models by using the concept of weak submodularity, which still allows for provable performance bounds even when the "diminishing returns" are slightly inconsistent.
Adaptive and Adversarial Settings
Sometimes, the value of a sensor depends on the outcome of previous measurements. This is known as adaptive submodularity. Adish Singla and Andreas Krause applied this to community sensing, creating mechanisms that recruit participants based on the data already collected to minimize costs.
Furthermore, in high-stakes environments, we must plan against adversaries. Andreas Krause and Daniel Golovin showed in Randomized Sensing in Adversarial Environments that combining submodular optimization with game theory allows for randomized sensing strategies that remain robust even when an attacker is trying to evade detection.
Broad Impact Across Domains
The submodular framework has become a "universal wrench" for infrastructure and safety:
- Epidemiology: Bijaya Adhikari and Anil Vullikanti use it to place "sentinel" sensors in hospitals to detect infection outbreaks early.
- Cybersecurity: Yuhan Suo and Yuanqing Xia apply it to schedule audits in large-scale networks to detect false data injection attacks without draining sensor batteries.
- Smart Grids: Teklemariam Tesfay used submodular heuristics to plan software patching for power grid sensors, ensuring the system remains observable even while some nodes are offline for updates.
By recognizing the shared mathematical structure of these diverse problems, researchers can move away from ad-hoc heuristics and toward algorithms with rigorous, predictable performance.