Additional IPC5 Resources

Problem Generation/Conversion Software

convertstacks3

Perl script for converting openstacks problems in CMC format to many different PDDL formulations. (The same script also generates problems for the Openstacks SP/QP/Time/MetricTime domains, but needs additional parameters for that.) Basic usage:

• convertstacks3 [--skip <k> -n <n>] <file>

  Extract problems <k>+1 .. <k>+<n> (default 1 .. #problems in <file>) from input <file> and output instances for the plain domain version (described below).

• convertstacks3 --sequenced [--skip <k> -n <n>] <file>

  Extract problems <k>+1 .. <k>+<n> from input <file> and output instances for the sequenced domain version (i.e., the "Propositional" version used in the competition).

generate-ipc-instances

Script to (re-)generate the IPC5 problem instances for the different Openstacks domains. (Also useful as a source of documentation of options for convertstacks3.) Note that this requires the CMC 2005 problem collection. Run with -? for usage info.

rover_strips_cost.pddl and rovergen3.cc

Domain and problem generator for the "Rovers STRIPS with travel costs" domain used as a basis for generating Rovers MSP problems. The problem generator is a minor modification of the IPC3 generator (available from http://planning.cis.strath.ac.uk/competition/). To generate problems with (travel) action costs, use option -o.

Alternative Domain Versions and Formulations

openstacks-plain.tar.gz

openstacks-plain-ground.tar.gz

Plain version of the Openstacks domain.

Like the competition "Propositional", but this version allows for concurrent actions. Note that the objective is to minimise the number of actions in the plan. Planners that minimise "parallel length" should use the competition "Propositional" version. The second archive contains fully grounded instances.

openstacks-sp-nce.pddl

Openstacks SP domain, formulation without conditional effects.

18/10/07: Domain updated. Previous version had a bug, which permitted the construction of solutions not possible in the Openstacks SP domain (with conditional effects). Thanks to Jorge Baier for noticing this!

This domain reformulation can be used with the Openstacks SP problem files. It is equivalent in the sense that it admits a greater-or-equal range of solution quality values (i.e., for every solution to an Openstacks SP problem, there exists a solution to the corresponding Openstacks SP-NCE problem of equal quality; conversely, for every solution to an Openstacks SP-NCE problem, there exists a solution to the corresponding Openstacks SP problem of equal or better quality). However, the two formulations use different sets of actions, so plans must be validated using the same domain specification that was used to generate them.

Solution Quality: Bounds & Best Known Solutions

Openstacks (Plain/Propositional)

(a)

Corresponding Constraint Modelling Challenge problem.

(b)

#products / #orders (in parenthesis: reduced #orders). Note that the (reduced) #orders is a simple upper bound on the number of stacks required.

(c)

Quality (max number of open stacks) in best known solution. One star indicates that the number is optimal, two stars that the problem (in plain formulation) has been solved by an optimal planner.

(d)

The constant offset between plan length and number of open stacks, for the plain formulation.

(e)

The constant offset between plan length and number of open stacks, for the sequenced (Propositional) formulation.

Openstacks SP

(a)

Corresponding 2005 Constraint Modelling Challenge problem.

(b)

Penalty model: Uniform or Exponential.

(c)

Maximum total penalty for unsatisfied product requests.

(d)

The fixed number of stacks (in parentheses: minimum number of stacks required to accommodate all product requests).

(e)

Highest known lower bound (max of two/three different lower bounds, as described in the workshop paper).

(f)

Best known solution. A star indicates the solution is optimal (matched by one of the lower bounds). In problems p15 - p18 the stack limit is large enough to accommodate all product requests, making a penalty of zero possible. For all other problems, the best known solution has been found by the MPFS solver.

Best known (non-competitor) solutions can be found here (gzipped tar file)

Openstacks QP

(a)

Corresponding 2005 Constraint Modelling Challenge problem (same as in the Openstacks SP domain).

(b)

Penalty model: Uniform or Exponential (same as in the Openstacks SP domain).

(c)

Maximum total penalty for unsatisfied product requests (same as in the Openstacks SP domain).

(d)

Penalty per stack used (in parentheses: minimum number of stacks required to accommodate all product requests).

(e)

Highest known lower bound. The lower bound is calculated as min N = 1 .. #orders, lower bound on the corresponding SP instance with N stacks plus the cost of N stacks.

(f)

Upper bound: Cost of a solution found by a simple (polynomial-time) greedy procedure.

(g)

Upper bound: Cost of the solution that delivers all requested products using a minimal number of stacks.

(h)

Cost (i.e., total penalty for unsatisfied product requests plus cost of stacks used) of best known solution (in parenthesis: number of stacks used by this solution). For instances p13, p14, p19 and p20, the best solution is one submitted by a planner in the competition. For remaining instances, it was found by trying the MPFS solver with different fixed numbers of stacks.

Openstacks Time

(a)

Corresponding 2005 Constraint Modelling Challenge problem (note: instances of the Openstacks Time and MetricTime domains are based on the same CMC problems as those of the Openstacks SP and QP domains, but the order of the two "Shaw" problems is reversed).

(b)

The fixed number of stacks (in parentheses: minimum number of stacks required).

(c)

Lower bound on makespan. This bound was obtained by solving a problem relaxation that amounts to a graph coloring problem with a fixed number of colors and a particular cost function.

(e)

Makespan of best known solution. For problems p19 and p20, this is a solution submitted by one of the competing planners. For remaining problems, the solution was found by running the LPG planner for a very long time (this was done as part of the problem instance construction for the Openstacks MetricTime domain).

Best known (non-competitor) solutions can be found here (gzipped tar file)

Openstacks MetricTime

(a)

Corresponding 2005 Constraint Modelling Challenge problem (same as in the Openstacks Time domain).

(b)

Penalty per stack (in parentheses: minimum number of stacks required).

(c)

Lower bound on total penalty. This bound is computed as min N = M..#orders, where M is the minimum number of stacks required to solve the problem, lower bound on makespan with N stacks plus the cost of N stacks. The lower bound on makespan used in this calculation is based on the h² makespan heuristic, and weaker than that used to compute lower bounds for the Openstacks Time domain. The more accurate lower bound used for that domain is too expensive to compute for smaller numbers of stacks. (The underlying problem, graph coloring, is tractable when the number of colors, i.e., stacks, is "close" to the number of nodes in the graph, i.e., orders, but NP-hard in general.)

(e)

Cost (cost of stacks used plus makespan) of best known solution. These solutions were all found by running the LPG planner, for a long time, on problem instances with different fixed numbers of stacks (this was done as part of instance construction).

Rovers MSP

Note: Values refer to the metric as specified in the competition domain: the objective is to minimise this value.

	(a)	(b)	(c)	(d)
Type I
p01	851.1	811.3*		4/5
p02	610.8	473.2*		5/6
p03	862.2	811.3*		5/6
p04	461.9	418.7*		5/5
p05	870.0	483.6*		6/6
p06	655.7	649.2*		5/8
p07	402.2	402.2*		2/5
Type II
p08	978.7	698.4*		6/9
p09	432.9	326.2*		9/9
p10	873.5	617.1*		6/9
p11	698.1	468.6*		7/8
p12	425.6	371.9	363.3	9/1
p13	1550.6	755.8	718.6	11/1
Type III
p14	578.4	442.2*		6/7
p15	3948.4	1004.5	940.6	21/2
p16	4672.3	944.7*		22/2
p17	1768.7	721.9*		18/1
p18	742.9	628.8*		8/1
p19	699.0	345.2*		6/6
p20	3183.1	1116.2	924.7	20/2

(a)

Upper bound from problem construction.

(b)

Best known solution. A star indicates the solution is optimal.

(c)

Lower bound.

(d)

Fraction of soft goals achieved in the best known solution.

Best known (non-competitor) solutions and cost lower bound tables can be found here (gzipped tar file).

Rovers QP

(a)

Upper bound: Total (max) penalty.

(b)

Upper bound from problem construction (i.e., lowest value achieved by an IPC3 plan).

(c)

Lower bound.

(d)

Best known solution. A star indicates the solution is optimal. A "(c)" indicates the best solution was submitted by one of the competing planners.

Best known (non-competitor) solutions and lower bound information (tables of jointly unsatisfiable plan constraints) can be found here (gzipped tar file).