Stronger abstraction heuristics through perimeter search

Eyerich, Patrick and Helmert, Malte. (2013) Stronger abstraction heuristics through perimeter search. In: Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013) : [held 10 - 14 June 2013 in Rome, Italy]. Palo Alto, Calif., pp. 303-307.

PDF - Published Version

Official URL: http://edoc.unibas.ch/dok/A6212200

Downloads: Statistics Overview


Perimeter search is a bidirectional search algorithm consisting of two phases. In the first phase, a limited regression search computes the perimeter, a region which must necessarily be passed in every solution. In the second phase, a heuristic forward search finds an optimal plan from the initial state to the perimeter. The drawback of perimeter search is the need to compute heuristic estimates towards every state on the perimeter in the forward phase. We show that this limitation can be effectively overcome when using pattern database (PDB) heuristics in the forward phase. The combination of perimeter search and PDB heuristics has been considered previously by Felner and Ofek for solving combinatorial puzzles. They claimed that, based on theoretical considerations and experimental evidence, the use of perimeter search in this context offers "limited or no benefits". Our theoretical and experimental results show that this assessment should be revisited.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:19 Nov 2018 16:18
Deposited On:23 May 2014 08:34

Repository Staff Only: item control page