### 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:

- The introduction of
*shadow information spaces*and corresponding combinatorial filters for counting and tracking moving targets (TRO 2012). - The reduction of numerous tracking problems to a simple paradigm of obstacles and partially distinguishable sensor beams (ACM TSM 14). This paper explains the figure above.
- The introduction of
*sensor lattices*for comparing the power of sensors in a sensor fusion system based on the level of ambiguity of each sensor mapping. This is to help in the design of planning and filtering algorithms. (RoMoCo 19) - Head tracking for virtual reality headsets, which is used in the Oculus Rift and many other consumer products (ICRA 14). We also developed a more advanced version, which takes into account human perception, but that is unfortunately patented.

## 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].

**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].

*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].

**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].