welcome: please sign in
location: Nomystery

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:

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:

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

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

Author(s)

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.

ASP Competition 2013: Nomystery (last edited 2013-03-16 09:10:32 by GiovambattistaIanni)