@inproceedings{eyerich-helmert:icaps-2013,
   author = "Patrick Eyerich and Malte Helmert",
   title = "Stronger Abstraction Heuristics Through Perimeter Search",
   booktitle = "Proceedings of the 23rd International Conference on
                  Automated Planning and Scheduling (ICAPS13)",
   month = "june",
   year = "2013",
   publisher = "AAAI Press",
   abstract =  "Perimeter search is a bidirectional search algorithm
                  consisting of two phases. In the first phase, a
                  limited regression search computes the
                  \emph{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 \emph{every} state on the
                  perimeter in the forward phase. We show that this
                  limitation can be effectively overcome when using
                  \emph{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."
}