提出高效路径搜索算法,提升移动机器人主动感知的探索效率。
An Efficient Beam Search Algorithm for Active Perception in Mobile Robotics

- 采用节点级束搜索,每节点保留最优路径,扩大解空间探索
- 引入期望增益指标,更好平衡探索与利用,提升路径质量
- 结合新型图构建方法,实现在复杂环境中的快速可靠导航
主动感知是自主机器人中的核心问题,要求机器人决定移动位置与感知方向以获取最有信息量的观测。现有方法或求解计算开销大的旅行商问题,或采用效率高但约束过强的最短路径树。本文提出节点级束搜索(NBS),在每个节点维护前B条候选路径,提升解空间探索能力;引入期望增益作为路径选择指标,更好平衡探索与利用;提出快速探索随机环形图(RRAG),通过局部采样确保复杂环境中图的连通性。在多个图上的系统性基准测试显示,NBS在低束宽下仍表现优异;结合RRAG在三个典型主动感知任务中均达最优,至少在一个任务上超越当前最优算法20%以上。真实机器人平台验证了方法在多种场景下的有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。