Neural Online Graph Exploration
  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.
