The 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems
Filtering and Planning in Information Spaces

Date: 11 October 2009, Time: 8:45-5:30
By: Steve LaValle, University of Illinois


With around 60 people attending, backed out the door, the workshop was a huge success. There were many great comments and questions during the day. The tutorial paper and corrected slides appear below. I hope to expand the notes, offer more tutorials, and perhaps make a book. Any feedback on the notes or slides below is highly welcome (whether or not you attended the tutorial). Thanks for meeting me in St. Louis! -Steve LaValle, Urbana, 20 Oct 2009


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.

Students are especially welcome!


The lectures are based on this TUTORIAL ARTICLE (CS UIUC Tech. Report, Oct. 2009); particular sections covered are mentioned on the schedule below.

Part Times Topic Materials
1 8:45-10:00Introduction, motivating tasks, overview of physical sensors, physical state spaces Sections 1 to 3.1, Slides1,Slides2,
Break 10:00-10:30
2 10:30-12:00Virtual sensor models, preimages, sensor lattices Sections 3.2 to 3.4, Slides3
Lunch 12:00-2:00
3 2:00-3:30Nondeterministic, probabilistic, and history-based sensors. Sensors over state-time space. Spatial and temporal filters. Sections 3.5 to 4.2, Slides4
Break 3:30-4:00
4 4:00-5:00Combinatorial filters, planning in information spaces Sections 4.3 and 5, Slides5
5 5:00-5:30Open problems and future research challenges Slides6

The break times coincide with IROS-wide coffee breaks.

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), DARPA SToMP grant HR0011-05-1-0008, and MURI/ONR grant N00014-09-1-1052.