An Empirical Study of GNN-Based Heuristics in Robotic Tasks

Advisor: Ulzhalgas Rakhman

Supervisor: Prof. Hector Geffner

Level: Bachelor’s Thesis

Topic

In robotic planning, efficiently finding sequences of actions to reach a goal state is a central challenge. Heuristics play a critical role in guiding search algorithms, and recent work has shown that Graph Neural Networks (GNNs) can learn heuristics directly from structured representations of planning problems. These learned heuristics have the potential to generalize across different tasks, problem sizes, and robotic domains.

The goal of this thesis is to study and evaluate GNN-based heuristics for robotic planning tasks, using the OGBench benchmark suite as a primary testing environment. You will work on adapting existing GNN architectures for numeric and robotic planning tasks, constructing graph-based representations of planning problems, and integrating these heuristics into search-based planning frameworks.

Your work will focus on empirical evaluation: assessing how well GNN heuristics guide search, analyzing their generalization across tasks and domains, and comparing their performance with classical heuristic methods. This thesis offers a combination of practical experimentation, and insights into the strengths and limitations of GNN-based heuristics for robotic tasks.

Goals

1. Test existing heuristics or/and policy learning approaches and evaluate their suitability in our setting.
2. Encode OGBench tasks as graphs suitable for GNN input, including numeric and relational features.
3. Investigate how well the heuristics generalize to unseen tasks and larger problem instances within robotic planning domains.

What we expect

• Good knowledge of Graph Neural Networks, Search Algorithms, Classical Planning etc.
• Good Python skills
• Experience with Linux and ROS/ROS2

Interested?

Please contact Ulzhalgas Rakhman and provide a short CV and a transcript of records.

References

[1] S. Park et al., “OGBench: Benchmarking Offline Goal-Conditioned RL”, The Thirteenth International Conference on Learning Representations (ICLR 2025), doi: 10.48550/arXiv.2410.20092.

[2] V. Borelli et al., “Learning Heuristics with Graph Neural Networks for Numeric Planning”, Proceedings of the International Symposium on Combinatorial Search, 18(1), 251-252, doi: 10.1609/socs.v18i1.36003.

[3] S. Stahlberg, “Learning Generalized Policies without Supervision Using GNNs”, In Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, volume 19, 474–483.