A Theory of Uncertainty Variables for State Estimation and Inference

Rajat Talak, Sertac Karaman, Eytan H. Modiano

Introduction

In fields such as robotics and signal processing, uncertainty is traditionally modeled using probability theory and random variables. While powerful, this approach often encounters two significant challenges: computational intractability and the reliance on arbitrary assumptions. Calculating full posterior distributions or Maximum A Posteriori (MAP) estimates can be prohibitively difficult in practice, leading engineers to assume additive Gaussian noise for mathematical convenience, even when physical noise is bounded or non-linear.

This paper proposes a mathematically rigorous alternative: Uncertainty Variables (UVs). By replacing probability measures with uncertainty sets, the authors develop a complete theory of inference that bridges the gap between robust optimization and traditional probability theory.

The Uncertainty Variable Framework

The core of this framework is the Uncertainty Variable, defined not by a distribution, but by an uncertainty set—a region where the realization of the variable is guaranteed to lie. Unlike random variables, UVs focus on the boundaries of possibility rather than the density of probability.

Illustrative examples of Uncertainty Variables (UVs): (a) spatial uncertainty in robotics, (b) disjoint uncertainty sets in a tunnel environment, and (c) uncertainty over parameters for a sequence of binary events.

The authors derive fundamental laws for UVs that mirror those of probability theory:

  • Law of Projections: The set-based equivalent of the Law of Total Probability.
  • Bayes’ Law for UVs: A method for updating uncertainty sets based on new observations.
  • Conditional Uncertainty Maps: Functions that link the realization of one variable to a set of possible realizations of another.

Bayesian Uncertainty Networks (BUNs)

To handle complex dependencies, the authors extend Bayesian Networks to the set-based domain through Bayesian Uncertainty Networks (BUNs). Crucially, they prove that structural properties like d-separation hold for BUNs exactly as they do for traditional random variables. This means that local independence properties defined by a graph are equivalent to global independence properties, allowing researchers to leverage existing algorithmic techniques for efficient inference in this new framework.

Key Insights and Point Estimation

A major contribution of this work is demonstrating that a rigorous logic of inference does not strictly require probability measures. The "triangulation principle"—intersecting sets to estimate a state—is shown to be a specific case of a Naive Bayes model within the UV framework.

A bounded uncertainty set in a 2D state space, representing a region of guaranteed realization.

Furthermore, the authors establish a deep connection to classical methods through the Canonical UV. If an uncertainty set is defined based on the log-likelihood of a probability distribution, the resulting UV point estimate becomes mathematically identical to a MAP estimate. This allows point estimation in a BUN to be framed as a convex optimization problem, which is often more computationally tractable than high-dimensional integration.

Conclusion and Future Work

The theory of Uncertainty Variables provides a solid theoretical foundation for state estimation under bounded noise. While the choice of representation functions for sets remains a topic for further study, the framework successfully recovers and generalizes existing heuristic methods in robotics. Future work will focus on benchmarking the computational performance of these optimization-based methods against traditional filters and applying the theory to complex motion planning and perception tasks.

Summary updated

BibTeX
@inproceedings{talak2019theory,
  author = {Rajat Talak and Sertac Karaman and Eytan H. Modiano},
  title = {{A Theory of Uncertainty Variables for State Estimation and Inference}},
  booktitle = {Allerton},
  year = {2019},
  doi = {10.1109/allerton.2019.8919919},
}
Figure