Abstract | ||
---|---|---|
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 nonexploratory strategy using A* and discuss its relation to existing algorithms such as D* Lite, PHA* with early stopping, EWP or exploration algorithms. |
Year | Venue | DocType |
---|---|---|
2015 | IJCAI | Conference |
Citations | PageRank | References |
0 | 0.34 | 18 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fabrice Mayran de Chamisso | 1 | 0 | 0.68 |
Laurent Soulier | 2 | 0 | 1.01 |
Michaël Aupetit | 3 | 261 | 25.59 |