Sensing and Filtering:
A tutorial based on preimages and information spaces

Date: June 7-8, 2011
Location: CIMAT, Guanajuato, Gto, Mexico
Presented by: Steve LaValle, University of Illinois
Hosts: Dr. Luz Abril Torres-Mendez (CINVESTAV Saltillo) and Dr. Rafael Murrieta Cid (CIMAT Guanajuato)


Some key points:

One of the greatest challenges and frustrations arising from uncertainty is the burden of modeling. Although robots and sensors may have imperfect or incomplete information of the environment, many approaches attempt to model everything probabilistically and then design filters that attempt to estimate likely states. This tutorial will cover some new techniques that in some contexts may allow the modeling burden to be completely avoided by carefully studying the amount of information that is minimally necessary to achieve some task. A mathematical framework will be presented for modeling cheap, minimalist sensors, which can then be used for a variety of tasks, such as exploration, navigation, tracking, monitoring, and security. The approach relies on the introduction of powerful, new combinatorial filters, which are a minimalist analog of common techniques such as Bayesian or Kalman filters. Once minimal information requirements are understood, simple, cheap robot systems can be constructed that are robust to uncertainties that never need to be explicitly handled. Furthermore, one can place probabilistic models over the minimalist structures to obtain even greater robustness in practice. Therefore, the methods from this course are compatible and complementary to common probabilistic techniques used in robotics and sensor networks.


The lectures are based on this TUTORIAL ARTICLE (to appear in Foundations and Trends in Robotics); particular sections covered are mentioned on the schedule below.

Part Times Topic Materials
Tuesday, June 7
1 9:30-10:30Introduction, perspective, motivating tasks, overview of physical sensors, physical state spaces Sections 1 and 2, Slides1,Slides2,
Break 10:30-10:50
2 10:50-11:50Physical state spaces, virtual sensor models Sections 3.1 to 3.2, Slides3
Break 11:50-12:10
3 12:10-13:10Virtual sensor models, preimages, sensor lattices Sections 3.2 to 3.4, Slides3
Overflow, discussion, questions 13:10-13:30
Wednesday, June 8
4 9:30-10:30Nondeterministic, probabilistic, and history-based sensors. Sensors over state-time space. Spatial and temporal filters. Sections 3.5 to 4.2, Slides4
Break 10:30-10:50
5 10:50-11:50Combinatorial filters, planning in information spaces Sections 4.3 and 5, Slides5
Break 11:50-12:10
6 12:10-13:10Open problems and future research challenges Slides6
Overflow, discussion, questions 13:10-13:30

Related Literature:

The plan is to follow the tutorial article above. Additional material may include pointers to recent papers and some material on information spaces from Planning Algorithms, S. M. LaValle, Cambridge University Press, 2006:

Some related recent research articles (the tutorial covers separate material, but these publications might help to understand the overall spirit):

This work is supported in part by and NSF grant 0904501 (IIS robotics), NSF grant 1035345 (Cyberphysical Systems),i DARPA SToMP grant HR0011-05-1-0008, and MURI/ONR grant N00014-09-1-1052.