Seminar Slides (2016) on Deterministic Oversubscription Action Planning with General Utility Functions

I started my work on the complex but fascinating Oversubscription planning (OSP) problem at Merch 2014.  In 2016 I have finalized my observations on oversubscription action planning with negative value effects which are captured in the more general term of planning with negative utility functions in my master thesis. Since most of the current work on OSP was concerned with 0-binary and non-negative utility functions, the novel results on planning with negative utility functions were uncomparable with the existing state-of-the-art at the time. Although real-world problems involve negative effects and actions with implicit and explicit negative utilities as in OSP problem it was quite difficult to show along the way the importance of this problem. The result of this work was published only in 2018 in a paper on Value Driven Landmarks for Oversubscription Planning. In my recent paper on “Economics of Human-AI Ecosystem: Value Bias and Lost Utility in Multi-Dimensional Gaps” I discuss the importance of real-world problem solving more deeply.

Two years after this seminar and about three years after writing that thesis, I am still struggling to publish the same old work…

My Seminar abstract from 2016 is available here

Seminar slides from 2016 are available here

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. In contrast to classical planning setup in which the objective is to achieve one of the equally attractive goal states at as low total action cost as possible, algorithmic progress in OSP has been rather slow. Recently, Mirkis and Domshlak (2014) investigated approximation techniques aiming at improving the scalability of OSP solvers, showing how standard goal-reachability landmarks of certain classical planning tasks can be compiled into an OSP task of interest, resulting in an equivalent OSP task with a lower cost allowance, and thus with a smaller search space. Based on this observation they introduced an effective framework for exploiting such landmarks in heuristic-search OSP.
The major limitation of the techniques developed by Mirkis and Domshlak was the restriction to only non-negative utility functions. In this work, we extend the scope of the landmark-based approximations to OSP problems with general utility functions and improve the scalability of the state-space search driven by these approximations. In particular, we define the notion of ‘net utility of an action’ which allows us to alleviate the dependence on value non-negativity, as well as captures relationships between state variables and different value assignments to a variable in successive states in a plan. Focusing on the net utility of an action we propose a novel framework for exploiting goal-reachability landmarks in problems with general utility functions, addressing both coverage and scalability aspects of heuristic-search OSP.
Our empirical evaluation shows that our approach allows for substantial reductions in search effort in problems with general utility functions, confirms the effectiveness of the proposed techniques in the private case of OSP problem with non-negative rewards as well, and opens a wide gate for further developments in oversubscription planning.

Oversubscription Planning Seminar Slide 2016:

(I added to the original slides two animation explainers from the recent year on the second slide to make a friendly introduction to the problem)

 

Previous version of the same abstract (2016)

Deterministic Oversubscription Action Planning with Negative Value Effects

While in classical planning the objective is to achieve one of the equally attractive goal states at as low total action cost as possible, In the basic setup of 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 the latter objective, no substantial algorithmic advances have been achieved over the years in deterministic OSP, compared to classical planning.

Recently, Mirkis and Domshlak (2014) investigated approximation techniques aiming at improving the scalability of OSP solvers, showing how standard goal-reachability landmarks of certain classical planning tasks can be compiled into an OSP task of interest, resulting in an equivalent OSP task with a lower cost allowance, and thus with a smaller search space. Based on this observation they introduced an effective framework for exploiting such landmarks in heuristic-search OSP. While this framework deals oversubscription planning problems with non-negative utility functions, problems with general utility function haven’t been addressed yet.

In this work, we continue the investigation of approximation techniques to improve the scalability of OSP solvers. We extend the scope of the landmark-based approximations to OSP problems with general utility functions and improve the scalability of the state-space search driven by these approximations with our focus on their accuracy.

In particular, we define the notion of a ‘net utility of an action’ which allows us to alleviate the dependence on value non-negativity, as well as capture inter-variable interaction and intra-variable assignment interactions, which hold an important role in utility-based orderability and comparability of states in OSP. Having the expressive power obtained when the focus is on actions, we are able to measure the utility of OSP plans (or states) in a wider context, and hence, produce more informed and accurate approximations, which leads to an effective search space and search effort reduction.

Focusing on the net utility of an action we propose a novel framework for exploiting such landmarks in problems with general utility functions, addressing both, coverage and scalability aspects of heuristic-search OSP.

Our empirical evaluation shows that our approach allows for substantial reductions in search effort in problems with general utility functions, confirms the effectiveness of the proposed techniques in the private case of OSP problem with non-negative rewards as well, and opens a wide gate for further developments in oversubscription planning.

Leave a Reply

Your email address will not be published. Required fields are marked *