OSP Background



We begin by surveying the necessary background for describing our work. For \(k\in {\mathbb N^{+}}\), by \([k]\) we denote the set \(\{1,2,…,k\}\). The indicator function of a subset \(A\) of a set \(X\) is a function \({\mathbb{1}}_{A} : X \rightarrow \{0,1\}\) defined as \({\mathbb{1}}_{A}(x) = 1\) if \(x \in A\) and \({\mathbb{1}}_{A}(x) = 0\) if \(x \not\in A\). Following [1], the size of a well-defined mathematical object \(x\). The size of a (reasonable) encoding of \(x\) is detonated as \(||x||\).

Over-Subscription Planning (OSP)

In what follows we adopt the OSP model representation of [2],  adopting a language close to the \({sas}^{+}\) language for classical planning [3, 4]. A deterministic oversubscription planning (OSP) task is given by a sextuple : \(\Pi = \langle V,s_0,u;A,c,b\rangle,\) where

  1. \(V = \{v_{1},…,v_{n}\}\) is a finite set of finite-domain state variables, with each complete assignment to \(V\) representing a state, and \(S = dom(v_1)\times….\times dom(v_n)\) being the state space of the task;
  2. \(s_0 \in S\) is a designated initial state;
  3. \(u\) is an efficiently computable state value function \(u :  U \rightarrow{\mathbb R}^{0+}\);
  4. \(A\) is a finite set of actions, with each operator \(a \in A\) represented by a pair \(\langle pre(a),eff(a)\rangle\) of partial assignments to \(V\), called preconditions and effects of \(a\), respectively;
  5. \(c : A \rightarrow {\mathbb R}\) is an operator cost function;
  6. \(b \in {\mathbb R}\) is a cost budget allowed for the task.

An assignment of a variable \(v\) to value \(d\) is denoted by \(\left< v/d \right>\); we often refer to such single variable assignments as propositions. For a partial assignment \(p\) to \(V\), let \({\cal V}(p) \subseteq V\) denote the subset of variables instantiated by \(p\), and, for \(v\in {\cal V}(p)\), \(p[v]\) denote the value provided by \(p\) to the variable \(v\). Action \(a\) is applicable in a state \(s\) iff \(s[v] = pre(a)[v]\) for all \(v\in {\cal V}(pre(a))\). Applying \(a\) changes the value of each \(v \in {\cal V}(eff(a))\) to \(eff(a)[v]\), and the resulting state is denoted by \(s [\![ a ]\!]\). This notation is only defined if \(a\) is applicable in \(s\). Denoting an empty sequence of operators by \(\epsilon\), applying a sequence of operators \(\left<a_{1},…,a_{m}\right>\); to a state \(s\) is defined inductively as \(s[\![ \epsilon]\!] := s\) and \(s[\![ a_{1},…,a_{j} ]\!]= s[\![ a_{1},…,a_{j-1}]\!][\![ a_{j}]\!]\). An operator sequence \(\pi\) is called an \(s\)-plan if it is applicable in state \(s\) and \(c(\pi) \leq b\). In out discussion, a plan that achieves a goal from state \(s\) will be referred as \(s\)-plan.

A deterministic classical planning task, is given by \(\Pi = \langle V,s_{0},g;A,c\rangle\), where the utility function and cost budget are replaced with a hard goal constraint which is a partial assignment on state variables \(G \subseteq V\).

We assume an additive utility function with multi-valued variables, defined as \(u(s) = \sum_{\left< v/d \right>\in s}{u_v(d)},\) with \(u_v(d) \in {\mathbb R}\) for all variable-value pairs \(\left< v/d \right>\). That is, negative utility values are allowed and each variable can get many value assignment with different utility value available for each variable-value pair.

Some auxiliary notation is used later on: for an OSP task \(\Pi =\langle V,s_{0},u;A,c,b\rangle\), by \({\cal D} = \bigcup_{v\in V}{dom(v)}\) we denote the union of the (uniquely labeled) state-variable domains. For a state \(s\) and a proposition \(\left< v/d \right> \in {\cal D}\), \(\left< v/d \right> \in s\) is used as a shortcut notation for \(s[v] = d\).

An example of Mirkis and Domshlak of a simple OSP task in [Figure-ref] is used to illustrate this model representation. In this example, a truck is initially at location \(A\), and it can drive (only) from location \(A\) to location \(B\) and from location \(B\) to location \(C\). Two packages, \(x\) and \(y\), are initially at location \(B\). When a package and the truck are in the same location, the package can be loaded onto the truck,
and when a package is on the truck, it can be unloaded at the truck’s current location.
Each (drive, load, and unload) operator in the task costs one unit, and the cost budget is set to four units. Finally, a value of one (value unit) is earned for each package present at location \(C\).

This OSP task \(\Pi\) is described here using three state variables \(V = \{t,x,y\}\), with \(dom(t) = \{A,B,C\}\) and \(dom(x)= dom(y) = \{A,B,C,T\}\), corresponding to the possible locations of the truck and the two packages, respectively. The operator set \(A = \{a_1,\ldots,a_{10}\}\) is detailed in [Figure-ref]. In the state model induced by this OSP task, we have \(S = dom(t) \times dom(x) \times dom(y)\), the initial state \(s_{0}=\text{ABB}\) (with the three letters in the names of the states capturing the three components of the domain cross-product), operator cost \(c(a_i) = 1\) for all operators \(a_i\), cost budget \(b=4\), and state values

TBD: U(x) example

The relevant parts of the state space are depicted in [Figure-ref] and[Figure-ref]  [Figure-ref] shows the region of the state space that is structurally reachable from the initial state \(ABB\), and the grayed area in [Figure-ref] corresponds to the sub-region that cannot be reached from the initial state under the budget \(b=4\).

Landmarks in Classical Planning

In classical planning, there are two types of landmarks, the “fact landmarks” and “action landmarks”. The “fact landmarks” are propositions that must be true at some point in every solution plan for a given planning task[5]. \(s\)-landmark is an assignment to a variable that is true at some point in every plan for a state \(s\).
Similarly to landmarks over facts, an action \(a\) is an action landmark of a planning task \(\Pi\) iff it is taken along every plan for \(\Pi\). A sufficient and efficiently testable condition for an action \(a\) being an action landmark is that a relaxed planning task without \(a\) is not solvable. Many state-of-the-art admissible heuristics for classical planning use what are called disjunctive action landmarks, each corresponding to a set of operators such that every \(s\)-plan contains at least one operator from that set [6, 7, 8, 9].

Following Mirkis and Domshlak [2] we consider this popular notion of landmarks, and refer to disjunctive action landmarks for a state \(s\) as \(s\)-landmarks. For ease of presentation, most of our discussion will take place in the context of landmarks for the initial state of the task, and these will simply be referred to as landmarks (for \(\Pi\)).

Logical landmarks for goal reachability [5, 6, 7, 10, 8, 9] have been found extremely effective in the context of optimal classical planning.

Landmarks in OSP

While landmarks play an essential role in (both satisficing and optimal) classical planning, the first framework for their exploitation in the context of OSP has been introduced by Mirkis and Domshlak [11, 6, 7].

  • Performing budget reducing compilation by compiling \(({\cal L}, lcost)\) into \(\Pi\), obtaining an OSP task \(\Pi_{\cal L}\), where \(\Pi_{\cal L}\) extends the structure of \(\Pi\) by mirroring the actions of each \(\epsilon\)-landmark \(L_i\) with their “cheaper by \(lcost(L_i)\)” versions. To compensate for the discounted actions, budget \(b\) is reduced by \(\sum_{i=1}^{n}{lcost} L_i)\). Domshlak and Mirkise [2] devised two versions of polynomial and sound budget reducing compilation; A basic compilation \(\Pi_{\cal L}\) applied on a pairwise disjoint landmarks and extended with auxiliary control structure, a generalized budget reducing compilation applied on an arbitrary (non-disjoint) sets of \(\epsilon\)-landmarks. This compilation can then be used within a heuristic search algorithm, as described next.
  • The optimal solution for \(\Pi_{\cal L}\) (and thus for \(\Pi\)) is then searched for using a search algorithm for optimal OSP such as a generic best-first branch-and-bound search or the OSP-customized branch-and-bound search framework \(inc-BFBB\) [12] illustrated in [Figure-ref] which described next.


    [1] B. Nebel, “On the compilability and expressive power of propositional planning formalisms,” Journal of artificial intelligence research, vol. 12, p. 271–315, 2000.
    title={On the compilability and expressive power of propositional planning formalisms},
    author={Nebel, Bernhard},
    journal={Journal of Artificial Intelligence Research},
    [2] C. Domshlak and V. Mirkis, “Deterministic oversubscription planning as heuristic search: abstractions and reformulations,” Journal of artificial intelligence research, vol. 52, p. 97–169, 2015.
    title={Deterministic oversubscription planning as heuristic search: Abstractions and reformulations},
    author={Domshlak, Carmel and Mirkis, Vitaly},
    journal={Journal of Artificial Intelligence Research},
    [3] C. Bäckström and I. Klein, “Planning in polynomial time: the sas-pubs class,” Computational intelligence, vol. 7, iss. 3, p. 181–197, 1991.
    title={Planning in polynomial time: the SAS-PUBS class},
    author={B{\"a}ckstr{\"o}m, Christer and Klein, Inger},
    journal={Computational Intelligence},
    publisher={Wiley Online Library}
    [4] C. Bäckström and B. Nebel, “Complexity results for sas+ planning,” Computational intelligence, vol. 11, iss. 4, p. 625–655, 1995.
    title={Complexity results for SAS+ planning},
    author={B{\"a}ckstr{\"o}m, Christer and Nebel, Bernhard},
    journal={Computational Intelligence},
    publisher={Wiley Online Library}
    [5] J. Hoffmann, J. Porteous, and L. Sebastia, “Ordered landmarks in planning,” Journal of artificial intelligence research, vol. 22, p. 215–278, 2004.
    title={Ordered landmarks in planning},
    author={Hoffmann, J{\"o}rg and Porteous, Julie and Sebastia, Laura},
    journal={Journal of Artificial Intelligence Research},
    [6] E. Karpas and C. Domshlak, “Cost-optimal planning with landmarks.,” in Ijcai, 2009, p. 1728–1733.
    title={Cost-Optimal Planning with Landmarks.},
    author={Karpas, Erez and Domshlak, Carmel},
    [7] M. Helmert and C. Domshlak, “Landmarks, critical paths and abstractions: what’s the difference anyway?,” in Icaps, 2009, p. 162–169.
    title={Landmarks, critical paths and abstractions: what's the difference anyway?},
    author={Helmert, Malte and Domshlak, Carmel},
    [8] B. Bonet and M. Helmert, “Strengthening landmark heuristics via hitting sets.,” in Ecai, 2010, p. 329–334.
    title={Strengthening Landmark Heuristics via Hitting Sets.},
    author={Bonet, Blai and Helmert, Malte},
    [9] F. Pommerening and M. Helmert, “Incremental lm-cut.,” in Icaps, 2013.
    title={Incremental LM-Cut.},
    author={Pommerening, Florian and Helmert, Malte},
    [10] C. Domshlak, M. Katz, and S. Lefler, “Landmark-enhanced abstraction heuristics,” Artificial intelligence, vol. 189, p. 48–68, 2012.
    title={Landmark-enhanced abstraction heuristics},
    author={Domshlak, Carmel and Katz, Michael and Lefler, Sagi},
    journal={Artificial Intelligence},
    [11] M. Katz and C. Domshlak, “Optimal admissible composition of abstraction heuristics,” Artificial intelligence, vol. 174, iss. 12-13, p. 767–798, 2010.
    title={Optimal admissible composition of abstraction heuristics},
    author={Katz, Michael and Domshlak, Carmel},
    journal={Artificial Intelligence},
    [12] V. Mirkis and C. Domshlak, “Landmarks in oversubscription planning,” in Proceedings of the twenty-first european conference on artificial intelligence, 2014, p. 633–638.
    title={Landmarks in oversubscription planning},
    author={Mirkis, Vitaly and Domshlak, Carmel},
    booktitle={Proceedings of the Twenty-first European Conference on Artificial Intelligence},
    organization={IOS Press}