טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMuller Daniel
SubjectPlanning Value Driven Action Landmarks in Over-Subscription
Decision-Making Systems with Arbitrarily Additive
General Utility Functions
DepartmentDepartment of Industrial Engineering and Management
Supervisor Dr. Erez Karpas


Abstract

Over-subscription planning (OSP) problem is a real-life problem of choosing an action sequence to reaches a state with a high utility, given a limited budget for total action cost. 

Most previous work on OSP assumed state variables with non-negative utility functions and 0-binary utility functions. While this utility setting allows using techniques similar to classical and partial-satisfaction planning, it limits the real expressivity of actions and utility formalism. In this work, we address OSP domains with arbitrarily additive general utility functions representation. We introduce the notions of the net and gross utility value of actions which provide a more comprehensive context of achievements evaluation and allows sustainability of solvers in domains with arbitrarily additive and negative utility value functions settings. Focused on the net utility, we capture relationships, inter- and intra-state dependencies between sets of state variables and handle negative interactions that occur in domains with non-negative utility settings as well. We use the notions of gross and net utility to examine the structure of plans on the level of action and sequences of operations and prove the ordinal and structural properties of a planned process for improvement as well as optimality of plans with arbitrarily additive general utilities.


To leverage the effectiveness of structural properties for improvement process, we introduce a compilation of an OSP task to classical planning, which forces a plan to conform to a method of improvement. The landmarks of this classical planning task constitute value driven landmarks to guide a process of improvement in the OSP complexity. These guiding landmarks must occur in every plan that improves over the utility of a given state with arbitrarily additive utility propositions.

We also introduce a value-driven solver with observations on domains with arbitrarily additive general utility state propositions and the utility of action functions in OSP optimization problem. Our empirical evaluations show that our approach allows for a substantial reduction in search effort in problems with arbitrarily additive general utility propositions due to the expressiveness of utility functions over actions. The value-driven landmarks are more informative in activities than previous state-of-the-art methods for landmark discovery for OSP and lead to overall, better search guidance and planning performance in domains with non-negative utility assumption as well. This thesis provides a theory and proves mathematically and empirically that classical and over-subscription planning better performed when combined in a mutually-stratifying way. This observation termed in this work as ``synergistic-criteria" for improvement process and defines a valuable investment with temporal ``window of opportunity to improve" and as ``prefix-suffix overlap" in future workflows.