טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMilostov Rinat
SubjectEnhancements of Abstraction Heuristics for Optimal
Sequential Planning
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 to build algorithms that are able to solve general tasks by synthesizing a course of actions in order to achieve certain goals. Planning algorithms perform reachability analysis in large-scale state spaces that are implicitly described in a concise manner via some intuitive declaration language.

The classic planning task description includes: a set of variables and a finite domain for each variable, a set of deterministic actions that changes variables' values, an initial state (full variable assignment) and a formal specification of goal states.

Typically we will try to solve this task by finding a sequence of actions that takes us from the initial state to some goal state. In optimal planning we try to find the shortest possible sequence.

The state space of such a planning task is typically huge, exponential in the number of state variables. In order to overcome this difficulty, we use a heuristic state-space search. This kind of approach involves some kind of search algorithm and a heuristic function. The heuristic function estimates the distance between a search node to the nearest goal node. Algorithms for optimal planning tasks use admissible (lower bound) heuristics in order to correctly direct the search and insure the optimality of the solution.

One of the powerful mechanisms for producing admissible heuristics are abstractions. An abstraction heuristic is based on mapping the planning task transition system to an abstracted transition system that is typically smaller. The heuristic value of a state is the distance from the corresponding state in the abstracted transition system to the closest abstracted goal state. By their definition, abstraction heuristics are always admissible.

There are several successful approaches to deriving abstraction-based heuristics, and here we focus on one of them, namely the merge-and-shrink abstractions.

Analyzing strengths and weaknesses of the merge-and-shrink abstractions, our primary objective in this work was to increase the accuracy of the induced heuristics by refining the strategy for the merge-and-shrink abstraction generation algorithm. We found that, in some cases, the current merge-and-shrink strategy wrongly decreases heuristic value by poor choices in the shrink step (regarding which states to shrink together) that creates "shortcuts" to the goal. We identify such cases, suggest approaches to avoid them, and conduct an experimental validation of our proposal.