TY - GEN
T1 - Exploratory digraph navigation using A
AU - De Chamisso, Fabrice Mayran
AU - Soulier, Laurent
AU - Aupetit, Michael
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84949758596&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84949758596
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 1624
EP - 1630
BT - IJCAI 2015 - Proceedings of the 24th International Joint Conference on Artificial Intelligence
A2 - Wooldridge, Michael
A2 - Yang, Qiang
PB - International Joint Conferences on Artificial Intelligence
T2 - 24th International Joint Conference on Artificial Intelligence, IJCAI 2015
Y2 - 25 July 2015 through 31 July 2015
ER -