Learning Transferable Graph Exploration
It addresses the challenge of generalizing exploration strategies for AI systems in real-world applications such as software testing and map building, representing an incremental advance in transfer learning for graph exploration.
The paper tackles the problem of efficient exploration in unseen graph-structured environments by learning a transferable policy from a distribution of environments, achieving superior performance over hand-engineered methods in tasks like software testing and mobile applications.
This paper considers the problem of efficient exploration of unseen environments, a key challenge in AI. We propose a `learning to explore' framework where we learn a policy from a distribution of environments. At test time, presented with an unseen environment from the same distribution, the policy aims to generalize the exploration strategy to visit the maximum number of unique states in a limited number of steps. We particularly focus on environments with graph-structured state-spaces that are encountered in many important real-world applications like software testing and map building. We formulate this task as a reinforcement learning problem where the `exploration' agent is rewarded for transitioning to previously unseen environment states and employ a graph-structured memory to encode the agent's past trajectory. Experimental results demonstrate that our approach is extremely effective for exploration of spatial maps; and when applied on the challenging problems of coverage-guided software-testing of domain-specific programs and real-world mobile applications, it outperforms methods that have been hand-engineered by human experts.