论文标题
神经在线图探索
Neural Online Graph Exploration
论文作者
论文摘要
我们可以学习如何有效地探索未知空间吗？为了回答这个问题，我们研究了在线图探索的问题，这是旅行销售人员问题的在线版本。我们将图形探索作为强化学习问题进行了重新制定，并应用了直接的未来预测（Dosovitskiy and Koltun，2017年）来解决它。当图形在线发现时，相应的马尔可夫决策过程需要动态状态空间，即可观察的图和动态动作空间，即形成图形边界的节点。据我们所知，这是以数据驱动方式求解在线图探索的首次尝试。我们对六个数据集的程序生成图和三个真实的城市道路网络进行实验。我们证明，我们的代理可以学习优于许多众所周知的图形遍历算法的策略，从而证实可以学习探索。
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.
