RRT-Based Incremental Path Search over Incrementally Revealed 3D Scene Graphs

Graph-based path planning commonly operates on an available topological representation, but robotic exploration may require searching for feasible paths while the environment graph is progressively revealed. This paper proposes MSG-RRT (Multi-Strategy Scene-Graph RRT), an RRT-based method for first-feasible-path discovery over incrementally revealed 3D scene graph topology. MSG-RRT operates on the discrete spatial-topological structure of the Places layer and combines goal-biased graph-node sampling with topology-constrained, goal-aware steering. Tree expansion is coupled with simulated local graph revelation, allowing newly revealed topology to participate in subsequent search. Experiments on a scene graph generated from the uHumans2 environment show that MSG-RRT reduces the average number of search iterations from 2185.45 to 683.90 and runtime from 14.50 s to 3.58 s compared with basic graph-space RRT, corresponding to reductions of 68.7% and 75.3%, respectively. Ablation and statistical analyses identify goal-biased sampling as the primary contributor to improved search efficiency. Comparisons with Lifelong Planning A* across multiple start—goal configurations reveal task-dependent performance, while parameter sensitivity and simulated edge omission experiments further characterize the influence of goal bias and incomplete graph observations. These findings demonstrate the potential of RRT-based search for first-feasible-path discovery under the evaluated incremental graph-revelation conditions.