Exploratory digraph navigation using A

We describe Exploratory Digraph Navigation as a fundamental problem of graph theory concerned with using a graph with incomplete edge and vertex information for navigation in a partially unknown environment. We then introduce EDNA^∗, a simple A^∗ extension which provably solves the problem and give worst-case bounds on the number of edges explored by said algorithm. We compare the performance of this algorithm to a non-exploratory strategy using A^∗ and discuss its relation to existing algorithms such as D^∗ Lite, PHA^∗ with early stopping, EWP or exploration algorithms.