Distributed Hierarchical Control for State Estimation With Robotic Sensor Networks

Charles Freundlich, Yan Zhang, Michael M. Zavlanos

TL;DR

This paper introduces a novel hierarchical approach for distributed state estimation using a team of robotic sensors. By clustering states and using a decentralized assignment algorithm, it enables efficient and scalable active sensing for large numbers of targets, outperforming existing methods in simulations and real-world experiments.

What Problem Does This Paper Address?

Estimating the state of multiple, spatially distributed targets (e.g., locations of objects) using a team of mobile robots is a challenging problem. Traditional methods often struggle with scalability due to the combinatorial explosion of possibilities when planning sensor trajectories for many targets and robots. This paper tackles the issue of efficiently coordinating a team of robots to gather information that minimizes estimation uncertainty, especially when dealing with a large number of targets and limited computational resources. The core challenge is to devise a strategy that is both optimal at a local level and scalable to a multi-robot, multi-target scenario.

Methods

The paper proposes a hierarchical Dynamic Programming (DP) framework. The key ideas are:

  • Clustering States: Instead of planning for each individual state (target) across the entire team, the states are first grouped into moderately sized clusters based on their prior geographic locations.
  • Local DP for Clusters: For each cluster, a local DP is formulated to compute optimal sensing policies. This involves discretizing the "covariance space" (representing the uncertainty in state estimation) into a finite set. This discretization is crucial for making the problem tractable.
  • Decentralized Assignment Algorithm: Once optimal policies for each cluster are computed offline, a decentralized auction mechanism is used to dynamically assign these clusters to individual robots in real-time. This allows robots to coordinate and decide which cluster to sense next, resolving conflicts through bidding.
  • Hybrid Controller: A controller is developed that manages robot states (busy, transit, done) and synchronizes navigation (moving and sensing) with coordination (auctioning and planning).

This hierarchical approach decomposes the complex global problem into smaller, manageable subproblems, making it computationally feasible.

Datasets

The paper does not explicitly mention or introduce new datasets for training. Instead, it relies on:

  • Simulated Data: Generated for various scenarios, including single target localization and multi-robot multi-target localization.
  • Real-World Experiments: Conducted using a team of two iRobot Creates robots equipped with stereo vision rigs. The targets were colored ping pong balls in a controlled workspace. Ground truth locations were provided by an OptiTrack motion capture system.

Key Insights and Ideas

  • Hierarchical Decomposition is Key to Scalability: The core insight is that breaking down the problem into clusters and then assigning these clusters to robots is essential for handling a large number of targets and robots, a significant limitation of previous methods.
  • Covariance Space Discretization: Effectively discretizing the space of uncertainty (covariance matrices) is critical for making the local DP tractable while still capturing important aspects of the estimation uncertainty.
  • Decentralized Auction for Dynamic Task Allocation: A distributed auction mechanism provides a robust and scalable way for robots to negotiate and acquire sensing tasks in real-time, adapting to changing conditions and other robots' actions.
  • Balancing Exploration and Exploitation: The framework implicitly balances exploring different sensing strategies within a cluster (to reduce uncertainty) and exploiting the best available policies for task assignment.
  • Real-World Validation: Demonstrating the approach on physical robots with stereo vision highlights its practical applicability beyond simulations.

Key Results

  • Scalability: The proposed method scales well to large numbers of states and robot sensors, a significant improvement over existing approaches.
  • Optimality at Cluster Level: The framework achieves optimality at the cluster level, meaning the sensing policies within each cluster are optimal.
  • Performance in Simulations: Simulations showed that the hierarchical DP approach performed comparably to or better than a state-of-the-art algorithm (ε-δRVI) in terms of observation requirements for landmark localization.
  • Real-World Performance: Experiments with two robots localizing eight ping pong balls demonstrated the effectiveness of the distributed auction and hierarchical control in a practical setting. The system successfully coordinated robots and achieved accurate localization.
  • Heuristic Comparison: In single-target localization, the proposed optimal local controller significantly outperformed heuristic policies like "closer," "circle," "static," and "random," achieving 115% of the reward of the "closer" and "random" policies.

Limitations and Future Work

  • Computational Complexity: While improved, the approach is still exponential in the number of hidden states per cluster. The effectiveness relies on keeping cluster sizes moderate.
  • Clustering Strategy: The paper notes that the clustering strategy is a design choice and can be effectively generated using prior information. However, more sophisticated adaptive clustering could be explored.
  • Exploration: The current approach focuses on non-myopic sensing (exploiting prior knowledge). Incorporating explicit exploration strategies to discover new features could be a future direction.
  • 3D Implementation: While the paper discusses 3D covariance matrices, the planning is primarily designed for 2D. Extending the planning to full 3D without significant computational overhead would be valuable.
  • Unmodeled Noise: The paper acknowledges that real-world noise is seldom perfectly Gaussian and that the data-driven noise model is an approximation. Future work could explore more robust noise modeling.

Summary updated

Abstract

This paper addresses active state estimation with a team of robotic sensors. The states to be estimated are represented by spatially distributed, uncorrelated, stationary vectors. Given a prior belief on the geographic locations of the states, we cluster the states in moderately sized groups and propose a new hierarchical dynamic programming framework to compute optimal sensing policies for each cluster that mitigates the computational cost of planning optimal policies in the combined belief space. Then, we develop a decentralized assignment algorithm that dynamically allocates clusters to robots based on the precomputed optimal policies at each cluster. The integrated distributed state estimation framework is optimal at the cluster level but also scales very well to large numbers of states and robot sensors. We demonstrate efficiency of the proposed method in both simulations and real-world experiments using stereoscopic vision sensors.
BibTeX
@article{freundlich2018distributed,
  author = {Charles Freundlich and Yan Zhang and Michael M. Zavlanos},
  title = {{Distributed Hierarchical Control for State Estimation With Robotic Sensor Networks}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2018},
  url = {https://openreview.net/forum?id=HPu_tUSWcE},
}
Figure