An Efficient Beam Search Algorithm for Active Perception in Mobile Robotics

Kaixian Qu, Han Wang, Victor Klemm, Cesar Cadena, Marco Hutter
Robotic Systems Lab, ETH Zurich
Accepted to The International Journal of Robotics Research (IJRR)
Paper arXiv Video Code

Our method enables efficient active perception across diverse scenarios.

Hardware Experiment Videos

Real Robot
Planner Visualization

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 (TSP) over heuristically selected informative nodes, or adopt a more efficient but overly constrained shortest path tree (SPT) 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 all 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.

Problem Formulation

We formulate active perception as a budget-constrained path optimization on a directed graph $\mathcal{G} = (\mathcal{V}, \mathcal{E}, g, c)$ with vertex gains $g(v) \geq 0$ and positive edge costs $c(e) > 0$. The objective is to find a path $p^*$ starting from $v_s$ that maximizes the accumulated gain under a cost budget:

$$p^* = \arg\max_{p \in \mathcal{P}} \; g(p) \quad \text{subject to} \quad c(p) \leq C$$

where $g(p)$ aggregates gains over the set of unique vertices visited and $c(p)$ sums edge costs along the path. We study this problem under three progressively more realistic settings:

  1. Graph a priori. The graph is fully known in advance. No need to explore.
  2. Graph online perception. The graph exists but is discovered incrementally through local sensing. Need to balance exploitation of known high-gain regions with exploration of the unknown.
  3. Active perception. No graph is given. The robot operates in continuous 3D space and must autonomously construct a graph within the discovered collision-free space $\mathcal{X}_{\mathrm{free}}$ while simultaneously planning to maximize a task-dependent objective.

(i) Full graph known; optimal path drawn

(ii) Nodes discovered as robot moves

(iii) Graph built from free space

Method Overview

Expected Gain

A path selection criterion that balances exploration and exploitation using frontier information.

Node-wise Beam Search

Maintains the top-B candidate paths per node, delivering strong performance even at low beam width.

RRAG

An incrementally built graph with full orientation sampling and strong connectivity in cluttered environments.

Expected Gain: Balancing Exploration and Exploitation

The choice of selection criterion determines how candidate paths are ranked. We consider three criteria:

  • Path Gain — uses accumulated gain directly, $q(p)=g(p)$. Provides no incentive to explore unknown regions.
  • Path Ratio — ranks paths by gain per cost, $q(p)=g(p)/c(p)$, implicitly assuming the same ratio can be sustained over the remaining budget.
  • Expected Gain (ours) — defines $q(p)=g_e(p)$: frontier paths extrapolate the ratio $g(p)/c(p)$ over the full budget, while non-frontier paths use $g(p)$. This balances exploration and exploitation.

Drag the budget slider and switch between criteria to see which path each method selects

Known region Unknown territory ? ? ? c=1 c=1 c=1 v₀ Start v₁ g=4 v₂ g=2 v₃ g=3 Non-frontier node Frontier node Selected path
123456
Path g(p) c(p) Score q(p)

Node-wise Beam Search (NBS)

Motivation. The standard beam search — depth-wise beam search (DBS) — retains the top $B$ paths globally at each search depth. This makes it prone to local optima: once the beam converges on the same high-gain region, all $B$ paths can terminate at the same node. Performance is also sensitive to the choice of $B$.

Key idea. NBS instead maintains the top $B$ paths per node. This guarantees at least one promising path at every visited node, encouraging broader exploration of the graph and making NBS robust even at $B=1$. Its time complexity is $O(|\mathcal{E}|\,D\,B\,(D + \log B))$ and its space complexity is $O(|\mathcal{V}|\,D\,B)$.

Algorithm: Node-wise Beam Search (NBS)
Input: Graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$, start node $v_s$, cost budget $C$
Parameters: beam width $B$, search depth $D$, path quality function $q$
Initialize best path $p^* \leftarrow (v_s)$, per-node beam $\textbf{open}[v_s] \leftarrow \{(v_s)\}$
for depth $d = 1$ to $D$ do
Initialize empty per-node heap $\textbf{heap}$
for each node $v \in \mathcal{V}$ do
for each path $p \in \textbf{open}[v]$ do
for each outgoing edge $(v, v')$ not already traversed in $p$ do
Extend: $p' \leftarrow p + (v, v')$
if $c(p') > C$: skip (budget exceeded)
if $q(p') > q(p^*)$: update $p^* \leftarrow p'$
Insert $p'$ into $\textbf{heap}[v']$, keeping only top-$B$ paths per node
$\textbf{open} \leftarrow \textbf{heap}$
return $p^*$

Rapidly-Exploring Random Annulus Graph (RRAG)

RRAG is an incrementally built graph for active perception, inspired by the Rapidly-exploring Random Graph (RRG). It enforces two spacing rules that give it an annulus structure:

  • Minimum distance $l_{\min}$: a new node is accepted only if it is farther than $l_{\min}$ from all nodes, preventing oversampling.
  • Maximum distance $l_{\max}$: edges are formed only between nodes within distance $l_{\max}$, bounding the out-degree.

Key properties:

  • Full orientation preservation. Unlike prior methods that keep only one orientation per position, RRAG retains all discrete orientations as distinct nodes within a node cluster, enabling richer path optimization.
  • Fallback local planner. In narrow or cluttered environments where straight-line connections fail, a local sampling-based planner based on RRT* finds collision-free paths, ensuring graph connectivity.
  • Guaranteed connectivity. We prove that the annulus graph is connected whenever $l_{\max} \geq 2\,l_{\min}$, provided the nodes satisfy packing and covering conditions.

Results

Benchmarking on Graphs

Before deploying in active perception, we benchmark all algorithms on abstract graphs in two progressively harder settings: graph a priori and graph online perception. We evaluate clustered and scattered gain distributions at two graph scales (25 × 25 m and 50 × 50 m), across all combinations of selection criteria and replanning strategies.

NBS (ours) DBS SPT TSP
Computation time Medium Low–Med. Low Med.–High
Gain Highest High Medium Low
Parameter sensitivity Low High Low High
Path selection sensitivity Low High High N/A
Summary of algorithm performance across graph benchmarking experiments. Best Good Poor

Key takeaways. In both settings, NBS achieves the highest gains with minimal sensitivity to beam width or path selection — even $B=1$ delivers strong results. In the online perception setting, the expected gain criterion outperforms path gain and path ratio by explicitly rewarding exploration of frontier regions. This criterion is adopted for all following active perception experiments.

Active Perception Performance

NBS achieves the highest normalized performance across all three representative active perception tasks: point collection (0.50), surface reconstruction (0.49), and volumetric exploration (0.77). It outperforms state-of-the-art methods by at least 20% in one or more tasks. NBS is particularly strong in point collection, where the sparse gain distribution causes other methods to get trapped in local optima.

Surface Reconstruction Comparison

Surface reconstruction comparison

Qualitative comparison of surface reconstruction quality across planners. NBS achieves the most complete coverage (445.73 m²).

Hardware Experiments

We validate our approach on the ANYmal quadruped robot equipped with a ZED X Mini camera, running the full planning and perception pipeline onboard. Experiments span autonomous surface reconstruction in indoor/outdoor environments and volumetric exploration in a cafeteria and lab. See the hardware experiment videos for qualitative results across all scenarios.

BibTeX

@article{qu2026efficient,
  title     = {An Efficient Beam Search Algorithm for Active Perception in Mobile Robotics},
  author    = {Qu, Kaixian and Wang, Han and Klemm, Victor and Cadena, Cesar and Hutter, Marco},
  journal   = {The International Journal of Robotics Research},
  year      = {2026}
}

Acknowledgements

This research was supported by the Swiss National Science Foundation through the National Centre of Competence in Digital Fabrication (NCCR dfab), by Huawei Tech R&D (UK) through a research funding agreement, and by an ETH RobotX research grant funded through the ETH Zurich Foundation.