Tree adaptive A*

Carlos Hernández, Xiaoxun Sun, Sven Koenig, Pedro Meseguer

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

17 Citations (Scopus)

Abstract

Incremental heuristic search algorithms can solve sequences of similar search problems potentially faster than heuristic search algorithms that solve each search problem from scratch. So far, there existed incremental heuristic search algorithms (such as Adaptive A*) that make the h-values of the current A* search more informed, which can speed up future A* searches, and incremental heuristic search algorithms (such as D* Lite) that change the search tree of the current A* search to the search tree of the next A* search, which can be faster than constructing it from scratch. In this paper, we present Tree Adaptive A*, which applies to goal-directed navigation in unknown terrain and builds on Adaptive A* but combines both classes of incremental heuristic search algorithms in a novel way. We demonstrate experimentally that it can run faster than Adaptive A*, Path Adaptive A* and D* Lite, the top incremental heuristic search algorithms in the context of goal-directed navigation in unknown grids. Categories and Subject Descriptors 1.2.8 [Problem Solving, Control Methods, and Search]: [Graph and tree search strategies] General Terms Algorithms, Experimentation.

Original languageEnglish
Title of host publication10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages113-120
Number of pages8
Volume1
Publication statusPublished - 2011
Event10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011 - Taipei, Taiwan, Province of China
Duration: 2 May 20116 May 2011

Other

Other10th International Conference on Autonomous Agents and Multiagent Systems 2011, AAMAS 2011
Country/TerritoryTaiwan, Province of China
CityTaipei
Period2/05/116/05/11

Keywords

  • Agent reasoning::Planning (single and multi-agent)
  • Path planning
  • Robot reasoning::Planning

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Tree adaptive A*'. Together they form a unique fingerprint.

Cite this