טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentPerel Anna
SubjectTractable Fragments of Makespan-optimal Classical Planning
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

In the field of classical planning nowadays heuristic state-space search is a common and successful approach to both satisficing and optimal planning. Apart from the choice of the search algorithm, heuristic-search solvers for optimal planning differ mainly in their admissible heuristic estimators. Recent years have seen a growing body of work on expanding the palette of admissible heuristic estimators for cost-optimal planning. To date, various

abstraction heuristics, and in particular, implicit abstraction heuristics, constitute state of the art in cost-optimal planning. With implicit abstractions, the abstract transition systems gets defined indirectly by transforming the original planning problem into an instance of a tractable fragment of optimal planning. Focusing on the idea of implicit abstractions, we investigate the computational complexity of various fragments of makespan-optimal planning, characterized by the topology of various graphical structures induced by the planning problems (such as, e.g., the causal graphs and domain transition graphs), and the arity of the problem's variable domains. In this work we present computational tractability analysis of makespan-optimal planning fragments that correspond to previously studied tractable fragments of cost-optimal planning. We show that, while for some of these fragments, tractability holds in makespan-optimizing setting, for other, the problem becomes NP-hard.