Additional IPC5 Resources Problem Generation/Conversion Software Alternative Domain Versions and Formulations Solution Quality: Bounds & Best Known Solutions Solvers

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

24/11/08: Script updated. Previous version had a bug, causing it to generate incorrect problems (i.e., not identical to those used in IPC5) in a few cases. The affected instances were: p04, p10 and p11 of the Time and MetricTime domains only.

Note that this requires the CMC 2005 problem collection and the file that specifies the extra tiny instances I created. 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.

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.

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 several different lower bounds; some are described in the workshop paper, some are more recent).

(f)

Best known solution. A star indicates the solution is optimal (not necessarily by matching the lower bound in column (e); in some cases it was proven by the constraint-based solver that generated the plan). In problems p15 - p18 the stack limit is large enough to accommodate all product requests, making a penalty of zero possible. For the other problems, the best known solution was found by either the MPFS solver, or a more recently developed constraint-based 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 (optimally) a problem relaxation that (partly) ignores the constraint that all start and ship actions must be separated (which is a consequence of the PDDL formulation). The relaxation was solved by a CSP formulation that amounts to a graph coloring problem with a fixed number of colors and some additional constraints.

(d)

Makespan of best known solution. These solutions were found by a constraint-based LDS search around the optimal solution to the relaxation used to compute the lower bound. The decimals are due to that plans are post-epsilonised to please the PDDL validator; they should be disregarded when comparing the solution to the lower bound.

Best known 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 in this calculation is (a lower bound on) the optimal solution cost to the same CSP formulation as in the relaxation used to lowerbound the Openstacks Time domain (because of differences in the PDDL encoding, this formulation is not a relaxation but an encoding of the actual problem for the MetricTime domain). The instances where the lower bound does not match the best solution (column (d)) are those where the CSP formulation could not be solved optimally for some value of N.

(d)

Cost (cost of stacks used plus makespan) of best known solution. These solutions were found by the procedure described for the calculation of the lower bound. For the cases where the CSP formulation could be solved optimally for every value of N, this solution is optimal (modulo plan post-epsilonisation).

(e)

Number of stacks used by the best known solution. In a few cases, equivalently valued solutions with different numbers of stacks exist.

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/10
p13	1550.6	755.8	718.6	11/12
Type III
p14	578.4	442.2*		6/7
p15	3948.4	1004.5	940.6	21/22
p16	4672.3	944.7*		22/22
p17	1768.7	721.9*		18/18
p18	742.9	628.8*		8/10
p19	699.0	345.2*		6/6
p20	3183.1	1116.2	924.7	20/20

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

Note: The seeming discrepancy between the lower bound and best solution for instance p02 is caused by the fact that the value of the solution plan is calculated by VAL, which uses a floating point representation, and the lower bound by software that uses a rational number representation, i.e., it's a round-off error.

3/11/10: Results updated with some improved lower bounds, and 5 new best solutions (p07, p08, p15, p17 and p18) contributed by Amanda and Andrew Coles.

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

Solvers (Domain-Specific and Generic)

os-solver.tar.gz

Contains the (C++) source code for:

• solver: My implementation of Garcia de la Banda's & Stuckey's algorithm for the basic openstacks problem (with some options and extensions). For a description of the algorithm, see their paper in the draft proceedings of the 2005 Constraint Modelling Challenge.
  The instance to be solved is read from stdin, in a simple format: the first line should contain two positive integers, #o (number of orders) and #p (number of products), and the following #o lines (one per order) should each contain #p (one per product) non-negative integers; a non-zero jth entry on the ith line means product j is requested by order i. (The format used in the 2005 Constraint Modelling Challenge is basically the same, but allows more than one instance specified in the same file, and a comment line at the start of each instance. converstacks3 --cut can be used to "excise" a single instance from a CMC file and strip away the comment line.)
  Options to the program include -prep (apply preprocessing, removing dominated products) and -try (use the "try decreasing bounds" strategy), plus a host of others that have little to do with basic functionality.
• mlfs: Implementation of the MPFS (Min-Penalty-for-Fixed-Sequence) branch-and-bound procedure. This program interprets the numbers in the input matrix that defines which orders request which products as the penalty associated with dropping that request. Has many options.
• test_bounds: Computes and prints various lower and upper bounds on solution quality. Many options. Input same as above.
• ost_sched and cdg_color: Constraint-based schedulers for openstacks Time problems. cdg_color is a "relaxed" scheduler (based on a kind of graph coloring problem) which produces lower bounds on makespan, while ost_sched solves the real problem. Both require the input to contain, in addition to the number of orders and products and the inclusion matrix as described above, an additional line with one positive integer per product, which is interpreted as the duration of the product-making task.

These programs depend on the HSP* code, so to compile them you need to have that. The schedulers also use the Gecode constraint programming library.