Act, Perceive, and Plan in Belief Space for Robot Localization

Michele Colledanchise, Damiano Malafronte, Lorenzo Natale

Abstract

In this paper, we outline an interleaved acting and planning technique to rapidly reduce the uncertainty of the estimated robot's pose by perceiving relevant information from the environment, as recognizing an object or asking someone for a direction. Generally, existing localization approaches rely on low-level geometric features such as points, lines, and planes, while these approaches provide the desired accuracy, they may require time to converge, especially with incorrect initial guesses. In our approach, a task planner computes a sequence of action and perception tasks to actively obtain relevant information from the robot's perception system. We validate our approach in large state spaces, to show how the approach scales, and in real environments, to show the applicability of our method on real robots. We prove that our approach is sound, probabilistically complete, and tractable in practical cases.

Introduction

Most robot localization and SLAM (Simultaneous Localization and Mapping) systems are "passive." They rely on low-level geometric features and wait for the robot's natural movement to provide enough data to converge on a position. This approach struggles in ambiguous environments, such as symmetrical hallways, or when the robot has no initial knowledge of its location (the "kidnapped robot" problem).

While Partially Observable Markov Decision Processes (POMDPs) offer a mathematical standard for planning under uncertainty, they are computationally expensive. This paper introduces an active localization framework that allows robots to "plan to learn" about their environment by planning in belief space—the space of probability distributions over possible locations—using an entropy-based heuristic to rapidly collapse uncertainty.

Methods

The core of the framework is an interleaved acting and planning process. Instead of executing a static path, the robot plans, acts, observes, and updates its internal "belief" map.

Belief Space Planning

In physical space, a robot's action (like moving "Right") might have multiple non-deterministic outcomes due to sensor noise or wheel slip. In belief space, this is represented as a single deterministic transition from one probability distribution to another. This conceptual shift makes the search tree for a planner much cleaner and more manageable.

Comparison of transitions in physical space (left) versus belief space (right).

Active Perception and Heuristics

The robot uses an entropy-based heuristic to guide its search. Entropy measures uncertainty; by favoring paths that lead to low-entropy states, the planner targets actions that provide the most information. To facilitate high-level reasoning, the system uses semantic-annotated maps. Rather than just seeing geometric points, the robot recognizes objects (e.g., chairs, plants) using a YOLO-based vision system.

An example of belief state transitions using 'Look' and 'Right' actions to resolve location uncertainty based on whether a window (W) is seen.

As shown in the figure above, the robot can decide to "Look" for a landmark. Depending on whether the landmark is seen or not, the belief state is updated, potentially localizing the robot much faster than random movement would.

Key Results

The approach was validated through simulations and real-world tests with an IIT-R1 humanoid robot.

  • Efficiency: In simulations with $10^3$ states, the proposed planner found solutions in 0.71 seconds, nearly 20 times faster than standard uniform-cost search (13.85 seconds).
  • Symmetry Breaking: In a real-world kitchen experiment, the robot successfully identified its location in a symmetrical room by planning a move specifically to check for a potted plant that would distinguish one corner from another.
  • Computational Tractability: The system demonstrated that subsequent replanning steps are significantly faster (e.g., dropping from 0.05s to 0.008s) because it leverages previously explored belief states stored in memory.

Conclusion

This research demonstrates that active planning in belief space is a sound and tractable way to handle robot localization. By treating perception as an intentional action rather than a passive byproduct of movement, robots can navigate complex, ambiguous environments more efficiently. Future work will focus on increasing the resolution of the grid maps and extending the framework to handle dynamic environments with moving objects or people.

Summary updated

Abstract

In this paper, we outline an interleaved acting and planning technique to rapidly reduce the uncertainty of the estimated robot's pose by perceiving relevant information from the environment, as recognizing an object or asking someone for a direction. Generally, existing localization approaches rely on low-level geometric features such as points, lines, and planes, while these approaches provide the desired accuracy, they may require time to converge, especially with incorrect initial guesses. In our approach, a task planner computes a sequence of action and perception tasks to actively obtain relevant information from the robot's perception system. We validate our approach in large state spaces, to show how the approach scales, and in real environments, to show the applicability of our method on real robots. We prove that our approach is sound, probabilistically complete, and tractable in practical cases.
BibTeX
@inproceedings{colledanchise2020act,
  author = {Michele Colledanchise and Damiano Malafronte and Lorenzo Natale},
  title = {{Act, Perceive, and Plan in Belief Space for Robot Localization}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2020},
  url = {https://openreview.net/forum?id=YvvblXYl0K},
}
Figure