טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAnton Nazarenko
SubjectParametric Complexity of Monotonic Relaxations
DepartmentDepartment of Industrial Engineering and Management
Supervisor Full Professor Domshlak Carmel
Full Thesis textFull thesis text - English Version


Abstract

For almost two decades, monotonic, or “delete free,” relaxation has been one of the key auxiliary tools in the practice of domain-independent deterministic planning. In particular, monotonic relaxation underlies most state-of-the-art heuristic functions in the context of both satisficing and cost-optimal planning. While satisficing planning for monotonic tasks is polynomial-time, cost-optimal planning for monotonic tasks is NP-equivalent. We investigate the worst-case time complexity of cost-optimal monotonic planning in the context of finite-domain representation of planning tasks. We establish both negative and positive results on the complexity of some wide fragments of cost-optimal monotonic planning, with the former stressing the role of the structure of state variable domains, and the latter stressing the role of the causal graph topology. Our results shed some light on the link between the complexity of general cost-optimal planning and the complexity of cost-optimal planning for the respective monotonic relaxations.