Active learning for adaptive mobile sensing networks

ABSTRACT

This paper investigates data-adaptive path planning schemes for wireless networks of mobile sensor platforms. We focus on applications of environmental monitoring, in which the goal is to reconstruct a spatial map of environmental factors of interest. Traditional sampling theory deals with data collection processes that are completely independent of the target map to be estimated, aside from possible a priori specifications reflective of assumed properties of the target. We refer to such processes as passive learning methods. Alternatively, one can envision sequential, adaptive data collection procedures that use information gleaned from previous observations to guide the process. We refer to such feedback-driven processes as active learning methods. Active learning is naturally suited to mobile path planning, in which previous samples are used to guide the motion of the mobiles for further sampling. This paper presents some of the most encouraging theoretical results to date that support the effectiveness of active over passive learning, and focuses on new results regarding the capabilities of active learning methods for mobile sensing. Tradeoffs between latency, path lengths, and accuracy are carefully assessed using our theory. Adaptive path planning methods are developed to guide mobiles in order to focus attention in interesting regions of the sensing domain, thus conducting spatial surveys much more rapidly while maintaining the accuracy of the estimated map. The theory and methods are illustrated in the application of water current mapping in a freshwater lake.

REFERENCES

• 1: http://limnosun.limnology.wisc.edu/.
• 2: http://www.cens.ucla.edu/portal/nims/.
• 3: Maxim A. Batalin , Mohammad Rahimi , Yan Yu , Duo Liu , Aman Kansal , Gaurav S. Sukhatme , William J. Kaiser , Mark Hansen , Gregory J. Pottie , Mani Srivastava , Deborah Estrin, Call and response: experiments in sampling the environment, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031499]
• 4: L. Breiman, J. Friedman, R. Olshen, and C. Stone. Classification and Regression Trees. Wadsworth, Belmont, CA, 1983.
• 5: M. Burnashev and K. S. Zigangirov. An interval estimation problem for controlled observations. Problems in Information Transmission, 10:223--231, 1974.
• 6: R. Castro, R. Willett, and R. Nowak. Faster rates in regression via active learning. In Proceedings of NIPS, 2005. (also technical report available at http://homepages.cae.wisc.edu~rcastro/ECE-05-3.pdf).
• 7: G. Golubev and B. Levit. Sequential recovery of analytic periodic edges in the binary image models. Mathematical Methods of Statistics, 12:95--115, 2003.
• 8: P. Hall and I. Molchanov. Sequential methods for design-adaptive estimation of discontinuities in regression curves and surfaces. The Annals of Statistics, 31(3):921--941, 2003.
• 9: J. P. Hespanha, H. J. Kim, and S. Sastry. Multiple-agent probabilistic pursuit-evasion games. In Proceedings of the Conference on Decision and Control, Dec. 1999.
• 10: M. Horstein. Sequential decoding using noiseless feedback. IEEE Trans. Information Theory, 9(3):136--143, 1963.
• 11: G. Kesidis, T. Konstantopoulos, and S. Phoha. Surveillance coverage of sensor networks under a random mobility strategy. In Proceedings of IEEE Sensors, pages 961--965, 2003.
• 12: A. Korostelev. On minimax rates of convergence in image models under sequential design. Statistics and Probability Letters, 43:369--375, 1999.
• 13: T. D. Parsons. Pursuit-evasion in a graph. In Y. Alani and D. R. Lick, editors, Theory and Application of Graphs, pages 426--441. Springer-Verlag, 1976.
• 14: M. Rahimi, R. Pon, W. J. Kaiser, G. S. Sukhatme, D. Estrin, and M. Srivastava. Adaptive sampling for environmental robotics. In Proceedings of IEEE Int. Conf. on Robotics and Automation, ICRA, 2004.
• 15: Rebecca Willett , Aline Martin , Robert Nowak, Backcasting: adaptive sampling for sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984641]
• 16: H. Yuan and C. Wu. An implicit 3d fully non-hydrostatic model for free-surface flows. International J. for Numerical Methods in Fluids, 46:709--733, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Sensors

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Signal processing

General Terms:
Algorithms, Theory

Keywords:
active learning, adaptive sampling, mobile sensors, path planning, sensor networks