Simple optimization techniques for a*-based search

Xiaoxun Sun, William Yeoh, Po-An Chen, Sven Koenig

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

8 Scopus citations

Abstract

In this paper, wo present two simple optimizations that can reduce the number of priority queue operations for A* and its extensions. Basically, when the optimized search algorithms expand a state, they check whether they will expand a successor of the state next. If so, they do not first insert it into the priority queue and then immediately remove it again. These changes might appear to be trivial but are well suited for Generalized Adaptive A*, an extension of A*. Our experimental results indeed show that they speed up Generalized Adaptive A* by up to 30 percent if its priority queue is implemented as a binary heap.

Original languageEnglish
Title of host publication8th International Joint Conference on Autonomous Agents and Multiagent Systems 2009, AAMAS 2009
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages696-701
Number of pages6
ISBN (Print)9781615673346
StatePublished - 1 Jan 2009
Event8th International Joint Conference on Autonomous Agents and Multiagent Systems 2009, AAMAS 2009 - Budapest, Hungary
Duration: 10 May 200915 May 2009

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume1
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Conference

Conference8th International Joint Conference on Autonomous Agents and Multiagent Systems 2009, AAMAS 2009
CountryHungary
CityBudapest
Period10/05/0915/05/09

Keywords

  • A* search
  • Incremental heuristic search
  • Path planning

Cite this