Papers for

automated sensor networks

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Programmable particles find hidden dangers with minimal resources

Optimal Proximity Black Hole Search with Programmable Matter

Abstract: The concept of programmable matter (PM) envisions objects composed of tiny, mobile particles capable of self-arrangement, which allows them to change shape, color, and move. We initiate the study of the Black Hole Search problem within the context of PM. The problem involves a dangerous and unnoticeable location, the black hole, that, without a trace, destroys any particle visiting it. In our setting, particles move inside a convex area embedded in a triangular grid, where one vertex is a black hole. The objective is for the particles to identify a restricted set of vertices containing the black hole while ensuring that at least one particle survives. We present an algorithm utilizing three particles capable of assuming just two colors to identify the dangerous region where the black hole resides. Furthermore, we demonstrate that this algorithm is Pareto optimal in terms of number of particles and number of colors required, and asymptotically optimal in terms of number of epochs, where an epoch refers to the minimal time window within which each particle completed an activation cycle at least once.

Mon 9 NovDistributed, Parallel, and Cluster Computing
The gist
Some materials can move and change shape by arranging tiny particles within them, like programmable matter. This paper looks at a problem where one spot in a grid is a black hole that destroys any particle entering, but the particles can't tell until one is lost. The researchers designed a way for just three particles with only two colors each to find the location of this dangerous spot without losing all particles. Their solution uses the smallest number of particles and colors possible and is also fast in terms of time cycles needed.
Open → 2611.12170v1

Active feature acquisition methods adapt to missing training data costs and performance

Active Feature Acquisition With Incomplete Training Data

Abstract: In many prediction tasks, acquiring all features can be a prohibitively expensive or outright impossible task. Further, in many cases a static subset of features may not be enough to solve the problem sufficiently across various instances. Active Feature Acquisition (AFA) addresses these problems by formalizing the trade-off between feature cost and predictive performance during sequential feature selection. However, prior AFA work largely assumes access to complete training data, an assumption that is often violated in practice. Here we study AFA with Incomplete Training Data (AFA-ITD), showing that under missing completely at random (MCAR) data, one-step acquisition values remain unchanged, whereas multi-step values can decrease. We analyze three approaches to learning from incomplete data: aliasing, filtering, and generative restoration. We show that filtering can require a number of training instances scaling exponentially with the dimension, whereas generative restoration scales exponentially with the acquisition budget. We empirically test our theory on a controlled experiment and across common AFA datasets and find that missingness mainly damages methods that exploit multi-step acquisitions and that generative restoration is able to recover lost performance in many experiments. Code is available at https://github.com/Linusaronsson/AFA-Benchmark/tree/missing-data.

Sat 26 SeptMachine LearningArtificial Intelligence
The gist
Sometimes gathering all information needed to make a prediction is too costly or impossible. The authors study how to actively decide which pieces of information (features) to get, even when the available training data is incomplete or missing some parts. They find that certain approaches to handle missing data work better than others, especially when planning multiple steps ahead. Their experiments show that methods using a generative model to restore missing data can recover much of the lost performance. This helps build smarter systems that gather information efficiently despite incomplete data.
Open → 2609.32325v1