Improved Two-Stage Theta* Algorithm for Path Planning with Uncertain Obstacles in Unstructured Rescuing Environments

Path planning aims to find a safe and efficient path from a starting point to an end point, and it has been well developed in fields such as robot navigation, autonomous driving, and intelligent decision systems. However, traditional path planning faces challenges in an uncertain rescuing environment due to limited sensing range and a lack of accurate obstacle information. In order to address this issue, this paper proposes an improved two-stage Theta* algorithm for handling multi-probability obstacle scenarios in unstructured rescue environments. First, a global probability raster map is constructed by integrating historical maps and expert prediction maps with probability weights quantifying the uncertainty in the spatial and temporal distribution of obstacles. Second, a probability-sensitive heuristic function (PSHF) is designed, and a Sigmoid function is used to map the probability field of obstacles, thereby enabling limited penetration in low-risk areas and enforced avoidance in high-risk areas. Furthermore, a multi-stage line-of-sight detection optimization mechanism is proposed, which combines probability soft threshold penetration and backtracking verification to improve the noise robustness. Finally, a hierarchical planning architecture is constructed to separate global probabilistic guidance from local strict obstacle avoidance, ensuring both the global optimality and local adaptability of the path. Extensive simulation results in mine rescue scenarios demonstrate that the proposed method achieves lower path cost and fewer path nodes compared to traditional A*, Dijkstra, and Theta* algorithms, while significantly reducing local replanning overhead and maintaining stable performance across multiple uncertain environments.