Graph-Theoretical Classi fication of the Complexities of Planning Domains



AbstractAutomated 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.
TypeMaster's thesis [Academic thesis]
Year2012
PublisherTechnical University of Denmark, DTU Informatics, E-mail: reception@imm.dtu.dk
AddressAsmussens Alle, Building 305, DK-2800 Kgs. Lyngby, Denmark
SeriesIMM-M.Sc.-2012-01
NoteSupervised by Associate Professor Thomas Bolander, tb@imm.dtu.dk, DTU Informatics
Electronic version(s)[pdf]
Publication linkhttp://www.imm.dtu.dk/English.aspx
BibTeX data [bibtex]
IMM Group(s)Computer Science & Engineering