|M.Sc Student||Nazarenko Anton|
|Subject||Parametric Complexity of Monotonic Relaxations|
|Department||Department of Industrial Engineering and Management||Supervisor||Professor Carmel Domshlak|
|Full Thesis text|
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.