Neural Online Graph Exploration
This work tackles the problem of efficient unknown space exploration for autonomous agents, offering a data-driven approach to an online version of the Traveling Salesperson Problem.
This paper addresses the Online Graph Exploration problem by reformulating it as a reinforcement learning task. The authors applied Direct Future Prediction to this problem, demonstrating that their agent can learn exploration strategies that outperform several well-known graph traversal algorithms on both procedurally generated graphs and real city road networks.
Can we learn how to explore unknown spaces efficiently? To answer this question, we study the problem of Online Graph Exploration, the online version of the Traveling Salesperson Problem. We reformulate graph exploration as a reinforcement learning problem and apply Direct Future Prediction (Dosovitskiy and Koltun, 2017) to solve it. As the graph is discovered online, the corresponding Markov Decision Process entails a dynamic state space, namely the observable graph and a dynamic action space, namely the nodes forming the graph's frontier. To the best of our knowledge, this is the first attempt to solve online graph exploration in a data-driven way. We conduct experiments on six data sets of procedurally generated graphs and three real city road networks. We demonstrate that our agent can learn strategies superior to many well known graph traversal algorithms, confirming that exploration can be learned.