A research paper led by Yunpeng Lyu, a 2024-entry doctoral student at Shanghai Jiao Tong University Global College (SJTUGC, abbreviated as GC hereafter), has been accepted for publication in IEEE Transactions on Robotics (T-RO), a leading international journal in robotics. The paper, titled “RPT*: Global Planning with Probabilistic Terminals for Target Search in Complex Environments,” was co-authored by researchers from GC and Carnegie Mellon University, with GC Associate Professor Zhongqiang Ren serving as the corresponding author.
The research was conducted at GC’s Robotics Autonomy and Planning Lab (RAP Lab). Addressing the challenge of target search in complex environments, the team proposed RPT*, a globally optimal planning algorithm, and developed a Hierarchical Autonomous Target Search (HATS) system. The approach has been validated in both simulation and real-world robotic experiments.
In applications such as search and rescue and environmental monitoring, mobile robots may need to search for an object across multiple candidate locations in a building. For example, a robot might be tasked with finding a set of keys left in one of several rooms, while only having uncertain prior knowledge about their location. Each candidate location has a different probability of containing the target.
The challenge is to determine the order in which the robot should visit these locations to minimize its expected travel cost. Unlike the classical Hamiltonian Path Problem (HPP), which seeks the shortest path that visits every vertex in a graph, target search allows the robot to stop once the target is found. This gives rise to the Hamiltonian Path Problem with Probabilistic Terminals (HPP-PT), in which the expected path cost depends not only on the locations visited but also on their visiting order. This history dependency makes the problem difficult to solve efficiently using many classical path-planning methods.
To address this challenge, the team developed RPT*, a heuristic-search-based algorithm. Its key innovation is the introduction of auxiliary variables that transform the history-dependent expected cost into a Markovian form. In the resulting state space, future expansions depend only on the current state, rather than the complete sequence of previously visited locations. This transformation avoids the computational bottleneck caused by the combinatorial growth of possible visiting orders. RPT* further incorporates an admissible heuristic that can be precomputed in polynomial time to guide the search, together with dominance-based pruning rules to eliminate redundant branches. The paper provides a proof of the algorithm’s optimality. For larger graphs, the team developed F-RPT*, a bounded-suboptimal variant based on focal search. F-RPT* can solve problems with up to 200 nodes within one minute while providing a theoretical guarantee on solution quality.
Research diagram of the published paper on RPT*
Extensive evaluations on the public TSPLIB benchmark and randomly generated synthetic datasets demonstrated the algorithms’ effectiveness. For graphs with up to 40 nodes, RPT* found optimal solutions within one minute and ran three orders of magnitude faster than integer programming methods. For graphs with 200 nodes, F-RPT* found near-optimal solutions with expected costs no more than 1% above the optimum.
Compared with baseline methods, including greedy approaches based on probability (GP) and distance (GD), the classical path solver LKH, and the reinforcement-learning-based method RL4CO, RPT* and F-RPT* achieved substantially better solution quality. The expected path cost of baseline methods was up to three times that of RPT*.
Research diagram of the published paper on HATS
To bring the planning algorithm to real-world robotic applications, the team developed HATS, a hierarchical system comprising perception, mapping, global planning and local planning modules. HATS supports two search scenarios. HATS-L enables lifelong target search in known environments, using Bayesian filtering to iteratively update target-location probabilities. HATS-U supports search in unknown environments by incrementally building maps through simultaneous localization and mapping (SLAM), extracting information gain from frontier points, and dynamically generating HPP-PT instances.
In simulation experiments, HATS demonstrated strong performance. In lifelong search (HATS-L), the RPT*-based planner achieved the lowest median task time and the smallest variance in a Gazebo environment measuring 80 × 80 meters and containing 20 candidate locations. In unknown-environment search (HATS-U), RPT* achieved a 100% success rate in both accurate-prior and misleading-prior scenarios. When prior information was inaccurate and included decoy locations, the greedy GP method was often distracted by the decoys, leading to a lower success rate. RPT* experienced only a slight increase in task duration. By minimizing expected cost, the algorithm naturally balances exploitation of high-probability regions with exploration of other candidate areas.
The team further validated HATS-U in two real-world scenarios: a quadruped robot searching for a backpack in a corridor and a wheeled robot searching for a trash bin in a laboratory. In both experiments, YOLO was used for real-time object detection. The robots autonomously explored previously unknown environments, incrementally built maps, dynamically planned their routes and successfully located the targets. These results demonstrate the versatility and robustness of HATS across different robot platforms and environments.
Research diagram of the published paper on real-world experiments
IEEE Transactions on Robotics is a leading international journal published by the IEEE Robotics and Automation Society, covering robotics, automation and related fields. The research presents a comprehensive approach to autonomous target search, from formulating a new planning problem and developing algorithms with theoretical guarantees to implementing a complete system and deploying it on real robots. It provides an efficient and theoretically grounded planning solution with potential applications in search and rescue, warehouse logistics and environmental monitoring. Looking ahead, the team plans to extend the research to multi-robot cooperative search, target-probability estimation using semantic maps, and dynamic target tracking.
Personal Introduction
Yunpeng Lyu is a 2024-entry doctoral student in Control Science and Engineering at GC. His research focuses on robot path planning and target search. Under the supervision of Associate Professor Zhongqiang Ren, he has conducted research on autonomous target-search planning, contributing to the core algorithm design, C++ implementation, simulation experiments and real-world robot deployment.
Zhongqiang Ren is an associate professor and doctoral supervisor at GC and the corresponding author of the paper. He received his PhD from Carnegie Mellon University. His research focuses on robot motion planning, autonomous navigation and multi-robot systems. He has published more than 40 research papers in leading robotics journals and conferences, including Science Robotics, IEEE Transactions on Robotics (T-RO), Robotics: Science and Systems (RSS), the IEEE International Conference on Robotics and Automation (ICRA), and the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). He has received multiple best-paper nominations and serves on the editorial boards of leading robotics journals and conferences.
