RPT*: Global Planning with Probabilistic Terminals for Target Search in Complex Environments

Yunpeng Lyu; Chao Cao; Ji Zhang; Howie Choset; Zhongqiang Ren

cs.ROJan 19, 2026

RPT*: Global Planning with Probabilistic Terminals for Target Search in Complex Environments

Authors: Yunpeng Lyu, Chao Cao, Ji Zhang, Howie Choset, Zhongqiang Ren

Organizations: Global College, Shanghai Jiao Tong University. · Robotics Institute, Carnegie Mellon University.

Abstract

Routing problems such as Hamiltonian Path Problem (HPP), seek a path to visit all the vertices in a graph while minimizing the path cost. This paper studies a variant, HPP with Probabilistic Terminals (HPP-PT), where each vertex has a probability representing the likelihood that the robot's path terminates there, and the objective is to minimize the expected path cost. HPP-PT arises in target object search, where a mobile robot must visit all candidate locations to find an object, and prior knowledge of the object's location is expressed as vertex probabilities. While routing problems have been studied for decades, few of them consider uncertainty as required in this work. The challenge lies not only in optimality ordering the vertices, as in standard HPP, but also in handling history dependency: the expected path cost depends on the order in which vertices were previously visited. This makes many existing methods inefficient or inapplicable. To address the challenge, we propose a search-based approach RPT* with solution optimality guarantees, which leverages dynamic programming in a new state space to bypass the history dependency and novel heuristics to speed up the computation. Building on RPT*, we design a Hierarchical Autonomous Target Search (HATS) system that combines RPT* with either Bayesian filtering for lifelong target search with noisy sensors, or autonomous exploration to find targets in unknown environments. Experiments in both simulation and real robot show that our approach can naturally balance between exploitation and exploration, thereby finding targets more quickly on average than baseline methods.

Figures & tables

Fig. 1: Target search in unknown environments using HPP-PT. (a) shows the scenario of a real robot experiment, including (i) the point cloud map of the environment after finding the target object, where the colored line shows the trajectory of the robot; (ii) a photo of the test space; and (iii) the wheeled robot used in this experiment. (b) shows the top-down view of the environment, where purple dots represent candidate target locations, with marker sizes proportional to their corresponding probabilities of finding the target object there. (c) is the visualization of the generated solution path.

Fig. 2: Visualization of related concepts.

Fig. 3: Heuristic function of our RPT* algorithm: for the remaining $k$ unvisited vertices, the heuristic models the process as $k$ steps, explicitly allowing for repeated visits to vertices.

Fig. 4: Illustration of shortcutting in the proof.

Fig. 5: The architecture and workflow of the Hierarchical planning system for Autonomous Target Search (HATS). HATS iteratively runs the workflow that begins by collecting sensory data and eventually outputs waypoints for execution. When local planning fails, HATS has a feedback loop that calls global planning to update the global path and search in different regions. The two variants HATS-L and HATS-U differ in their global planning.

Fig. 6: Probability calculation for candidate points in the HATS-U. For each candidate point $x$ , we compute (b) the density of unknown space $\phi_{u}(x)$ , (c) the geometric visibility $\phi_{g}(x)$ , and (d) the prior knowledge of object $\phi_{o}(x)$ . These terms are linearly combined and utilized as the vertex probability within an HPP-PT instance.

Fig. 7: Two types of datasets for experiment. (a) is the att48 instance from public TSPLIB dataset: 48 U.S. capital cities. (b) is an example of the synthetic dataset: a randomly generated graph with 10 vertices.

Fig. 8: Average runtime comparison of IP baselines and our RPT*.

Instance	IP Cost	RPT* Cost	RPT* Savings (vs. IP)
gr17	16.1545	16.1473	0.045%
gr21	13.9029	13.9024	0.004%
gr24	9.4408	9.4400	0.008%
fri26	13.2027	13.1946	0.061%
bays29	12.9606	12.9526	0.062%

TABLE I: IP vs. RPT* solution cost comparison

Fig. 9: Comparison of the DP baseline with RPT*. (a) Runtime comparison. DP solves instances with up to approximately $24$ vertices within the runtime limit, whereas RPT* solves instances with up to approximately $40$ vertices to optimality. (b) Number of processed states. The DP baseline computes an order of magnitude more states than RPT*, and the gap increases rapidly as the number of vertices grows.

Fig. 10: Impact of heuristic. (a) Runtime comparison. (b) Normalized runtime ratio. For graphs with up to $40$ vertices, both methods have almost the same success rates, while heuristic helps save $30\%$ - $50\%$ runtime than the uninformed RPT*.

Fig. 11: Impact of focal search. (a) Runtime and success rates of F-RPT* ( $\epsilon=0.01$ ). (b) Comparison of different $\epsilon$ . Focal search helps RPT* to solve problems with up to $200$ vertices. A small $\epsilon$ can speed up the search and further increasing $\epsilon$ does not provide much additional reduction in the runtime.

Fig. 12: Comparison against baselines. (a) Runtime comparison. (b) Solution cost comparison. In both (a) and (b), solid lines denote the proposed methods, RPT* and F-RPT*; the dashed line denotes the uninformed ablation baseline $\text{RPT* }_{\mathrm{noh}}$ ; and dash-dotted lines denote the non-optimal baselines GP, GD, and LKH. Our RPT* and F-RPT* run slower than the baseline but find better quality solutions.

Fig. 13: Comparison between F-RPT* and the RL4CO-based learning baseline. (a) Runtime comparison. (b) Solution cost comparison and normalized ratio of RL4CO with respect to F-RPT*. RL4CO provides fast online inference and competitive solutions, while F-RPT* retains the bounded-suboptimality guarantee and achieves lower expected cost in the tested instances.

Fig. 14: Experimental setup for lifelong target search. (a) The $80\times 80$ m simulation environment and robot model in Gazebo. (b) Pre-constructed map with $20$ candidate target locations. In each trial, one location is randomly selected as the true target location and is marked in orange, while the remaining locations are target-absent and are marked in blue. The size of the blue or orange circle indicates the sampled probability values at each location. A larger probability corresponds to a larger circle.

Fig. 15: Mission duration of HATS-L with different global solvers. The boxplot reports the mission duration of RPT*, GP, GD, LKH, and the RL4CO-based baseline over $20$ randomized trials. Each box shows the interquartile range, the center line shows the median, and the whiskers indicate the empirical minimum and maximum. RPT* achieves the lowest median mission duration and a relatively compact distribution, demonstrating the benefit of optimizing the HPP-PT expected cost under Bayesian belief updates.

Fig. 16: Experimental setup for target search in unknown environments. (a) The $101\times 101$ m forest environment. (b) Visualization of the search process.

Planner	Success ( $/10$ )	Mission Duration (s)
RPT* (Ours)	$10$	$77.2$
GP	$10$	$\mathbf{49.5}$
GD	$10$	$170.6$
LKH	$5$	$439.2$
RL4CO	$3$	$420.6$

TABLE II: Accurate-prior results over

10

randomized trials.

Planner	Success ( $/10$ )	Mission Duration (s)
RPT* (Ours)	$\mathbf{10}$	$\mathbf{90.7}$
GP	$9$	$101.4$
GD	$9$	$180.6$
LKH	$6$	$484.8$
RL4CO	$2$	$414.0$

TABLE III: Misleading-prior results over

10

randomized trials.

$\mathbf{\delta}$ (m)	Success ( $/10$ )	Mission Duration (s)	Deviation (%)
$1$	$10$	$94.7$	$+4.4$
$2$	$10$	$95.7$	$+5.5$
$3$	$10$	$\mathbf{90.7}$	$\mathbf{0.0}$
$4$	$10$	$77.7$	$-14.3$
$5$	$10$	$91.8$	$+1.2$

TABLE IV: Sensitivity to the bandwidth parameter

\delta

with a fixed

\delta_{\mathrm{dist}}=5

in the misleading-prior scenario. Mission duration is averaged over successful trials.

$\mathbf{\delta_{\mathrm{dist}}}$ (m)	Success ( $/10$ )	Mission Duration (s)	Deviation (%)
$4$	$10$	$93.9$	$+3.5$
$5$	$10$	$\mathbf{90.7}$	$\mathbf{0.0}$
$6$	$10$	$91.7$	$+1.1$

TABLE V: Sensitivity to the cluster-merge distance

\delta_{\mathrm{dist}}

with a fixed

\delta=3

in the misleading-prior scenario. Mission duration is averaged over successful trials.

Fig. 17: Experiment of HATS-U in a corridor setting using a quadruped robot. (a) Panoramic view of the environment and the robot. (b) Snapshots of the occupancy grid and camera image during the search process.

Fig. 18: Snapshots of the occupancy grid and camera image during the target search process using the wheeled robot in a lab setting.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Parameter	Meaning	Usage
$\alpha_{1}$	True-positive rate in the Bayesian observation model	HATS-L (in Sec. V-B ); set to $0.8$
$\alpha_{2}$	False-positive rate in the Bayesian observation model	HATS-L (in Sec. V-B ); set to $0.4$
$p_{H}$	Belief threshold for declaring target-present	HATS-L (in Sec. VI-D ); set to $0.98$
$p_{L}$	Belief threshold for declaring target-absent	HATS-L (in Sec. VI-D ); set to $0.02$
$w_{u}$	Weight on unknown-space density $\phi_{u}$	HATS-U (in Sec. V-C ); set to $0.3$
$w_{g}$	Weight on geometric visibility $\phi_{g}$	HATS-U (in Sec. V-C ); set to $0.3$

Appendix

TABLE VI: Main HATS hyperparameters.

Robot Motion Planning

Robot motion planning finds safe, feasible paths and trajectories for robots moving through constrained, changing environments.

See all 271 papers

Learning Semantic Priorities for Autonomous Target Search
Mar 31, 2026Max Lodel, Nils Wilde, Robert Babuška +1Search-and-Rescue Robotics
Department of Cognitive Robotics (CoR), Delft University of Technology, The Netherlands · CIIRC, Czech Technical University in Prague, Czech Republic
HEHA: Bounded Suboptimal Planning for Constrained Routing and Its Use in Heterogeneous Multi-Robot Exploration of Unknown Environments
Oct 5, 2025Longrui Yang, Yiyu Wang, Jingfan Tang +4Multi-Robot Exploration Constrained Motion Planning
Shanghai Jiao Tong University in China · Carnegie Mellon University, PA, 15213
Reward-Guided RRT* for Budgeted Task and Motion Planning
Oct 26, 2026Vinícius Araújo de Oliveira, Gabriel Ferreira Mendes Lourenço, Paulo L. J. Drews-Jr +2Motion Planning Sampling-Based Motion Planning
Computer Vision and Robotics Laboratory (VeRLab), Dept. of Computer Science, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil. · NAUTEC, Center for Computational Science, Universidade Federal do Rio Grande - FURG, Rio Grande, Brazil. · Dept. of Electronics Engineering, Universidade Federal de Minas Gerais, Belo Horizonte, Brazil.

Mar 31, 2026J/K move · Enter open · S save

Learning Semantic Priorities for Autonomous Target Search

Max Lodel, Nils Wilde, Robert Babuška, Javier Alonso-Mora

Department of Cognitive Robotics (CoR), Delft University of Technology, The Netherlands · CIIRC, Czech Technical University in Prague, Czech Republic

Search-and-Rescue Robotics

Open paper AskPDF arXiv

The use of semantic features can improve the efficiency of target search in unknown environments for robotic search and rescue missions. Current target search methods rely on training with large datasets of similar domains, which limits the adaptability to diverse environments. However, human experts possess high-level knowledge about semantic relationships necessary to effectively guide a robot during target search missions in diverse and previously unseen environments. In this paper, we propose a target search method that leverages expert input to train a model of semantic priorities. By employing the learned priorities in a frontier exploration planner using combinatorial optimization, our approach achieves efficient target search driven by semantic features while ensuring robustness and complete coverage. The proposed semantic priority model is trained with several synthetic datasets of simulated expert guidance for target search. Simulation tests in previously unseen environments show that our method consistently achieves faster target recovery than a coverage-driven exploration planner.

Abstract

Robot Motion Planning

Explore similar work

Learning Semantic Priorities for Autonomous Target Search

HEHA: Bounded Suboptimal Planning for Constrained Routing and Its Use in Heterogeneous Multi-Robot Exploration of Unknown Environments

Reward-Guided RRT* for Budgeted Task and Motion Planning