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

• URL: http://arxiv.org/abs/2601.12701v1
• Date: Mon, 19 Jan 2026 03:55:35 GMT
• Title: RPT*: Global Planning with Probabilistic Terminals for Target Search in Complex Environments
• Abstract summary: This paper studies a variant, HPP with Probabilistic Terminals (HPP-PT)<n>HPP-PT arises in target object search, where a mobile robot must visit all candidate locations to find an object.<n>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 novels to speed up the computation.
• Score: 24.363288778774404
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Routing problems such as Hamiltonian Path Problem (HPP), seeks 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 optimally 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.

Related papers

• Polar Coordinate-based Differential Evolution for Moving Target Search Using Vision Sensor on Unmanned Aerial Vehicles [0.23332469289621782]
  In search and rescue operations, there is a period known as the "golden time" during which the probability of finding the target alive is highest.<n>We propose a new search algorithm for unmanned aerial vehicles (UAVs) with a focus on improving the detection probability and execution time.
  arXiv  Detail & Related papers  (2026-07-20T10:03:43Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  We propose SCoTT, a wireless-aware path planning framework.<n>We show that SCoTT achieves path gains within 2% of DP-WA* while consistently generating shorter trajectories.<n>We also show the practical viability of our approach by deploying SCoTT as a ROS node within Gazebo simulations.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• Search-Based Path Planning in Interactive Environments among Movable Obstacles [8.023424148846265]
  This paper introduces two PAMO formulations, i.e., bi-objective and resource constrained problems in an occupancy grid.<n>We develop PAMO*, a planning method with completeness and solution optimality guarantees, to solve the two problems.<n>Our results show that, PAMO* can often find optimal solutions within a second in cluttered maps with up to 400 objects.
  arXiv  Detail & Related papers  (2024-10-24T00:02:58Z)
• LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
  Path planning is a fundamental scientific problem in robotics and autonomous navigation.<n>Traditional algorithms like A* and its variants are capable of ensuring path validity but suffer from significant computational and memory inefficiencies as the state space grows.<n>We propose a new LLM based route planning method that synergistically combines the precise pathfinding capabilities of A* with the global reasoning capability of LLMs.<n>This hybrid approach aims to enhance pathfinding efficiency in terms of time and space complexity while maintaining the integrity of path validity, especially in large-scale scenarios.
  arXiv  Detail & Related papers  (2024-06-20T01:24:30Z)
• POA: Passable Obstacles Aware Path-planning Algorithm for Navigation of a Two-wheeled Robot in Highly Cluttered Environments [53.41594627336511]
  Passable Obstacles Aware (POA) planner is a novel navigation method for two-wheeled robots in a cluttered environment. Our algorithm allows two-wheeled robots to find a path through passable obstacles.
  arXiv  Detail & Related papers  (2023-07-16T19:44:27Z)
• GP-guided MPPI for Efficient Navigation in Complex Unknown Cluttered Environments [2.982218441172364]
  This study presents the GP-MPPI, an online learning-based control strategy that integrates Model Predictive Path Intergal (MPPI) with a local perception model. We validate the efficiency and robustness of our proposed control strategy through both simulated and real-world experiments of 2D autonomous navigation tasks.
  arXiv  Detail & Related papers  (2023-07-08T17:33:20Z)
• Learning Coverage Paths in Unknown Environments with Deep Reinforcement Learning [17.69984142788365]
  Coverage path planning ( CPP) is the problem of finding a path that covers the entire free space of a confined area. We investigate how suitable reinforcement learning is for this challenging problem. We propose a computationally feasible egocentric map representation based on frontiers, and a novel reward term based on total variation.
  arXiv  Detail & Related papers  (2023-06-29T14:32:06Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• DDPEN: Trajectory Optimisation With Sub Goal Generation Model [70.36888514074022]
  In this paper, we produce a novel Differential Dynamic Programming with Escape Network (DDPEN) We propose to utilize a deep model that takes as an input map of the environment in the form of a costmap together with the desired position. The model produces possible future directions that will lead to the goal, avoiding local minima which is possible to run in real time conditions.
  arXiv  Detail & Related papers  (2023-01-18T11:02:06Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• Hierarchical Path-planning from Speech Instructions with Spatial Concept-based Topometric Semantic Mapping [7.332652485849632]
  This study aims to realize a hierarchical spatial representation using a topometric semantic map and path planning with speech instructions, including waypoints. We conducted experiments in home environments using the Toyota Human Support Robot on the SIGVerse simulator and in a lab-office environment with the real robot, Albert. Navigation experiments using speech instructions with a waypoint demonstrated a performance improvement of SpCoTMHP over the baseline hierarchical path planning method with path costs.
  arXiv  Detail & Related papers  (2022-03-21T09:15:25Z)
• Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes [7.766921168069532]
  Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots through which they can navigate from their initial positions to specified goal positions. In this paper, we enhance existing SAT-based algorithm for MRPP via spartification of the set of candidate paths for each robot from which target Boolean encoding is derived.
  arXiv  Detail & Related papers  (2021-03-08T00:57:42Z)
• POMP: Pomcp-based Online Motion Planning for active visual search in indoor environments [89.43830036483901]
  We focus on the problem of learning an optimal policy for Active Visual Search (AVS) of objects in known indoor environments with an online setup. Our POMP method uses as input the current pose of an agent and a RGB-D frame. We validate our method on the publicly available AVD benchmark, achieving an average success rate of 0.76 with an average path length of 17.1.
  arXiv  Detail & Related papers  (2020-09-17T08:23:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.