@MASTERSTHESIS\{IMM2012-06221,
    author       = "S. B{\o}g",
    title        = "Graph-Theoretical Classification of the Complexities of Planning Domains",
    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         = "Supervised by Associate Professor Thomas Bolander, tb@imm.dtu.dk, {DTU} Informatics",
    url          = "http://www.imm.dtu.dk/English.aspx",
    abstract     = "Automated planning is one of the cornerstones of modern Artificial Intelligence (AI). As with many of the fields within {AI,} automated planning is something we do naturally as humans yet is extremely hard to do computationally, this seems paradoxical. Therefore there is much interest in determining under what conditions automated planning is easy. This thesis examines the use of the state graph of planning problems to define conditions on automated planning. As a part of this two new cases are presented where planning is easier than full automated planning and in one of the cases actually tractable."
}