Exploratory Digraph Navigation Using a
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 non-exploratory strategy using A* and discuss its relation to existing algorithms such as D* Lite, PHA* with early stopping, EWP or exploration algorithms.
Cite
Text
de Chamisso et al. "Exploratory Digraph Navigation Using a." International Joint Conference on Artificial Intelligence, 2015.Markdown
[de Chamisso et al. "Exploratory Digraph Navigation Using a." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/dechamisso2015ijcai-exploratory/)BibTeX
@inproceedings{dechamisso2015ijcai-exploratory,
title = {{Exploratory Digraph Navigation Using a}},
author = {de Chamisso, Fabrice Mayran and Soulier, Laurent and Aupetit, Michaël},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {1624-1630},
url = {https://mlanthology.org/ijcai/2015/dechamisso2015ijcai-exploratory/}
}