טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentBahumi Roei
SubjectDeeply Preferred Operators: Lazy Search Meets Lookahead
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

At the center of the problem of intelligent autonomous behavior is the task of action selection, and AI planning is the model-based computational approach to this task. The models represent the initial situation, actions, sensors, and goals. Planning-specific languages are used to describe such models concisely. The main challenge in planning is computational since even the most conservative planning models are intractable in the worst case. However, using sophisticated search algorithms and rigorous search guiding tools, practically interesting instances of even intractable models can often be solved very efficiently.

Heuristic in state-space search is one of the most prominent approaches to domain independent planning. Traditionally, heuristics are used to estimate the distance from states to the goal. In domain-independent heuristic search planning, using extra information derived from the heuristic computation to mark some successors as preferred, and then biasing the search towards the preferred successors, resulted in significant improvements in planning performance.

Preferred operators, however, help to discriminate only between the immediate successors of the evaluated state. In addition, although relaxed planning satisficing and the derivation of preferred operators is polynomial in time, modern planning systems end up spending at least 85% of their search time on calculating heuristic values.

In this work, we propose a technique that takes advantage of more of the information provided by the heuristic computation. This technique consists of two components. The first component corresponds to a generalization of the notion of preferred operators to what we call deeply preferred operators. This generalization allows for exploiting even more information provided by the heuristic, preferring descendants of the state being evaluated at various depths. The second component corresponds to a suitable generalization of deferred heuristic evaluation, also known as lazy search, to such ``deeply preferred'' descendants. A picturesque description of our technique can be viewed as a depth drill into the search space that, when accurate, can significantly reduce the number of heuristic evaluations for states at various depths, not just in the last layer of the search.

Our empirical evaluation demonstrates that this technique results in performance improvement over using standard preferred operators within lazy search; it significantly reduced the runtime and memory usage, and even increases the number of planning tasks being solved within the standard runtime allowance.