IROS 2009 TUTORIAL
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
Afterward:
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
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.
Students are especially welcome!
Schedule:
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
|
| Morning
|
| 1 | 8:45-10:00 | Introduction, 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:00 | Virtual sensor models, preimages,
sensor lattices
| Sections 3.2 to 3.4, Slides3
|
| Afternoon
|
| Lunch | 12:00-2:00
|
| 3 | 2:00-3:30 | Nondeterministic, 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:00 | Combinatorial filters, planning in information spaces
| Sections 4.3 and 5, Slides5
|
| 5 | 5:00-5:30 | Open 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):
- 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].
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.