@MASTERSTHESIS\{IMM2012-06488,
    author       = "M. B. Ettienne",
    title        = "Increasing the Efficiency and Feasibility of Automated Planning through the Specification of Domain-dependent Heuristic Information",
    year         = "2012",
    school       = "Technical University of Denmark, {DTU} Informatics, {E-}mail: reception@imm.dtu.dk",
    address      = "Asmussens Alle, Building 305, {DK-}2800 Kgs. Lyngby, Denmark",
    type         = "",
    note         = "{DTU} supervisor: Thomas Bolander, tobo@imm.dtu.dk, {DTU} Informatics",
    url          = "http://www.imm.dtu.dk/English.aspx",
    abstract     = "A* with admissible heuristics is the leading approach to optimal planning. Pattern database (PDB) heuristics are admissible heuristics based on abstractions of the search space and have recently had a breakthrough as general heuristics for automated planning. The selection of appropriate abstractions is of paramount importance to the informedness of a {PDB} heuristic. Based on a combination of novel and well-known techniques, we show how to efficiently constrain abstractions which leads to increased informedness of {PDB} heuristics. State-of-theart in {PDB} heuristics iteratively selects promising abstractions from the search space of all possible abstractions using modified local search techniques. We introduce an approach called variable pruned mutex constrained extended pattern database generation that has several theoretical advantages over the state-of-the-art approach. Some of which lead to more informed {PDB} heuristics, while others lead to reduced computation time without affecting informedness. Experimental evaluations show that our approach also improves state-of-the-art for {PDB} heuristics in practice."
}