Learning Shortest Paths with Generative Flow Networks

Abstract:In this paper, we present a novel learning framework for finding shortest paths in graphs utilizing Generative Flow Networks (GFlowNets). First, we examine theoretical properties of GFlowNets in non-acyclic environments in relation to shortest paths. We prove that, if the total flow is minimized, forward and backward policies traverse the environment graph exclusively along shortest paths between the initial and terminal states. Building on this result, we reduce shortest-path finding in an arbitrary unweighted graph to finding a non-acyclic GFlowNet with minimal total flow, and approximate it in practice by training with flow regularization. We experimentally demonstrate the performance of our method in pathfinding in permutation environments and in solving Rubik's Cubes of various sizes. For the latter problems, our approach shows competitive results with state-of-the-art machine learning approaches designed specifically for this task in terms of the solution length, while requiring smaller search budget at test-time.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Machine Learning (stat.ML)

arXiv:2603.01786 [cs.LG]

(or arXiv:2603.01786v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2603.01786 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.