טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentMirkis Vitaly
SubjectAbstractions and Approximations for Oversubscription
Planning
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Carmel Domshlak
Full Thesis textFull thesis text - English Version


Abstract

In deterministic oversubscription planning (OSP), the objective is to achieve an as valuable as possible subset of goals within a fixed allowance of the total action cost.

Although numerous applications in various fields share this objective, no substantial algorithmic advances have been made in deterministic OSP, and this in contrast to a tremendous progress that has been achieved in the area of classical deterministic planning. Tracing the key sources of progress in classical planning, we identify a severe lack of effective domain-independent approximations for OSP.

With our focus here on optimal planning, two classes of approximation techniques have been found especially useful in the context of optimal classical planning: those based on state-space abstractions

and these based on logical landmarks for goal reachability. The question we study here is whether some similar-in-spirit, yet possibly mathematically different, approximation techniques can be developed for OSP.

In the context of abstractions, we define the notion of additive abstractions for OSP, study the complexity of deriving effective abstractions from a rich space of hypotheses, and reveal some substantial, empirically relevant islands of tractability. In the context of landmarks, we show how standard goal-reachability landmarks of certain classical planning tasks can be compiled into the OSP task of interest, resulting in an equivalent OSP task with a lower cost allowance, and thus with a smaller search space.

Our empirical evaluation confirms the effectiveness of the proposed techniques, and opens a wide gate for further developments in oversubscription planning.