Learning Shortest Paths with Generative Flow Networks

Researchers present a novel framework using Generative Flow Networks (GFlowNets) to solve shortest path problems in graphs. The method proves that minimizing total flow forces GFlowNets to traverse only shortest paths, demonstrating competitive performance in pathfinding tasks including solving Rubik's Cubes with smaller search budgets than existing approaches.

• →GFlowNets can be theoretically proven to find shortest paths when total flow is minimized in non-acyclic environments.
• →The pathfinding problem in arbitrary graphs can be solved by training non-acyclic GFlowNets with flow regularization.
• →The method shows competitive results with state-of-the-art approaches for solving Rubik's Cubes while requiring smaller search budgets.
• →Experimental validation includes pathfinding in permutation environments and complex puzzle-solving tasks.
• →This approach bridges theoretical graph theory with practical machine learning applications for optimization problems.