# Nomystery

## Problem Description

Nomystery is a transportation planning domain taken from the 2011's International Planning Competition, quite similar to other domains such as the Transport domain included both in the International Planning Competitions celebrated in 2008 and 2011. In the context of the ASP Competition Series, this problem is similar to Airport Pickup and Fastfood Optimization which appeared at the 2011 ASP Competition.

This domain was proposed in the planning community by Hootan Nakhost [1,2] to assess the performance of planners in problems with constrained resources:

`An ubiquitous feature of planning problems is the need to economize limited resources such as fuel or money. While heuristic search, mostly based on relaxation heuristics, is currently the superior method for most varieties of planning, its ability to solve critically resource-constrained problems is limited: relaxation heuristics basically ignore the resource consumption by actions. Nomystery is a nice test domain to study the behavior of planning algorithms in planning problems with resources.`

*In Nomystery, a truck moves in a weighted graph where a set of packages must be transported between nodes. Actions move the truck along edges and load/unload packages. Each move consumes the edge weight in fuel. The edge weights are uniformly drawn between 1 and an integer W. The initial fuel supply is set to C * M where M is the minimum required amount of fuel, calculated using a domain-specific optimal solver, and C >= 1 is a (float) input parameter that denotes the ratio between the available fuel vs. the minimum amount required. The closer C to 1, the more constrained the problem. If C=1only the optimal plan solves the problem. *

*The authors originally provided two versions of the domain, called Hard and Hard-cost. They differ only in the cost of the actions. In the first one, all the actions have unitary cost, while in the second version the cost of moving a track equals the fuel consumed. According to the author: *

`In the Hard encoding, problems with 12 locations and 12 packages become quite challenging for state-of-the-art planners when``C`is close to 1 [2]. Hard-cost encoding makes the problems easier for the current planners. The reason is that the heuristic functions that consider costs are not any more completely ignorant to the resource consumption of actions. However, this type of encoding is not always feasible for resource planning; there might be several resources and the cost of the plan might be different from the amount of the resource consumption. However, our initial experiments show problems in this encoding with 12 locations and 15 packages become challenging for current planners when`C`is close to`1`.

From the two versions of the domain only the Hard one (where cost of the plan and resource consumption are not related) has been considered at IPC 2011 (Deterministic Track). As the domain creator said, this was the most difficult one of the two formulations for planning systems. We retained the Hard version of the problem for the ASP Competition 2013. Instances have only one truck.

## Predicates

**Input**:`at/2, fuel/2, fuelcost/3, goal/2, step/1`**Output**:`load/4, unload/4, drive/4`

## Input format

In the setting of the ASP competition, input predicates encode the weighted graph at hand, the initial positions of packages and of the truck, the initial fuel available and the final requested destination for packages. In detail input assertions are to be interpreted as follows:

`fuelcost(c,a,b)`: the locations `a` and `b` are connected and the cost for travelling from `a` to `b` is `c` (for `c` a positive integer) `at(o,l)`: the object `o` (either a package or a truck) is initially at location `l` `fuel(t,l)`: the initial fuel available for truck `t` is `l` (for `l` a positive integer) `goal(p,l)`: at the final step, the package `p` must stay at location `l` `step(s)`: `s` is an allowed step, for `s` a positive integer value

the predicate `step` is intended in order to encode the maximum number of allowed steps. It can be assumed that for 1..n the allowed steps, then `step(1) .. step(n)` assertions hold.

## Output format

An answer for an instance of the problem encodes a sequence of actions of at most `N` steps (for `N` the maximum value of `x` for the assertions in the form `step(x)` given as input) which move all packages from starting locations to their goal locations, using the allowed trucks. A truck can carry many packages at once, and consumes fuel when travelling across locations, according to fuel costs of each edge. The three types of actions are `load`, `unload` and `drive`. Note that the generated witness can be shorter than `N` actions, and that steps in which no action is carried out are allowed.

`load(p,t,l,s)`: at step `s`, the truck `t` loads package `p`, at location `l`. This action can be carried out only if at step `s-1` (or at the initial input state) `p` and `t` were previously located at `l`.

`unload(p,t,l,s)`: at step `s`, the truck `t` unloads package `p`, at location `l`. This action can be carried out only if, at step `s-1` (or at the initial input state), `t` was located at `l`, and `p` was loaded into the truck.

`drive(t,l1,l2,s)`: at step `s`, the truck `t` drives from `l1` to `l2`, reducing thus its fuel level. This action can be carried out only if at step `s-1` (or at the initial input state), `t` was located at `l1`, `l1` and `l2` are connected by an arc of cost `c`, the previous fuel of `t` was `f1`, and `f1-c = f >= 0`.

## Example(s)

A possible input is:

fuelcost(10,a,b). fuelcost(10,b,a). at(t0,a). fuel(t0,56). at(p0,a). goal(p0,b). step(1). step(2). step(3). step(4). step(5). step(6). step(7). step(8). step(9). step(10).

Thus, the output of the solver should look like:

unload(p0,t0,b,10). drive(t0,a,b,4). load(p0,t0,a,3). drive(t0,b,a,2). drive(t0,a,b,1).

Additional sample instances: download

## Problem Peculiarities

**Type**: Search **Competition**: Both

## Notes and Updates

Feb 9-th, 2013. Specified that a truck can carry more than one package at once.

## Author(s)

- Authors: Giovambattista Ianni, Carlos Linares Lopez
- Affiliation: University of Calabria, Italy and Universidad Carlos III de Madrid, Spain

- Original Authors: Hootan Nakhost, Jörg Hoffmann
- Affiliation: University of Alberta, Canada and Saarland University, Germany

## References

[1] Hoffmann, J. (2007). SAT encodings of state-space reachability problems in numeric domains. In In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07)

[2] Nakhost, H., Hoffmann, J., & Müller, M. (2010). Improving local search for resource-constrained planning. In International Symposium on Combinatorial Search.