Sensing and Filtering: A Fresh Perspective Based on Preimages and Information Spaces
By Steven M. LaValle, Department of Computer Science, University of Illinois, Urbana-Champaign, USA, lavalle@uiuc.edu
Abstract
This monograph presents an unusual perspective on sensing uncertainty and filtering with the intention of understanding what information is minimally needed to achieve a specified task. Information itself is modeled using information space concepts, which originated from dynamic game theory (rather than information theory, which was developed mainly for communication). The guiding principle in this monograph is avoid sensing, representing, and encoding more than is necessary. The concepts and tools are motivated by many tasks of current interest, such as tracking, monitoring, navigation, pursuit-evasion, exploration, and mapping. First, an overview of sensors that appear in numerous systems is presented. Following this, the notion of a virtual sensor is explained, which provides a mathematical way to model numerous sensors while abstracting away their particular physical implementation. Dozens of useful models are given, each as a mapping from the physical world to the set of possible sensor outputs. Preimages with respect to this mapping represent a fundamental source of uncertainty: These are equivalence classes of physical states that would produce the same sensor output. Pursuing this idea further, the powerful notion of a sensor lattice is introduced, in which all possible virtual sensors can be rigorously compared. The next part introduces filters that aggregate information from multiple sensor readings. The integration of information over space and time is considered. In the spatial setting, classical triangulation methods are expressed in terms of preimages. In the temporal setting, an information-space framework is introduced that encompasses familiar Kalman and Bayesian filters, but also introduces a novel family called combinatorial filters. Finally, the planning problem is presented in terms of filters and information spaces. The monograph concludes with some discussion about connections to many related research fields and numerous open problems and future research directions.
Sensing and Filtering
Where do robots get their information? For a given task, what information is actually necessary? What is even meant by "information"? These questions lie at the heart of robotics and fall under the realm of sensing and filtering. In Sensing and Filtering, the author presents an unusual view of these subjects by characterizing the uncertainty due to the many-to-one mappings between the world and sensor readings. This is independent of noise-based uncertainty and reveals critical structure about the possible problems that can be solved using specific sensors. The set of all sensor models is arranged into a lattice that enables them to be compared for purposes of interchangeability. Filters, which combine sensor observations, are expressed in terms of information states (not information theory), a concept that was introduced in decision and control theory. Sensing and Filtering provides the reader with modeling tools and concepts for developing robotic systems that accomplish their tasks while carefully avoiding the reconstruction of unnecessary state information. This is in contrast to the approach usually taken in planning and control, which is to fully reconstruct and maintain the state at all times. The new approach may enable simple, robust, and inexpensive solutions to tasks such as navigation, topological mapping, coverage, patrolling, tracking, and pursuit-evasion.
