CIMAT/CINVESTAV Tutorial 2011

SUMMER SHORT COURSE

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)

Motivation:

Some key points:

Gigantic SLAM problems require techniques to reduce model complexity.
Extreme uncertainty is produced by perfectly predictable sensors.
Simple, efficient filters can be made that avoid full state recovery.
With sensing uncertainty, planning occurs in an information space, not the configuration space.
Filters and information spaces can be simplified before probabilistic models are introduced.

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.

Schedule:

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:30 Introduction, 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:50 Physical state spaces, virtual sensor models Sections 3.1 to 3.2, Slides3

Break 11:50-12:10

3 12:10-13:10 Virtual 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:30 Nondeterministic, 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:50 Combinatorial filters, planning in information spaces Sections 4.3 and 5, Slides5

Break 11:50-12:10

6 12:10-13:10 Open problems and future research challenges Slides6

Overflow, discussion, questions 13:10-13:30

Part	Times	Topic	Materials
Tuesday, June 7
1	9:30-10:30	Introduction, 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:50	Physical state spaces, virtual sensor models	Sections 3.1 to 3.2, Slides3
Break	11:50-12:10
3	12:10-13:10	Virtual 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:30	Nondeterministic, 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:50	Combinatorial filters, planning in information spaces	Sections 4.3 and 5, Slides5
Break	11:50-12:10
6	12:10-13:10	Open 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):

Sensor beams, obstacles, and possible paths. B. Tovar, F. Cohen, and S. M. LaValle. In Proceedings Workshop on Algorithmic Foundations of Robotics (WAFR), 2008. [pdf] [ps.gz].
Tracking hidden agents through shadow information spaces. J. Yu and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2008. [pdf] [ps.gz].
Localization with limited sensing. J. M. O'Kane and S. M. LaValle. IEEE Transactions on Robotics, 23(4):704--716, August 2007. [pdf] [ps.gz].
Distance-optimal navigation in an unknown environment without sensing distances. B. Tovar, R Murrieta, and S. M. LaValle. IEEE Transactions on Robotics, 23(3):506--518, June 2007. [pdf] [ps.gz].
Using a robot to learn geometric information from permutations of landmarks. B. Tovar, L. Freda, and S. M. LaValle. In Contemporary Mathematics, volume 438, pages 33--45. American Mathematical Society, 2007. [pdf] [ps.gz].
Probabilistic localization with a blind robot. L. H. Erickson, J. Knuth, J. M. O'Kane, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2008. [pdf] [ps.gz].
Manipulating Ergodic Bodies Through Gentle Guidance. L. Bobadilla, K. Gossman, and S. M. LaValle. In Proceedings of the IEEE Conference on Robot Motion and Control, 2011. [pdf]

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.