Position paper: Incremental search algorithms considered poorly understood

Carlos Hernández, Jorge Baier, Tansel Uras, Sven Koenig

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)

Abstract

Incremental search algorithms, such as D* Lite, reuse information from previous searches to speed up the current search and can thus solve sequences of similar search problems faster than Repeated A*, which performs repeated A* searches. In this position paper, we study goal-directed navigation in initially unknown terrain and point out that it is currently not well understood when D* Lite runs faster than Repeated A*. In general, it appears that Repeated A* runs faster than D* Lite for easy navigation problems (where the agent reaches the goal with only a small number of searches), which means that it runs faster than D* Lite quite often in practice. We draw two conclusions, namely that incremental search algorithms need to be evaluated in more diverse testbeds to improve our understanding of their properties and that they can be improved to be more competitive for easy navigation problems.

Original languageEnglish
Title of host publicationProceedings of the 5th Annual Symposium on Combinatorial Search, SoCS 2012
Pages159-161
Number of pages3
Publication statusPublished - 2012
Event5th International Symposium on Combinatorial Search, SoCS 2012 - Niagara Falls, ON, Canada
Duration: 19 Jul 201221 Jul 2012

Other

Other5th International Symposium on Combinatorial Search, SoCS 2012
Country/TerritoryCanada
CityNiagara Falls, ON
Period19/07/1221/07/12

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Position paper: Incremental search algorithms considered poorly understood'. Together they form a unique fingerprint.

Cite this