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 metadatas

https://hal-cea.archives-ouvertes.fr/cea-01844044
Contributor : Léna Le Roy <>
Submitted on : Thursday, July 19, 2018 - 10:14:44 AM
Last modification on : Monday, February 10, 2020 - 6:14:16 PM

Identifiers

  • HAL Id : cea-01844044, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

69