M.Sc Student | Lefler Sagi |
---|---|

Subject | Enhancing Abstractions with Landmarks |

Department | Department of Industrial Engineering and Management |

Supervisor | Professor Carmel Domshlak |

Full Thesis text |

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.