An Efficient Beam Search Algorithm for Active Perception in Mobile Robotics

Kaixian Qu, Han Wang, Victor Klemm, Cesar Cadena, Marco HutterarXiv 2026 · DOI · arXiv

TL;DR

This paper introduces Node-wise Beam Search (NBS), a highly robust path-planning algorithm that prevents robots from getting stuck in local optima during active perception tasks. Combined with a novel incremental graph structure called the Rapidly-exploring Random Annulus Graph (RRAG), this approach allows mobile robots to efficiently map unknown environments in real-time, outperforming existing state-of-the-art methods by over 20%.

What Problem Does This Paper Address?

When an autonomous robot enters an unfamiliar environment, it faces a fundamental dilemma: it must decide where to move and what to sense to gather the most useful information while respecting constraints like battery life or time. This challenge is known as Informative Path Planning (IPP).

IPP is notoriously difficult (NP-hard). Existing solutions typically fall into two flawed categories:

  1. TSP-based approaches: They select interesting viewpoints first and then use a Traveling Salesman Problem solver to route between them. This decouples path optimization from node selection, leading to slow computations and suboptimal paths.
  2. Tree-based approaches (like Shortest Path Trees): These are fast but overly restrictive, allowing only a single path to each location and forcing the robot into awkward maneuvers to turn around.

Standard depth-wise beam search (DBS) offers a middle ground by keeping the top-$B$ paths at each step. However, it suffers from "beam collapse"—where all top paths converge onto the same local hotspot, blinding the robot to better long-term exploration opportunities elsewhere.

Methods

The authors tackle these limitations with three core contributions:

  1. Node-wise Beam Search (NBS): Instead of keeping the top $B$ paths globally at each search depth, NBS maintains the top $B$ candidate paths per node. This simple but powerful twist ensures that promising paths spread across different regions of the graph are preserved, maintaining search diversity.
  2. Expected Gain Metric: To better balance exploration and exploitation, the authors introduce a new path selection criterion. For paths ending at a "frontier" (the boundary of known space), it extrapolates potential future gains based on the current gain-to-cost ratio, naturally incentivizing the robot to venture into unknown territory.
Illustration of path selection criteria comparing path gain, path ratio, and the proposed expected gain.
  1. Rapidly-exploring Random Annulus Graph (RRAG): An incremental graph construction method tailored for active perception. Unlike previous methods that store only one orientation per position, RRAG preserves multiple discrete orientations. It also incorporates a Fallback Local Planner (FLS) based on RRT* to ensure the robot can navigate tight, cluttered spaces where straight-line connections fail.

Datasets

The framework was evaluated in simulation using the Habitat Synthetic Scenes Dataset (HSSD) across eight distinct, highly detailed 3D indoor environments. The algorithms were benchmarked across three representative active perception tasks: point collection, surface reconstruction, and volumetric exploration.

Key Insights and Ideas

  • Defeating Beam Collapse: By tracking the best paths per node rather than globally, NBS acts as an excellent diversity preserver. Even with a minimal beam width of $B=1$, it remains remarkably robust and computationally lightweight.
  • The Frontier Extrapolation Shortcut: The authors mathematically prove (Theorem 1) that extrapolating frontier path gains using individual path ratios yields the exact same optimal path selection as computing a global maximum ratio. This insight drastically cuts down computational overhead during planning.
  • Orientation Matters: Retaining multiple yaw angles at a single spatial position prevents the typical pitfall of tree-based planners: executing awkward, energy-wasting back-and-forth maneuvers just to turn the robot's camera around.

Key Results

  • 20%+ Performance Leap: In simulated HSSD environments, NBS combined with RRAG achieved the highest performance across all three tasks, outperforming state-of-the-art methods like FUEL, RRT*, and traditional TSP-based planners by at least 20% in one or more scenarios.
  • Point Collection Dominance: In the challenging point collection task, NBS surpassed the second-best algorithm by 16% in normalized gain.
  • Real-World Deployment: The entire pipeline was successfully validated on a physical ANYmal quadruped robot, running completely onboard in real-time across diverse environments like labs, an engine museum, and an outdoor space.
The planning pipeline and surface reconstruction task validated on the ANYmal quadruped robot.

Limitations and Future Work

  • Lack of Formal Proof: While empirically superior, the paper does not provide a formal mathematical proof of global optimality for the NBS algorithm.
  • Semantic Blindness: The current framework is entirely semantic-agnostic. It treats all unknown space equally rather than prioritizing high-value semantic targets (e.g., searching for a specific object based on language instructions).
  • Voxel Independence Assumption: To maintain real-time performance, the volumetric and surface reconstruction tasks assume additive node-wise gains, ignoring complex inter-node visibility correlations (which would require expensive per-voxel tracking to avoid double-counting).
  • Mapping Paradigms: The implementation currently relies on Euclidean Signed Distance Fields (ESDF). The authors note that extending this to modern representations like 3D Gaussian Splatting is an important next step.

Summary updated

Abstract

Active perception is a fundamental problem in autonomous robotics in which the robot must decide where to move and what to sense in order to obtain the most informative observations for accomplishing its mission. Existing approaches either solve a computationally expensive traveling salesman problem over heuristically selected informative nodes, or adopt a more efficient but overly constrained shortest path tree formulation. To address these limitations, we explore beam search algorithms as scalable alternatives. While the standard beam search provides scalability by preserving the top-B paths at each depth level, it is prone to local optima and exhibits parameter sensitivity. Our first contribution is a node-wise beam search (NBS) algorithm, which maintains top-B candidates per node to enable more effective exploration of the solution space. Systematic benchmarking on graphs shows that NBS consistently outperforms other baselines and maintains strong performance even at low beam widths. As a second contribution, we integrate the concept of frontiers into the path selection criterion, introducing the expected gain metric, which better balances exploration and exploitation compared to existing alternatives. Our third contribution proposes the rapidly-exploring random annulus graph (RRAG), a novel graph construction method that preserves full orientation sampling and ensures connectivity in cluttered environments through a fallback local sampling-based planner. Extensive experiments demonstrate that NBS combined with RRAG achieves the highest performance across all three representative active perception tasks, outperforming state-of-the-art algorithms by at least 20% in one or more tasks. We further validate the approach on real robotic platforms in different scenarios.
BibTeX
@misc{qu2026efficient,
  author = {Kaixian Qu and Han Wang and Victor Klemm and Cesar Cadena and Marco Hutter},
  title = {{An Efficient Beam Search Algorithm for Active Perception in Mobile Robotics}},
  year = {2026},
  eprint = {2604.23327},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2604.23327},
}

Loading related content...

Figure