---
title: "Exploratory Digraph Navigation Using A"
authors:
  - "Fabrice Mayran de Chamisso"
  - "Laurent Soulier"
  - "Michaël Aupetit"
doi: ""
url: "https://ijcai.org/proceedings/2015/232"
pdf: "https://ijcai.org/proceedings/2015/0232.pdf"
venue: "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence"
year: 2015
pages: "1624-1629"
track: "Main Track"
keywords:
---

# Exploratory Digraph Navigation Using A

Fabrice Mayran de Chamisso, Laurent Soulier, Michaël Aupetit

*Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence*, pages 1624-1629.

## 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.