Integrating Human-Provided Information Into Belief State Representation Using Dynamic Factorization

Rohan Chitnis, Leslie Pack Kaelbling, Tomás Lozano-Pérez

Abstract

Robots operating in complex, real-world environments must synthesize their own sensor observations with high-level information provided by humans. Maintaining an accurate "belief state"—a probability distribution over possible world configurations—is computationally challenging as the state space grows exponentially with the number of objects. We propose Dynamic Factorization, a novel approach that allows a robot to fluidly group and ungroup related objects in its internal model. By dynamically joining variables into joint factors upon receiving constraints and splitting them when independence is restored, our method enables efficient reasoning over complex human advice. Experimental results in simulated cooking environments demonstrate that Dynamic Factorization significantly outperforms static baselines in both success rate and inference speed.

Introduction

In robotics, a belief state represents the robot's best estimate of the world's current state given incomplete and noisy information. Traditional approaches often utilize "factored" beliefs, assuming independence between objects to maintain computational tractability. For instance, the location of a set of keys is typically treated as independent of the location of a wallet.

However, human advice—such as "the keys are near the wallet"—introduces dependencies that break these independence assumptions. Standard systems face a dilemma: they either ignore these correlations, leading to inaccuracies, or they attempt to model the full joint distribution, which becomes prohibitively slow as the number of objects increases. This challenge is exacerbated in "open domains" where the robot may discover new objects over time.

Dynamic Factorization

The core of our approach is a belief state that adapts its structure in real-time based on incoming information.

Dynamic Joining and Factor Graph Construction

When a robot receives a constraint linking multiple variables (e.g., a human assertion about object proximity), it merges these variables into a single "joint factor." This process is illustrated in the evolution of the robot's internal factor graph.

Evolution of the factor graph as new human assertions are received.

As shown in Figure 2, assertions about object colors or relative locations trigger the creation of new factors or the merging of existing ones. This allows the robot to calculate the joint probability distribution for specific, related groups of objects without needing to model the entire world jointly.

Impact on Probability Distributions

The impact of a joining operation on the probability distribution is significant. When information like "NextTo(location(object1), location(object2))" is received, the robot transitions from maintaining independent marginals for each object to a joint distribution that captures the new dependency.

Transition from independent marginal distributions (Belief B) to a joint distribution (Belief B') after receiving a spatial constraint.

Complexity Management and Splitting

To prevent the model from becoming overly complex, we implement two key mechanisms:

  1. The "Too Big" Safety Valve: If joining variables would result in a factor exceeding computational limits, the information is stored "lazily" in a ComplexFluents database, accessed only during state sampling.
  2. Dynamic Splitting: The robot periodically evaluates whether grouped variables have become independent (e.g., after a direct observation). Using Jensen-Shannon (JS) divergence to measure reconstruction error, the robot splits factors if the loss in accuracy is below a threshold $\epsilon$.

Experimental Results

We evaluated Dynamic Factorization in simulated 2D and 3D cooking environments. In a 5x5 gridworld with 10 ingredients, our method achieved a 99% success rate, compared to just 5% for a static baseline within the same time constraints. Furthermore, the dynamic approach was 100x to 200x faster at answering queries, maintaining high performance even as the number of objects scaled.

Conclusion and Future Work

Dynamic Factorization provides a flexible framework for integrating human knowledge into robotic belief states. By treating the factor structure as a fluid entity, robots can maintain efficiency without sacrificing the ability to reason about complex relationships. Future work will explore "approximately folding" complex constraints to reduce eager computation costs and incorporating pragmatic reasoning to better interpret the intent behind human communication.

Summary updated

Abstract

In partially observed environments, it can be useful for a human to provide the robot with declarative information that represents probabilistic relational constraints on properties of objects in the world, augmenting the robot's sensory observations. For instance, a robot tasked with a search-and-rescue mission may be informed by the human that two victims are probably in the same room. An important question arises: how should we represent the robot's internal knowledge so that this information is correctly processed and combined with raw sensory information? In this paper, we provide an efficient belief state representation that dynamically selects an appropriate factoring, combining aspects of the belief when they are correlated through information and separating them when they are not. This strategy works in open domains, in which the set of possible objects is not known in advance, and provides significant improvements in inference time over a static factoring, leading to more efficient planning for complex partially observed tasks. We validate our approach experimentally in two open-domain planning problems: a 2D discrete gridworld task and a 3D continuous cooking task. A supplementary video can be found at http://tinyurl.com/chitnis-iros-18.
BibTeX
@inproceedings{chitnis2018integrating,
  author = {Rohan Chitnis and Leslie Pack Kaelbling and Tomás Lozano-Pérez},
  title = {{Integrating Human-Provided Information Into Belief State Representation Using Dynamic Factorization}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=qX-zrZPwWcfy},
}
Figure