Exploratory Digraph Navigation Using A

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

Exploratory Digraph Navigation Using A

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

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. 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.

Fabrice Mayran de Chamisso, Laurent Soulier, and Michaël Aupetit. 2015. Exploratory Digraph Navigation Using A. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 1624–1629. https://ijcai.org/proceedings/2015/232

@inproceedings{ijcai2015p232,
  title     = {Exploratory Digraph Navigation Using A},
  author    = {de Chamisso, Fabrice Mayran and Soulier, Laurent and Aupetit, Michaël},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {1624--1629},
  year      = {2015},
  month     = {7},
  note      = {Main Track},
  url       = {https://ijcai.org/proceedings/2015/232},
}

TY  - CPAPER
TI  - Exploratory Digraph Navigation Using A
AU  - de Chamisso, Fabrice Mayran
AU  - Soulier, Laurent
AU  - Aupetit, Michaël
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 1624
EP  - 1629
UR  - https://ijcai.org/proceedings/2015/232
ER  -