TY - GEN
T1 - Simple optimization techniques for a*-based search
AU - Sun, Xiaoxun
AU - Yeoh, William
AU - Chen, Po-An
AU - Koenig, Sven
PY - 2009/5/10
Y1 - 2009/5/10
N2 - 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.
AB - 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.
KW - A search
KW - Incremental heuristic search
KW - Path planning
UR - http://www.scopus.com/inward/record.url?scp=84899786361&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84899786361
SN - 9781615673346
VL - 2
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 931
EP - 936
BT - 8th International Joint Conference on Autonomous Agents and Multiagent Systems 2009, AAMAS 2009
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 8th International Joint Conference on Autonomous Agents and Multiagent Systems 2009, AAMAS 2009
Y2 - 10 May 2009 through 15 May 2009
ER -