PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Yash Rampuria, Rohan Garg, Daniele Gammelli, Marco Pavone

arXiv:2610.28953v1cs.RO

TL;DR

Existing graph tools do not provide a shared way to build and maintain navigation graphs for both robot deployment and learning. GGRAPH provides that GPU-resident library, and its graph-based exploration policies reach baseline quality with an order of magnitude less training time.

  • Problem

    No shared tool builds and maintains growing navigation graphs for both robot deployment and learning, despite their use in planning and learned policies.

    Source: §I · p. 1

  • Method

    GGRAPH is a GPU-resident navigation-graph library that incrementally builds persistent graphs from occupancy grids or elevation maps for ROS 2 deployment and parallel policy learning.

    Source: §I · pp. 1–2

  • Results

    Graph-based exploration policies reach baseline quality in an order of magnitude less wall-clock training time, outperform TARE and state-of-the-art methods at similar budgets, and transfer to simulated and real-robot deployment.

    Source: §I · p. 2, §VI · p. 8

  • Takeaways & Limitations

    The same GPU kernels support classical-planner deployment and batched policy learning, including graph correction after loop closure.

    Source: §VI · p. 7

Abstract

from arXiv · show

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.

I. INTRODUCTION

Graphs are a natural representation for robot navigation, but existing tools do not provide shared graph construction and maintenance for deployment and learning. GGRAPH makes the navigation graph a GPU-resident, batched, loop-closure-aware data structure for both.

I. INTRODUCTION

  • Existing deployment planners build graphs in planner-specific, single-robot code, while learning pipelines rebuild each environment’s graph on the CPU; a 16-worker run spends much wall-clock time maintaining graphs.GPU graph libraries target fixed graphs rather than graphs that grow, merge, and are re-scored during rollouts.Source: §I · p. 1
  • GGRAPH provides one GPU-resident navigation-graph library for deployment and learning, with stable node identities and vectorized graph updates.It accepts occupancy grids or elevation maps and exposes shortest paths, connectivity, and frontiers as CUDA tensors.Source: §I · p. 1
  • GGRAPH addresses the infrastructure gap with a batched graph data structure shared by deployment and learning, where improvements in a shared design tool can transfer between simulation and robots.Prior infrastructure tools are valued because one implementation serves both deployment and simulation training.Source: §I · pp. 1–2
  • GGRAPH’s contributions include real-robot graph validation and graph-based exploration policies that reach prior learned-policy quality in a fraction of training time and outperform baselines on held-out maps.The library also reports graph updates in tens of milliseconds at a million nodes and environment-step throughput up to 27× a SoTA baseline.Source: §I · p. 2

II. RELATED WORK

Prior navigation systems combine sparse graphs with dense maps, while graph libraries and learning pipelines have distinct limitations for dynamically updated navigation graphs. GGRAPH’s target is to make a graph the primary representation and support spatial merging, navigation, and batched learning in one library.

A. Representations for Navigation

  • Navigation representations range from occupancy and volumetric maps to topological maps and scene graphs; planners such as GBPlanner and TARE combine graphs with dense maps that remain necessary for exploration scoring.GGRAPH instead makes the graph primary, storing frontier, semantic, and learned attributes on nodes while using dense maps only as transient inputs.Source: A. Representations for Navigation · p. 2

B. Graph Libraries and Ecosystems

  • Navigation planners mutate graphs in custom C++ or Python code, while GPU graph libraries lack spatial merging and navigation operations for graphs that change during exploration.SWAGGER builds from a single map; PyTorch Geometric batches fixed model-input graphs, and cuGraph provides analytics over edge lists.Source: B. Graph Libraries and Ecosystems · p. 2
  • GGRAPH combines GPU acceleration, spatial merging, navigation and exploration operations, and batched policy learning in one library.The comparison table covers capabilities required of navigation graphs for deployment and learning.Source: B. Graph Libraries and Ecosystems · p. 2, Table I · p. 2

C. Learning-Based Robot Exploration

Graph-based exploration policies use a graph both as the traversed map and as input to a graph neural network, but prior approaches trained with relatively few CPU-based workers. The paper formulates exploration as sequential graph decisions that reward newly observed space and penalize travel distance.

C. Learning-Based Robot Exploration

  • Prior graph-based exploration methods trained in 2-D grid worlds with 16 to 32 Ray workers for one to three days, with graph construction in ARiADNE’s released code running on the CPU.GGRAPH’s GPU graph construction and merging let hundreds of environments step together, making on-policy methods such as PPO practical.Source: C. Learning-Based Robot Exploration · p. 2

III. PROBLEM FORMULATION

  • The task is to explore and observe all reachable free space while traveling the shortest possible path in an a priori unknown environment.At each timestep, the robot receives a local observation and maintains a stitched world-frame graph of collision-free waypoints and edges.Source: §III · pp. 2–3
  • The robot’s action is to travel to an adjacent graph node, and the reward credits newly observed free space while penalizing distance traveled.The formulation treats policy learning as an MDP over the incrementally updated graph.Source: §III · p. 3

IV. METHODOLOGY

GGRAPH uses a GPU pipeline to build and update navigation graphs and a parallel reinforcement-learning pipeline to train graph neural network policies. Its graph builder samples local waypoints, merges observations into a persistent graph, and supports node attributes, graph search, loop closure, and batched execution.

IV. METHODOLOGY

  • The methodology pairs a batched GPU graph builder with a parallel RL pipeline that trains a graph neural network directly on graphs across hundreds of environments.The same update kernels build local graphs, merge them into persistent world-frame graphs, and write per-node scores for one robot or N environments.Source: §IV · p. 3

A. Batched Graph Builder

  • Local graph construction detects frontiers in one map pass, then samples waypoints along free-space skeletons, obstacle boundaries, and open regions.For 2.5-D elevation inputs, slope and step-height processing lifts the map into a 3-D traversability volume before sampling.Source: A. Batched Graph Builder · p. 3
  • Each local graph is merged by batched nearest-neighbor assignment, snapping nodes to existing global nodes or appending them with fresh identifiers.Candidate edges are radius-proposed and checked with GPU-parallel line-of-sight tests; degree caps and pruning constrain graph edges and node retention.Source: A. Batched Graph Builder · p. 3
  • Per-node graph layers store computed or externally supplied attributes as GPU tensors, with overwrite, blend, or moving-average policies for repeated observations.The layer outputs can be consumed as policy features or planner scores without copies.Source: A. Batched Graph Builder · p. 3
  • Graph search provides parallel breadth-first search, Bellman–Ford shortest paths, and pointer-jumping connected components; Bellman–Ford relaxes all edges in one kernel launch rather than serializing a priority queue.The graph is materialized in compressed-sparse-row form from edge tensors.Source: A. Batched Graph Builder · p. 3
  • Loop closure correction gathers each node’s displacement from its creating odometry frame in O(N), then remerges spatially coincident nodes and rechecks frontier validity.The correction avoids graph traversal, sensor re-integration, and occupancy reprojection.Source: A. Batched Graph Builder · pp. 3–4
  • Batched execution steps N independent GPU-resident graph builders together and supplies padded graph tensors directly to a graph-conditioned policy.The stated batch-size bound is kernel saturation, rather than Python or PCIe overhead.Source: A. Batched Graph Builder · p. 4
  • A ROS 2 wrapper accumulates sensor data and odometry into a rolling map, feeds the incremental builder, and exposes graph layers for external scores.The exploration node is one such wrapper.Source: A. Batched Graph Builder · p. 4

B. Parallel Policy Learning For Exploration

GGRAPH supports exploration-policy learning with graph-based policies trained across parallel environments. The setup uses prior exploration rewards and PPO rollouts collected from independent episodes.

B. Parallel Policy Learning For Exploration

  • The policy uses separate actor and critic networks shared across environments, with the full training loop—including graph maintenance, environment updates, observation, and reward computation—on the GPU.Keeping the environment and learner on the GPU avoids CPU–GPU transfers.Source: B. Parallel Policy Learning For… · p. 4
  • Training uses 2-D occupancy-map worlds, with 150 newly generated validation maps split evenly across easy, medium, and complex tiers.The validation maps are excluded from training; difficulty increases with dead-end corridors and free-space boundary-to-area ratio.Source: B. Parallel Policy Learning For… · p. 4
  • The reward credits frontier-cell removal, penalizes travel distance, and adds a completion bonus of 20.The coefficients are a = 1/64 and b = 1/50, with the same coefficients as.Source: B. Parallel Policy Learning For… · p. 4
  • Each PPO iteration collects T steps from each of N environments into a rollout batch of B = NT transitions, then updates the actor and critic using mini-batches.The policy parameters are held fixed during collection; environments reset independently upon episode termination or reaching the episode-length limit.Source: B. Parallel Policy Learning For… · p. 4

V. EXPERIMENTS

The experiments examine GGRAPH’s deployment performance, its ability to accelerate graph-based policy learning across parallel robots, and whether trained policies transfer to simulation and real-world exploration.

V. EXPERIMENTS

  • The experiments ask how GGRAPH compares with open-source single-robot deployment libraries and whether it accelerates policy learning across thousands of parallel environments.They also test whether policies trained with GGRAPH can explore unknown environments in high-fidelity simulators and the real world.Source: §V · p. 4

A. Robot Deployment

GGRAPH builds 3-D graphs from real sensor data, with frontier and semantic node attributes. Its loop-closure pipeline corrects the graph after odometry drift in milliseconds.

1) Real-World 3-D Graphs:

  • GGRAPH builds a persistent world-frame graph from local graphs sampled from Spot’s campus sensor sequence, with collision-free nodes, traversable edges, GPU shortest paths, and frontier queries.The internally computed frontier layer marks nodes at the known-free/unknown boundary; the externally supplied semantic layer labels grass or pavement from camera views.Source: 1) Real-World 3-D Graphs · p. 4
  • Repeated observations accumulate so semantic labels stabilize as the robot moves.The semantic channel uses labels produced by ExploRFM from the camera view.Source: 1) Real-World 3-D Graphs · pp. 4–5

2) Loop Closure:

  • The 14.08 m loop-closure gap from combined 22% scale error and 160 mm/m additive world-frame bias is restored in 2.26 ms.Each node stores its odometry-step index, letting correction translate nodes in one vectorized pass rather than re-integrating sensor data or warping a volumetric map.Source: 2) Loop Closure · p. 5, Figure 4 · p. 5

3) Graph Update Time:

GGRAPH updates graphs as they grow and batches graph-based exploration environments for learning. Its update performance supports real-time planning at large map scales, while environment-step throughput improves with parallelism.

3) Graph Update Time:

  • At 100,000 nodes, a full graph update takes about 7 ms and is about 120× faster than the SWAGGER-and-NetworkX baseline; at one million nodes it takes 62 ms.At 0.5 m node sampling distance, one million nodes can cover a 500×500 m area.Source: 3) Graph Update Time · p. 5
  • Building the local graph, selecting candidate edges, and checking collisions take about 3 ms at every size; update-time growth comes from merging nodes, de-duplicating edges, and pruning node degrees.Source: 3) Graph Update Time · p. 5

B. Robot Learning

  • Prior graph-based exploration policies used Python graph maintenance and one Ray worker per environment, capping parallelism at CPU thread count.GGRAPH’s learning experiments measure throughput, training time, and final policy performance against this setup.Source: B. Robot Learning · p. 5

1) Batched Environment-Step Throughput:

  • Graph-step throughput is measured as applying an action, updating the graph, and returning the next observation and reward.The learning comparison uses ARiADNE’s released checkpoint and identical graph-sampling parameters across the two pipelines.Source: 1) Batched Environment-Step Throughput · p. 5
  • At N = 512, GGRAPH reaches about 6,500 env-steps per second versus 244 for ARiADNE, a 27× speedup.The throughput advantage grows with parallel robots, from approximately 6× at N = 16 to 26× at N = 256, before leveling off.Source: 1) Batched Environment-Step Throughput · p. 5

2) Wall-Clock Training Efficiency and Performance on 2-D Grid Worlds:

GGRAPH-based policies learn effective exploration paths within shorter training budgets than ARiADNE SAC-16. The results also show that rollout allocation matters: very short rollouts slow early PPO learning.

2) Wall-Clock Training Efficiency and Performance on 2-D Grid Worlds:

  • At 6 h, PPO achieves a mean path length of 1255 px and 97% success, versus 1333 px and 91% for the released policy; PPO reduces complex-map paths from 2050 to 1825 px.Table II reports mean path length in grid cells and success across 150 validation maps, with 50 maps per difficulty tier.Source: Table II · p. 6, 2) Wall-Clock Training Efficiency and… · p. 6
  • The evaluation compares throughput as parallel robot counts increase and tracks PPO reward against wall-clock time; exploration curves measure path length, for which lower is better.The training comparison uses 150 independently generated validation maps, evenly divided among easy, medium, and complex tiers.Source: Figure 6 · p. 6, Figure 7 · p. 6, 2) Wall-Clock Training Efficiency and… · p. 6
  • With 16,384 transitions per iteration, 512 environments × 32 steps learns fastest early and remains among the highest-reward configurations over two hours.At 2,048 and 4,096 environments, rollouts shrink to 8 and 4 steps, truncating return estimates and slowing early learning.Source: 2) Wall-Clock Training Efficiency and… · p. 6
  • PPO falls below the released checkpoint’s path length after roughly 2 h, despite that checkpoint’s 24 h training time.Both GGRAPH-based pipelines learn shorter paths than ARiADNE SAC-16 within the same budget.Source: 2) Wall-Clock Training Efficiency and… · p. 6

3) Deployment of the Learned Policy in a High-Fidelity Simulator and the Real World:

GGRAPH-trained policies achieve competitive exploration paths in simulated outdoor and indoor environments, and the PPO policy also transfers to a real Spot robot. The evaluations include matched-coverage vehicle runs and a real-office exploration run using onboard cameras.

3) Deployment of the Learned Policy in a High-Fidelity Simulator and the Real World:

  • The simulated vehicle follows graph-selected goal nodes as waypoints, and policies are compared at equal coverage, with runs ending at 99.8%.Coverage counts 1 m cells as covered when the vehicle passes within 20 m; the map is 150 × 150 m.Source: 3) Deployment of the Learned Policy in… · p. 6
  • 1040 m: GGRAPH PPO explores the outdoor map in the shortest path, 9% shorter than ARiADNE’s released checkpoint.The policy was trained for 1.5 h with 512 robots; GGRAPH SAC drove 1139 m in 615 s, comparable to the released checkpoint’s 1143 m in 642 s.Source: 3) Deployment of the Learned Policy in… · p. 6, Figure 9 · p. 7
  • On medium and complex validation maps, PPO takes the shortest path among learned policies, while nearest-frontier fails to complete either example.The trajectory figure marks starts, final poses, and unexplored regions; DNF denotes failure to complete exploration.Source: Figure 8 · p. 7
  • In the indoor simulator, GGRAPH PPO matches ARiADNE’s path length with 1.5 h of training, compared with ARiADNE’s 24 h.The indoor map is 130 × 100 m and consists of long corridors and lobby areas.Source: 3) Deployment of the Learned Policy in… · p. 7, Figure 10 · p. 7
  • The simulation-trained PPO policy explores a real Spot office floor using onboard cameras, with a path length of 157 m.It was trained only on 2-D grid-world maps; when glass doors led to unreachable frontier nodes, connectivity checks removed them and the policy moved to reachable frontiers.Source: 3) Deployment of the Learned Policy in… · p. 7

VI. CONCLUSION

GGRAPH provides GPU-resident graph operations for deployment and policy learning, including loop-closure correction and large-scale simulation. The conclusion reports faster exploration-policy training and transfer to simulated and real robots.

VI. CONCLUSION

  • GGRAPH maintains graph operations and attribute layers on the GPU, corrects drifted graphs after loop closure in milliseconds, and steps a thousand simulated robots per tick.The same kernels build 3-D graphs and support frontier and semantic layers used by classical planners.Source: §VI · p. 7
  • GGRAPH-trained exploration policies reach baseline quality with an order of magnitude less wall-clock training time.The conclusion also reports performance against classical planners on held-out maps, TARE in simulation, and ARiADNE and GRATE at similar training budgets.Source: §VI · p. 8
  • The policy transfers to a ground vehicle in a high-fidelity simulator and to a real-world Spot robot.The real-world exploration run used onboard cameras; the policy was trained on simulated maps.Source: §VI · p. 8, Figure 11 · p. 8

Related papers

Loading 2610.28953v1…