Learning-Guided Sparsification of Dynamic Graphs in Robotic Exploration
Authors: Adithya V. Sastry, Bibek Poudel, Weizi Li
Organizations: Independent Researcher Knoxville, TN, USA · Purdue University West Lafayette, IN, USA · University of California, Riverside Riverside, CA, USA
Many robotic exploration algorithms rely on graph structures for frontier-based exploration and dynamic path planning. However, these graphs grow rapidly, accumulating redundant information and impacting performance. We present a hybrid transformer-based framework trained with Proximal Policy Optimization which complements exploration algorithms by pruning these graphs during exploration, limiting their growth and reducing the accumulation of excess information. The framework was evaluated on simulations of a robotic agent using Rapidly-Exploring Random Trees to carry out frontier-based exploration, where the learned policy reduces graph size by up to 96%. We find preliminary evidence that our framework enables effective, generalizable exploration under reduced information density, consistently outperforming the randomly pruned baseline and improving both exploration efficiency and computational efficiency beyond the unpruned baseline for complex long-horizon exploration tasks. To the best of our knowledge, these results are the first suggesting the viability of RL to prune dynamic graphs used in robotic exploration algorithms.
Figures & tables
Fig. 1: Left: An example environment the robot explores. Middle: Exploration progress without pruning. Right: Exploration progress with pruning over a comparable time period. Magenta blocks are obstacles, gray area represents explored free space, black area represents unexplored free space, blue represents the exploration graph, and yellow represents the robot’s field of view. Pruning reduces the exploration graph size by up to 96 %, demonstrating the potential for intelligent sparsification in graph-based exploration.
Fig. 2: Overview of the framework for pruning robotic exploration graphs. An image of the current map (top left) is split into patches, tokenized, and positionally embedded before passing through a Gated Transformer-XL encoder and multi-layer perceptron layers for feature extraction. The extracted features feed into separate actor and critic heads, where the actor predicts the means, standard deviations, and mixing weights that define a Gaussian Mixture Model (GMM) over the environment. To determine which nodes to prune, the coordinates of nodes in the exploration graph are projected onto this GMM. The environment is then split into the same patches created by the tokenizer, and the highest probability nodes in each patch are retained; all others are pruned.
Fig. 3: Exploration progress across various environment complexities and time horizons, measured as a percentage-point (pp) difference from the baseline (exploration without pruning). Learned pruning (ours) remains within 4.5 pp of the exploration progress without pruning and consistently exceeds the exploration progress under uniform random pruning. Further, learned pruning generalizes to a variety of exploration tasks despite being trained on only high-complexity short-horizon simulations. As both the complexity of environments and the exploration time horizon increase, learned pruning becomes increasingly advantageous. Long-horizon runs use n=100 instead of the n=500 used for short-horizon runs due to increased computational cost of running long-horizon experiments. Error bars are roughly ±1 SE of the difference in mean exploration progress. Note that the stated number of ”moves” for each experiment refers to the value set for both the maximum number of robot moves ( λM ) and the maximum number of RRT growth attempts ( λR ).
Fig. 4: Heat map showing the wall-clock speedup relative to the unpruned baseline that results from applying learned pruning to various combinations of environment complexities and exploration time horizons. In sufficiently complex environments and long horizons, learned pruning achieves substantial computational efficiency gains relative to the unpruned baseline, consistent with the expected impact of a large reduction in the exploration graph size.
Pruning Method
Sparse 100 mov.
Moderate 100 mov.
Dense 100 mov.
Dense 1000 mov.
Dense 2000 mov.
None
68.94±14.38
50.84±13.36
13.49±4.63
29.78±9.22
31.99±12.39
Random
60.52±14.10
44.45±11.36
11.15±3.61
22.99±6.87
29.82±9.95
Learned (ours)
64.64±14.79
48.48±12.76
11.95±3.87
31.13±8.65
34.15±11.32
TABLE I: Final explored area (%, mean ± std) under different pruning strategies, environment complexities, and time horizons.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Parameter
Value
PPO
Learning Rate ( α )
1×10−4
Discount Factor ( γ )
0.99
GAE Estimation ( λ )
0.95
Clip Parameter ( ϵ )
0.1
Value Function Coeff.
0.5
Entropy Coeff.
5×10−4
Appendix
TABLE II: Training hyperparameters for PPO, policy networks, and simulation environment.
Autonomous mobile robots require spatial representations that capture geometry and semantics while staying sparse enough for planning in large, unknown environments. Graphs provide a natural representation for this purpose and underpin both classical planning methods and a growing class of reinforcement-learning (RL) policies. However, RL training needs hundreds to thousands of parallel environments, each constructing and updating its own graph. Existing graph libraries are typically designed for either single-robot deployment or fixed graphs, and CPU-based graph construction limits scalable training to only a few dozen environments. We introduce GGraph, an open-source GPU-accelerated graph library for both robot deployment and large-scale learning. GGraph supports real robots through ROS 2 interfaces and vectorized GPU-based policy training, with built-in support for tasks including 3-D navigation, exploration, and loop-closure integration. For single-robot operation, GGraph updates graphs in milliseconds. At scale, it enables graph-based exploration policies to train across hundreds of parallel robots, reducing wall-clock training time by one order of magnitude. Across simulation and real-world experiments, these results establish GGraph as a unified graph infrastructure for both large-scale robot learning and deployment.
Representation learning has enabled classical exploration strategies to be extended to deep Reinforcement Learning (RL), but often makes algorithms more complex and theoretical guarantees harder to establish. We introduce Random Feature Information Gain (RFIG), grounded in Bayesian kernel methods theory, which uses random Fourier features to approximate information gain and compute exploration bonuses in non-countable spaces. We provide error bounds on information gain approximation and avoid the black-box aspects of neural network-based uncertainty estimation, for optimism-based exploration. We present practical details that make RFIG scalable to deep RL scenarios, enabling smooth integration into standard deep RL algorithms. Experimental evaluation across diverse control and navigation tasks demonstrates that RFIG achieves competitive performance with well-established deep exploration methods while offering superior theoretical interpretation.
Waris Radji, Odalric-Ambrym Maillard
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France
Autonomous exploration of cluttered environments requires efficient exploration strategies that guarantee safety against potential collisions with unknown random obstacles. This paper presents a novel approach combining a graph neural network-based exploration greedy policy with a safety shield to ensure safe navigation goal selection. The network is trained using reinforcement learning and the proximal policy optimization algorithm to maximize exploration efficiency while reducing the safety shield interventions. However, if the policy selects an infeasible action, the safety shield intervenes to choose the best feasible alternative, ensuring system consistency. Moreover, this paper proposes a reward function that includes a potential field based on the agent's proximity to unexplored regions and the expected information gain from reaching them. Overall, the approach investigated in this paper merges the benefits of the adaptability of reinforcement learning-driven exploration policies and the guarantee ensured by explicit safety mechanisms. Extensive evaluations in simulated environments demonstrate that the approach enables efficient and safe exploration in cluttered environments.
Luleå University of Technology · Robotics and AI Group, Department of Computer Science, Electrical and Space Engineering, Luleåa University of Technology, Sweden