## Additional IPC5 Resources |

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

(a) | (b) | (c) | (d) | (e) | |

p01 | | 5/5 | 3** | 15 | 20 |

p02 | | 5/5 | 3** | 15 | 20 |

p03 | | 5/5 | 3** | 15 | 20 |

p04 | | 5/5 | 3** | 15 | 20 |

p05 | | 5/5 | 3** | 15 | 20 |

p06 | wbop_10_10 #11 | 10/10 | 5** | 30 | 40 |

p07 | wbop_10_10 #18 | 10/10 | 6** | 30 | 40 |

p08 | nwrssmaller #3 | 15/25 | 7* | 55 | 80 |

p09 | nwrssmaller #4 | 15/25 | 7* | 55 | 80 |

p10 | wbop_20_20 #12 | 20/20 | 9** | 60 | 80 |

p11 | wbop_20_20 #14 | 20/20 | 9** | 60 | 80 |

p12 | wbop_20_20 #21 | 20/20 | 12** | 60 | 80 |

p13 | wbop_20_20 #35 | 20/20 | 16* | 60 | 80 |

p14 | wbop_20_20 #37 | 20/20 | 15* | 60 | 80 |

p15 | Shaw #4 | 20/20 | 13* | 60 | 80 |

p16 | Shaw #24 | 20/20 | 14* | 60 | 80 |

p17 | nrwslarger #1 | 20/30 | 12* | 70 | 100 |

p18 | nrwslarger #3 | 25/60(59) | 10* | 109 | 168 |

p19 | sp4 #1 | 25/25 | 9* | 75 | 100 |

p20 | wbop_30_30 #17 | 30/30 | 10* | 90 | 120 |

p21 | wbop_30_30 #20 | 30/30 | 9* | 90 | 120 |

p22 | wbop_30_30 #26 | 30/30 | 15* | 90 | 120 |

p23 | wbop_30_30 #37 | 30/30 | 20* | 90 | 120 |

p24 | gp50by50 #2 | 50/50 | 40* | 150 | 200 |

p25 | gp50by50 #4 | 50/50 | 30* | 150 | 200 |

p26 | sp4 #2 | 50/50 | 19* | 150 | 200 |

p27 | sp4 #3 | 75/75 | 34 | 225 | 300 |

p28 | gp100by100 #2 | 100/100 | 75* | 300 | 400 |

p29 | gp100by100 #4 | 100/100 | 60* | 300 | 400 |

p30 | sp4 #4 | 100/100 | 54 | 300 | 400 |

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

(a) | (b) | (c) | (d) | (e) | (f) | |

p01 | wbop_10_10 #11 | E | 70 | 4 (5) | 6 | 6* |

p02 | wbop_10_10 #18 | E | 70 | 5 (6) | 4 | 4* |

p03 | nwrsSmaller #3 | U | 90 | 6 (7) | 2 | 2* |

p04 | nwrsSmaller #4 | U | 100 | 6 (7) | 3 | 4* |

p05 | wbop_20_20 #12 | E | 140 | 8 (9) | 4 | 4* |

p06 | wbop_20_20 #14 | E | 140 | 8 (9) | 4 | 4* |

p07 | wbop_20_20 #21 | E | 300 | 11 (12) | 8 | 8* |

p08 | wbop_20_20 #35 | E | 620 | 15 (16) | 16 | 24* |

p09 | wbop_20_20 #37 | E | 620 | 14 (15) | 16 | 16* |

p10 | Shaw #24 | U | 120 | 13 (14) | 1 | 1* |

p11 | Shaw #4 | U | 120 | 12 (13) | 1 | 1* |

p12 | nwrsLarger #1 | U | 153 | 11 (12) | 1 | 1* |

p13 | nwrsLarger #3 | U | 223 | 9 (10) | 2 | 3* |

p14 | sp4 #1 | U | 65 | 7 (9) | 1 | 2* |

p15 | wbop_30_30 #17 | E | 210 | 11 (10) | 0* | |

p16 | wbop_30_30 #20 | E | 210 | 11 (9) | 0* | |

p17 | wbop_30_30 #26 | E | 450 | 17 (15) | 0* | |

p18 | wbop_30_30 #37 | E | 930 | 21 (20) | 0* | |

p19 | gp50by50 #2 | U | 1581 | 37 (40) | 24 | 95 |

p20 | gp50by50 #4 | U | 1348 | 27 (30) | 22 | 125 |

- (a)
- Corresponding 2005 Constraint Modelling Challenge problem.
- (b)
- Penalty model:
**U**niform or**E**xponential. - (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)

(a) | (b) | (c) | (d) | (e) | (f) | (g) | (h) | |

p01 | wbop_10_10 #11 | E | 70 | 14.0 (5) | 38.0 | 70.0 | 70.0 | 59.0 (2,3) |

p02 | wbop_10_10 #18 | E | 70 | 11.6 (6) | 35.6 | 60.6 | 69.6 | 52.8 (3) |

p03 | nwrsSmaller #3 | U | 90 | 12.8 (7) | 24.8 | 84.8 | 89.6 | 70.0 (5) |

p04 | nwrsSmaller #4 | U | 100 | 14.2 (7) | 29.2 | 96.2 | 99.4 | 79.8 (4) |

p05 | wbop_20_20 #12 | E | 140 | 15.5 (9) | 39.5 | 120.5 | 139.5 | 98.5 (5) |

p06 | wbop_20_20 #14 | E | 140 | 15.5 (9) | 39.5 | 120.5 | 139.5 | 94.0 (4) |

p07 | wbop_20_20 #21 | E | 300 | 25.0 (12) | 110.0 | 265.0 | 300.0 | 248.0 (8) |

p08 | wbop_20_20 #35 | E | 620 | 38.7 (16) | 364.7 | 565.7 | 619.2 | 593.1 (13) |

p09 | wbop_20_20 #37 | E | 620 | 41.3 (15) | 347.3 | 568.3 | 619.5 | 554.3 (11) |

p10 | Shaw #24 | U | 120 | 8.5 (14) | 24.5 | 114.2 | 119.0 | 90.5 (9) |

p11 | Shaw #4 | U | 120 | 9.2 (13) | 27.2 | 115.5 | 119.6 | 88.4 (7) |

p12 | nwrsLarger #1 | U | 153 | 12.75 (12) | 32.75 | 151.75 | 153.0 | 122.0 (8) |

p13 | nwrsLarger #3 | U | 223 | 22.3 (10) | 43.3 | 216.3 | 223.0 | 185.6 (2) |

p14 | sp4 #1 | U | 65 | 7.2 (9) | 27.6 | 55.2 | 64.8 | 42.8 (4) |

p15 | wbop_30_30 #17 | E | 210 | 17.5 (10) | 40.5 | 164.5 | 175.0 | 138.0 (6) |

p16 | wbop_30_30 #20 | E | 210 | 17.5 (9) | 40.5 | 171.5 | 157.5 | 120.5 (5) |

p17 | wbop_30_30 #26 | E | 450 | 25.0 (15) | 131.0 | 400.0 | 375.0 | 331.0 (11) |

p18 | wbop_30_30 #37 | E | 930 | 42.2 (20) | 390.2 | 848.2 | 844.0 | 650.8 (14) |

p19 | gp50by50 #2 | U | 1581 | 39.5 (40) | 84.5 | 1580.5 | 1580.0 | 1524.0 (6) |

p20 | gp50by50 #4 | U | 1348 | 44.9 (30) | 86.9 | 1347.9 | 1347.0 | 1336.3 (7) |

- (a)
- Corresponding 2005 Constraint Modelling Challenge problem (same as in the Openstacks SP domain).
- (b)
- Penalty model:
**U**niform or**E**xponential (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.

(a) | (b) | (c) | (d) | |

p01 | wbop_10_10 #11 | 8 (5) | 188 | 188.01 * |

p02 | wbop_10_10 #18 | 9 (6) | 138 | 138.009* |

p03 | nwrsSmaller #3 | 13 (7) | 267 | 271.017 |

p04 | nwrsSmaller #4 | 13 (7) | 296 | 296.013* |

p05 | wbop_20_20 #12 | 18 (9) | 288 | 288.009* |

p06 | wbop_20_20 #14 | 18 (9) | 248 | 250.011 |

p07 | wbop_20_20 #21 | 18 (12) | 330 | 330.011* |

p08 | wbop_20_20 #35 | 19 (16) | 312 | 312.013* |

p09 | wbop_20_20 #37 | 18 (15) | 314 | 316.018 |

p10 | Shaw #4 | 18 (13) | 354 | 354.015* |

p11 | Shaw #24 | 18 (14) | 334 | 335.016 |

p12 | nwrsLarger #1 | 18 (12) | 392 | 394.015 |

p13 | nwrsLarger #3 | 18 (10) | 514 | 519.021 |

p14 | sp4 #1 | 23 (9) | 309 | 309.01 * |

p15 | wbop_30_30 #17 | 28 (10) | 368 | 368.009* |

p16 | wbop_30_30 #20 | 28 (9) | 368 | 370.011 |

p17 | wbop_30_30 #26 | 28 (15) | 490 | 492.014 |

p18 | wbop_30_30 #37 | 28 (20) | 492 | 495.016 |

p19 | gp50by50 #2 | 48 (40) | 818 | 825.076 |

p20 | gp50by50 #4 | 48 (30) | 753 | 754.055 |

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

(a) | (b) | (c) | (d) | (e) | |

p01 | wbop_10_10 #11 | 41.0 (5) | 471.0 | 471.012* | 7 |

p02 | wbop_10_10 #18 | 32.0 (6) | 422.0 | 422.011* | 8-10 |

p03 | nwrsSmaller #3 | 55.5 (7) | 855.0 | 855.018* | 8 |

p04 | nwrsSmaller #4 | 66.5 (7) | 959.0 | 959.016* | 10 |

p05 | wbop_20_20 #12 | 52.0 (9) | 914.0 | 1032.020 | 12 |

p06 | wbop_20_20 #14 | 27.0 (9) | 649.0 | 710.021 | 12 |

p07 | wbop_20_20 #21 | 59.0 (12) | 1232.0 | 1232.020* | 14 |

p08 | wbop_20_20 #35 | 100.0 (16) | 2066.0 | 2066.030* | 17 |

p09 | wbop_20_20 #37 | 54.5 (15) | 1287.0 | 1287.030* | 18 |

p10 | Shaw #4 | 71.5 (13) | 1478.5 | 1478.520* | 15 |

p11 | Shaw #24 | 73.0 (14) | 1552.0 | 1552.020* | 16 |

p12 | nwrsLarger #1 | 88.0 (12) | 1724.0 | 1724.020* | 15 |

p13 | nwrsLarger #3 | 35.3 (10) | 1033.5 | 1033.530* | 15 |

p14 | sp4 #1 | 40.5 (9) | 1036.5 | 1036.520* | 15 |

p15 | wbop_30_30 #17 | 23.5 (10) | 839.0 | 983.530 | 29 |

p16 | wbop_30_30 #20 | 34.5 (9) | 914.5 | 1162.530 | 17 |

p17 | wbop_30_30 #26 | 78.0 (15) | 1744.0 | 2226.030 | 20 |

p18 | wbop_30_30 #37 | 100.0 (20) | 2564.0 | 2961.030 | 23 |

p19 | gp50by50 #2 | 120.5 (40) | 6306.0 | 6306.050* | 44 |

p20 | gp50by50 #4 | 144.5 (30) | 5772.5 | 6697.050 | 38 |

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

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

(a) | (b) | (c) | (d) | |

p01 | 177.207 | 79.3947 | 68.039 | 68.0393* |

p02 | 83.2222 | 38.1111 | 32.66664 | 32.6666* |

p03 | 193.375 | 57.11 | 28.495 | 29.19* |

p04 | 115.086 | 38 | 18.45714 | 23.8857* |

p05 | 652.119 | 266 | 98.9422 | 98.9422* |

p06 | 201.949 | 68.901 | 37.39194 | 37.39194* |

p07 | 284.625 | 116.196 | 20.90763 | 39.5558 |

p08 | 1600.00 | 856 | 484 | 556 |

p09 | 2724.78 | 1558.74 | 427.834 | 535.834 |

p10 | 2801.13 | 1484.63 | 219.4673 | 255.738 |

p11 | 2921.92 | 1559.42 | 624.778 | 750.494 |

p12 | 2112.61 | 1282.68 | 238.4037 | 250.716 (c) |

p13 | 9739.31 | 5309.38 | 1291.35 | 1528.16 |

p14 | 1868.69 | 929.05 | 257.647 | 274.208 |

p15 | 6314.47 | 3108.81 | 1079.9151 | 1689.93 |

p16 | 5918 | 3234 | 1269 | 1555 |

p17 | 8968.99 | 5101.07 | 1297.5664 | 2125.58 |

p18 | 14171 | 8390 | 2200 | 3372 |

p19 | 7340.40 | 3896.32 | 1471.03 | 2150.26 (c) |

p20 | 47722.891 | 30590 | 6106 | 7912.32 |

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

- 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*j*th entry on the*i*th 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.