Learning-Guided Sparsification of Dynamic Graphs in Robotic Exploration

Adithya V. Sastry; Bibek Poudel; Weizi Li

cs.ROApr 15, 2026

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

Abstract

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

Panel of Figure 1 — 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

\pm 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 (

\lambda_{M}

) and the maximum number of RRT growth attempts (

\lambda_{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$ $\pm 14.38$	$50.84$ $\pm 13.36$	$13.49$ $\pm 4.63$	$29.78$ $\pm 9.22$	$31.99$ $\pm 12.39$
Random	$60.52$ $\pm 14.10$	$44.45$ $\pm 11.36$	$11.15$ $\pm 3.61$	$22.99$ $\pm 6.87$	$29.82$ $\pm 9.95$
Learned (ours)	$64.64$ $\pm 14.79$	$48.48$ $\pm 12.76$	$11.95$ $\pm 3.87$	$31.13$ $\pm 8.65$	$34.15$ $\pm 11.32$

TABLE I: Final explored area (%, mean

\pm

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 ( $\alpha$ )	$1{\times}10^{-4}$
	Discount Factor ( $\gamma$ )	$0.99$
	GAE Estimation ( $\lambda$ )	$0.95$
	Clip Parameter ( $\epsilon$ )	$0.1$
	Value Function Coeff.	$0.5$
	Entropy Coeff.	$5{\times}10^{-4}$

Appendix

TABLE II: Training hyperparameters for PPO, policy networks, and simulation environment.

Graph Sparsification

Graph sparsification reduces a graph's edges while retaining the structure or task performance needed for analysis and learning.

See all 20 papers

GGraph: A GPU-Accelerated Library for Graph-Based Robot Deployment and Learning
Oct 20, 2026Yash Rampuria, Rohan Garg, Daniele Gammelli +1Robot Learning Robotic RL
Stanford University, CA
Information-Based Exploration via Random Features for Reinforcement Learning
Jul 20, 2026Waris Radji, Odalric-Ambrym MaillardRL Exploration Uncertainty-Aware Exploration
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France
A Graph-Based Reinforcement Learning Approach with Frontier Potential Based Reward for Safe Cluttered Environment Exploration
Apr 16, 2025Gabriele Calzolari, Vidya Sumathy, Christoforos Kanellakis +1Reward Shaping Mobile Robotics
Luleå University of Technology · Robotics and AI Group, Department of Computer Science, Electrical and Space Engineering, Luleåa University of Technology, Sweden

Oct 20, 2026J/K move · Enter open · S save

GGraph: A GPU-Accelerated Library for Graph-Based Robot Deployment and Learning

Yash Rampuria, Rohan Garg, Daniele Gammelli, Marco Pavone

Stanford University, CA

Robot Learning Robotic RL Graph-Based Planning Robot Navigation

Open paper AskPDF arXiv

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.

Abstract

Graph Sparsification

Explore similar work

GGraph: A GPU-Accelerated Library for Graph-Based Robot Deployment and Learning

Information-Based Exploration via Random Features for Reinforcement Learning

A Graph-Based Reinforcement Learning Approach with Frontier Potential Based Reward for Safe Cluttered Environment Exploration