*THIS PAGE IS IN PROGRESS

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

- \(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; - \(s_0 \in S\) is a designated
*initial state*; - \(u\) is an efficiently computable
*state value*function \(u : U \rightarrow{\mathbb R}^{0+}\); - \(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; - \(c : A \rightarrow {\mathbb R}\) is an
*operator cost*function; - \(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].

*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.

FIGURE

FIGURE

[Bibtex]

```
@article{Nebel:jair00,
title={On the compilability and expressive power of propositional planning formalisms},
author={Nebel, Bernhard},
journal={Journal of Artificial Intelligence Research},
volume={12},
pages={271--315},
year={2000}
}
```

[Bibtex]

```
@article{mirkis:domshlak:jair15,
title={Deterministic oversubscription planning as heuristic search: Abstractions and reformulations},
author={Domshlak, Carmel and Mirkis, Vitaly},
journal={Journal of Artificial Intelligence Research},
volume={52},
pages={97--169},
year={2015}
}
```

[Bibtex]

```
@article{Backstrom:Klein:ci91,
title={Planning in polynomial time: the SAS-PUBS class},
author={B{\"a}ckstr{\"o}m, Christer and Klein, Inger},
journal={Computational Intelligence},
volume={7},
number={3},
pages={181--197},
year={1991},
publisher={Wiley Online Library}
}
```

[Bibtex]

```
@article{Backstrom:Nebel:ci95,
title={Complexity results for SAS+ planning},
author={B{\"a}ckstr{\"o}m, Christer and Nebel, Bernhard},
journal={Computational Intelligence},
volume={11},
number={4},
pages={625--655},
year={1995},
publisher={Wiley Online Library}
}
```

[Bibtex]

```
@article{HoffmannPS04,
title={Ordered landmarks in planning},
author={Hoffmann, J{\"o}rg and Porteous, Julie and Sebastia, Laura},
journal={Journal of Artificial Intelligence Research},
volume={22},
pages={215--278},
year={2004}
}
```

[Bibtex]

```
@inproceedings{karpas.ijcai09,
title={Cost-Optimal Planning with Landmarks.},
author={Karpas, Erez and Domshlak, Carmel},
booktitle={IJCAI},
pages={1728--1733},
year={2009}
}
```

[Bibtex]

```
@inproceedings{helmert:domshlak:icaps09,
title={Landmarks, critical paths and abstractions: what's the difference anyway?},
author={Helmert, Malte and Domshlak, Carmel},
booktitle={ICAPS},
pages={162--169},
year={2009}
}
```

[Bibtex]

```
@inproceedings{bonetH:ecai10,
title={Strengthening Landmark Heuristics via Hitting Sets.},
author={Bonet, Blai and Helmert, Malte},
booktitle={ECAI},
pages={329--334},
year={2010}
}
```

```
@inproceedings{pommerening:13,
title={Incremental LM-Cut.},
author={Pommerening, Florian and Helmert, Malte},
booktitle={ICAPS},
year={2013}
}
```

[Bibtex]

```
@article{domshlak:katz:lefler:aij12,
title={Landmark-enhanced abstraction heuristics},
author={Domshlak, Carmel and Katz, Michael and Lefler, Sagi},
journal={Artificial Intelligence},
volume={189},
pages={48--68},
year={2012},
publisher={Elsevier}
}
```

[Bibtex]

```
@article{Katz:Domshlak:aij00,
title={Optimal admissible composition of abstraction heuristics},
author={Katz, Michael and Domshlak, Carmel},
journal={Artificial Intelligence},
volume={174},
number={12-13},
pages={767--798},
year={2010},
publisher={Elsevier}
}
```

[Bibtex]

```
@inproceedings{mirkis:domshlak:ecai2014,
title={Landmarks in oversubscription planning},
author={Mirkis, Vitaly and Domshlak, Carmel},
booktitle={Proceedings of the Twenty-first European Conference on Artificial Intelligence},
pages={633--638},
year={2014},
organization={IOS Press}
}
```