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.
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.