טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentLefler Sagi
SubjectEnhancing Abstractions with Landmarks
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

The field of automated, domain-independent planning aims at building algorithms able to synthesize a course of actions to achieve certain goals and/or exhibit desirable behaviors. In general, planning algorithms perform reachability analysis in large-scale state modules that are implicitly described in a concise manner via some intuitive declaration language. The classical case attempts to transform a system with deterministic dynamics from a given initial state into a goal state. Such a planning task is defined by five elements: (1) a set of state variables and their domains, describing the possible states of the system, (2) a set of actions, or operators, defining how can we change the state of the system, (3) an initial state, given by a complete assignment to the state variable, (4) a description of goal states and (5) a real-valued, non-negative action cost function.

The state space of such a planning task is typically huge, exponential in the number of state variables. A common and successful approach to solving such tasks is heuristic state-space search. Heuristic functions are used by informed-search procedures to estimate the distance from a search node to the nearest goal node. To guarantee optimal solutions, the heuristic function must be admissible, that is, should under-estimate the distance to the goal.

A growing body of work on expanding the palette of heuristic estimators is seen in the recent years. Two powerful mechanisms for devising admissible heuristics are abstractions and landmarks. An abstraction heuristic is based on mapping the planning task transition system to an abstract transition system. The heuristic value of a state is then the distance from the corresponding state in the abstract transition system to the closest abstract goal state. Abstraction heuristics are always admissible by their very definition. Planning landmarks are facts that must be true at some point in every solution plan. Recently a method to produce admissible heuristics from landmarks was presented and shown to favorably compete with the state-of-the-art of cost-optimal heuristic search.

In this work we suggest putting both methods together by integrating landmark information into abstractions, and propose a concrete realization of this direction suitable for structural-pattern abstractions, as well as for other abstraction heuristics. Our empirical evaluation shows that landmark information can substantially improve the quality of abstraction heuristic estimates.