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 ϕu(x) , (c) the geometric visibility ϕg(x) , and (d) the prior knowledge of object ϕ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* ( ϵ=0.01 ). (b) Comparison of different ϵ . Focal search helps RPT* to solve problems with up to 200 vertices. A small ϵ can speed up the search and further increasing ϵ 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 RPT* 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×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×101 m forest environment. (b) Visualization of the search process.
Planner
Success ( /10 )
Mission Duration (s)
RPT* (Ours)
10
77.2
GP
10
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)
10
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.
δ (m)
Success ( /10 )
Mission Duration (s)
Deviation (%)
1
10
94.7
+4.4
2
10
95.7
+5.5
3
10
90.7
0.0
4
10
77.7
−14.3
5
10
91.8
+1.2
TABLE IV: Sensitivity to the bandwidth parameter δ with a fixed δdist=5 in the misleading-prior scenario. Mission duration is averaged over successful trials.
δdist (m)
Success ( /10 )
Mission Duration (s)
Deviation (%)
4
10
93.9
+3.5
5
10
90.7
0.0
6
10
91.7
+1.1
TABLE V: Sensitivity to the cluster-merge distance δdist with a fixed δ=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.
Figure 25Figure 26Figure 27Figure 28Figure 29
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Parameter
Meaning
Usage
α1
True-positive rate in the Bayesian observation model
HATS-L (in Sec. V-B ); set to 0.8
α2
False-positive rate in the Bayesian observation model
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.
Max Lodel, Nils Wilde, Robert Babuška +1
Department of Cognitive Robotics (CoR), Delft University of Technology, The Netherlands · CIIRC, Czech Technical University in Prague, Czech Republic
This paper considers the path planning problem for autonomous exploration of an unknown environment using multiple heterogeneous robots such as drones, wheeled, and legged robots, with different capabilities to traverse complex terrains. A key challenge there is to intelligently allocate the robots to the unknown areas to be explored and determine the visiting order of those areas subject to traversability constraints, which leads to a large-scale constrained multiple hamiltonian path problem (mHPP) that needs to be quickly and iteratively solved every time when new space is explored. To address the hallenge, we propose HEHA (Hierarchical Exploration with Heterogeneous Agents) using a recent hierarchical method that decomposes the exploration into global planning and local planning. The major contribution in HEHA is its global planning, where we propose a new routing algorithm RCH (Routing with Constraints and Heterogeneity) that can quickly find bounded sub-optimal solutions for mHPP to minimize the maximum path length (i.e., makespan) among the agents subject to traversability constraints. Additionally, the local planner in HEHA also considers heterogeneity to avoid repeated and duplicated exploration among the robots. The experimental results show, in the presence of heterogeneous traversability, our RCH can solve mHPP with up to 47% smaller makespan than several baselines, and HEHA can reduce the exploration time by up to 30% compared with existing approaches.
Longrui Yang, Yiyu Wang, Jingfan Tang +4
Shanghai Jiao Tong University in China · Carnegie Mellon University, PA, 15213
Robotic missions involving spatially distributed tasks often require jointly selecting rewarding locations and planning feasible motions under limited travel budgets. This paper proposes Reward-Guided RRT*, a new sampling-based framework that constructs a budget-feasible mission through a sequence of locally joint task-selection-and-motion-planning stages, evaluated directly in the continuous state space, without requiring a precomputed task-transition graph. The method incrementally builds a mission using reward-guided RRT* searches, while a return-feasibility procedure ensures that each selected task can be visited without violating the mission budget. Experiments with increasing obstacle complexity and number of tasks show solutions comparable to VNS-PRM* while requiring substantially fewer sampled states. We also extend the framework to Dubins steering and evaluate it in CoppeliaSim with a scaled car-like robotic platform, demonstrating its ability to incorporate vehicle kinematic constraints.
Vinícius Araújo de Oliveira, Gabriel Ferreira Mendes Lourenço, Paulo L. J. Drews-Jr +2
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.