Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Léna Le Roy Connect in order to contact the contributor
Submitted on : Thursday, July 19, 2018 - 10:14:44 AM
Last modification on : Thursday, February 17, 2022 - 10:08:06 AM


  • HAL Id : cea-01844044, version 1


F.M. de Chamisso, L. Soulier, M. Aupetit. Exploratory digraph navigation using A. 24th International Joint Conference on Artificial Intelligence, IJCAI 2015, Jul 2015, Buenos Aires, Argentina. pp.1624-1630. ⟨cea-01844044⟩



Record views