Steven M. LaValle

Simpler Sensor Fusion

Sensor fusion is the problem of transforming data that arrives from sensors, in a way that is useful for making decisions or estimating values of desired variables. This sensor data could come from many different sensors, or correspond to multiple readings of a single sensor, or any combination. The problems appears everywhere, including robot localization, map building, SLAM, target tracking, counting people, GPS, and so on. (A classical name for this area is filtering, which sometimes has confusing connotations.) The key challenge is to find a representation that can be incrementally updated as new sensor data arrives, yet is sufficiently powerful enough for the desired task. In most problems there is an underlying state space, in which the state at a given time cannot be directly observed. The classical sensor fusion goal is to estimate the state; however, a more interesting situation is to estimate just enough about the state to be sufficient for a task, such a counting the number of people in a room (rather than calculating their precise positions).

One of the most common representations is a probability distribution over a state space, which results in Bayesian filters (see this book for robotics examples). Within that category, the most useful method to data has been Kalman filters, which are optimal in a very narrow sense of linear Gaussian systems, but seem to work well more broadly. In our research, we develop more general representations that are more customizable to particular tasks. These are based on the notion of information spaces (which we call I-spaces) from game theory (von Neumann, Morgenstern, 1944) and control theory (Basar, Olsder, 1982). For an introduction to I-spaces, see Chapter 11 of my Planning Algorithms book or the "Minimalism in Robotics" tutorial on my tutorials page.

We have worked on this problem for over two decades. One key outcome is the introduction a new category of sensor fusion methods called combinatorial filters (or combinatorial sensor fusion). These are largely based on sets and functions, and are thus more general than Bayesian representations, which require measure-theoretic foundations, prior distributions, and many more modeling assumptions. Because they are simpler, combinatorial filters provide insight into how to develop simpler, more reliable robot systems. Furthermore, they often reduce the computational costs because they have less information to maintain. The methods directly address uncertainty that arises from the many-to-one mappings of states to sensor outputs, rather than focus on sensor noise (but both can be handled together). This carefully avoids many modeling burdens that are not absolutely necessary to the problem at hand. An overview of these concepts is provided by my (relatively short) book Sensing and Filtering.

Some highlights of the papers below are:



Papers on Sensor Fusion

Sensor lattices: Structures for comparing information feedback. S. M. LaValle. In IEEE International Workshop on Robot Motion and Control, 2019. [pdf].

Head tracking for the Oculus Rift. S. M. LaValle, A. Yershova, M. Katsev, and M. Antonov. In IEEE International Conference on Robotics and Automation, 2014. [pdf].

Combinatorial filters: Sensor beams, obstacles, and possible paths. B. Tovar, F. Cohen, L. Bobadilla, J. Czarnowski, and S. M. LaValle. ACM Transactions on Sensor Networks, 10(3), 2014. [pdf].

Counting moving bodies using sparse sensor beams. L. E. Erickson, J. Yu, Y. Huang, and S. M. LaValle. IEEE Transactions on Automation Science and Engineering, 10(4):853-861, 2014. [pdf].

Exploration of an unknown environment with a differential drive disc robot. G. Laguna, R. Murrieta-Cid, H. M. Becerra, R. Lopez-Padilla, and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2014. [pdf].

Planning under topological constraints using beam-graphs. V. Narayanan, P. Vernaza, M. Likhachev, and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2013. [pdf].

Sensing and Filtering: A Fresh Perspective Based on Preimages and Information Spaces. S. M. LaValle. volume 1:4 of Foundations and Trends in Robotics Series. Now Publishers, Delft, The Netherlands, 2012. [pdf].

Counting moving bodies using sparse sensor beams. L. Erickson, J. Yu, Y. Huang, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf].

Optimal gap navigation for a disc robot. R. Lopez-Padilla, R. Murrieta-Cid, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf].

Controlling wild bodies using discrete transition systems. L. Bobadilla, O. Sanchez, J. Czarnowski, K. Gossman, and S. M. LaValle. 2012. Unpublished manuscript, [pdf].

Shadow information spaces: Combinatorial filters for tracking targets. J. Yu and S. M. LaValle. IEEE Transactions on Robotics, 28(2):440-456, 2012. [pdf].

Story validation and approximate path inference with a sparse network of heterogeneous sensors. J. Yu and S. M. LaValle. In IEEE International Conference on Robotics and Automation, 2011. [pdf].

Minimalist multiple target tracking using directional sensor beams. L. Bobadilla, O. Sanchez, J. Czarnowski, and S. M. LaValle. In Proceedings IEEE International Conference on Intelligent Robots and Systems, 2011. [pdf].

Sensor lattices: A preimage-based approach to comparing sensors. S. M. LaValle. September 2011. Department of Computer Science, University of Illinois, [pdf].

Mapping and pursuit-evasion strategies for a simple wall-following robot. M. Katsev, A. Yershova, B. Tovar, R. Ghrist, and S. M. LaValle. IEEE Transactions on Robotics, 27(1):113-128, 2011. [pdf].

Cyber detectives: Determining when robots or people misbehave. J. Yu and S. M. LaValle. In Proceedings Workshop on Algorithmic Foundations of Robotics (WAFR), 2010. [pdf].

Sensor beams, obstacles, and possible paths. B. Tovar, F. Cohen, and S. M. LaValle. In G. Chirikjian, H. Choset, M. Morales, and T. Murphey, editors, Algorithmic Foundations of Robotics, VIII. Springer-Verlag, Berlin, 2009. [pdf].

Distance-optimal navigation in an unknown environment without sensing distances. B. Tovar, R Murrieta-Cid, and S. M. LaValle. IEEE Transactions on Robotics, 23(3):506-518, June 2007. [pdf].