Published In

IEEE Robotics and Automation Letters

Document Type


Publication Date



Mobile Sensors -- Computers


We consider the problem of adaptive sampling for boundary estimation, where the goal is to identify the two dimensional spatial extent of a phenomenon of interest. Motivated by applications in estimating the spread of wildfires with a mobile sensor, we present a novel graph-based algorithm that is efficient in both the number of samples taken and the distance traveled. The key idea behind our approach is that by sampling locations close to known cut edges (edges whose vertices lie on opposite sides of the boundary), we can reliably find additional cut edges. Our approach repeats this process of using the newly discovered cut edges to find additional cut edges, eventually identifying all vertices lying adjacent to the boundary. We show that our method achieves both a sample complexity and a distance traveled that are within a constant factor of the optimal values. Moreover, the computational complexity of determining sample locations and paths is O(1), making its deployment on mobile sensors highly realistic. Experimental results on both synthetic and historical wildfire data show that our proposed algorithm outperforms existing methods in terms of sample complexity, distance traveled, and computation time.


This article has been accepted for publication in a future issue of this journal, but has not been fully edited. Content may change prior to final publication. Citation information: DOI 10.1109/LRA.2022.3145977, IEEE Robotics and Automation Letters



Persistent Identifier