Master Thesis: An Efficient Beam Search Algorithm for Active Perception in Mobile Robotics

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. Website for more demonstrations

Decision Making and Motion Planning Research Intern, Qcraft

Description: During the internship, I independently designed and deployed an A*-based motion search algorithm to accelerate the Initializer stage of the autonomous driving planner. The previous search method, based on Dynamic Programming, frequently suffered from high latency and computation timeouts in complex scenarios. To address this limitation, I proposed a new A* search framework inspired by a neural planner to guide the search expansion. I was responsible for the entire development cycle, including proposal design, algorithm derivation, system refactoring, debugging visualization, and benchmarking. The new searcher generates high-quality feasible trajectories in significantly shorter time without sacrificing performance. In large-scale simulations for L4 systems, the passing rate improved by 0.38%, the number of Initializer timeouts was reduced by 77%, and the average computation time on hardware platforms decreased by 34%, after which the module was successfully deployed. To further adapt the method for L2 deployment, I redesigned the heuristic function using reference lines and reference speed tables and introduced caching mechanisms to accelerate repeated searches. While maintaining nearly unchanged performance, the optimized system reduced Initializer timeouts by 96%, lowered its average computation time by 70.42%, and reduced the overall planner latency by 41.59%. In addition, I improved leading group selection and leading cost computation to better handle lane-change interactions, and contributed to internal simulation dashboards and evaluation tools to enhance development efficiency and testing coverage.

Improvement on Computation

Semester Project: Temporal Sampling-Based Algorithm for Motion Planning in Dynamic Environments

Abstract: Sampling-based motion planning has become highly popular in industry and academia, due to its flexibility and ability to deal with high dimensional planning. Despite the introduction of a great number of algorithms, most of these focus on either motion planning in dynamic environments for holonomic robots, or handling differential constraints in static environments. In this work, we present Temporal RRT*, an incremental sampling-based approach for motion planning able to avoid moving obstacles, which can further extend to the planning for nonholonomic robots. The proposed approach extends RRT* by adding the time dimension in the tree, encoding each vertex the time-to-arrive and the collision-free time intervals. In addition, We present its successful extension to nonholonomic planning in two different robots, dubins cars and quadrotors. A series of experiments demonstrates that our planner generates more efficient paths, outperforming other state-of-the-art sampling based planners. Furthermore, we show that our algorithm is able to perform real-time planning in simulation. Project Report