A Graph-Based Approach to Boundary Estimation with Mobile Sensors

Sean O. Stalley, Dingyu Wang, Gautam Dasarathy, John Lipor

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)4991-4998
Number of pages8
JournalIEEE Robotics and Automation Letters
Issue number2
StatePublished - Apr 1 2022


  • Environment monitoring and management
  • Machine learning for robot control
  • Sensor-based control

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Biomedical Engineering
  • Human-Computer Interaction
  • Mechanical Engineering
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Control and Optimization
  • Artificial Intelligence


Dive into the research topics of 'A Graph-Based Approach to Boundary Estimation with Mobile Sensors'. Together they form a unique fingerprint.

Cite this