Combinatorial Filters: Handling Sensing Uncertainty by Avoiding Big Models

Steven M. LaValle, University of Illinois

Over the past several years, Bayesian filtering techniques have become mainstream tools in robotics research that handles uncertainty. Variations include the classical Kalman filter and recent particle filters, all of which are routinely used for robot localization, navigation, and map building. In this talk, I will introduce a new class of filters, called combinatorial filters, that are distinctive in several ways: 1) they simplify modeling burdens by avoiding probabilities, 2) they are designed for processing information from the weakest sensors possible, and 3) they avoid unnecessary state estimation. In many ways, they are the direct analog to Bayesian filters, but handle substantial amounts of uncertainty by refusing to model it. The emphasis is on detecting and maintaining tiny pieces of information that are critical to solving robotic tasks, such as navigation, map building, target tracking, and pursuit-evasion.

Speaker Biography

Steve LaValle is Professor of Computer Science in the Department of Computer Science at the University of Illinois. He received his Ph.D. in Electrical Engineering from the University of Illinois in 1995. From 1995-1997 he was a postdoctoral researcher and lecturer in the Department of Computer Science at Stanford University. From 1997-2001 he was an Assistant Professor in the Department of Computer Science at Iowa State University. His research interests include robotics, sensing, cyber-physical systems, planning algorithms, computational geometry, and control theory. He authored the book Planning Algorithms, Cambridge University Press, 2006 (which is available on line at