# Technical Report for the Paper on Value Driven Landmarks for Oversubscription Planning

A detailed technical report of out ICAPS 2018 paper Value Driven Landmark for Oversubscription Planning is available. In the technical report, we provide detail examples of the theory in the paper. We look closely at the terms of optimality and achievements concerning the complexity of the real-world scenarios. ICAPS 2018 Slides of our presentation along with supplementary material can be found at the publication page.
Starting with the most fundamental question of what additive utility function in OSP problem is, we point out the challenges in multi-valued planning tasks with additive utility setting. We discuss the relationships between state variables and different value assignments to a variable in successive states along a plan. We closely consider negative interactions between state variables with multi-valued (non-zero binary) utility setting, and we show how these negative interactions could occur in tasks with non-negative utility setting.
We treat the OSP task as a process of improvement of the initial state rather than a process of collecting valuable facts is the most basic fundamental of our approach. In contrast to classical planning and partial satisfaction problems where there is one explicit assignment for each variable that is defined as valuable, OSP with additive utility functions allows for each variable to be associated with a set of different utilities. Thus, in the additive utility case, a variable assignment is valuable if its utility is better than the utility at the initial state, where an optimal solution will be the maxima(red circle) l utility over all variables that are {\em mutually consistent}. Therefore, it is easy to see that the concept of {\em improving states} rather than collecting valuable facts is much more suitable for the general case.
In order to capture the properties of the process, we define the net and gross term for the utility of actions which allow us to evaluate achievements with relative terms within the ongoing process of utility maximization. Each process that improves utility must agree with a few several structural properties of optimal. We can define these properties over process due to the definition of the net and gross actions. Finally, we represent these properties with Value-Driven Landmarks, These Value Landmarks are domain-independent (can be applied in each task if sequential decisions or actions), and lead to better performance, sometimes, as you can see in the attached image, without a search at all.
The red circle emphasizes the tasks that solved without search since no plan that meets optimal properties as applicable. In real-world scenarios that involve budget thus is very likely to happen at some point during the search.

Oversubscription action planning with value landmarks – Empirical evaluation of the improving approach

Stay tuned, we will keep update here the progress of our research and if you find that problem interesting, let us know, there is a lot of work and we will be more than happy to collaborate.

We will soon post a call for collaboration with some of our suggestions.

# Introduction to our research on oversubscription planning – OSP

Introduction

Oversubscription planning termed by D. Smith (2004), also referred to as OSP, deals with achieving a state with a high utility value, given a budget on total action cost. This formulation allows us to handle situations with under-constrained resources, which do not allow us to achieve all possible goal facts. OSP objective differs from classical planning objective, in which the objective is to find a cheap plan which achieves all goal facts. In optimal OSP and optimal classical planning, the tasks are further constrained to finding a path which achieves a state with maximal utility, and, to finding the cheapest cost path which achieves the goal, respectively.

Over the years, the theory and practice of classical planning have been studied and advanced much more intensively compared to OSP. Recent work (Mirkis & Domshlak 2013,2014; Domshlak & Mirkis 2015) made several contributions aiming at improving the scalability of OSP solvers. In particular, they developed a planner which exploits standard landmark discovery tools of classical planning, as well as abstractions for solving OSP problems. They showed how standard goal-reachability landmarks of certain classical planning tasks could be generated to represent achievements of valuable facts of the original OSP task. These landmarks compiled into the original OSP task to obtain an equivalent OSP task with a lower cost allowance, and thus with a smaller effective search space. In this research, we investigate approximation methods for OSP, aiming at extending the scope of the landmark-based approximations for OSP, as well as on improving the scalability of the state-space search driven by these approximations. We propose techniques which allow us to discover more informative landmarks than previous methods. Furthermore, our techniques are applicable for OSP tasks generalized to additive utility setting.

Starting with the most basic question of what additive utility function in OSP problem is, we point out the challenges in multi-valued planning tasks with additive utility setting. We discuss the relationships between state variables and different value assignments to a variable in successive states along a plan. We closely consider negative interactions between state variables with multi-valued (non-zero binary) utility setting, and we show how these negative interactions could occur in tasks with non-negative utility setting. We introduce a novel heuristic search approach to address additive utility OSP tasks which differs from the traditional automated action planning approach in the sense of interpretation of the objective of planning for valuable facts. With our focus on improving state-variables rather than on collecting valuable facts, we define the utility of actions. Investigation of planning tasks and their utility structure with the utility of action definition in hand allowed us to discover properties of optimal plans on the level of actions and sequences of actions. A synergistic combination of these properties allows handling OSP additive utility functions over multi-valued variables.

# Check out our paper in ICAPS 2018

Our paper on Value Driven Landmarks for Oversubscription Planning [1] is presented in the International Conference on Automated Planning and Scheduling  – ICAPS 2018

Oversubscription planning is the problem of choosing an action sequence which reaches a state with a high utility, given a budget for total action cost. Most previous work on oversubscription planning was restricted to only non-negative utility functions and 0-binary utility functions. While this restriction allows using techniques similar to partial satisfaction planning, it limits the expressivity of the formalism. In this paper, we address oversubscription planning with general additive utility functions over a finite-domain representation. We introduce the notions of net utility of an action, and of a gross positive action. Using these notions, we prove several properties about the structure of an optimal plan, which are then compiled into a classical planning problem. The landmarks of this classical planning problem are value driven landmarks of the original oversubscription problem, that is, they must occur in any action sequence which improves utility. An empirical evaluation demonstrates that these landmarks are more informative than previous state-of-the-art methods for landmark discovery for oversubscription planning, and lead to better planning performance.

[1] D. Muller and E. Karpas, “Value driven landmarks for oversubscription planning.,” in Icaps, 2018.
[Bibtex]
@inproceedings{muller:Karpas:icaps18,
title={Value Driven Landmarks for Oversubscription Planning.},
author={Muller, Daniel and Karpas, Erez},
booktitle={ICAPS},
year={2018}
}