Exploratory digraph navigation using A - Archive ouverte HAL Access content directly
Conference Papers Year : 2015

Exploratory digraph navigation using A

(1) , (1) , (2)
1
2

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.
Not file

Dates and versions

cea-01844044 , version 1 (19-07-2018)

Identifiers

  • HAL Id : cea-01844044 , version 1

Cite

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⟩
51 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More